J'écris un simulateur de la machine SECD en C # guidé par le Description sur Wikipedia . J'ai les opérations de base terminées, mais je ne suis pas sûr de la manière de mettre en œuvre les instructions chez Wikipedia Il est indiqué sur RAP fonctionne comme AP, seulement qu'elle remplace une occurrence d'un environnement factice avec le courant actuel, faisant ainsi des fonctions récursives possibles
et pour AP apparaît une fermeture et une liste de valeurs de paramètre de la pile. La fermeture est appliquée aux paramètres en installant son environnement en tant qu'entrepray, en appuyant sur la liste des paramètres devant celle-ci, effacer la pile et régler C sur le pointeur de fonction de la fermeture. Les valeurs précédentes de S, E et la valeur suivante de C sont enregistrées sur la décharge.
Voici mon implémentation de Notez que Qu'est-ce qui me confond est exactement comment RAP . RAP :
AP Il est écrit:
AP liste est ma mise en œuvre d'un Cellule de style LISP "inconvénient". rap diffère de ap ? Par exemple, ce qui arrive exactement au registre de l'environnement (e)? Je trouve la définition de Wikipedia un peu ambiguë et je n'ai pas pu trouver autre chose qui l'explique bien.
3 Réponses :
Secd n'est pas récursif de la queue, bien que vous puissiez créer Une machine secd récursive de queue (PDF) .
L'instruction AP est utilisée pour compiler une liaison" Let ", tandis que l'instruction de rap est utilisée pour compiler une liaison" LETRec '".
'LETRec' est différent de "let" parce que vous pouvez "voir" l'environnement où la fonction récursive est définie, de sorte que vous puissiez l'appeler de manière récursive (donc, par exemple, vous définissez une fonction "factorielle" et vous pouvez l'appeler Dans le corps de la fonction).
RAP modifie l'environnement en appelant Rplaca (similaire à SetCar! Dans le schéma). Une instruction de DUM précédente ajoute une voiture "mannequin" à l'environnement (qui n'est jamais utilisée), et le PAP supprime cette "voiture" mannequin "dans l'environnement et le remplace avec la solution appropriée.
Transitions de l'état sont comme: Voir aussi revisitant le Secd et la puissance de Lisp , citant: et
L'instruction de rap est utilisée pour prendre en charge les appels de fonction récursive et les travaux en remplaçant un environnement factice précédemment créé sur la pile, appelé Omega, par un qui contient toutes les fonctions visibles dans la portée récursive. La spécification utilise Rplaca pour indiquer que le fonctionnement de remplacement, et c'est ce que nous avons utilisé dans notre implémentation de LISP du Secd, aussi: ...
Lorsque vous essayez de mettre en œuvre le rap à Erlang, je suis resté coincé car il n'y a pas d'opérations destructrices sur des listes. Pas dans l'API standard et apparemment pas dans l'API système non plus. Donc, le Secd Erlang a l'air bien, seulement il ne fonctionne pas.
Vous devriez vraiment récupérer une copie du merveilleux petit livre de Peter Henderson "Application de programmation fonctionnelle et mise en œuvre". Il décrit et construit minutieusement une machine sect et lispkit lisp.
Pour référence, voici une machine de seconde complète dans ~ 100 lignes de F #, puis un LISPKIT LISP compilé et teste environ 100. github.com/ashleyf/lispkit/blob/master/program.fs
En plus de l'excellente réponse acceptée, je voulais fournir davantage une explication de pourquoi L'environnement (le Dans un appel de fonction typique, une nouvelle liste est enfoncée sur Pour résoudre ce problème, rap est requis.
E dans secd ) stocke toutes les entités persistées (fonctions, constantes, variables, etc.). E est essentiellement une pile de listes. Les choses dans E sont chargées sur la pile s , puis exécuté ou utilisée par des commandes dans C . Tout dans E est donné un identifiant afin qu'il puisse être référencé plus tard. Cet identifiant est typiquement un tuple (x, y) , où x représente l'emplacement de la liste sur la pile et y représente une position dans cette liste.
E et maintenant toutes les variables locales peuvent avoir des identifiants comme (| e |, y) , où | E | désigne la taille de E . Ceci est très problématique pour les fonctions récursives, cependant, car la taille de la pile augmente avec chaque appel de fonction, il n'ya aucun moyen d'assigner les identifiants utilisables de variables locales.
rap fait la plupart des éléments AP fait, mais au lieu de pousser une nouvelle liste sur la pile d'environnement, il remplace tout ce qui est à la tête du E avec la nouvelle liste d'environnements.