Quel est l'ensemble minimum de primitives requis de manière à ce qu'une langue soit complète et une variante LISP?
On dirait que la voiture, la CDR et un certain contrôle de flux et quelque chose pour REPL est suffisant. C'est bien s'il y a une telle liste.
suppose qu'il n'y a que 3 types de données, d'entiers, de symboles et de listes. (comme dans picolisp)
4 Réponses :
Le La Lambda Calculus est Turing complet. Il a une primitive - la Lambda. Traduire cela à une syntaxe LISP est assez trivial.
En fait, il a trois primitives: expressions Lambda, appels de fonction et références variables.
Je crois que l'ensemble minimum est ce que John McCarthy a publié dans le document original.
Le code .
Il y a une bonne discussion de cela dans le FAQ LISP . Cela dépend de votre choix de primitives. Le «manuel de programmeur LISP 1.5» d'origine McCarthy l'a fait avec cinq fonctions: voiture, CDR, inconvénients, équation et atome.
Lecture de ladite FAQ, il apparaît qu'il a utilisé ces cinq fonctions avec les formes spéciales, la Lambda et la citation.
La meilleure façon de le savoir, c'est si vous le mettez en œuvre. J'ai utilisé 3 étés pour créer Zozotez qui est un LISP McCarty-ISH exécuté sur Brainfuck .
J'ai essayé de savoir ce dont j'avais besoin et sur un forum, vous trouverez un thread qui dit Vous n'avez besoin que de Lambda. Ainsi, vous pouvez faire tout un LISP dans le calcul de Lambda si vous le souhaitez. Je l'ai trouvé intéressant, mais c'est à peine la voie à suivre si vous voulez quelque chose qui a finalement d'effets secondaires et travaille dans le monde réel.
Pour un Turing complet Lisp j'ai utilisé Paul Grahams Explication du papier de McCarthy et tout ce dont vous avez vraiment besoin est:
c'est-à-dire 10. En plus de cela, avoir une implémentation que vous pouvez tester et non seulement sur une planche à dessin:
c'est thats 12. Dans mon zozotez i Impleméted Je recommande à quiconque d'implémenter un interprète LISP1, dans les deux définir et flambda (macroes anonymes, comme Lambda) aussi. Je pourrais l'alimenter une bibliothèque implémentant toute lisp liée dynamique (ELISP, PICOLISP) à l'exception des E / S de fichier (car le BF sous-jacent ne le prend pas en charge autre que STDIN / STDOUT).
lisp et (pas LISP) , pour bien 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 toutes les autres langages de programmation La manière dont vous mettez en place un interprète est très similaire. Par exemple. dans le vidéos SICP Les magiciens font un interprète pour Une langue logique, mais la structure et la manière de la mettre en œuvre est très similaire à un interprète LISP, même si cette langue est complètement différente de la LISP.
EN.Wikipedia.org/wiki/unLambda
Je ne suis pas sûr d'accepter que UNLAMBDA est une variante LISP.
Je l'ai mentionné juste pour le plaisir, et c'est fonctionnel
Notez que les entiers sont inutiles, vous pouvez les implémenter des fonctions pures.