Quali problemi di integrazione C si presentano con le implementazioni VM senza stack?

Question

Con VM impilabile intendo implementazione che mantiene il proprio stack nell'heap invece di utilizzare il sistema "C-stack". Questo ha molti vantaggi come la continuazione e lo stato serializzabile, ma ha anche alcuni svantaggi quando si tratta di C-binding, in particolare per il tipo di callback C-VM-C (o VM-C-VM).

La domanda è: quali sono esattamente questi svantaggi? Qualcuno potrebbe dare un buon esempio di un vero problema?

Answer 1

Sembra che tu abbia già familiarità con alcuni degli svantaggi e dei vantaggi.

Alcuni altri: a) permette di sostenere una corretta ottimizzazione chiamata coda, anche se l'implementazione sottostante non ha alcun supporto per esso b) più facile costruire cose come un livello di linguaggio "stack trace" c) Più facile aggiungere opportune continuazioni, come hai sottolineato

Recentemente ho scritto un semplice interprete "Scheme" in C#, che inizialmente utilizzava lo stack .NET. Poi ho ri-scritto per utilizzare uno stack esplicito - in modo forse la seguente vi aiuterà:

La prima versione utilizzato lo stack di runtime .NET implicita ...

Inizialmente, era solo una gerarchia di classi, con diverse forme (Lambda, Let, ecc) che sono implementazioni la seguente interfaccia:

// 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 sembrava come ci si aspetterebbe:

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

Per aggiungere " builtins" al mio schema interprete, inizialmente ho avuto la seguente interfaccia:

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

Questo è stato quando ha usato lo stack di runtime .NET implicita. C'era sicuramente meno codice, ma era impossibile aggiungere cose come la corretta ricorsione della coda e, cosa più importante, era strano per il mio interprete essere in grado di fornire una traccia di stack "a livello di linguaggio" nel caso di un errore di runtime.

Quindi l'ho riscritto per avere uno stack esplicito (heap allocato).

mia interfaccia "IFunction" dovuto cambiare al seguente, in modo da poter implementare cose come "mappa" e "applicare", che chiamano nuovamente dentro l'interprete 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); 
} 

E iFORM cambiato :

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

Dove IThreadState è la seguente:

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

E ITask è:

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

E il mio "evento" main loop è:

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 è solo un compito che chiama IForm.Evaluate con un ambiente specifico.

Personalmente, ho trovato questa nuova versione molto più "carina" con cui lavorare da un punto di vista dell'implementazione - facile ottenere una traccia di stack, facile da implementare continuazioni complete (anche se ... Non l'ho fatto ancora - ho bisogno di rendere i miei "stack" elenchi di collegamenti persistenti piuttosto che usare C# Stack, e ITask "restituisce" il nuovo ThreadState piuttosto che mutarlo in modo che possa avere un task "call-continuation" ... ecc. ecc.

Fondamentalmente, sei meno dipendente dall'implementazione linguistica sottostante.

L'unico lato negativo che riesco a trovare è la prestazione ... Ma nel mio caso, è solo un interprete quindi non mi interessa molto delle prestazioni comunque.

Mi piacerebbe anche puntare a questo articolo molto bello sui benefici di ri-scrittura di codice ricorsivo come codice iterativo con una pila, da uno dei del compilatore C++ KAI gli autori: Considering Recursion

Answer 2

Dopo e- conversazione via mail con Steve Dekorte (autore del linguaggio di programmazione Io) e Konstantin Olenin, ho trovato un problema e una (parziale) soluzione ad esso. Immaginate la chiamata dalla funzione VM alla C, che richiama il metodo VM. Durante il periodo di tempo in cui la VM esegue la richiamata, parte dello stato della VM si trova all'esterno della VM: nello stack C e nei registri. Se si salva lo stato della VM in quel momento, è garantito che non è possibile ripristinare lo stato correttamente la volta successiva che viene caricata la VM.

La soluzione è modellare VM come attore di ricezione messaggi: la VM può inviare notifiche asincrone al codice nativo e il codice nativo può inviare notifiche asincrone alla VM. Cioè, nell'ambiente a thread singolo, quando VM acquisisce il controllo, nessuno stato aggiuntivo viene memorizzato al di fuori di esso (ad eccezione dei dati irrilevanti per il runtime di VM).

Ciò non significa che è possibile ripristinare correttamente lo stato della macchina virtuale in qualsiasi circostanza, ma almeno, è possibile creare il proprio sistema affidabile su di esso.