Comment implémenter les continuations ?

Question

Je travaille sur un interpréteur Scheme écrit en C.Actuellement, il utilise la pile d'exécution C comme sa propre pile, ce qui présente un problème mineur lors de l'implémentation des continuations.Ma solution actuelle consiste à copier manuellement la pile C sur le tas, puis à la recopier si nécessaire.En plus de ne pas être standard C, cette solution n'est pas idéale.

Quelle est la manière la plus simple d’implémenter des continuations pour Scheme en C ?

Answer 1

Je me souviens avoir lu un article qui pourrait vous être utile : Cheney sur le M.T.A. :-)

Certaines implémentations de Scheme que je connais, telles que SIS, allouent leurs trames d'appel sur le tas.

@ollie :Vous n'avez pas besoin d'effectuer le levage si toutes vos trames d'appel sont sur le tas.Il y a bien sûr un compromis en termes de performances :le temps de levage, par rapport à la surcharge nécessaire pour allouer toutes les images sur le tas.Il devrait peut-être s'agir d'un paramètre d'exécution réglable dans l'interpréteur.:-P

Answer 2

Un bon résumé est disponible dans Stratégies de mise en œuvre pour des continuations de première classe, un article de Clinger, Hartheimer et Ost.Je recommande de regarder en particulier la mise en œuvre de Chez Scheme.

La copie de pile n'est pas si complexe et il existe un certain nombre de techniques bien comprises pour améliorer les performances.L'utilisation de trames allouées au tas est également assez simple, mais vous faites un compromis en créant une surcharge pour une situation "normale" dans laquelle vous n'utilisez pas de continuations explicites.

Si vous convertissez le code d'entrée en style de transmission de continuation (CPS), vous pouvez éliminer complètement la pile.Cependant, bien que CPS soit élégant, il ajoute une autre étape de traitement au niveau du front-end et nécessite une optimisation supplémentaire pour surmonter certaines implications en termes de performances.

Answer 3

Si vous partez de zéro, vous devriez vraiment vous pencher sur la transformation du style de réussite des passes (CPS).

Les bonnes sources incluent "LISP en petits morceaux" et Le schéma de Marc Feeley en présentation de 90 minutes.

Answer 4

Il semble que la thèse de Dybvig n’ait pas été mentionnée jusqu’à présent.C'est un plaisir à lire.Le modèle basé sur un tas est le plus facile à mettre en œuvre, mais la pile basée est plus efficace.Ignorez le modèle basé sur les chaînes.

R.Kent Dybvig."Trois modèles de mise en œuvre pour le programme".http://www.cs.indiana.edu/~dyb/papers/3imp.pdf

Consultez également les documents de mise en œuvre sur ReadScheme.org.http://library.readscheme.org/page8.html

Le résumé est le suivant :

Cette thèse présente trois modèles de mise en œuvre pour le langage de programmation du schéma.Le premier est un modèle basé sur un tas utilisé dans une certaine forme dans la plupart des implémentations de schémas à ce jour;La seconde est un nouveau modèle basé sur la pile qui est considérablement plus écent que le modèle basé sur un tas pour exécuter la plupart des programmes;et le troisième est un nouveau modèle basé sur des chaînes destiné à être utilisé dans une implémentation de processeur multiple du schéma.

Le modèle basé sur un tas alloue plusieurs structures de données importantes dans un tas, y compris les listes de paramètres réelles, les environnements de liaison et les trames d'appel.

Le modèle basé sur la pile alloue ces mêmes structures sur une pile chaque fois que possible.Il en résulte moins d'allocation de tas, moins de références de mémoire, des séquences d'instructions plus courtes, moins de collecte de déchets et une utilisation plus eccient de la mémoire.

Le modèle basé sur des chaînes alloue les versions de ces structures directement dans le texte du programme, qui est représentée comme une chaîne de symboles.Dans le modèle basé sur des chaînes, les programmes de schémas sont traduits dans un langage FFP conçu spécialement pour soutenir le schéma.Les programmes de cette langue sont directement exécutés par la machine FFP, un ordinateur de réduction de chaîne de processeurs multiples.

Le modèle basé sur la pile présente un avantage pratique immédiat ;Il s'agit du modèle utilisé par le système Chez Scheme de l'auteur, une implémentation haute performance du schéma.Le modèle basé sur des chaînes sera utile pour fournir un schéma en tant qu'alternative de haut niveau à FFP sur la machine FFP une fois la machine réalisée.

Answer 5

Outre les bonnes réponses que vous avez obtenues jusqu'à présent, je recommande celle d'Andrew Appel Compilation avec continuations.Il est très bien écrit et même s'il ne traite pas directement du C, il constitue une source d'idées très intéressantes pour les rédacteurs de compilateurs.

Le Chicken Wiki contient également des pages que vous trouverez très intéressantes, telles que structure interne et processus de compilation (où CPS est expliqué avec un exemple réel de compilation).

Answer 6

Les exemples que vous pouvez consulter sont : Poulet (une implémentation de Scheme, écrite en C qui prend en charge les continuations) ;Celui de Paul Graham Sur Lisp - où il crée un transformateur CPS pour implémenter un sous-ensemble de continuations en Common Lisp ;et Blocs Web - un framework web basé sur les continuations, qui implémente également une forme limitée de continuations en Common Lisp.

Answer 7

Les suites ne sont pas le problème :vous pouvez implémenter ceux avec des fonctions régulières d'ordre supérieur en utilisant CPS.Le problème avec l'allocation naïve de pile est que les appels de fin ne sont jamais optimisés, ce qui signifie que vous ne pouvez pas planifier.

La meilleure approche actuelle pour mapper la pile de spaghettis du schéma sur la pile consiste à utiliser des trampolines :essentiellement une infrastructure supplémentaire pour gérer les appels non de type C et les sorties de procédures.Voir Style trampoline (ps).

Il y a du code illustrant ces deux idées.

Answer 8

La méthode traditionnelle consiste à utiliser setjmp et longjmp, bien qu'il y ait des mises en garde.

Voici un explication assez bonne

Answer 9

Les continuations consistent essentiellement en l'état enregistré de la pile et des registres du processeur au moment des changements de contexte.À tout le moins, vous n'êtes pas obligé de copier la totalité de la pile dans le tas lors du changement, vous pouvez uniquement rediriger le pointeur de pile.

Les continuations sont implémentées de manière triviale à l’aide de fibres. http://en.wikipedia.org/wiki/Fiber_%28computer_science%29.Les seules choses qui nécessitent une encapsulation minutieuse sont la transmission des paramètres et les valeurs de retour.

Dans Windows, les fibres sont réalisées à l'aide de la famille d'appels CreateFiber/SwitchToFiber.dans les systèmes compatibles Posix, cela peut être fait avec makecontext/swapcontext.

boost::coroutine a une implémentation fonctionnelle de coroutines pour C++ qui peut servir de point de référence pour l'implémentation.

Answer 10

Utilisez plutôt une pile explicite.

Answer 11

Patrick a raison, la seule façon de le faire est d'utiliser une pile explicite dans votre interpréteur et de placer le segment approprié de la pile dans le tas lorsque vous devez le convertir en continuation.

C'est fondamentalement la même chose que ce qui est nécessaire pour prendre en charge les fermetures dans les langages qui les prennent en charge (les fermetures et les continuations étant quelque peu liées).

Answer 12

Comme soegaard souligné, la référence principale reste celui-ci

L'idée est qu'une continuation est une fermeture qui conserve sa pile de contrôle d'évaluation.La pile de contrôle est nécessaire pour poursuivre l'évaluation à partir du moment où la suite a été créée à l'aide de call/cc.

Souvent, l'invocation de la continuation prolonge le temps d'exécution et remplit la mémoire de piles dupliquées.J'ai écrit ce code stupide pour prouver que, dans mit-scheme, cela fait planter le schéma,

Le code additionne les 1000 premiers nombres 1+2+3+...+1000.

(call-with-current-continuation 
 (lambda (break)
   ((lambda (s) (s s 1000 break))
    (lambda (s n cc)
      (if (= 0 n)
          (cc 0)
          (+ n
             ;; non-tail-recursive,
             ;; the stack grows at each recursive call
             (call-with-current-continuation
              (lambda (__)
                (s s (- n 1) __)))))))))

Si vous passez de 1 000 à 100 000, le code passera 2 secondes, et si vous augmentez le nombre saisi, il plantera.