return, continue, break in einem Interpreter



  • Hallo,

    ich werkel zur Zeit an einem Interpreter für eine kleine Programmiersprache. Ich komme im Grunde auch sehr gut voran. Zuletzt stieß ich bei der Implementation von Funktionen auf ein Problem: Wie soll ich ein 'return' in einer Funktion darstellen?

    Dazu kurz etwas zu meinem Aufbau:
    Das Eingabeskript wird geparst und in einen AST (Abstract Syntax Tree) verwandelt, soweit nichts weltbewegendes. Ein Funktionsaufruf (!) besteht dabei aus Argumenten und der aufzurufenden Funktion. Es werden also zunächst die Argumente ausgewertet und anschließend die Funktion mit diesen Argumenten aufgerufen. Eine Funktion ist dabei ein Objekt vom Typ Function , die einen Block besitzt, der aus Knoten / ASTs besteht, die ausgewertet werden können.

    Wird die Funktion im Skript also aufgerufen (bspw. do_it(10) ), so wird zunächst das Argument ausgewertet (Datentyp Double) und an das Funktionsobjekt übergeben, das do_it repräsentiert. Im C++-Code sieht das etwa so aus:

    // Wir befinden uns in einem Knoten des AST, der einem Funktionsaufruf entspricht:
    std::vector<Datatype> arguments ...
    // ...
    return function_object.run(arguments);
    

    Jeder Knoten gibt immer einen Datatype zurück.

    Also stellt sich nun die Frage: Wie soll man ein return implementieren, das im Skript in der Funktion vorkommt? Beispiel:

    function do_it(arg)
      if do_it < 15
        return 1
      println("Bei der Bearbeitung ist ein Fehler aufgetreten.")
      return "Fehlercode: 0x42"
    end
    

    Der run -Code vom function_object würde einfach sequentiell die Anweisungen ausführen, das return kann den Ausführungsfluss aber nicht beeinflussen. Es würde also an der Stelle nichts merkliches passieren und der restliche Teil würde auch noch ausgeführt werden (was ja falsch ist).

    Eine Möglichkeit wäre das Setzen eines Flags für den Aufrufer. Dann würde das Ausführen des Funktionobjektes nicht in einem Rutsch geschehen, sondern nur Stück für Stück und nach jeder Ausführung wird geprüft, ob das return-Flag gesetzt ist. Das ist aber alles andere als schön (und performant), weil verhältnismäßig selten ein return stattfindet. Dieses "Polling" ist also m.M.n. keine Lösung.

    Die andere Möglichkeit (die ich jetzt auch gewählt habe) ist im Grunde recht elegant (wobei das wohl Ansichtssache ist :P): Da ich C++ verwende, missbrauche ich einfach die Exceptions. Bei einem return wird der Kontrollfluss der run -Methode des Funktionobjektes durch eine ReturnStatementException unterbrochen, die von dem try-catch -Block um die run -Methode gefangen und bearbeitet werden würde. Das funktioniert auch tadellos. Für andere Kontrollstatement ( continue , break etc.) würde man das ganz analog implementieren können.

    Meine Frage ist nun im Grunde: Wenn ich nicht C++, sondern eine Sprache ohne Exceptions (z.B. C) verwendet hätte, würde das so nicht funktionieren. D.h. mein Design stützt sich also auf die verwendete Programmiersprache. Das ist nicht gut, wie ich finde. Ich schätze also, dass ich bei meinem Design einen entscheidenden Fehler gemacht habe, oder einfach etwas anderes übersehe. Da das meine ersten Gehversuche mit dem Interpreterbau sind, ist es verkraftbar, wenn ich irgendwo was falsch gemacht habe. Wie implementiert man sowas also allg. bei einem Interpreter? Wie man das über eine (virtuelle) Maschine machen würde, ist mir klar.

    Für Hilfe bzw. Denkanstöße wäre ich sehr dankbar.



  • Was hindert dich daran aus der run-Methode mittels eines returns herauszuspringen, sobald du auf ein "return" im AST triffst?



  • Das Problem ist, dass das Funktionobjekt nur einen Node* hält, der einen "Block" repräsentiert. Ein Block ist dabei nichts weiter als eine Liste von Nodes, die dann die eigentlichen Anweisungen darstellen. D.h. insbesondere, dass ein return -Statement nichts weiter als ein Node in eben jenem Block ist. Wird der Block evaluiert, so evaluiert dieser einfach nur sequentiell die Einzelnen Knoten seiner Liste, er weiß also nicht, was genau sich hinter einem Node* versteckt.

    Auch wenn man den Block weglassen würde und die Liste der Anweisungsknoten direkt in dem Funktionobjekt speichern würde, änderte das nichts an der eigentlichen Problematik.



  • Hey,
    ja, soweit ich mich erinnere habe ich auch eine ganze Zeit gebraucht, bis ich einen richtigen Weg für das spontane springen aus Funktionen implementieren konnte.
    Kurz zu meinem grundlegenden Aufbau:
    Funktionen implementieren bei mir das IEvaluable-interface, welches die virtuelle Funktion

    Eval(EvaluationContext&)
    

    bereitstellt. Zusätzlich haben meine Funktionen, ähnlich wie du, den Code, den sie ausführen in einem Container als Member gespeichert.
    Kommt es nun während der allgemeinen Ausführung des Codes zu einer Funktion/IEvaluable, dann wird deren Eval-Funktion aufgerufen und der gerade aktuelle EvaluationContext übergeben. Die Eval-Funktion erzeugt mittels EvaluationContext einen neuen EvaluationScope, der eine Tabelle enthält, in der die funktionslokalen Variablen gespeichert werden und einen Zeiger auf den nun auszuführenden Code. Dieser stammt ja aus dem Container, der in der Funktionsklasse existiert.
    Nun ruft die Eval-Funktion die EvalScope-Funktion vom EvaluationContext auf, die nun den eben angelegten Scope ausführt.
    Nun wiederholt sich das Spiel immer wieder, wenn eine Funktion ausgeführt wird.
    Sooo und nun der Trick:
    Der EvaluationContext besitzt auch die Funktion EndScope. Wenn im auszuführenden Code ein

    return
    

    auftaucht, dann wird dieses genau wie ein Funktion evaluiert. Das einzige was es macht ist dann EndScope() aufzurufen, was den aktuellen Funktionsscope samt Zeiger auf den Funktionscode löscht und den entsprechenden vorherigen Zustand wiederherstellt. Die Ausführung geht jetzt also mit dem alten Zustand weiter.

    Man jetzt habe ich wahrscheinlich verwirrender erklärt als ich wollte, aber ich hatte das Gefühl, dass ich nicht nur den kleinen Teil mit dem EndScope erwähnen kann, da es sonst unverstädnlich wird.
    Naja...
    Vllt. gibts ja einen Denkanstoß

    Gruß Gate



  • Wieso eigentlich ein Baum und nicht eine Liste? Vor dem Aufrufen auf den Stack die aktuelle Position ablegen und ein return holt sich den Wert und setzt dann den Befehlszeiger neu. Also eben wie bei Assembler.



  • Oliver schrieb:

    Wieso eigentlich ein Baum und nicht eine Liste? Vor dem Aufrufen auf den Stack die aktuelle Position ablegen und ein return holt sich den Wert und setzt dann den Befehlszeiger neu. Also eben wie bei Assembler.

    Weil es dann eben kein Syntaxbaum ist, der abgearbeitet wird.

    Um solche Probleme zu loesen, sollte man schon mal ein Buch zum Compilerbau oder verwandtes gelesen haben. Auch hilft es sich bestehende Beispiele fuer andere Skriptsprachen wie Scheme oder Lua anzusehen.



  • Der Ansatz von Gate klingt tatsächlich ganz brauchbar. Wesentlich besser als mein Exception-return.

    Mein Interpreter ist eigentlich aus den Magazinartikeln bzgl. Compiler- und Interpreterbau entstanden, richtig intensiv hatte ich mich in Form von Fachliteratur zu dem Thema noch nicht beschäftigt, was natürlich alles andere als clever bei einem so komplexen Themenbereich ist. Wie sich herausstellt, sollte ich das also tatsächlich nachholen, bevor ich weiter mache bzw. nochmal neu anfange.


Anmelden zum Antworten