无堆栈VM实现会出现哪些C集成问题？

无堆栈VM我指的是在堆上维护自己的堆栈而不是使用系统"C-stack"的实现.这有很多优点,如continuation和serializable状态,但在C-bindings方面也有一些缺点,特别是对于C-VM-C类型的回调(或VM-C-VM).

问题是这些缺点到底是什么？有人能举一个真实问题的好例子吗？

听起来你已经熟悉了一些缺点和优点.

其他一些:a)使得有可能支持正确的尾调用优化,即使底层实现没有任何支持b)更容易构建像语言级别"堆栈跟踪"的东西c)更容易添加适当的延续,就像你一样指出

我最近在C#中编写了一个简单的"Scheme"解释器,它最初使用的是.NET堆栈.然后我重新编写它以使用显式堆栈 - 所以可能以下内容将帮助您:

第一个版本使用隐式.NET运行时堆栈...

最初,它只是一个类层次结构,不同的表单(Lambda,Let等)是以下接口的实现:

// A "form" is an expression that can be evaluted with
// respect to an environment
// e.g.
// "(* x 3)"
// "x"
// "3"
public interface IForm
{
    object Evaluate(IEnvironment environment);
}

IEnvironment看起来像你期望的那样:

/// 

/// Fundamental interface for resolving "symbols" subject to scoping.
/// 
public interface IEnvironment
{
    object Lookup(string name);
    IEnvironment Extend(string name, object value);
}

为了向我的Scheme解释器添加"builtins",我最初有以下接口:

/// 

/// A function is either a builtin function (i.e. implemented directly in CSharp)
/// or something that's been created by the Lambda form.
/// 
public interface IFunction
{
    object Invoke(object[] args);
}

那时它使用了隐式.NET运行时堆栈.肯定有更少的代码,但是不可能添加正确的尾递归之类的东西,最重要的是,我的解释器在运行时错误的情况下能够提供"语言级"堆栈跟踪是很尴尬的.

所以我重新编写了一个显式(堆分配)堆栈.

我的"IFunction"接口必须更改为以下内容,以便我可以实现"map"和"apply"之类的东西,它们会回调到Scheme解释器:

/// 

/// A function that wishes to use the thread state to
/// evaluate its arguments. The function should either:
/// a) Push tasks on to threadState.Pending which, when evaluated, will
///   result in the result being placed on to threadState.Results
/// b) Push its result directly on to threadState.Results
/// 
public interface IStackFunction
{
    void Evaluate(IThreadState threadState, object[] args);
}

并且IForm改为:

public interface IForm
{
    void Evaluate(IEnvironment environment, IThreadState s);
}

IThreadState的位置如下:

/// 

/// The state of the interpreter.
/// The implementation of a task which takes some arguments,
/// call them "x" and "y", and which returns an argument "z",
/// should follow the following protocol:
/// a) Call "PopResult" to get x and y
/// b) Either
///   i) push "z" directly onto IThreadState using PushResult OR
///   ii) push a "task" on to the stack which will result in "z" being
///       pushed on to the result stack.
/// 
/// Note that ii) is "recursive" in its definition - that is, a task
/// that is pushed on to the task stack may in turn push other tasks
/// on the task stack which, when evaluated, 
/// ... ultimately will end up pushing the result via PushResult.
/// 
public interface IThreadState
{
    void PushTask(ITask task);
    object PopResult();
    void PushResult(object result);
}

而ITask是:

public interface ITask
{
    void Execute(IThreadState s);
}

而我的主要"事件"循环是:

ThreadState threadState = new ThreadState();
threadState.PushTask(null);
threadState.PushTask(new EvaluateForm(f, environment));
ITask next = null;

while ((next = threadState.PopTask()) != null)
    next.Execute(threadState);

return threadState.PopResult(); // Get what EvaluateForm evaluated to

EvaluateForm只是一个用特定环境调用IForm.Evaluate的任务.

就个人而言,我发现这个新版本从实现的角度来看更加"好" - 容易获得堆栈跟踪,很容易实现完全延续(虽然......我还没有这样做 - 需要使我的"堆栈"持久链接列表而不是使用C#Stack,并且ITask"返回"新的ThreadState而不是改变它以便我可以进行"调用 - 继续"任务)...等等.

基本上,您只是较少依赖底层语言实现.

我能找到的唯一缺点就是表现......但就我而言,它只是一个翻译,所以我对表现并不在乎.

我还要指出这篇关于将递归代码重写为带有堆栈的迭代代码的好处的文章,由KAI C++编译器的作者之一:考虑递归