Combien de primitives faut-il pour construire une machine LISP? Dix, sept ou cinq?

Question

Sur ce site ils disent qu'il y a 10 LISP primitives. Les primitives sont: atom, quote, eq, car, cdr, cons, cond, lambda, label, apply.

http://hyperpolyglot.wikidot.com/lisp#ten-primitives

Stevey estime qu'il y a sept (ou cinq):

Its part of the purity of the idea of LISP: you only need the seven (or is 
it five?) primitives to build the full machine.

http://steve-yegge.blogspot.com/2006/04/lisp-is-not-acceptable-lisp.html

Quel est le nombre minimal de primitives pour construire une machine LISP (c'est à dire quelque chose qui peut vous exécutez un eval/valeur de la fonction de code LISP)? (Et qui sont-ils?)

(Je peux comprendre que vous pourriez vivre sans atom, label and apply)

Answer 1

Base de Prédicats/F-fonctions

McCarthy' Élémentaire S-fonctions et Prédicats ont été:

1. atom

   Ce qui était nécessaire car car et cdr sont définis pour les listes seulement, ce qui signifie que vous ne pouvez pas compter sur n'importe quelle sorte de réponse à indiquer ce qui se passait si vous avez donné, car d'un atome.

2. eq

   Pour tester l'égalité entre les atomes.

3. car

   Pour le retour de la première moitié (adresse) de la cons de la cellule. (Contenu du registre d'adresse).

4. cdr

   Pour le retour de la deuxième moitié (décrémenter) de la cons de la cellule. (Contenu de décrémenter le registre).

5. cons

   Pour effectuer un nouveau contre de la cellule, avec l'adresse de la moitié contenant le premier argument de cons, et la diminution de la moitié contenant le deuxième argument.

Les lier ensemble: S-Fonctions

Il a ensuite continué à ajouter à sa base de la notation, pour permettre l'écriture de ce qu'il a appelé S-fonctions:

1. quote

   Pour représenter une expression sans l'évaluer.

2. cond

   Le conditionnelles de base pour être utilisé avec la décrit précédemment prédicats.

3. lambda

   Pour désigner une fonction.

4. label

   Mais il n'a pas besoin de cela pour la récursivité, il pourrait ne pas avoir connu sur le Y Combinator (c onformément à Paul Graham), il a ajouté ceci pour des raisons de commodité et pour faciliter la récursivité.

---

Donc vous pouvez voir qu'il a réellement défini 9 de base "opérateurs" pour sa machine Lisp. Dans une précédente réponse à une autre de vos questions, j'ai expliqué comment on pourrait représenter et d'opérer sur les nombres avec ce système.

Mais la réponse à cette question dépend vraiment de ce que vous voulez de votre machine Lisp. Vous pourriez mettre en œuvre l'un sans l' label de la fonction, comme vous avez pu simplement fonctionnellement compose tout, et d'obtenir la récursivité par le biais de l'application de la Y Combinator.

atom pourrait être mis au rebut si vous avez défini l' car opération sur les atomes de revenir NIL.

Vous pourriez, pour l'essentiel, McCarthy LISP machine avec 7 de ces 9 défini primitives, mais vous pourriez ostensiblement définir une version plus concise en fonction de la façon dont beaucoup de désagréments que vous voulez infliger à soi-même. J'aime sa machine assez fines, ou le nombre de primitives dans les nouveaux langages comme Clojure.

Answer 2

Le meilleur moyen de savoir réellement ce est sûr, c'est si vous la mettre en œuvre. J'ai utilisé 3 étés de créer Zozotez qui est un McCarty-ish LISP en cours d'exécution sur Brainfuck.

J'ai essayé de trouver ce dont j'avais besoin et sur un forum, vous trouverez un thread qui dit que Vous avez seulement besoin de lambda. Ainsi, vous pouvez prendre un ensemble de LISP dans le lambda calcul, je vous le désirez. J'ai trouvé ça intéressant, mais ce n'est pas la voie à suivre si vous voulez quelque chose qui finalement a des effets secondaires et fonctionne dans le monde réel.

Pour une Turing LISP j'ai utilisé Paul Grahams explication de McCarthy papier et tous vous avez vraiment besoin est:

• symbole-évaluation
• la forme spéciale de devis
• forme spéciale si (ou (cond)
• forme spéciale lambda (similaire à la citation)
• la fonction eq
• la fonction de l'atome
• la fonction cons
• la fonction de voiture
• la fonction cdr
• la fonction de répartition (liste-lambda)

C'est 10. En plus de cela, d'avoir une application que vous pouvez tester et pas seulement sur une planche à dessin:

• fonction de lecture
• la fonction d'écriture

C'est 12. Dans mon Zozotez j'ai mis en oeuvre ensemble et flambda (anonyme macroes, comme la lambda). J'ai pu nourrir une bibliothèque mise en œuvre de toute dynamique lié lisp (Elisp, picoLisp), à l'exception d'e/S de fichier (parce que le sous-jacent BF ne prend pas en charge d'autres que stdin/stdout).

Je recommande à quiconque de mettre en œuvre un LISP1-interprète dans les deux LISP (et non pas LISP) afin de mieux comprendre comment une langue est mis en œuvre. LISP est très simple syntaxe c'est donc un bon point de départ pour un analyseur. Je suis actuellement en train de travailler sur un schéma compilateur écrit en scheme, avec des objectifs différents (comme Staline est pour cible C), espérons-le, BF comme l'un d'eux.

Answer 3

McCarthy a utilisé sept opérateurs pour définir le Lisp d'origine: quote , atom , eq , car , cdr , cons et cond . Cet article retrace ses pas.

Answer 4

Cette faq membres:

Il n'y a pas de "meilleur" ensemble minimal de primitives; tout dépend de la mise en œuvre. Par exemple, même quelque chose d'aussi fondamental que les numéros de n'a pas besoin d'être primitive, et peut être représenté sous forme de listes. Un possible ensemble de primitives peuvent inclure VOITURE, CDR, et les INCONVÉNIENTS pour la manipulation de S-expressions, de LIRE et d'IMPRIMER pour l'entrée/sortie de la S-expressions et APPLIQUER et d'EVAL pour les tripes d'un interprète. Mais alors vous pourriez souhaitez ajouter LAMBDA pour les fonctions EQ pour l'égalité, pour COND les conditions, fixées pour l'attribution et à la DEFUN pour les définitions. CITATION peut venir dans maniable.

Qui vient de l'École de Science Informatique, Carnegie Melon site web.

Answer 5

Voir cette autre question pour construire des macros à partir du jeu de 7 primitives de Paul Graham.