Quels problèmes d'intégration C surviennent avec les implémentations VM sans pile?

Question

Par VM sans pile, j'entends l'implémentation qui maintient sa propre pile sur le tas au lieu d'utiliser le système "C-stack". Cela présente de nombreux avantages, tels que les continuations et l'état sérialisable, mais présente également certains inconvénients en ce qui concerne les liaisons C, en particulier les types de rappels C-VM-C (ou VM-C-VM). La question est de savoir exactement quels sont ces inconvénients? Quelqu'un pourrait-il donner un bon exemple d'un vrai problème?

Answer 1

Il semble que vous connaissiez déjà certains des inconvénients et des avantages.

Quelques autres: a) permet de soutenir une bonne optimisation des appels récursifs même si la mise en œuvre sous-jacente n'a pas de soutien pour elle b) plus facile de construire des choses comme un niveau de langue « trace de la pile » c) plus facile pour ajouter des suites correctes, comme vous l'avez souligné

J'ai récemment écrit un simple interpréteur "Scheme" en C#, qui utilisait initialement la pile .NET. puis je re-écrit pour utiliser une pile explicite - donc peut-être ce qui suit vous aidera à:

La première version a utilisé la pile d'exécution .NET implicite ...

Dans un premier temps, il était juste une hiérarchie de classes, avec différentes formes (Lambda, Let, etc.) étant mise en oeuvre de l'interface suivante:

// 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 avait l'air que vous attendez:

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

Pour ajouter " builtins » à mon interprète Scheme, je devais d'abord l'interface suivante:

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

C'était quand il a utilisé la pile d'exécution .NET implicite. Il y avait certainement moins de code, mais il était impossible d'ajouter des choses comme la récursion de queue, et surtout, il était difficile pour mon interpréteur de fournir une trace de pile de "niveau de langage" dans le cas d'une erreur d'exécution. Je l'ai donc réécrit pour avoir une pile explicite (allouée en tas).

mon interface « IFunction » a dû changer à ce qui suit, pour que je puisse mettre en œuvre des choses comme « carte » et « appliquer », qui appellent de nouveau dans l'interpréteur 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); 
} 

Et IForm changé :

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

Où IThreadState est comme suit:

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

Et ITask est:

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

Et ma boucle principale "événement" est:

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 est juste une tâche qui appelle IForm.Evaluate avec un environnement spécifique.

Personnellement, j'ai trouvé cette nouvelle version beaucoup plus "agréable" à travailler du point de vue de la mise en œuvre - facile d'obtenir une trace de pile, facile à mettre en œuvre des suites complètes (bien que ... pour l'instant - besoin de faire de mes piles "persistantes" les listes liées plutôt que d'utiliser C# Stack, et ITask "retourne" le nouveau ThreadState plutôt que de le muter pour que je puisse avoir une tâche "continuation de l'appel" ... etc.

Fondamentalement, vous dépendez moins de l'implémentation du langage sous-jacent. À propos du seul inconvénient que je peux trouver est la performance ... Mais dans mon cas, c'est juste un interprète, donc je ne me soucie pas beaucoup de la performance de toute façon.

Je tiens également à vous à cet article très agréable sur les avantages de re-écriture de code récursif code itérative avec une pile, par l'un des auteurs du KAI compilateur C++: Considering Recursion

Answer 2

Après e Conversation par mail avec Steve Dekorte (auteur du langage de programmation Io) et Konstantin Olenin, j'ai trouvé un problème et une solution (partielle). Imaginez l'appel de la fonction VM vers C, qui rappelle la méthode VM. Pendant la période où VM exécute le rappel, la partie de l'état de la machine virtuelle se trouve en dehors de la machine virtuelle: dans la pile et les registres C. Si vous souhaitez enregistrer l'état de la machine virtuelle à ce moment, il est garanti que vous ne pourrez pas restaurer l'état correctement la prochaine fois que la machine virtuelle est chargée. La solution consiste à modéliser la machine virtuelle en tant qu'acteur de réception de message: la machine virtuelle peut envoyer des notifications asynchrones au code natif et le code natif peut envoyer des notifications asynchrones à la machine virtuelle. C'est-à-dire, dans l'environnement à un seul thread, lorsque la VM prend le contrôle, aucun état supplémentaire n'est stocké en dehors de celle-ci (à l'exception des données non pertinentes pour l'exécution de la VM). Cela ne signifie pas que vous pouvez restaurer correctement l'état de la machine virtuelle en toutes circonstances, mais au moins, vous pouvez créer votre propre système fiable par-dessus.