McCarthys LISP von 1959
Anfang 1959 schrieb John McCarthy ein bahnbrechendes Papier, in dem nur neun primitive Funktionen definiert wurden, die zusammengenommen noch heute die Grundlage für alle LISP-ähnlichen Sprachen bilden. Das Papier ist hier digitalisiert erhältlich:
http://www-formal.stanford.edu/jmc/recursive.pdf
Ihre Aufgabe ist es voll einen Parser und Interpreter für McCarthys LISP umzusetzen genau wie im Jahr 1960 Papier beschrieben: Das heißt, die Funktionen QUOTE
, ATOM
, EQ
, CAR
, CDR
, CONS
, COND
, LAMBDA
, und LABEL
alle funktionsfähig sein sollten. Das Papier wird Vorrang vor diesem Aufforderungstext haben, wenn man die Richtigkeit der Antworten betrachtet, aber ich habe versucht, die folgenden neun Funktionen zusammenzufassen. Beachten Sie, dass die Sprache in GROSSBUCHSTABEN angegeben wird und keine Fehlerprüfung erforderlich ist. Alle Eingaben sollten als gültig angenommen werden.
Typen
- Es gibt nur zwei Arten in McCarthys LISP: Ein Atom und eine verknüpfte Liste, die rekursiv als Kopf definiert ist, bei der es sich um eine Liste oder ein Atom handeln kann, und eine Liste, an die der Kopf angehängt ist (Schwanz).
NIL
hat die besondere Eigenschaft, sowohl ein Atom als auch eine Liste zu sein. - Gemäß dem Papier bestehen Atomnamen nur aus Großbuchstaben, Zahlen und dem Leerzeichen, wobei Zeichenfolgen aus aufeinanderfolgenden Leerzeichen nur als ein Leerzeichen betrachtet und alle führenden und nachfolgenden Leerzeichen entfernt werden sollten. Beispiel äquivalente Atom Namen (ersetzen Strich mit Leerzeichen):
___ATOM__1__ = ATOM_1
. Beispiel nicht äquivalente Atomnamen:A_TOM_1 != ATOM_1
- Listen sind in Klammern angegeben, und
NIL
am Ende jeder Liste befindet sich eine implizite . Elemente in einer Liste werden durch Kommas und nicht wie in den meisten modernen Lisps durch Leerzeichen getrennt. So ist die Liste(ATOM 1, (ATOM 2))
wäre{[ATOM 1] -> {[ATOM 2] -> NIL} -> NIL}
.
QUOTE
:
- Nimmt ein Argument, das entweder ein Atom (einzelnes Element) oder eine verknüpfte Liste sein kann. Gibt das Argument genau zurück.
- Testfälle:
(QUOTE, ATOM 1) -> ATOM 1
(QUOTE, (ATOM 1, ATOM 2)) -> (ATOM 1, ATOM 2)
ATOM
:
- Nimmt ein Argument, das entweder ein Atom (einzelnes Element) oder eine verknüpfte Liste sein kann. Gibt
T
(true) zurück, wenn das Argument ein Atom ist, oderNIL
(false), wenn das Argument kein Atom ist. - Testfälle:
(ATOM, (QUOTE, ATOM 1)) -> T
(ATOM, (QUOTE, (ATOM 1, ATOM 2))) -> NIL
EQ
:
- Nimmt zwei Argumente, die Atome sein müssen (Verhalten ist undefiniert, wenn eines der Argumente kein Atom ist). Gibt
T
(true) zurück, wenn die beiden Atome äquivalent sind, oderNIL
(false), wenn dies nicht der Fall ist . - Testfälle:
(EQ, (QUOTE, ATOM 1), (QUOTE, ATOM 1)) -> T
(EQ, (QUOTE, ATOM 1), (QUOTE, ATOM 2)) -> NIL
CAR
:
- Nimmt ein Argument, das eine Liste sein muss (Verhalten ist undefiniert, wenn es keine Liste ist). Gibt das erste Atom (Kopf) dieser Liste zurück.
- Testfälle:
(CAR, (QUOTE, (ATOM 1, ATOM 2))) -> ATOM 1
CDR
:
- Nimmt ein Argument, das eine Liste sein muss (Verhalten ist undefiniert, wenn es keine Liste ist). Gibt jedes Atom außer dem ersten Atom der Liste zurück, dh den Schwanz. Beachten Sie, dass jede Liste implizit endet. Wenn Sie
NIL
alsoCDR
eine Liste mit nur einem Element ausführen, wird dies zurückgegebenNIL
. - Testfälle:
(CDR, (QUOTE, (ATOM 1, ATOM 2))) -> (ATOM 2)
(CDR, (QUOTE, (ATOM 1))) -> NIL
CONS
:
- Nimmt zwei Argumente an. Das erste kann ein Atom oder eine Liste sein, das zweite muss eine Liste oder sein
NIL
. Stellt das erste Argument vor das zweite Argument und gibt die neu erstellte Liste zurück. - Testfälle:
(CONS, (QUOTE, ATOM 1), (QUOTE, NIL)) -> (ATOM 1)
(CONS, (QUOTE, ATOM 1), (CONS, (QUOTE, ATOM 2), (QUOTE, NIL))) -> (ATOM 1, ATOM 2)
COND
:
- Dies ist die "if-else" -Anweisung von LISP. Nimmt eine Anzahl von Argumenten variabler Länge an, von denen jedes eine Liste mit genau 2 Länge sein muss. Werten Sie für jede Argumentliste nacheinander den ersten Ausdruck aus, und geben Sie den zugehörigen zweiten Ausdruck zurück, wenn dies der Fall ist (T), und beenden Sie die Funktion . Wenn der erste Term nicht wahr ist, fahren Sie mit dem nächsten Argument fort und testen Sie dessen Zustand usw., bis der erste wahre Zustand erreicht ist. Mindestens eine der Argumentbedingungen kann als wahr angenommen werden - wenn sie alle falsch sind, ist dies undefiniertes Verhalten. Auf Seite 4 finden Sie ein gutes Beispiel für das Verhalten dieser Funktion.
- Testfälle:
(COND, ((ATOM, (QUOTE, ATOM 1)), (QUOTE, 1)), ((ATOM, (QUOTE, (ATOM 1, ATOM 2))), (QUOTE, 2))) -> 1
(COND, ((ATOM, (QUOTE, (ATOM 1, ATOM 2))), (QUOTE, 2)), ((ATOM, (QUOTE, ATOM 1)), (QUOTE, 1))) -> 1
LAMBDA
:
- Definiert eine anonyme Funktion. Nimmt zwei Argumente an, das erste ist eine Liste von Atomen, die die Argumente für die Funktion darstellen, und das zweite ist ein beliebiger S-Ausdruck (der Funktionskörper), der normalerweise die Argumente verwendet.
- Testfälle:
- Eine anonyme "isNull" -Funktion definieren und verwenden:
((LAMBDA, (ATOM 1), (EQ, ATOM 1, (QUOTE, NIL))), (QUOTE, NIL)) -> T
((LAMBDA, (ATOM 1), (EQ, ATOM 1, (QUOTE, NIL))), (QUOTE, ATOM 1)) -> NIL
LABEL
:
- Gibt einer anonymen
LAMBDA
Funktion einen Namen , mit der diese Funktion auch rekursiv im Hauptteil von aufgerufen werden kannLAMBDA
. Nimmt zwei Argumente an, wobei das erste ein Label und das zweite dieLAMBDA
Funktion ist, an die das Label gebunden werden soll. Gibt den angegebenen Namen zurück. Der Gültigkeitsbereich allerLABEL
Namen ist global, und die Neudefinition von aLABEL
ist ein undefiniertes Verhalten. - Unterhaltsame Tatsache, es
LABEL
ist eigentlich nicht notwendig, rekursive Funktionen zu erstellen, da wir jetzt wissen,LAMBDA
dass sie mit einem 'Y-Combinator' verwendet werden können , um diese Aufgabe zu erfüllen, aber McCarthy war sich dieser Methode beim Schreiben des Originalpapiers nicht bewusst. Es macht das Schreiben von Programmen sowieso einfacher. - Testfälle:
(LABEL, SUBST, (LAMBDA, (X, Y, Z), (COND, ((ATOM, Z), (COND, ((EQ, Y, Z), X), ((QUOTE, T), Z))), ((QUOTE, T), (CONS, (SUBST, X, Y, (CAR, Z)), (SUBST, X, Y, (CDR, Z))))))) -> SUBST
- (nach dem Ausführen des oben)
(SUBST, (QUOTE, A), (QUOTE, B), (QUOTE, (A, B, C))) -> (A, A, C)
Um die SUBST
obige Funktion besser zu veranschaulichen, könnte sie als dieser Python-ähnliche Pseudocode dargestellt werden:
def substitute(x, y, z): # substitute all instances of y (an atom) with x (any sexp) in z
if isAtom(z):
if y == z:
return x
elif True:
return z
elif True:
return substitute(x,y,z[0]) + substitute(x,y,z[1:])
FINAL TEST CASE:
Wenn ich es richtig transkribiert habe, sollte Ihr Dolmetscher in der Lage sein, EVAL
mit diesem Code zu interpretieren :
(LABEL, CAAR, (LAMBDA, (X), (CAR, (CAR, X))))
(LABEL, CDDR, (LAMBDA, (X), (CDR, (CDR, X))))
(LABEL, CADR, (LAMBDA, (X), (CAR, (CDR, X))))
(LABEL, CDAR, (LAMBDA, (X), (CDR, (CAR, X))))
(LABEL, CADAR, (LAMBDA, (X), (CAR, (CDR, (CAR, X)))))
(LABEL, CADDR, (LAMBDA, (X), (CAR, (CDR, (CDR, X)))))
(LABEL, CADDAR, (LAMBDA, (X), (CAR, (CDR, (CDR, (CAR, X))))))
(LABEL, ASSOC, (LAMBDA, (X, Y), (COND, ((EQ, (CAAR, Y), X), (CADAR, Y)), ((QUOTE, T), (ASSOC, X, (CDR, Y))))))
(LABEL, AND, (LAMBDA, (X, Y), (COND, (X, (COND, (Y, (QUOTE, T)), ((QUOTE, T), (QUOTE, NIL)))), ((QUOTE, T), (QUOTE, NIL)))))
(LABEL, NOT, (LAMBDA, (X), (COND, (X, (QUOTE, NIL)), ((QUOTE, T), (QUOTE, T)))))
(LABEL, NULL, (LAMBDA, (X), (AND, (ATOM, X), (EQ, X, (QUOTE, NIL)))))
(LABEL, APPEND, (LAMBDA, (X, Y), (COND, ((NULL, X), Y), ((QUOTE, T), (CONS, (CAR, X), (APPEND, (CDR, X), Y))))))
(LABEL, LIST, (LAMBDA, (X, Y), (CONS, X, (CONS, Y, (QUOTE, NIL)))))
(LABEL, PAIR, (LAMBDA, (X, Y), (COND, ((AND, (NULL, X), (NULL, Y)), (QUOTE, NIL)), ((AND, (NOT, (ATOM, X)), (NOT, (ATOM, Y))), (CONS, (LIST, (CAR, X), (CAR, Y)), (PAIR, (CDR, X), (CDR, Y)))))))
(LABEL, EVAL, (LAMBDA, (E, A), (COND, ((ATOM, E), (ASSOC, E, A)), ((ATOM, (CAR, E)), (COND, ((EQ, (CAR, E), (QUOTE, QUOTE)), (CADR, E)), ((EQ, (CAR, E), (QUOTE, ATOM)), (ATOM, (EVAL, ((CADR, E), A)))), ((EQ, (CAR, E), (QUOTE, EQ)), (EQ, (EVAL, (CADR, E, A)), (EVAL, (CADDR, E, A)))), ((EQ, (CAR, E), (QUOTE, COND)), (EVCON, (CDR, E), A)), ((EQ, (CAR, E), (QUOTE, CAR)), (CAR, (EVAL, (CADR, E), A))), ((EQ, (CAR, E), (QUOTE, CDR)), (CDR, (EVAL, (CADR, E), A))), ((EQ, (CAR, E), (QUOTE, CONS)), (CONS, (EVAL, (CADR, E), A), (EVAL, (CADDR, E), A))), ((QUOTE, T), (EVAL, (CONS, (ASSOC, (CAR, E), A), (EVLIS, (CDR, E), A)), A)))), ((EQ, (CAAR, E), (QUOTE, LABEL)), (EVAL, (CONS, (CADDAR, E), (CDR, E)), (CONS, (CONS, (CADAR, E), (CONS, (CAR, E), (CONS, A, (QUOTE, NIL))))))), ((EQ, (CAAR, E), (QUOTE, LAMBDA)), (EVAL, (CADDAR, E), (APPEND, (PAIR, (CADAR, E), (EVLIS, (CDR, E), A)), A))))))
(LABEL, EVCON, (LAMBDA, (C, A), (COND, ((EVAL, (CAAR, C), A), (EVAL, (CADAR, C), A)), ((QUOTE, T), (EVCON, (CDR, C), A)))))
(LABEL, EVLIS, (LAMBDA, (M, A), (COND, ((NULL, M), (QUOTE, NIL)), ((QUOTE, T), (CONS, (EVAL, (CAR, M), A), (EVLIS, (CDR, M), A))))))
Nach dem Ausführen dieses Ungetüms sollte diese Zeile Folgendes zurückgeben (A, B, C)
:
(EVAL, (QUOTE, (CONS, X, (QUOTE, (B, C)))), (QUOTE, ((X, A), (Y, B))))
Um jedoch John McCarthy selbst auf Seite 16 zu zitieren, scheinen ihm die Zeichen auf seinem Computer ausgegangen zu sein:
Wenn mehr Zeichen auf dem Computer verfügbar wären, könnte dies erheblich verbessert werden ...
Daher ist diese Herausforderung mit Code-Golf gekennzeichnet und die kürzeste Antwort in Zeichen wird der Gewinner sein. Es gelten Standardlücken. Viel Glück!
Anmerkung zu String Evals : Ich verstehe, dass einige denken, dass es möglich sein könnte, diese Herausforderung zu gewinnen, indem sie Lisp verwenden und die Syntax an die Sprache des Hosts anpassen und dann einen String verwenden (eval)
. Ich bin nicht besonders davon überzeugt, dass dieser Ansatz vor allem bei den Regeln für die Benennung von Bezeichnern gewinnen wird, und selbst wenn ich der Meinung eval
wäre, dass das Verbieten von Zeichenfolgen in allen Sprachen ein subjektiver und rutschiger Anstieg wäre. Aber ich möchte die Leute nicht dafür bestrafen, dass sie diese Herausforderung auf die "richtige" Weise gemeistert haben, also kann ich zwei Gewinner für diese Herausforderung zulassen, einen in einer Lisp-ähnlichen Sprache und einen in einer Nicht-Lispy-Sprache, falls dies zu einem Problem wird .
quelle
((LAMBDA, (ATOM 1), (EQ, ATOM 1, (QUOTE, NIL))), (QUOTE, NIL)) -> NIL
wo die(QUOTE NIL)
am Ende ist die Eingabe, so sollte dies zurückkehrenT
?-> NIL
CONS
sagen Sie: "Hängt das erste Argument an das zweite Argument an und gibt die neu erstellte Liste zurück." In den Testfällen wird jedoch das zweite Argument an das erste Argument angehängt. Welches ist richtig?Antworten:
Python 3, 770 Bytes
Dies ist eine REPL für stdin / stdout. Erwartet, dass jede Zeile eine vollständige oder leere Anweisung ist.
eval
wird verwendet, um die Implementierung zu verkürzen, ist aber ansonsten für die Logik nicht erforderlich.quelle
SUBST
Beispiel ist (meines Wissens) als Testfall immer noch defekt. Eines derCOND
s erreicht das Ende, bevor es a findetT
.EVAL
(so angenehm überrascht, dass ich dieses beim ersten Versuch richtig verstanden habe!), Dass ich Ihnen jetzt das Kopfgeld und die akzeptierte Antwort erteilen werde!R(E(P(l)
Setup ;-)repr
, E =eval
, P =parse
, l =line
.