c - una - integrales indefinidas

¿Qué problemas de integración C surgen con las implementaciones de VM sin apilamiento?

Question

Por VM sin apilamiento me refiero a la implementación que mantiene su propia pila en el montón en lugar de utilizar el sistema "C-stack". Esto tiene muchas ventajas, como las continuas y el estado serializable, pero también tiene algunas desventajas cuando se trata de enlaces C, especialmente para el tipo de devolución de llamada C-VM-C (o VM-C-VM).

La pregunta es cuáles son exactamente estas desventajas? ¿Alguien podría dar un buen ejemplo de un problema real?

Answer 1

Después de una conversación por correo electrónico con Steve Dekorte (autor del lenguaje de programación Io) y Konstantin Olenin, encontré un problema y una solución (parcial). Imagine la llamada de la función VM a C, que devuelve la llamada al método VM. Durante el período de tiempo en que la máquina virtual ejecuta la devolución de llamada, parte del estado de la máquina virtual queda fuera de la máquina virtual: en la pila C y se registra. Si desea guardar el estado de la VM en ese momento, se garantiza que no podría restaurar el estado correctamente la próxima vez que cargue VM.

La solución es modelar VM como un actor que recibe mensajes: VM puede enviar notificaciones asincrónicas al código nativo y el código nativo puede enviar notificaciones asincrónicas a la VM. Es decir, en el entorno de subproceso único, cuando VM obtiene el control, no se almacena ningún estado adicional fuera de él (excepto datos irrelevantes para el tiempo de ejecución de VM).

Esto no significa que pueda restaurar correctamente el estado de la VM en ninguna circunstancia, pero al menos, puede construir su propio sistema confiable encima.

Answer 2

Parece que ya está familiarizado con algunas de las desventajas y ventajas.

Algunos otros: a) Hace posible apoyar la optimización adecuada de la cola incluso si la implementación subyacente no tiene ningún soporte para ella b) Es más fácil construir cosas como un "rastro de pila" a nivel de lenguaje c) Es más fácil agregar continuaciones apropiadas, como usted señalado

Hace poco escribí un intérprete simple "Scheme" en C #, que inicialmente usaba la pila .NET. Luego lo re-escribí para usar una pila explícita, por lo que quizás lo siguiente te ayudará a:

La primera versión usaba la pila de tiempo de ejecución .NET implícita ...

Inicialmente, era solo una jerarquía de clases, con diferentes formas (Lambda, Let, etc.) siendo implementaciones de la siguiente interfaz:

// 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 se veía como era de esperar:

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

Para agregar "builtins" a mi intérprete Scheme, inicialmente tenía la siguiente interfaz:

/// <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);
}

Fue entonces cuando utilizó la pila de tiempo de ejecución .NET implícita. Definitivamente había menos código, pero era imposible agregar cosas como recursividad de cola adecuada, y lo más importante, era incómodo para mi intérprete poder proporcionar un rastro de pila de "nivel de idioma" en el caso de un error de tiempo de ejecución.

Así que reescribí para tener una pila explícita (pila asignada).

Mi interfaz "IFunction" tuvo que cambiar a lo siguiente, para poder implementar cosas como "mapa" y "aplicar", que devuelven la llamada al intérprete de 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);
}

Y IForm cambió a:

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

Donde IThreadState es el siguiente:

/// <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);
}

Y ITask es:

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

Y mi ciclo principal de "eventos" es:

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 es solo una tarea que llama a IForm.Evaluate con un entorno específico.

Personalmente, encontré esta nueva versión mucho más "agradable" para trabajar desde un punto de vista de implementación: fácil de obtener un seguimiento de la pila, fácil de implementar implementaciones completas (aunque ... aún no lo he hecho). para hacer que mis "pilas" persistan en listas enlazadas en lugar de usar C # Stack, y ITask "devuelve" el nuevo ThreadState en lugar de mutarlo para que pueda tener una "tarea de continuación de llamadas" ... etc., etc.

Básicamente, eres menos dependiente de la implementación del lenguaje subyacente.

El único inconveniente que puedo encontrar es el rendimiento ... Pero en mi caso, es solo un intérprete, así que no me importa mucho el rendimiento de todos modos.

También te dirijo a este artículo muy bueno sobre los beneficios de volver a escribir código recursivo como código iterativo con una pila, por uno de los autores del compilador KAI C ++: Considerando la recursividad