Wirklich Minimum Lisp

Question

Was ist die minimale Menge von Primitiven erforderlich, so dass eine Sprache abgeschlossen ist Turing und lispelt Variante?

Scheint, wie Auto, cdr und einige Flusssteuerung und etwas für REPL ist genug. Es ist schön, wenn es eine solche Liste ist.

Angenommen, es gibt nur drei Arten von Daten, Zahlen, Symbolen und Listen. (Wie in picolisp)

Answer 1

Es gibt eine gute Diskussion über diese in der Lisp FAQ . Es hängt von Ihrer Wahl von Primitiven. McCarthy original "LISP 1.5 Programmierhandbuch" tat es mit fünf Funktionen:. CAR, CDR, CONS, EQ und ATOM

Answer 2

Die Lambda-Kalkül abgeschlossen ist Turing. Es hat eine primitive - das Lambda. Die Übertragung dieser auf eine Lisp-Syntax ziemlich trivial ist.

Answer 3

Ich glaube, das Minimum ist, was John McCarthy in der Originalarbeit veröffentlicht.

Die Wurzeln von Lisp .

Der Code .

Answer 4

Der beste Weg, um tatsächlich diese sicher zu wissen, ist, wenn Sie es implementieren. Ich habe 3 Sommer Zozotez zu schaffen, die ein McCarty-ish LISP auf Brainfuck .

Ich habe versucht, herauszufinden, was ich brauchte, und in einem Forum finden Sie einen Faden finden, der sagt Sie nur Lambda brauchen. So können Sie eine ganze LISP in Lambda-Kalkül machen, wenn Sie möchten. Ich fand es interessant, aber es ist kaum der Weg zu gehen, wenn Sie etwas wollen, dass schließlich Nebenwirkungen und arbeitet in der realen Welt hat.

Für eine Turing komplette LISP verwendete ich Paul Grahams Erklärung von McCarthys Papier und alles, was Sie wirklich brauchen ist:

• Symbol-Auswertung
• spezielle Form Zitat
• spezielle Form if (oder cond)
• Sonderform lambda (ähnlich zu zitieren)
• Funktion eq
• Funktion Atom
• Funktion cons
• Funktion Auto
• Funktion cdr
• function-Versand (grundsätzlich gelten, aber nicht tatsächlich an das System ausgesetzt, so dass es eine Liste behandelt, wo das erste Element ist eine Funktion)

Das ist 10. Zusätzlich dazu, eine Implementierung zu haben, dass Sie testen können, und zwar nicht nur auf dem Reißbrett:

• Funktion Lese
• Funktion write

Das ist 12. In meinem Zozotez I implemeted set und flambda (anonym macroes, wie lambda) als auch. Ich konnte ihm eine Bibliothek füttere jeden dynamischen gebunden Lisp (Elisp, picoLisp) mit Ausnahme der Datei Implementierung I / O (da die zugrunde liegende BF nicht unterstützt andere als stdin / stdout).

ich jedem empfehlen einen LISP1-Interpreter zu implementieren, sowohl LISP und (not LISP), um vollständig zu verstehen, wie eine Sprache umgesetzt wird. LISP hat eine sehr einfache Syntax, so dass es ein guter Ausgangspunkt ist. Für alle anderen Programmiersprachen, wie Sie einen Dolmetscher implementieren ist sehr ähnlich. Z.B. in den SICP Videos die Assistenten machen einen Interpreter für eine logische Sprache, aber die Struktur und wie sie umzusetzen ist sehr ähnlich zu einem Lisp-Interpreter, obwohl diese Sprache als Lisp völlig anders.