Какие проблемы C-интеграции возникают при реализации виртуальных машин без стека?

Похоже, вы уже знакомы с некоторыми недостатками и преимуществами.

Некоторые другие: а) Позволяет поддерживать правильную оптимизацию хвостовых вызовов, даже если базовая реализация не поддерживает ее. б) Легче создавать такие вещи, как «трассировка стека» на уровне языка. в) Легче добавлять правильные продолжения, когда вы указал

Недавно я написал простой интерпретатор Scheme на C#, который изначально использовал стек .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 с определенной средой.

Лично я нашел эту новую версию намного "приятнее" для работы с точки зрения реализации - легко получить трассировку стека, легко реализовать полные продолжения (хотя... я еще не сделал этого - нужно чтобы сделать мои «стеки» постоянными связанными списками, а не использовать стек С#, а ITask «возвращает» новый ThreadState, а не мутирует его, чтобы у меня была задача «продолжения вызова»)... и т. д. и т. д.

По сути, вы просто меньше зависите от базовой языковой реализации.

Единственным недостатком, который я могу найти, является производительность... Но в моем случае это просто интерпретатор, поэтому меня все равно не волнует производительность.

Я также хотел бы указать вам на эту очень хорошую статью о преимуществах переписывания рекурсивного кода как итеративного кода со стеком, написанную одним из авторов компилятора KAI C++: Учет рекурсии

После переписки по электронной почте со Стивом Декорте (автором языка программирования Io) и Константином Олениным я нашел проблему и (частичное) ее решение. Представьте себе вызов функции VM из C, которая вызывает метод VM. В течение периода времени, когда ВМ выполняет обратный вызов, часть состояния ВМ лежит вне ВМ: в стеке C и регистрах. Если вы сохраните состояние ВМ в этот момент, то гарантировано, что вы не сможете правильно восстановить состояние при следующей загрузке ВМ.

Решение состоит в том, чтобы смоделировать виртуальную машину как действующее лицо, принимающее сообщения: виртуальная машина может отправлять асинхронные уведомления в собственный код, а собственный код может отправлять асинхронные уведомления в виртуальную машину. То есть в однопоточной среде, когда виртуальная машина получает управление, за ее пределами не сохраняется никакое дополнительное состояние (за исключением данных, не относящихся к среде выполнения виртуальной машины).

Это не означает, что вы сможете корректно восстановить состояние ВМ при любых обстоятельствах, но, по крайней мере, вы сможете построить на ее основе собственную надежную систему.