Was ist der Mindestsatz an Primitiven, die benötigt werden, damit eine Sprache Turing-vollständig und eine Lisp-Variante ist?
Scheint wie Auto, CDR und einige Flusskontrolle und etwas für REPL ist genug. Es wäre schön, wenn es eine solche Liste gibt.
Angenommen, es gibt nur 3 Arten von Daten, Ganzzahlen, Symbole und Listen (wie in Picolip)
Es gibt eine gute Diskussion 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.
Der Lambda-Kalkül ist abgeschlossen. Es hat ein Primitiv - das Lambda. Das zu einer Lisp-Syntax zu übersetzen ist ziemlich trivial.
Ich glaube, die Mindestmenge ist das, was John McCarthy in der Originalarbeit veröffentlicht hat.
Der Code .
Der beste Weg, dies wirklich zu wissen, ist, wenn Sie es implementieren. Ich habe 3 Sommer benutzt, um Zozotez zu erstellen, was ein McCarty-ish LISP ist, der auf Brainfuck .
Ich habe versucht, herauszufinden, was ich brauche, und in einem Forum findest du einen Thread, der sagt: Du brauche nur lambda. Du kannst also einen ganzen LISP im Lambda-Kalkül machen, wenn du möchtest. 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 einen Turing-kompletten LISP habe ich Paul Grahams Erklärung von McCarthy's Papier benutzt und alles was du wirklich brauchst ist:
>Das ist 10. Zusätzlich zu einer Implementierung, die Sie testen können und nicht nur auf einem Zeichenbrett:
Das ist 12. In meiner Zozotez implementierte ich auch set und flambda (anonyme Makros, wie Lambda). Ich könnte es eine Bibliothek füttern, die jede dynamische gebundene Lisp (Elisp, picoLisp) mit Ausnahme von Datei-I / O implementieren (weil die zugrunde liegende BF es anders als Stdin / Stdout nicht unterstützt).
Ich empfehle jedem, einen LISP1-Interpreter in LISP und (not LISP) zu implementieren, um zu verstehen, wie eine Sprache implementiert 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 den SICP-Videos machen die Wizards einen Interpreter für eine logische Sprache, aber Die Struktur und ihre Implementierung sind einem Lisp-Interpreter sehr ähnlich, obwohl diese Sprache völlig anders ist als Lisp.
Tags und Links lisp turing-complete