So implementieren Sie eine verzögerte Auswertung von if ()

10

Ich implementiere derzeit einen Ausdrucksauswerter (einzeilige Ausdrücke wie Formeln), der auf Folgendem basiert:

  • Der eingegebene Ausdruck wird tokenisiert, um Literal-Boolesche Werte, Ganzzahlen, Dezimalstellen, Zeichenfolgen, Funktionen und Bezeichner (Variablen) zu trennen.
  • Ich habe den Shunting-Yard-Algorithmus implementiert (leicht modifiziert, um Funktionen mit variabler Anzahl von Argumenten zu handhaben), um Klammern zu entfernen und die Operatoren mit einer anständigen Priorität in einer nachfixierten Reihenfolge zu ordnen
  • Mein Rangierplatz erzeugt einfach eine (simulierte) Warteschlange von Token (mithilfe eines Arrays kann meine Powerbuilder Classic-Sprache Objekte definieren, verfügt jedoch nur über dynamische Arrays als nativen Speicher - keine echte Liste, kein Wörterbuch), die ich nacheinander mit a auswerte einfache Stapelmaschine

Mein Evaluator arbeitet gut, aber ich vermisse immer noch einen if()und frage mich, wie ich vorgehen soll.

Wenn ich bei meiner nachträglichen und stapelbasierten Rangierauswertung if()als weitere Funktion mit einem wahren und einem falschen Teil hinzufüge , zeigt eine einzelne if(true, msgbox("ok"), msgbox("not ok"))beide Nachrichten an, während ich nur eine anzeigen möchte. Dies liegt daran, dass beim Auswerten einer Funktion bereits alle Argumente ausgewertet und auf den Stapel gelegt wurden.

Könnten Sie mir eine Möglichkeit geben, if()faul zu implementieren ?

Ich habe überlegt, diese als eine Art Makro zu verarbeiten, aber zu einem frühen Zeitpunkt habe ich noch keine Zustandsbewertung. Vielleicht muss ich eine andere Art von Struktur als eine Warteschlange verwenden, um die Bedingung und die wahren / falschen Ausdrücke getrennt zu halten? Im Moment wird der Ausdruck vor der Auswertung analysiert, aber ich plane auch, die Zwischendarstellung als eine Art vorkompilierten Ausdruck für die zukünftige Auswertung zu speichern.

Bearbeiten : Nach einigem Nachdenken über das Problem denke ich, ich könnte eine Baumdarstellung meines Ausdrucks erstellen (ein AST anstelle eines linearen Token-Streams), aus der ich den einen oder anderen Zweig von mir leicht ignorieren könnte if().

Seki
quelle

Antworten:

9

Hier gibt es zwei Möglichkeiten.

1) Nicht ifals Funktion implementieren . Machen Sie es zu einer Sprachfunktion mit spezieller Semantik. Einfach zu machen, aber weniger "rein", wenn alles eine Funktion sein soll.

2) Implementieren Sie die Semantik "Aufruf nach Namen", die viel komplizierter ist, aber es der Compilermagie ermöglicht, sich um das Problem der verzögerten Bewertung zu kümmern, während sie ifals Funktion anstelle eines Sprachelements beibehalten wird. Es geht so:

ifist eine Funktion, die zwei Parameter akzeptiert, die beide als "nach Namen" deklariert sind. Wenn der Compiler feststellt, dass er etwas an einen By-Name-Parameter übergibt, ändert er den zu generierenden Code. Anstatt den Ausdruck auszuwerten und den Wert zu übergeben, wird ein Abschluss erstellt, der den Ausdruck auswertet und diesen stattdessen übergibt. Beim Aufrufen eines By-Name-Parameters innerhalb der Funktion generiert der Compiler Code, um den Abschluss auszuwerten.

Mason Wheeler
quelle
Ich bin mir nicht sicher, aber sollte "Schließung" "Thunk" sein? Hmm, vielleicht nicht; Ich habe mir gerade die Wikipedia-Seite angesehen: "Ein Thunk ist ein parameterloser Abschluss".
Wenn Sie "Call by Name" sagen, beziehen Sie sich auf global? Alternativ zum globalen Call-by-Name wird nur ein Schließungstyp implementiert, dann nimmt die if-Funktion nur 3 Abschlüsse und wertet zwei aus (Bedingung und dann oder sonst), aber nicht alles muss als Abschluss erkannt werden, wie z. B. vollständiger Call-by-Name Namenssemantik
Jimmy Hoffa
@Matt: Der Begriff "Thunk" kann im Zusammenhang mit der Programmierung verschiedene andere Dinge bedeuten, und "parameterloser Abschluss" ist nicht der erste, an den ich denke, wenn ich ihn höre. "Closure" ist viel eindeutiger.
Mason Wheeler
1
@ JimmyHoffa: Wenn ich "Call by Name" sage, beziehe ich mich auf einen bestimmten Stil zum Einrichten eines Funktionsarguments, der optional sein sollte. Ähnlich wie in vielen vorhandenen Sprachen können Sie festlegen, ob ein Parameter als Wert oder als Referenz übergeben werden soll. In diesem Szenario müssen Sie die Auswahl treffen, um den Namen zu übergeben.
Mason Wheeler
Während Ihr Vorschlag zur Semantik "Call by Name" mir einige interessante Punkte gezeigt hat, ist es für meinen Evaluator ein wenig übertrieben, da er kein vollständiger Compiler ist, da meine Funktionsaufrufe einzeilig sind (denken Sie an MS-Excel-Formeln). Ich denke, ich könnte einen Schritt nach dem Einreihen von Token hinzufügen, indem ich eine Pseudoauswertung des Stapels durchführe, um den aufrufenden Baum abzuleiten. Es sollte einfacher sein, vom Baum die zu verwerfenden Zweige zu erkennen.
Seki
3

Anstelle der Funktion mit der Signatur:

object if(bool, object, object)

Gib ihm die Unterschrift:

object if(bool, object function(), object function())

Dann ifruft Ihre Funktion die entsprechende Funktion basierend auf der Bedingung auf und wertet nur eine davon aus.

Hand-E-Food
quelle
1

Es ist ganz einfach, wenn Sie alles träge kompilieren. Sie müssen über einige Mittel verfügen, um festzustellen, ob ein Wert bereits ausgewertet wurde oder ob eine weitere Evlauation erforderlich ist.

Dann können Sie Folgendes tun: Wenn es sich um ein Literal oder eine Variable handelt (haben Sie diese?, Dh Namen von Funktionen?), Schieben Sie sie auf den Stapel. Wenn es sich um eine Anwendung einer Funktion handelt, kompilieren Sie sie separat und verschieben Sie den Einstiegspunkt auf den Stapel.

Die Ausführung eines Programms ist dann lediglich eine Schleife, bis die Oberseite des Stapels ausgewertet wird und keine Funktion mehr. Wenn es nicht ausgewertet wird oder eine Funktion ist, rufen Sie den Code auf, auf den der Stapel oben zeigt.

Ingo
quelle