Quel est l'ensemble minimum de primitives requis pour qu'une langue soit complète de Turing et une variante Lisp?Lisp vraiment minimum
On dirait que la voiture, le cdr et un peu de contrôle de flux et quelque chose pour REPL est suffisant. Ce serait bien s'il y a une telle liste.
On suppose qu'il n'y a que trois types de données, des entiers, des symboles et des listes. (Comme dans picolisp)
Il y a une bonne discussion à ce sujet dans le Lisp FAQ. Cela dépend de votre choix de primitives. Le "Manuel du Programmeur LISP 1.5" de McCarthy l'a fait avec cinq fonctions: CAR, CDR, CONS, EQ et ATOM.
En lisant ladite FAQ, il apparaît qu'il a utilisé ces cinq fonctions avec les formes spéciales CONS, LAMBDA et QUOTE. – Zak
Le lambda calculus est turation complète. Il a une primitive - le lambda. Traduire cela en une syntaxe Lisp est plutôt trivial.
En fait, il a * trois * primitives: expressions lambda, appels de fonctions et références variables. –
Je crois que l'ensemble minimal est ce que John McCarthy a publié dans l'article original.
La meilleure façon de le savoir est de l'implémenter. J'ai utilisé 3 étés pour créer Zozotez qui est un LISP McCarty-ish fonctionnant sur Brainfuck.
J'ai essayé de savoir ce que je avais besoin et sur un forum, vous trouverez un fil qui dit You only need lambda. Ainsi, vous pouvez faire un LISP tout dans le calcul lambda si vous le souhaitez. Je l'ai trouvé intéressant, mais ce n'est pas la voie à suivre si vous voulez quelque chose qui a finalement des effets secondaires et fonctionne dans le monde réel.
Pour une Turing complète LISP je Paul Grahams explanation of McCarthy's paper et tout ce que vous avez vraiment besoin est:
Cest 10. en plus de cela, d'avoir une mise en œuvre que vous pouvez tester et non pas seulement sur une planche à dessin:
C'est 12.Dans mon Zozotez j'ai implémété set et flambda (macro anonymes, comme lambda) ainsi. Je pourrais lui fournir une librairie implémentant un lisp lié dynamique (Elisp, picoLisp) à l'exception des E/S de fichiers (car le BF sous-jacent ne le supporte pas autre que stdin/stdout).
Je recommande à quiconque de mettre en œuvre un LISP1-interprète, dans les deux LISP et (not LISP), pour comprendre comment une langue est mise en œuvre. LISP a une syntaxe très simple, donc c'est un bon point de départ. Pour tous les autres langages de programmation, la façon dont vous implémentez un interpréteur est très similaire. Par exemple. dans le SICP videos les assistants font un interpréteur pour un langage logique, mais la structure et comment l'implémenter est très similaire à un interpréteur Lisp même si ce langage est complètement différent de Lisp.
Notez que les entiers sont inutiles, vous pouvez les implémenter à partir de fonctions pures. – celtschk