使用无栈虚拟机实现时，会出现哪些C语言集成问题？

Question

我所说的无栈虚拟机是指在堆上维护自己的堆栈，而不是使用系统的“C堆栈”的实现。这有很多优点，比如可以实现连续性和可序列化状态，但在涉及C绑定时也有一些缺点，特别是涉及到C-VM-C回调（或VM-C-VM）的情况。

问题是这些缺点具体是什么？是否能给出一个真实问题的好例子？

- Oleg Andreev

Answer 1

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

其他一些优点： 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看起来就像你期望的那样：

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

为了将“内建函数”添加到我的Scheme解释器中，我最初的接口如下：

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

那时它使用了隐式的 .NET 运行时堆栈。代码量明显较少，但无法添加像适当的尾递归这样的东西，最重要的是，在运行时出现错误时，我的解释器无法提供“语言级别”的堆栈跟踪，这让人感到很尴尬。

所以我重新编写了一个显式（堆分配）的堆栈。

我的“IFunction”接口必须更改为以下内容，以便我可以实现诸如“map”和“apply”之类的东西，这些东西会回调到Scheme解释器中：

/// <summary>
/// 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
/// </summary>
public interface IStackFunction
{
    void Evaluate(IThreadState threadState, object[] args);
}

现在IForm已经更新为：

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

在这里，IThreadState的含义如下：

/// <summary>
/// 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.
/// </summary>
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++编译器的作者之一撰写的：考虑递归。

- Paul Hollingsworth

---

其实，问题只是关于考虑仅原生代码集成的缺点。但还是谢谢你分享故事。 - Oleg Andreev

Answer 2

经过与Io编程语言的作者Steve Dekorte和Konstantin Olenin的电子邮件交流，我发现了一个问题以及（部分）解决方案。 想象一下从VM调用C函数，该函数回调VM方法的情况。在VM执行回调的期间，VM状态的一部分位于VM之外：在C堆栈和寄存器中。如果此时保存VM状态，则保证无法在下次加载VM时正确地恢复状态。

解决方案是将VM建模为接收消息的actor：VM可以向本机代码发送异步通知，本机代码也可以向VM发送异步通知。也就是说，在单线程环境中，当VM获得控制权时，除了与VM运行时无关的数据之外，不会存储任何其他状态。

这并不意味着您可以在任何情况下正确地恢复VM状态，但至少，您可以在其上构建自己的可靠系统。

- Oleg Andreev