Was ist die Mindestmenge von Primitiven erforderlich, so dass eine Sprache Turing abgeschlossen ist und eine Lisp-Variante?Wirklich Minimum Lisp
Scheint, wie Auto, cdr und einige Flusssteuerung und etwas für REPL ist genug. Es ist nett, wenn es solche Liste gibt.
Angenommen, es nur drei Arten von Daten, Zahlen, Symbole und Listen sind. (Wie in picolisp)
Es gibt eine gute Diskussion über diesen in den Lisp FAQ. Es hängt von Ihrer Wahl der Primitiven ab. McCarthy's originales "LISP 1.5 Programmer's Manual" hat es mit fünf Funktionen gemacht: CAR, CDR, CONS, EQ und ATOM.
Lesen der besagten FAQ, es scheint, dass er diese fünf Funktionen zusammen mit den Sonderformen CONS, LAMBDA und QUOTE verwendet hat. – Zak
Die lambda calculus Turing abgeschlossen ist. Es hat ein Primitiv - das Lambda. Das zu einer Lisp-Syntax zu übersetzen ist ziemlich trivial.
Eigentlich hat es * drei * Primitive: Lambda-Ausdrücke, Funktionsaufrufe und Variablenreferenzen. –
Ich glaube, das Minimum Set ist, was John McCarthy in der Originalarbeit veröffentlicht hat.
Der beste Weg, um dies wirklich zu wissen, ist, wenn Sie es implementieren. Ich verwendete 3 Sommer, um Zozotez zu erstellen, das ein McCarty-ish LISP ist, das auf Brainfuck läuft.
Ich habe versucht, herauszufinden, was ich brauchte und auf einem Forum finden Sie einen Thread, der You only need lambda. sagt 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, das schließlich Nebenwirkungen hat und in der realen Welt funktioniert.
Für eine Turing komplette LISP habe ich Paul Grahams explanation of McCarthy's paper und alles, was Sie wirklich brauchen, ist:
Das ist 10. Zusätzlich dazu, eine Implementierung zu haben, dass Sie nicht nur auf dem Reißbrett testen:
Das ist 12.In meinem Zozotez implementierte ich auch set und flambda (anonyme Makros, wie Lambda). Ich könnte es eine Bibliothek füttern, die irgendein dynamisches gebundenes Lisp (Elisp, picoLisp) mit Ausnahme der Datei I/O einführt (weil die zugrundeliegende BF es außer stdin/stdout nicht unterstützt).
ich jedem empfehlen einen LISP1-Interpreter zu implementieren, sowohl in LISP und (not LISP), zu verstehen vollständig, wie eine Sprache umgesetzt wird. LISP hat eine sehr einfache Syntax, daher ist es ein guter Ausgangspunkt. Für alle anderen Programmiersprachen ist die Implementierung eines Interpreters sehr ähnlich. Z.B. in der SICP videos machen die Wizards einen Interpreter für eine logische Sprache, aber die Struktur und wie man sie implementiert ist sehr ähnlich zu einem Lisp-Interpreter, obwohl diese Sprache völlig anders ist als Lisp.
Beachten Sie, dass Integer nicht erforderlich sind, Sie können sie aus reinen Funktionen implementieren. – celtschk