Какие проблемы C-интеграции возникают с реализациями VM без стеков?

Question

Под виртуальной машиной без стека я подразумеваю реализацию, которая поддерживает собственный стек в куче, а не использует систему "C-stack". Это имеет много преимуществ, таких как продолжения и сериализуемое состояние, но также имеет некоторые недостатки, когда речь идет о C-привязках, особенно о обратных вызовах типа C-VM-C (или VM-C-VM).

Вопрос в том, что именно эти недостатки? Может ли кто-нибудь привести хороший пример реальной проблемы?

Answer 1

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

Некоторые другие: а) делает возможным поддерживать надлежащую оптимизацию конечного вызова, даже если базовая реализация не имеет никакой поддержки; б) легче создавать такие вещи, как "трассировка стека" на уровне языка; в) легче добавлять правильные продолжения, поскольку вы указал

Недавно я написал простой интерпретатор "Scheme" в C#, который первоначально использовал стек.NET. Затем я переписал его, чтобы использовать явный стек - так что, возможно, вам поможет следующее:

Первая версия использовала неявный стек времени выполнения.NET...

Первоначально это была просто иерархия классов, в которой различные формы (лямбда, пусть и т. Д.) Являлись реализациями следующего интерфейса:

// 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. Оценивать в определенной среде.

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

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

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

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

Answer 2

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

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

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