Wie viele Primitive benötigt man zum Aufbau einer LISP-Maschine? Zehn, sieben oder fünf?

Auf dieser Website Sie sagen, es gibt 10 LISP-primitive.
Die primitive sind: atom, quote, eq, car, cdr, cons, cond, lambda, label, apply.

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

Stevey rechnet, sind es sieben (oder fünf):

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

Was ist die minimale Anzahl von primitiven zu bauen, eine LISP-Maschine (dh etwas, das kann eine eval/Wert-Funktion auf LISP-code)? (Und welche sind Sie?)

(Ich kann dich verstehen, könnte auch ohne Leben atom, label and apply)

InformationsquelleAutor der Frage hawkeye | 2010-08-14

  1. 7

    Sehen diese andere Frage zu konstruieren Makros aus Paul Grahams 7 primitive.

    InformationsquelleAutor der Antwort DomQ

  2. 56

    Basic Prädikate/F-Funktionen

    McCarthy's Elementare S-Funktionen und Prädikate waren:

    1. atom

      Das war notwendig, weil die car-und cdr sind so definiert, zeigt nur, was bedeutet, dass Sie nicht rechnen kann, auf jede beliebige Art von Antwort, um anzuzeigen, was geschehen war, wenn Sie gab car ein atom.

    2. eq

      Zur Prüfung der Gleichheit zwischen den Atomen.

    3. car

      Für die Rückgabe der ersten Hälfte (Adresse) des cons-Zelle. (Inhalt von Adresse registrieren).

    4. cdr

      Für die Rücksendung der zweiten Hälfte (Dekrement) der cons-Zelle. (Inhalt des decrement register).

    5. cons

      Für eine neue cons-Zelle mit der Adresse, die Hälfte mit dem ersten argument, um die Nachteile, und der Dekrement-Hälfte mit dem zweiten argument.

    Binden es zusammen: S-Funktionen

    Er ging dann auf hinzufügen, um seine grundlegende notation, zu aktivieren, zu schreiben, was er als S-Funktionen:

    1. quote

      Zur Darstellung eines Ausdrucks, ohne zu bewerten.

    2. cond

      Die grundlegende bedingte verwendet werden die zuvor beschriebenen Prädikaten.

    3. lambda

      Bezeichnen eine Funktion.

    4. label

      Obwohl er nicht brauchen diese für Rekursion, könnte er nicht gewusst haben über die Y-Combinator (laut Paul Graham), er fügte hinzu, diese für die Bequemlichkeit und ermöglichen eine einfache Rekursion.

    So dass Sie sehen können, ist er eigentlich definiert 9 basic "Operatoren" für seine Lisp-Maschine. In einer früheren Antwort auf die anderen Fragen, ich erklärte ihm wie Sie konnte stellen und betreiben auf zahlen mit diesem system.

    Aber die Antwort auf diese Frage hängt wirklich davon ab, was Sie wollen aus Ihrem Lisp-Maschine. Könnte man implementieren, ohne die label Funktion, als könnte man Sie einfach funktionell Komponieren alles, und erhalten die Rekursion durch Anwendung der Y-Combinator.

    atom konnte verworfen werden, wenn Sie definiert die car Betrieb auf Atome zurück NIL.

    Könnte man im Grunde McCarthys LISP-Maschine mit 7 von diesen 9 definiert primitive, aber man konnte angeblich definieren einer knapperen version, je nachdem, wie viel Unannehmlichkeiten, die Sie wollen, um zu zufügen auf sich selbst. Ich mag seine Maschine ziemlich gut, oder die vielen primitiven, die in den neueren Sprachen wie Clojure.

    InformationsquelleAutor der Antwort Isaac

  3. 13

    Der beste Weg, um wirklich wissen, dass das für Sie sicher ist, wenn Sie es umsetzen. Habe ich 3 Sommern zu erstellen Zozotez das ist ein McCarty-ish LISP läuft auf Brainfuck.

    Habe ich versucht herauszufinden, was ich brauchte, und ein forum findest du einen thread, der sagt Sie müssen nur die lambda. So können Sie eine ganze LISP im lambda-Kalkül ich Sie gerne. Ich fand es interessant, aber es ist kaum der Weg zu gehen, wenn Sie etwas wollen, schließlich hat Nebenwirkungen und funktioniert in der realen Welt.

    Für eine Turing-vollständige LISP, die ich verwendet Paul Grahams Erklärung der McCarthy-Papier und alles, was Sie wirklich brauchen, ist:

    • symbol-Bewertung
    • Besondere form zitieren
    • Besondere form wenn (oder cond)
    • Besondere form lambda (ähnlich zu zitieren)
    • Funktion eq
    • Funktion atom
    • Funktion cons
    • Funktion Auto
    • Funktion cdr
    • - Funktion-Versand (Liste-lambda)

    Thats, 10. Zusätzlich zu dieser, eine Umsetzung, die Sie testen können und nicht nur auf einem Zeichenbrett:

    • Funktion Lesen
    • Funktion schreiben

    Thats 12. In meinem Zozotez ich implemeted gesetzt und flambda (anonym macroes, wie lambda). Ich konnte ihn ernähren, eine Bibliothek, die Implementierung einer dynamischen gebunden lisp (Elisp, picoLisp) mit Ausnahme der Datei-I/O (da das zugrunde liegende BF unterstützt keine anderen als stdin/stdout).

    Ich jedem empfehlen, zu implementieren LISP1-interpreter in beiden LISP und (nicht LISP), um vollständig zu verstehen, wie eine Sprache implementiert ist. LISP hat eine sehr einfache syntax, so ist es ein guter Ausgangspunkt für einen parser. Ich arbeite aktuell an ein Schema-compiler geschrieben, im Schema mit verschiedenen Zielen (wie Stalin ist für den Gegner C), hoffentlich wird BF als einer von Ihnen.

    InformationsquelleAutor der Antwort Sylwester

  4. 8

    McCarthy verwendet sieben Operatoren zu definieren, die der original-Lisp: quoteatomeqcarcdrcons und cond. Dieser Artikel seine Schritte zurückverfolgt.

    InformationsquelleAutor der Antwort Vijay Mathew

  5. 6

    Diese faq Staaten:

    Es gibt keine einzelne "beste" minimalen Satz von primitiven; es hängt alles davon ab,
    die Umsetzung. Zum Beispiel, sogar etwas so einfaches wie die zahlen
    muss nicht primitiv, und kann dargestellt werden als Listen. Eine mögliche
    Satz von primitiven aufnehmen könnte, CAR, CDR und CONS für die manipulation von
    S-Ausdrücke, LESEN und DRUCKEN für die Eingabe/Ausgabe von S-Ausdrücke
    und APPLY und EVAL für den Mut eines Dolmetschers. Aber dann könnten Sie
    hinzufügen möchten LAMBDA für Funktionen, EQ für die Gleichstellung, für COND
    - Bedingungen, für die Zuordnung und DEFUN für Definitionen. ZITAT
    könnte in handliches kommen auch.

    Kommt von der School of Computer Science, Carnegie Melon website.

    InformationsquelleAutor der Antwort bennybdbc

  6. 1

    Paul Graham implementiert eval mit sieben.

    In der McCarthy-Micro Handbuch für LISP implementiert er mit eval zehn.

    InformationsquelleAutor der Antwort hawkeye

  7. 0

    Du brauchst nur ein x86 MOV - Anweisung.

    "Der M/o/Vfuscator (kurz 'o', klingt wie "mobfuscator") kompiliert Programme in "mov" - Anweisungen, und nur "mov" - Anweisungen. Arithmetik, Vergleiche, Sprünge, Funktionsaufrufe, und alles, was ein Programm muss ausgeführt werden durch mov-Operationen; es ist kein self-modifying code, keine transport-triggered-Berechnung, und keine andere form der nicht-mov Betrug".

    Aber im ernst, diese primitive wird nicht implementieren die Lisp-Maschine. Eine Maschine muss über Einrichtungen wie I/O, und die garbage collection. Nicht zu erwähnen, eine Funktion aufrufen Mechanismus! Okay, Sie haben sieben primitiven, die Funktionen. Wie funktioniert die Maschine, eine Funktion aufzurufen?

    Dem richtigen Verständnis von dem, was diese primitiven machen es möglich, dass Sie aussetzen der Befehlssatz eines Universelle Turing-Maschine. Weil diese Anweisungen sind "Lispy", durch die ein Abrutschen der Zunge (sprechen mit einem Lisp) wir heimlich nennen dies ein "Lisp-Maschine". "Universal" bedeutet, dass die Maschine programmierbar ist: mit einer Kombination von Anweisungen angewendet, um die Universelle Turing-Maschine können wir instanziieren alle Turing-Maschine. Aber so weit, all das ist ein rein mathematisches Konstrukt.

    Tatsächlich simulieren diese UTM—merke es körperlich, um ihn zu erkunden auf einem computer, wir brauchen eine Maschine, die nach einem Weg für uns, um tatsächlich Eingang jene Formen, die Sie erstellen, Turing-Maschinen, die aus Kombinationen von diesen sieben Lisp-Anweisungen. Und wir brauchen auch eine form der Ausgabe; die Maschine so zu mindestens in der Lage sein, uns zu sagen, "ja", "Nein" oder "Warte, ich bin noch läuft".

    In anderen Worten, der einzige Weg, diese sieben Anweisungen praktisch arbeiten, ist, wenn Sie gehostet sind, in einer größeren Maschine, die Umwelt.

    Beachten Sie auch, dass Graham die sieben primitiven haben keine explizite Unterstützung für zahlen, so dass Sie würde haben, Sie zu bauen aus-Funktionen ("Kirche Ziffern" - Technik). Keine Produktion Lisp-Implementierung hat so eine verrückte Sache.

    InformationsquelleAutor der Antwort Kaz

Schreibe einen Kommentar