Lisp- Programmierer rühmen sich, dass Lisp eine mächtige Sprache ist, die aus einer sehr kleinen Menge primitiver Operationen aufgebaut werden kann . Lassen Sie uns diese Idee verwirklichen, indem wir einen Dolmetscher für einen Dialekt namens Golf spielen tinylisp
.
Sprachspezifikation
In dieser Spezifikation kann jede Bedingung, deren Ergebnis als "undefiniert" beschrieben wird, irgendetwas in Ihrem Interpreter bewirken: abstürzen, unbemerkt fehlschlagen, zufälliges Gobbldegook erzeugen oder wie erwartet arbeiten. Eine Referenzimplementierung in Python 3 finden Sie hier .
Syntax
Token in tinylisp sind (
, )
oder eine beliebige Zeichenfolge aus einem oder mehreren druckbaren ASCII-Zeichen mit Ausnahme von Klammern oder Leerzeichen. (Dh der folgende reguläre Ausdruck:. [()]|[^() ]+
) Jedes Token, das ausschließlich aus Ziffern besteht, ist ein Ganzzahlliteral. (Führende Nullen sind in Ordnung.) Alle Token , das nicht-Ziffern enthält ein Symbol, auch numerische aussehenden Beispiele mögen 123abc
, 3.14
und -10
. Alle Leerzeichen (einschließlich mindestens der ASCII-Zeichen 32 und 10) werden ignoriert, mit Ausnahme der Tatsache, dass sie Token trennen.
Ein tinylisp-Programm besteht aus einer Reihe von Ausdrücken. Jeder Ausdruck ist entweder eine Ganzzahl, ein Symbol oder ein S-Ausdruck (Liste). Listen bestehen aus null oder mehr Ausdrücken in Klammern. Zwischen den Elementen wird kein Trennzeichen verwendet. Hier sind Beispiele für Ausdrücke:
4
tinylisp!!
()
(c b a)
(q ((1 2)(3 4)))
Ungeformte Ausdrücke (insbesondere Ausdrücke mit nicht übereinstimmenden Klammern) führen zu undefiniertem Verhalten. (Die Referenzimplementierung schließt offene Parens automatisch und beendet das Parsen für nicht übereinstimmende nahe Parens.)
Datentypen
Die Datentypen von tinylisp sind Ganzzahlen, Symbole und Listen. Eingebaute Funktionen und Makros können auch als Typ betrachtet werden, obwohl ihr Ausgabeformat undefiniert ist. Eine Liste kann beliebig viele Werte eines beliebigen Typs enthalten und beliebig tief verschachtelt sein. Ganzzahlen müssen mindestens von -2 ^ 31 bis 2 ^ 31-1 unterstützt werden.
Die leere Liste ()
- auch als Null bezeichnet - und die Ganzzahl 0
sind die einzigen Werte, die als logisch falsch betrachtet werden. Alle anderen Ganzzahlen, nicht leeren Listen, eingebauten Werte und alle Symbole sind logisch wahr.
Auswertung
Ausdrücke in einem Programm werden in der angegebenen Reihenfolge ausgewertet und die Ergebnisse an stdout gesendet (mehr zur Ausgabeformatierung später).
- Ein ganzzahliges Literal wird zu sich selbst ausgewertet.
- Die leere Liste
()
wertet sich selbst aus. - Eine Liste mit einem oder mehreren Elementen wertet das erste Element aus, behandelt es als Funktion oder Makro und ruft es mit den verbleibenden Elementen als Argumente auf. Wenn das Element keine Funktion / kein Makro ist, ist das Verhalten undefiniert.
- Ein Symbol wird als Name ausgewertet und gibt den Wert an, der in der aktuellen Funktion an diesen Namen gebunden ist. Wenn der Name in der aktuellen Funktion nicht definiert ist, wird er im globalen Bereich als an ihn gebundener Wert ausgewertet. Wenn der Name im aktuellen oder globalen Bereich nicht definiert ist, ist das Ergebnis undefiniert (die Referenzimplementierung gibt eine Fehlermeldung aus und gibt null zurück).
Eingebaute Funktionen und Makros
Es gibt sieben integrierte Funktionen in tinylisp. Eine Funktion wertet jedes ihrer Argumente aus, bevor sie eine Operation auf sie anwendet und das Ergebnis zurückgibt.
c
- Konsumentenliste. Nimmt zwei Argumente, einen Wert und eine Liste, und gibt eine neue Liste zurück, die durch Hinzufügen des Werts am Anfang der Liste erhalten wird.h
- Kopf ( Auto , in Lisp-Terminologie). Nimmt eine Liste und gibt das erste Element in der Liste zurück, oder nil, wenn nil angegeben wird.t
- tail ( cdr , in der Lisp-Terminologie). Nimmt eine Liste und gibt eine neue Liste zurück, die alle Elemente außer dem ersten enthält, oder nil, wenn nil angegeben wird.s
- subtrahieren. Nimmt zwei ganze Zahlen und gibt die erste minus die zweite zurück.l
- weniger als. Nimmt zwei ganze Zahlen; Gibt 1 zurück, wenn der erste kleiner als der zweite ist, andernfalls 0.e
- gleich. Nimmt zwei Werte desselben Typs (beide Ganzzahlen, beide Listen oder beide Symbole); Gibt 1 zurück, wenn die beiden gleich sind (oder in jedem Element identisch sind), andernfalls 0. Das Testen von Builtins auf Gleichheit ist nicht definiert (Referenzimplementierung funktioniert wie erwartet).v
- eval. Nimmt eine Liste, eine Ganzzahl oder ein Symbol, die einen Ausdruck darstellen, und wertet ihn aus. Zum Beispiel(v (q (c a b)))
ist das Tun dasselbe wie das Tun(c a b)
;(v 1)
gibt1
.
"Wert" umfasst hier eine Liste, eine Ganzzahl, ein Symbol oder eine integrierte Funktion, sofern nicht anders angegeben. Wenn eine Funktion als typenspezifisch aufgeführt ist, ist die Übergabe unterschiedlicher Typen undefiniertes Verhalten, ebenso wie die Übergabe der falschen Anzahl von Argumenten (die Referenzimplementierung stürzt im Allgemeinen ab).
Es gibt drei eingebaute Makros in tinylisp. Ein Makro wertet im Gegensatz zu einer Funktion seine Argumente nicht aus, bevor Operationen auf sie angewendet werden.
q
- Zitat. Nimmt einen Ausdruck und gibt ihn ohne Bewertung zurück. Das Auswerten(1 2 3)
gibt beispielsweise einen Fehler aus, weil versucht wird,1
eine Funktion oder ein Makro aufzurufen ,(q (1 2 3))
die Liste jedoch zurückgegeben wird(1 2 3)
. Das Auswertena
gibt den Wert an, der an den Namen gebunden ista
, aber(q a)
gibt den Namen selbst an.i
- ob. Es werden drei Ausdrücke verwendet: eine Bedingung, ein iftrue-Ausdruck und ein iffalse-Ausdruck. Wertet zuerst die Bedingung aus. Wenn das Ergebnis falsch (0
oder null) ist, wird der iffalse-Ausdruck ausgewertet und zurückgegeben. Andernfalls wird der iftrue-Ausdruck ausgewertet und zurückgegeben. Beachten Sie, dass der Ausdruck, der nicht zurückgegeben wird, niemals ausgewertet wird.d
- def. Nimmt ein Symbol und einen Ausdruck. Wertet den Ausdruck aus und bindet ihn an das angegebene Symbol, das im globalen Bereich als Name behandelt wird. Anschließend wird das Symbol zurückgegeben. Der Versuch, einen Namen neu zu definieren, sollte fehlschlagen (unbeaufsichtigt, mit einer Meldung oder durch Absturz; die Referenzimplementierung zeigt eine Fehlermeldung an). Hinweis: Es ist nicht erforderlich, den Namen vor der Übergabe in Anführungszeichen zu setzend
. Es ist jedoch erforderlich, den Ausdruck in Anführungszeichen zu setzen, wenn es sich um eine Liste oder ein Symbol handelt, das nicht ausgewertet werden soll, z(d x (q (1 2 3)))
.
Die Übergabe der falschen Anzahl von Argumenten an ein Makro ist ein undefiniertes Verhalten (Absturz der Referenzimplementierung). Übergeben von etwas, das kein Symbol ist, als erstes Argument für d
undefiniertes Verhalten (die Referenzimplementierung gibt keinen Fehler aus, aber der Wert kann später nicht referenziert werden).
Benutzerdefinierte Funktionen und Makros
Ausgehend von diesen zehn integrierten Funktionen kann die Sprache durch die Erstellung neuer Funktionen und Makros erweitert werden. Diese haben keinen dedizierten Datentyp. Es handelt sich lediglich um Listen mit einer bestimmten Struktur:
- Eine Funktion ist eine Liste von zwei Elementen. Der erste ist entweder eine Liste mit einem oder mehreren Parameternamen oder ein einzelner Name, der eine Liste aller an die Funktion übergebenen Argumente erhält (wodurch Funktionen mit variabler Arität möglich sind). Der zweite ist ein Ausdruck, der der Funktionskörper ist.
- Ein Makro ist dasselbe wie eine Funktion, enthält jedoch nil vor dem oder den Parameternamen und ist daher eine Liste mit drei Elementen. (Der Versuch, Listen mit drei Elementen aufzurufen, die nicht mit nil beginnen, ist undefiniert. Die Referenzimplementierung ignoriert das erste Argument und behandelt sie auch als Makros.)
Der folgende Ausdruck ist beispielsweise eine Funktion, die zwei Ganzzahlen hinzufügt:
(q List must be quoted to prevent evaluation
(
(x y) Parameter names
(s x (s 0 y)) Expression (in infix, x - (0 - y))
)
)
Und ein Makro, das eine beliebige Anzahl von Argumenten akzeptiert und das erste auswertet und zurückgibt:
(q
(
()
args
(v (h args))
)
)
Funktionen und Makros können direkt aufgerufen, über Namen gebunden d
und an andere Funktionen oder Makros übergeben werden.
Da Funktionskörper zur Definitionszeit nicht ausgeführt werden, können rekursive Funktionen einfach definiert werden:
(d len
(q (
(list)
(i list If list is nonempty
(s 1 (s 0 (len (t list)))) 1 - (0 - len(tail(list)))
0 else 0
)
))
)
Beachten Sie jedoch, dass die obige Methode nicht geeignet ist, um eine Längenfunktion zu definieren, da sie nicht verwendet wird ...
Endanruf-Rekursion
Die Rückrufrekursion ist ein wichtiges Konzept in Lisp. Es implementiert bestimmte Arten von Rekursionen als Schleifen, wodurch der Aufrufstapel klein bleibt. Ihr tinylisp-Interpreter muss die korrekte Tail-Call-Rekursion implementieren!
- Wenn der Rückgabeausdruck einer benutzerdefinierten Funktion oder eines benutzerdefinierten Makros ein Aufruf einer anderen benutzerdefinierten Funktion oder eines anderen benutzerdefinierten Makros ist, darf Ihr Interpreter zur Auswertung dieses Aufrufs keine Rekursion verwenden. Stattdessen müssen die aktuelle Funktion und die aktuellen Argumente durch die neue Funktion und die neuen Argumente und die neue Schleife ersetzt werden, bis die Aufrufkette aufgelöst ist.
- Wenn der Rückgabeausdruck einer benutzerdefinierten Funktion oder eines benutzerdefinierten Makros ein Aufruf von ist
i
, werten Sie den ausgewählten Zweig nicht sofort aus. Überprüfen Sie stattdessen, ob es sich um einen Aufruf einer anderen benutzerdefinierten Funktion oder eines anderen benutzerdefinierten Makros handelt. Wenn ja, tauschen Sie die Funktion und die Argumente wie oben aus. Dies gilt für beliebig tief verschachtelte Vorkommen voni
.
Die Schwanzrekursion muss sowohl für die direkte Rekursion (eine Funktion ruft sich selbst auf) als auch für die indirekte Rekursion (Funktion a
ruft Funktion auf, b
die [etc] aufruft, die Funktion aufruft) funktionieren a
.
Eine rekursive Längenfunktion (mit einer Hilfsfunktion len*
):
(d len*
(q (
(list accum)
(i list
(len*
(t list)
(s 1 (s 0 accum))
)
accum
)
))
)
(d len
(q (
(list)
(len* list 0)
))
)
Diese Implementierung funktioniert für beliebig große Listen, die nur durch die maximale Ganzzahlgröße begrenzt sind.
Umfang
Funktionsparameter sind lokale Variablen (eigentlich Konstanten, da sie nicht geändert werden können). Sie befinden sich im Gültigkeitsbereich, während der Hauptteil des Aufrufs dieser Funktion ausgeführt wird, und außerhalb des Gültigkeitsbereichs, wenn tiefere Aufrufe ausgeführt werden und nachdem die Funktion zurückgegeben wurde. Sie können global definierte Namen "schattieren", wodurch der globale Name vorübergehend nicht verfügbar wird. Der folgende Code gibt beispielsweise 5 und nicht 41 zurück:
(d x 42)
(d f
(q (
(x)
(s x 1)
))
)
(f 6)
Der folgende Code gibt jedoch 41 zurück, da x
auf Aufrufebene 1 von Aufrufebene 2 aus nicht zugegriffen werden kann:
(d x 42)
(d f
(q (
(x)
(g 15)
))
)
(d g
(q (
(y)
(s x 1)
))
)
(f 6)
Die einzigen Namen, die zu einem bestimmten Zeitpunkt im Geltungsbereich sind, sind 1) die lokalen Namen der aktuell ausgeführten Funktion (falls vorhanden) und 2) globale Namen.
Anforderungen für die Vorlage
Ein- und Ausgabe
Ihr Interpreter liest das Programm möglicherweise aus stdin oder aus einer Datei, die über stdin oder ein Befehlszeilenargument angegeben wurde. Nachdem jeder Ausdruck ausgewertet wurde, sollte er das Ergebnis dieses Ausdrucks mit einer nachgestellten Newline an stdout ausgeben.
- Ganzzahlen sollten in der natürlichsten Darstellung Ihrer Implementierungssprache ausgegeben werden. Es können negative ganze Zahlen mit führenden Minuszeichen ausgegeben werden.
- Symbole sollten als Zeichenfolgen ohne umgebende Anführungszeichen oder Escapezeichen ausgegeben werden .
- Listen sollten mit allen durch Leerzeichen getrennten und in Klammern gesetzten Elementen ausgegeben werden. Ein Leerzeichen in den Klammern ist optional
(1 2 3)
und kann( 1 2 3 )
in beiden Formaten verwendet werden. - Die Ausgabe von integrierten Funktionen und Makros ist undefiniertes Verhalten. (Die Referenzinterpretation zeigt sie als
<built-in function>
.)
Andere
Der Referenzinterpreter enthält eine REPL-Umgebung und die Möglichkeit, tinylisp-Module aus anderen Dateien zu laden. Diese werden zur Vereinfachung bereitgestellt und sind für diese Herausforderung nicht erforderlich.
Testfälle
Die Testfälle sind in mehrere Gruppen unterteilt, so dass Sie einfachere testen können, bevor Sie sich mit komplexeren befassen. Sie funktionieren jedoch auch einwandfrei, wenn Sie sie alle in einer Datei zusammen ablegen. Vergessen Sie jedoch nicht, die Überschriften und die erwartete Ausgabe zu entfernen, bevor Sie sie ausführen.
Wenn Sie die Tail-Call-Rekursion ordnungsgemäß implementiert haben, wird der abschließende (mehrteilige) Testfall zurückgegeben, ohne dass ein Stapelüberlauf verursacht wird. Die Referenzimplementierung berechnet es in ungefähr sechs Sekunden auf meinem Laptop.
quelle
-1
, kann ich dennoch den Wert -1 generieren(s 0 1)
.F
sind in function nicht verfügbar,G
wenn sieF
aufgerufen werdenG
(wie bei dynamischem Scoping), aber sie sind auch nicht verfügbar,H
wennH
eine verschachtelte Funktion in function definiert istF
(wie bei lexikalischem Scoping) - siehe Testfall 5. So nennen Sie es "lexikalisch" "könnte irreführend sein.Antworten:
Python 2,
685675660657646642640 BytesLiest die Eingabe von STDIN und schreibt die Ausgabe nach STDOUT.
Obwohl dies nicht unbedingt erforderlich ist, unterstützt der Interpreter Nullfunktionen und Makros und optimiert die durchgeführten Tail Calls
v
.Erläuterung
Parsing
Um die Eingabe zu analysieren, umgeben wir zuerst jedes Vorkommen von
(
und)
mit Leerzeichen und teilen die resultierende Zeichenfolge in Wörter auf. Dies gibt uns die Liste der Token. Wir pflegen einen AusdrucksstapelE
, der anfangs leer ist. Wir scannen die Token in der Reihenfolge:(
, schieben wir eine leere Liste oben in den Ausdrucksstapel.)
, platzieren wir den Wert oben im Ausdrucksstapel und hängen ihn an die Liste an, die zuvor darunter im Stapel war.Wenn
)
der Ausdrucksstapel beim Verarbeiten eines normalen Tokens oder nach dem Entfernen eines Ausdrucks aus dem Stapel aufgrund von leer ist, befindet sich der Ausdruck auf der obersten Ebene, und wir bewerten den Wert, den wir sonst angehängt hätten, mithilfe vonV()
und Drucken Sie das Ergebnis entsprechend formatiert ausF()
.Auswertung
Wir pflegen den globalen Geltungsbereich
G
als Liste von Schlüssel / Wert-Paaren. Anfangs enthält es nur die eingebauten Funktionen (aber nicht die Makros und nicht diev
, die wir als Makro behandeln), die als Lambdas implementiert sind.Die Auswertung erfolgt im Inneren
V()
, das den auszuwertenden Ausdruck benötigte
, und im lokalen Bereich,L
der auch eine Liste von Schlüssel / Wert-Paaren ist (bei der Auswertung eines Ausdrucks der obersten Ebene ist der lokale Bereich leer.) Die Eingeweide vonV()
Live in einer Endlosschleife, auf diese Weise führen wir die Tail-Call-Optimierung (TCO) durch, wie später erläutert wird.Wir verarbeiten
e
nach seiner Art:Wenn es sich um eine leere Liste oder eine Zeichenfolge handelt, die in ein int konvertierbar ist, geben wir sie sofort zurück (möglicherweise nach der Konvertierung in int). Andernfalls,
Wenn es sich um eine Zeichenfolge handelt, schlagen wir sie in einem Wörterbuch nach, das aus der Verkettung des globalen und des lokalen Bereichs besteht. Wenn wir einen zugehörigen Wert finden, geben wir ihn zurück. andernfalls
e
muss der Name einer eingebauten Makro (dh seinq
,i
,d
oderv
), und wir unverändert zurück. Andernfalls, wenne
es sich nicht um eine Zeichenfolge handelt,e
ist eine (nicht leere) Liste, dh ein Funktionsaufruf. Wir bewerten das erste Element der Liste, dh den Funktionsausdruck, durchV()
rekursiven Aufruf (unter Verwendung des aktuellen lokalen Gültigkeitsbereichs). Wir nennen das Ergebnisf
. Der Rest der ListeA
ist die Liste der Argumente.f
kann nur eine Zeichenfolge sein, in diesem Fall ein eingebautes Makro (oder die Funktionv
), ein Lambda, in diesem Fall eine eingebaute Funktion oder eine Liste, in diesem Fall eine benutzerdefinierte Funktion oder ein benutzerdefiniertes Makro.Wenn
f
es sich um eine Zeichenfolge handelt, dh um ein eingebautes Makro, wird es direkt verarbeitet. Wenn es sich um das Makroi
oder handeltv
, werten wir seinen ersten Operanden aus und wählen entweder den zweiten oder dritten Operanden im Fall von entsprechend ausi
oder verwenden das Ergebnis des ersten Operanden im Fall vonv
; Anstatt den ausgewählten Ausdruck rekursiv auszuwerten, was TCO zunichte machen würde, ersetzen wir ihn einfach durche
den genannten Ausdruck und springen an den Anfang der Schleife. Wennf
es sich um das Makro handeltd
, fügen wir ein Paar, dessen erstes Element der erste Operand ist und dessen zweites Element das Ergebnis der Auswertung des zweiten Operanden ist, an den globalen Gültigkeitsbereich anG
und geben den ersten Operanden zurück. Andernfallsf
ist das Makroq
. In diesem Fall geben wir den Operanden einfach direkt zurück.Wenn
f
also ein Lambda ist oder eine Liste, deren erstes Element nicht ist()
, dann ist es eine nichtnulläre Funktion, kein Makro. In diesem Fall werden die Argumente, dh die Elemente vonA
, ausgewertet und durchA
das Ergebnis ersetzt.Wenn
f
es ein Lambda ist, nennen wir es, übergeben ihm die entpackten ArgumenteA
und geben das Ergebnis zurück.Andernfalls
f
handelt es sich um eine Liste, dh eine benutzerdefinierte Funktion oder ein benutzerdefiniertes Makro. Seine Parameterliste ist das vorletzte Element, und sein Hauptteil ist das letzte Element. Wie bei den Makrosi
undv
, um die TCO durchzuführen, wird der Body nicht rekursiv ausgewertet, sondern durche
den Body ersetzt und mit der nächsten Iteration fortgefahren. Im Gegensatz zui
undv
ersetzen wir jedoch auch den lokalen GültigkeitsbereichL
durch den neuen lokalen Gültigkeitsbereich der Funktion. Wenn es sich bei der ParameterlisteP
tatsächlich um eine Liste handelt, wird der neue lokale Gültigkeitsbereich erstellt, indem die ParameterlisteP
mit der Argumentliste komprimiert wirdA
. Andernfalls handelt es sich um eine variable Funktion. In diesem Fall enthält der neue lokale Bereich nur ein Element, das Paar(P, A)
.REPL
Wenn Sie damit spielen möchten, finden Sie hier eine REPL-Version des Interpreters. Es unterstützt das Neudefinieren von Symbolen und das Importieren von Dateien entweder über die Befehlszeilenargumente oder über das
(import <filename>)
Makro. Um den Interpreter zu beenden, beenden Sie die Eingabe (normalerweise Strg + D oder Strg + Z).Code-Snippet anzeigen
Und hier ist eine Beispielsitzung, in der die Zusammenführungssortierung implementiert wird:
Code-Snippet anzeigen
quelle
import zlib;exec(zlib.decompress(your_code_compressed_in_bytes))
A[0]
eine Variable mit einemA
in diesem Fall leer ist), und ich möchte nicht "regressieren".C (GNU), 1095 Bytes
Ein Großteil der Aktion findet in der Riesenfunktion statt
v
. Anstatt die Schwanzrekursion explizit zu implementieren,v
ist sie so strukturiert, dass viele der Aufrufe vonv
bisv
von der Optimierung der Schwanzrekursion von gcc verarbeitet werden. Es gibt keine Müllabfuhr.Dies nutzt die GCC-Erweiterungen stark aus, sodass sie nur mit gcc kompiliert werden können (verwenden Sie den Befehl
gcc -w -Os tl.c
). Es werden auch einigescanf
Erweiterungen verwendet, die unter Windows, das ich normalerweise verwende, nicht verfügbar waren. Die Aussicht, den Parser mit Standard zu schreiben,scanf
war so schrecklich, dass ich stattdessen eine Linux-VM verwendete, um das Programm zu testen. Das Parsen ohnescanf
Zeichenklassen hätte wahrscheinlich mehr als 100 Bytes hinzugefügt.Semi-ungolfed
quelle
Ceylon, 2422 Bytes
(Ich denke, das ist mein längstes Golfprogramm.)
Ich hätte ein paar Bytes mehr Golf spielen können, da ich an einigen Stellen zwei Buchstaben als Bezeichner verwendet habe, aber für diese habe ich keine aussagekräftigen Einzelbuchstaben mehr. Obwohl es auch so nicht so aussieht wie Ceylon ...
Dies ist eine objektorientierte Implementierung.
Wir haben eine Werteschnittstelle
V
mit implementierenden KlassenL
(Liste - nur ein Wrapper um eine Ceylon - Sequenz vonV
),S
(Symbol - Wrapper um eine Zeichenkette),I
(Ganzzahl - Wrapper um eine Ceylon - Ganzzahl) undB
(eingebaute Funktion oder Makro, ein Wrapper um eine Ceylon-Funktion).Ich verwende die Standard-Ceylon-Gleichheitsnotation, indem ich die
equals
Methode (und auch dashash
Attribut, das wirklich nur für Symbole benötigt wird) sowie das Standardattributstring
für die Ausgabe implementiere .Wir haben ein boolesches Attribut
b
(das standardmäßig wahr ist, in leeren Listen überschrieben wirdI
undL
false zurückgibt) und zwei Methodenl
(dieses Objekt aufrufen, dh als Funktion verwenden) undvO
(einen Schritt auswerten). Beide geben entweder einen Wert oder ein Fortsetzungsobjekt zurück, das dann die Auswertung für einen weiteren Schritt ermöglicht, und führenvF
(vollständige Auswertung) Schleifen durch, bis das Ergebnis keine Fortsetzung mehr ist.Eine Kontextschnittstelle ermöglicht den Zugriff auf Variablen. Es gibt zwei Implementierungen
G
für den globalen Kontext (der das Hinzufügen von Variablen mithilfe desd
eingebauten Kontexts ermöglicht) undLC
für einen lokalen Kontext, der aktiv ist, wenn der Ausdruck einer Benutzerfunktion ausgewertet wird (er greift auf den globalen Kontext zurück).Die Symbolauswertung greift auf den Kontext zu, Listen (falls nicht leer) bewerten, indem sie zuerst ihr erstes Element auswerten und dann ihre Aufrufmethode aufrufen. Der Aufruf wird nur von Listen und eingebauten Elementen implementiert - er wertet zuerst das Argument aus (wenn eine Funktion, nicht ein Makro) und erledigt dann die eigentlichen interessanten Dinge - für eingebaute Elemente nur das, was fest codiert ist, für Listen erstellt er einen neuen lokalen Kontext und gibt a zurück Fortsetzung damit.
Für die eingebauten Funktionen habe ich einen ähnlichen Trick verwendet wie in meinem Shift-Interpreter , der es mir ermöglicht, sie mit den benötigten Argumenttypen zu definieren, sie jedoch mit einer generischen Sequenz unter Verwendung von Reflection aufzurufen (die Typen werden zum Zeitpunkt des Aufrufs überprüft). Dies vermeidet Typkonvertierungs- / Assertionsprobleme innerhalb der Funktionen / Makros, benötigt jedoch Funktionen der obersten Ebene, damit ich deren Metamodellobjekte erhalten
Function
kann.Die
p
Funktion (Parsen) teilt den String in Leerzeichen, Zeilenumbrüche und Klammern auf, durchläuft dann die Token und erstellt Listen mithilfe eines Stapels und einer laufenden Liste.Der Interpreter (in der
run
Methode, die der Einstiegspunkt ist) nimmt dann diese Liste von Ausdrücken (die nur Werte sind), wertet sie aus und gibt das Ergebnis aus.Unten finden Sie eine Version mit Kommentaren und einem Formatierer.
Eine frühere Version , bevor ich (mit einigen Missverständnissen über Listenauswertung und immer noch) Golf spielt begonnen wird bei gefunden meiner Github - Repository , werde ich diese setzt es bald (so sicher zu betrachten macht die erste Version , wenn Sie das Original will).
quelle