Die Herausforderung besteht darin, einen Interpreter für die untypisierte Lambda-Rechnung mit möglichst wenigen Zeichen zu schreiben . Wir definieren den untypisierten Lambda-Kalkül wie folgt:
Syntax
Es gibt die folgenden drei Arten von Ausdrücken:
Ein Lambda-Ausdruck hat die Form,
(λ x. e)
bei der esx
sich um einen beliebigen legalen Variablennamen und einene
beliebigen legalen Ausdruck handeln kann. Hierx
heißt der Parameter unde
heißt der Funktionskörper.Der Einfachheit halber fügen wir die weitere Einschränkung hinzu, dass es keine Variable mit demselben Namen geben darf, wie
x
derzeit im Gültigkeitsbereich. Eine Variable beginnt im Gültigkeitsbereich zu sein, wenn ihr Name zwischen(λ
und erscheint, und.
endet am entsprechenden Gültigkeitsbereich)
.- Funktionsanwendung hat die Form
(f a)
wof
unda
sind gesetzliche Ausdrücke. Hierf
heißt die Funktion unda
heißt das Argument. - Eine Variable hat die Form,
x
bei derx
es sich um einen zulässigen Variablennamen handelt.
Semantik
Eine Funktion wird angewendet, indem jedes Vorkommen des Parameters im Funktionskörper durch sein Argument ersetzt wird. Formal ein Ausdruck der Form ((λ x. e) a)
, in dem x
ein Name ist variabel und e
und a
sind Ausdrücke, bewertet (oder reduziert) auf den Ausdruck , e'
wo e'
das Ergebnis des Ersetzens jedes Auftreten x
in e
mit a
.
Eine Normalform ist ein Ausdruck, der nicht weiter ausgewertet werden kann.
Die Herausforderung
Ihre Mission ist es, einen Interpreter zu schreiben, der als Eingabe einen Ausdruck des untypisierten Lambda-Kalküls ohne freie Variablen verwendet und als Ausgabe die Normalform des Ausdrucks (oder einen Ausdruck, der Alpha-Kongruenz zu ihm aufweist) erzeugt. . Wenn der Ausdruck keine normale Form hat oder kein gültiger Ausdruck ist, ist das Verhalten undefiniert.
Die Lösung mit der geringsten Anzahl von Zeichen gewinnt.
Ein paar Notizen:
- Die Eingabe kann entweder von stdin oder von einem Dateinamen als Befehlszeilenargument gelesen werden (Sie müssen nur das eine oder das andere implementieren - nicht beide). Die Ausgabe erfolgt nach stdout.
- Alternativ können Sie eine Funktion definieren, die die Eingabe als Zeichenfolge verwendet und die Ausgabe als Zeichenfolge zurückgibt.
- Wenn für Sie Nicht-ASCII-Zeichen problematisch sind, können Sie
\
anstelle von λ den Backslash ( ) verwenden. - Wir zählen die Anzahl der Zeichen, nicht die Bytes. Selbst wenn Ihre Quelldatei als Unicode kodiert ist, zählt λ als ein Zeichen.
- Zulässige Variablennamen bestehen aus einem oder mehreren Kleinbuchstaben, dh Zeichen zwischen a und z (alphanumerische Namen, Großbuchstaben oder nicht-lateinische Buchstaben müssen nicht unterstützt werden - dies macht Ihre Lösung jedoch nicht ungültig).
- In Bezug auf diese Herausforderung sind keine Klammern optional. Jeder Lambda-Ausdruck und jede Funktionsanwendung wird von genau einem Klammerpaar umgeben. Kein Variablenname wird in Klammern gesetzt.
- Syntaktischer Zucker wie das Schreiben
(λ x y. e)
für(λ x. (λ y. e))
muss nicht unterstützt werden. - Wenn eine Rekursionstiefe von mehr als 100 erforderlich ist, um eine Funktion auszuwerten, ist das Verhalten undefiniert. Das sollte mehr als niedrig genug sein, um ohne Optimierung in allen Sprachen implementiert zu werden und dennoch groß genug, um die meisten Ausdrücke ausführen zu können.
- Sie können auch davon ausgehen, dass der Abstand wie in den Beispielen ist, dh keine Leerzeichen am Anfang und Ende der Eingabe oder vor einem
λ
oder.
genau einem Leerzeichen nach einem.
und zwischen einer Funktion und ihrem Argument und nach einemλ
.
Sample Input und Output
Eingang:
((λ x. x) (λ y. (λ z. z)))
Ausgabe:
(λ y. (λ z. z))
Eingang:
(λ x. ((λ y. y) x))
Ausgabe:
(λ x. x)
Eingang:
((λ x. (λ y. x)) (λ a. a))
Ausgabe:
(λ y. (λ a. a))
Eingang:
(((λ x. (λ y. x)) (λ a. a)) (λ b. b))
Ausgabe:
(λ a. a)
Eingang:
((λ x. (λ y. y)) (λ a. a))
Ausgabe:
(λ y. y)
Eingang:
(((λ x. (λ y. y)) (λ a. a)) (λ b. b))
Ausgabe:
(λ b. b)
Eingang:
((λx. (x x)) (λx. (x x)))
Ausgabe: alles (Dies ist ein Beispiel für einen Ausdruck ohne normale Form)
Eingang:
(((λ x. (λ y. x)) (λ a. a)) ((λx. (x x)) (λx. (x x))))
Ausgabe:
(λ a. a)
(Dies ist ein Beispiel für einen Ausdruck, der sich nicht normalisiert, wenn Sie die Argumente vor dem Funktionsaufruf auswerten, und leider ein Beispiel, für das mein Lösungsversuch fehlschlägt.)Eingang:
((λ a. (λ b. (a (a (a b))))) (λ c. (λ d. (c (c d)))))
Ausgabe:
`(λ a. (λ b. (a (a (a (a (a (a (a (a b))))))))))
Dies berechnet 2 ^ 3 in Zahlen der Kirche.
(\y. a)
.Antworten:
Neueste:
Ich habe es auf 644 Zeichen reduziert und Teile von cEll in cOpy und Par zerlegt. Zwischengespeicherte Aufrufe von cell und cdr in temporäre lokale Variablen und Verschieben dieser lokalen Variablen in Globals in "Terminal" -Funktionen (dh nicht rekursiven Funktionen). Außerdem sind Dezimalkonstanten kürzer als Zeichenliterale und dieses fiese Geschäft ...
... identifiziert Kleinbuchstaben korrekt (unter der Annahme von ASCII), akzeptiert aber auch alle von `{|} ~. (Dieselbe Beobachtung zu ASCII wird in diesem hervorragenden Video zu UTF-8 gemacht .)
Et viola: |
Vorhin:
Kann ich ein paar Stimmen für Mühe bekommen? Ich arbeite seit einer Woche Tag und Nacht daran. Ich habe das Originalpapier von McCarthy ausgegraben und war von einem Fehler im Papier selbst geplagt, bis ich den Anhang zu Paul Grahams The Roots of Lisp gelesen habe . Ich war so abgelenkt, dass ich mich aus meinem Haus ausgesperrt und dann völlig vergessen hatte, bis ich in dieser Nacht um 12:30 Uhr wieder nach Hause kam (ein wenig zu spät, um den Hausverwalter anzurufen, der weit draußen in der Grafschaft wohnt), und das Geld ausgeben musste Nacht bei meiner Großmutter (Hacken weg, bis mein Laptop Akku trocken war).
Und nach alledem ist es noch lange nicht so weit bis zum Sieger!
Ich bin mir nicht sicher, wie ich das verkürzen soll. und ich habe alle schmutzigen Tricks benutzt, die mir einfallen! Vielleicht geht es nicht in C.
Mit etwas Großzügigkeit beim Zählen (der erste Block nimmt eine Zeichenfolge und druckt das Ergebnis aus) sind es
778770709694 Zeichen. Aber um es eigenständig zu machen, muss es diesensbrk
Aufruf haben. Und um kompliziertere Ausdrücke verarbeiten zu können, ist auch dersignal
Handler erforderlich . Und natürlich kann es nicht mit einem Code, der versucht zu verwenden, zu einem Modul gemacht werdenmalloc
.Also leider ist es hier:
Hier ist der Block kurz vor den endgültigen Reduzierungen. Die Tricks hier sind ganzzahlige Cursor anstelle von Zeigern (unter Ausnutzung des 'impliziten int'-Verhaltens) und die Verwendung von' Arbeitsspeicher ': Dies
char*n
ist der' neue 'oder' nächste 'Zeiger in den freien Raum. Aber manchmal schreibe ich einen String in den Speicher, rufe dann strlen auf und erhöhe n; effektiv Speicher verwenden und dann zuweisen, nachdem die Größe einfacher zu berechnen ist. Sie können sehen, dass dies praktisch direkt aus dem McCarthy-Artikel hervorgeht, mit Ausnahme dercell()
Schnittstellen zwischen den Funktionen und der Zeichenfolgendarstellung von Daten.quelle
sprintf(n,...);n+=strlen(n)+1;
ist besser, alsn+=sprintf(n,...)+1;
die Array-Syntax zu invertieren,x[m]
anstattm[x]
mir zu erlauben, alle Indirektionen durch ein 'postfix'-Makro zu ersetzen#define M [m]
...x M
das 1 Zeichen spart und einen "freien" Zeilenumbruch ergibt, da Leerzeichen zum Trennen der Token erforderlich sind.// um ...
durchläuft die Zeichenfolge und zählt die runden Klammern, bis er die übereinstimmende enge Klammer auf der richtigen Verschachtelungsebene findet.Binäre Lambda-Rechnung 186
Das im Hex-Dump unten gezeigte Programm
akzeptiert nicht ganz das von Ihnen vorgeschlagene Format. Es wird vielmehr ein Lambda-Term im binären Lambda-Kalkül-Format (BLC) erwartet. In der normalen Formreduktion wird jedoch jeder einzelne Schritt mit minimalen Klammern angezeigt.
Beispiel: Berechnung von 2 ^ 3 in Zahlen der Kirche
Speichern Sie den obigen Hex-Dump mit xxd -r> symbolic.Blc
Besorgen Sie sich einen BLC-Interpreter von http://tromp.github.io/cl/uni.c
Da der Hexdump eher unlesbar ist, handelt es sich hier um eine "disassemblierte" Version
Ersetzen Sie 00 (Lambda) durch \ und 01 (Anwendung) durch @ Jetzt ist es fast so lesbar wie Brainfuck :-)
Siehe auch http://www.ioccc.org/2012/tromp/hint.html
quelle
Haskell,
342323317305 ZeichenZum jetzigen Zeitpunkt ist dies die einzige Lösung, die ((λ f. (Λ x. (Fx))) (λ y. (Λ x. Y)) zum korrekten Ergebnis (λ x. (Λ z. x)) und nicht (λ x. (λ x. x)). Die korrekte Implementierung des Lambda-Kalküls erfordert eine Substitution ohne Capture , auch wenn durch die Vereinfachung dieses Problems garantiert wird, dass keine Variable eine andere Variable in ihrem Gültigkeitsbereich abschattet. (Mein Programm funktioniert auch ohne diese Garantie.)
Anmerkungen:
Ungolfed-Version mit Dokumentation.
quelle
Python -
321320Hier ist mein (fester) Versuch:
quelle
Ruby 254 Zeichen
Es kann gerne verwendet werden
Die Lösung ist noch nicht voll ausgereift, aber schon fast unlesbar.
quelle
Bearbeiten: Überprüfen Sie meine Antwort unten für 250 unter reinem JavaScript.
2852243 Zeichen mit LiveScript (Kein Regex! Nicht voll ausgereift - könnte verbessert werden)Prüfung:
Welches ist
3^2=9
, wie auf OP angegeben.Wenn jemand neugierig ist, ist hier eine erweiterte Version mit einigen Kommentaren:
quelle
Waterhouse Arc - 140 Zeichen
quelle
C 1039 Bytes
Variablen können als Eingabe mit Kleinbuchstaben [von a..z] eingegeben werden. Das System kann Variablen mit Großbuchstaben [von A..Z] generieren, wenn dies in der Ausgabe erforderlich ist. Nehmen Sie eine ASCII-Zeichenkonfiguration an.
quelle
Haskell 456 C
Es kann viel kürzer sein, wenn die Lazy-Evaluierungsfunktion von Haskell vollständig genutzt wird. Leider weiß ich nicht, wie ich es machen soll.
Außerdem werden im Analyseschritt viele Zeichen verschwendet.
Ungolfed-Version
quelle
Erhält 231 mit JavaScript / ohne Regex
Erhält 2-Elemente-Arrays.
1
steht fürλ
und 2 steht für eine Bruijn-Indexvariable.Prüfung:
quelle
Python: 1266 Zeichen (gemessen mit wc)
Bei weitem nicht die kürzeste, aber es behandelt die Alpha-Umbenennung und alle in OPs Post aufgeführten Beispiele korrekt.
quelle
except NameError
mit nur ersetzenexcept
? (3) Funktionsnamen mit zwei Zeichen können in Namen mit einem Zeichen umbenannt werden. (4) Es gibt einige Stellen, an denen Sie Aufgaben haben, die mit Leerzeichen versehen sind=
. (5)if t[0]=='c'
kann durch ersetzt werdenif'c'==t[0]
.C ++ (gcc) ,
782766758731 BytesProbieren Sie es online!
Die Grundidee hierbei ist, dass der Code eine interne Darstellung verwendet, die auf der Idee von de Bruijn-Indizes basiert - mit der Ausnahme, dass ich die Indizes umdrehe, um die Lambda-Tiefe der Bindung der referenzierten Variablen anzuzeigen. Im Code:
E::t
stellt den Typ eines Knotens dar - 0 für einen variablen Blattknoten, 1 für einen Lambda-Knoten und 2 für einen Funktionsanwendungsknoten. (So gewählt, dass es mit der Arität des Knotens übereinstimmt, was zufällig möglich ist.) DannE::l
undE::r
sind die Kinder (nurE::l
für einen Lambda-Knoten), undE::i
ist der Lambda-Tiefenindex für einen variablen Blattknoten.E::E(E&o,int d,int e)
klont einen Teilausdruck, der sich ursprünglich in Lambda-Tiefe befand,d
um ihn an einer neuen Position in Lambda-Tiefe einzufügend+e
. Dabei werden Variablen in Lambda-Tiefe wenigerd
beibehalten als Variablen in Lambda-Tiefe mindestensd
um inkrementierte
.E::s
führt eine Ersetzung des Unterausdrucksv
in eine Variablennummerd
durch,*this
während Variablennummern dekrementiert werden, die größer sind alsd
(unde
ist ein internes Detail, das das Lambda-Tiefeninkrement nachverfolgt, wenn es aufgerufen werden mussE::c
).E::R
Sucht nach einer einzelnen Beta-Reduktion, die ausgeführt werden soll, und bevorzugt Instanzen ganz oben oder ganz links gemäß einer Suche in der AST vor der Bestellung. Es wird ein Wert ungleich Null zurückgegeben, wenn eine Leistungsreduzierung gefunden wurde, oder Null, wenn keine gefunden wurde.E::u
ist eineto_string
Typoperation, die eine "vom Menschen lesbare" Zeichenfolge unter Verwendung von synthetischen Namen für die Variablen wiederherstellt. (Beachten Sie, dass dieV
Helferfunktion aufgrund des geringen Golfspiels nur Namen generiert, diea
durch enthalteni
.)E::E(int d, std::map<std::string, int> m, char*&s)
parst eine Eingabezeichenfolges
in einen Ausdruck AST auf der Grundlage einer Zuordnungm
der aktuell gebundenen Variablennamen zu lambda-tiefen Indizes.f
ist die Hauptfunktion zur Beantwortung der Frage.(Wie Sie am TIO-Link sehen können, verarbeitet der Code Variablennamen mit mehreren Zeichen und erhält auch die richtige Antwort von
(\ a. (\ b. a))
for((\ f. (\ x. (f x))) (\ y. (\ x. y)))
. Es kommt auch nur so vor, dass der Parsing-Code das Spiegeln von Variablen ohne zusätzliche Kosten verarbeiten kann.)-16 Bytes, teils aufgrund einer Idee von ceilingcat (die ich mir auch selbst ausgedacht hatte), teils aufgrund des Wechsels
E*a=new E;
zuE&a=*new E;
und dann des Wechselsa->
zua.
-8 weitere Bytes aufgrund eines weiteren Kommentars von ceilingcat (Zuweisung
a.t
von ternary ausklammern )-27 Bytes aus der Konvertierung von Parser und Klon in Konstruktoren von
E
quelle
C 637 Bytes
Diese Version verwendet keine Hilfsvariablen (daher folgt dies nicht zu 100% dem, was die Lambda-Rechnung sagt ... wie viele andere hier ...). Jede Variable muss 1 Zeichen lang sein (wie einige andere hier). Testcode:
Ergebnisse:
Dies ist der Semi-Ungolf:
quelle