5

Ich implementiere eine einfache C-ähnliche Sprache in OCaml und, wie üblich, AST ist meine Zwischencode-Darstellung. Da ich einige Traversale am Baum machen werde, wollte ich ein Besuchermuster implementieren, um den Schmerz zu lindern. Mein AST folgt derzeit die Semantik der Sprache:OCaml Besuchermuster

type expr = Plus of string*expr*expr | Int of int | ... 
type command = While of boolexpr*block | Assign of ... 
type block = Commands of command list 
... 

Das Problem ist jetzt, dass Knoten in einem Baum von einem anderen Typ sind. Idealerweise würde ich an die Besuchsprozedur eine einzelne Funktion übergeben, die einen Knoten behandelt; Die Prozedur würde den Typ des Knotens einschalten und die Arbeit entsprechend ausführen. Jetzt muss ich für jeden Knotentyp eine Funktion übergeben, die nicht als beste Lösung erscheint.

Es scheint mir, dass ich (1) wirklich mit diesem Ansatz gehen kann oder (2) nur einen einzigen Typ oben habe. Was ist der übliche Weg, um das zu erreichen? Vielleicht OO benutzen?

+0

Können Sie den Typ angeben, den Ihre Funktion haben soll? –

Antwort

10

Niemand verwendet das Besuchermuster in funktionalen Sprachen - und das ist gut so. Mit Pattern Matching können Sie die gleiche Logik glücklicherweise viel einfacher und direkter implementieren, indem Sie (gegenseitig) rekursive Funktionen verwenden.

zum Beispiel annehmen, dass Sie einen einfachen Dolmetscher für Ihren AST schreiben wollte:

let rec run_expr = function 
    | Plus(_, e1, e2) -> run_expr e1 + run_expr e2 
    | Int(i) -> i 
    | ... 

and run_command = function 
    | While(e, b) as c -> if run_expr e <> 0 then (run_block b; run_command c) 
    | Assign ... 

and run_block = function 
    | Commands(cs) = List.iter run_command cs 

Das Besuchermuster wird in der Regel dies nur erschweren, vor allem, wenn die Ergebnistypen heterogen sind, wie hier.

+0

+1 Ein kleiner logistischer Vorteil des Besuchers über diese Implementierung (die ich noch wählen würde) ist die Tatsache, dass es eine gemeinsame Schnittstelle für alle Besuchsoperationen bietet. – Mau

+2

@Mau, ja, aber ich bin mir nicht sicher, was das dich kaufen würde, obwohl. Diese Schnittstelle ist sowohl unterspezifiziert (vollständig generische Typen, die nichts sagen) als auch überspezifiziert (besuchen Sie Methoden für alle Fälle, auch wenn Sie nicht alle in vielen Fällen benötigen). Was noch wichtiger ist, welche Art von generischer Abstraktion möchte man über alle möglichen Besucher aufbauen? –

+0

Danke für die Antwort. Ich weiß, dass Mustererkennung mir diese Fähigkeit gibt. Im Wesentlichen ist es einfacher, die Baumdurchquerung jedes Mal, wenn ich sie brauche, für einige Funktionen erneut zu schreiben, anstatt ein Besuchermuster zu implementieren. – bellpeace

5

Es ist tatsächlich möglich, eine Klasse mit einer Besuchsmethode pro AST-Typ zu definieren (die standardmäßig nichts tut), und Ihre Besuchsfunktionen nehmen eine Instanz dieser Klasse als Parameter. Tatsächlich wird ein solcher Mechanismus in der OCaml-Welt verwendet, wenn auch nicht so oft.

Insbesondere die CIL library hat einen Besucher Klasse (https://github.com/kerneis/cil/blob/develop/src/cil.mli#L1816 für die Schnittstelle sehen). Beachten Sie, dass CIL-Besucher von Natur aus zwingend erforderlich sind (Transformationen werden vor Ort durchgeführt). Es ist jedoch durchaus möglich, Besucher zu definieren, die einen AST in einen anderen mappen, z. B. in Frama-C, der auf CIL basiert und In-Place- und Copy-Besucher anbietet. Schließlich Cαml, ein AST-Generator, der sich leicht um gebundene Variablen kümmert, Karten erzeugt und Besucher zusammen mit den Datentypen faltet.

4

Wenn Sie viele verschiedene rekursiven Operationen über einen Satz von sich gegenseitig rekursiven Datentypen (wie ein AST) schreiben müssen, dann können Sie offene Rekursion verwenden (in Form von Klassen), um die Traversal und sparen Sie sich eine Kesselblech zu kodieren.

Es gibt ein Beispiel für eine solche Besucherklasse in Real World OCaml.