Lisp vraiment minimum

Question

Quelle est l'ensemble minimum de primitives requises, telles qu'une langue est complète et une Turing variante Lisp?

On dirait voiture, cdr et un certain 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)

Answer 1

Il y a une bonne discussion sur cela dans le Lisp FAQ . Cela dépend de votre choix de primitives. original "LISP 1.5 Manuel du programmeur" de McCarthy l'a fait avec cinq fonctions:. CAR, CDR, CONS, EQ et ATOM

Answer 2

Le lambda-calcul est Türing complète. Il dispose d'une primitive - lambda. Traduire que d'une syntaxe Lisp est assez trivial.

Answer 3

Je crois que l'ensemble minimal est ce que John McCarthy a publié dans le document original.

Les racines de Lisp .

code.

Answer 4

La meilleure façon de savoir réellement ce pour sûr est que si vous le mettre en œuvre. J'ai utilisé 3 étés pour créer Zozotez qui est un LISP McCarty-ish en cours d'exécution sur Brainfuck .

J'ai essayé de savoir ce que je avais besoin et sur un forum, vous trouverez un fil qui dit vous ne devez lambda. Ainsi, vous pouvez faire un LISP tout dans le calcul lambda si vous le souhaitez. Je l'ai trouvé intéressant, mais il est loin d'être le chemin à parcourir si vous voulez quelque chose qui finalement a des effets secondaires et travaille dans le monde réel.

Pour une LISP complète Turing j'ai utilisé Paul Grahams explication de papier de McCarthy et tout ce que vous avez vraiment besoin est:

• symbole évaluation
• forme spéciale citation
• forme particulière si (ou cond)
• forme spéciale lambda (similaire à citer)
• fonction eq
• atome de fonction
• contre la fonction
• voiture de fonction
• fonction cdr
• fonction expédition (appliquer essentiellement mais pas réellement exposé au système afin qu'il gère une liste où le premier élément est une fonction)

10. Cest En plus de cela, d'avoir une mise en œuvre que vous pouvez tester et non pas seulement sur une planche à dessin:

• fonction read
• écriture fonction

12. Cest Dans mon Zozotez Je implemeted set et flambda (de MACROES anonymes, comme lambda) ainsi. Je pourrais nourrir une bibliothèque mise en œuvre de toute Lisp lié à la dynamique (Elisp, picolisp) à l'exception du fichier E / S (parce que le BF sous-jacente ne 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 il est donc un bon point de départ. Pour toutes les autres langages de programmation que vous mettez en œuvre un interprète est très similaire. Par exemple. dans les vidéos SICP les assistants faire un interprète un langage logique, mais la structure et la façon de la mettre en œuvre est très similaire à un interprète Lisp même si cette langue est tout à fait différente de celle Lisp.