Comment amorcer un interpréteur Lisp à l'aide de l'évaluateur métacirculaire

Question

Je suis en train d'implémenter un interpréteur Lisp en C pur et j'ai du mal à faire la transition de C vers Lisp.

Après les étapes de Peter Norvig dans son blog post, j'ai un REPL qui parse jusqu'à présent des expressions Lisp dans les structures de données Lisp et sérialise la structure de données résultant de nouveau dans une expression Lisp qui est imprimé comme indiqué ci-dessous:

J'ai également mis en œuvre les sept primitives described de Paul Grahm, et je comprends l'évaluateur métacirculaire qui s'y trouve. Mes problèmes surviennent en écrivant la partie du code C (pas lisp!) Qui exécute réellement la structure de données une fois qu'elle a été analysée (la partie "eval") dans l'image montrée ci-dessus. À ma connaissance, avec l'évaluateur métacirculaire, il est possible d'écrire la sémantique de l'évaluation des procédures Lisp dans Lisp lui-même. Pour cette raison je veux laisser cette partie du programme en Lisp, cependant, il semble évident qu'à un moment donné j'ai besoin d'écrire du code C qui applique réellement des primitives ou des procédures aux structures de données Lisp. Quand je vais écrire ce code cependant, je me retrouve à écrire la même logique que l'évaluateur métacirculaire itslef, juste la version C.

Ma question est de savoir si je dois mettre en œuvre eval et apply en C (comme Peter Norvig a fait en Python) ou s'il y a une façon de démarrer l'interpréteur Lisp où sont effectivement écrit la seule mise en œuvre de eval et apply en Lisp?

Answer 1

Il n'est pas possible d'implémenter eval et apply dans Lisp si vous créez un interpréteur en C. La raison en est que vous avez besoin d'interpréter l'interpréteur et que vous aurez un problème de bootstrap.

Vous pouvez le rendre minimal en le faisant piloter par les données. Par exemple, toute syntaxe primitive possède une balise et un pointeur de fonction qui prend expression et environnement. Fondamentalement le symbole quote peut évaluer à cela et vous avez eval appeler la fonction. Toutes les fonctions primitives ont un tag + pointeur de fonction, puis apply et eval auront beaucoup moins à faire et plus facile à étendre.

Vous avez raison que eval et apply se sentira comme l'équivalent C du même puisque c'est exactement ce que c'est. Heck même mon brainfuck project fuit un évaluateur métacirculaire si vous regardez assez proche.