Getippter abstrakter Syntaxbaum mit Funktionsanwendung

Question

Ich versuche, einen typisierten abstrakten Syntaxbaumdatentyp zu schreiben, der Funktionsanwendung darstellen kann.

Bisher habe ich

type Expr<'a> = 
    | Constant of 'a 
    | Application of Expr<'b -> 'a> * Expr<'b> // error: The type parameter 'b' is not defined 

Ich glaube nicht, es gibt einen Weg in F # etwas wie ‚für alle b‘ auf der letzten Zeile zu schreiben - ich bin falsch, dieses Problem anbietet?

Answer 1

Im Allgemeinen ist das F # -Typsystem nicht aussagekräftig genug, um einen typisierten abstrakten Syntaxbaum (wie in Ihrem Beispiel) (direkt) zu definieren. Dies kann unter Verwendung von generalized algebraic data types (GADTs) erfolgen, die in F # nicht unterstützt werden (obwohl sie in Haskell und OCaml verfügbar sind). Es wäre schön, dies in F # zu haben, aber ich denke, es macht die Sprache ein bisschen komplexer.

Technisch spricht der Compiler, weil die Typvariable 'b nicht definiert ist. Aber natürlich, wenn Sie es definieren, erhalten Sie den Typ Expr<'a, 'b>, der eine andere Bedeutung hat.

Wenn Sie dies in F # ausdrücken wollte, dann würden Sie eine Abhilfe basierend auf Schnittstellen verwenden müssen (eine Schnittstelle können generische Methode haben, die Ihnen eine Möglichkeit geben Zwang wie exists 'b auszudrücken, was Sie hier benötigen). Dies wird wahrscheinlich sehr bald sehr hässlich, so dass ich nicht denke, es ist ein guter Ansatz, aber es würde wie folgt aussehen:

// Represents an application that returns 'a but consists 
// of an argument 'b and a function 'b -> 'a 
type IApplication<'a> = 
    abstract Appl<'b> : Expr<'b -> 'a> * Expr<'b> -> unit 

and Expr<'a> = 
    // Constant just stores a value... 
    | Constant of 'a 
    // An application is something that we can call with an 
    // implementation (handler). The function then calls the 
    // 'Appl' method of the handler we provide. As this method 
    // is generic, it will be called with an appropriate type 
    // argument 'b that represents the type of the argument. 
    | Application of (IApplication<'a> -> unit) 

Um einen Ausdruck Baum von (fun (n:int) -> string n) 42 darstellen, könnte man so etwas schreiben:

let expr = 
    Application(fun appl -> 
    appl.Appl(Constant(fun (n:int) -> string n), 
       Constant(42))) 

eine Funktion zum auswerten des Ausdrucks kann wie folgt geschrieben werden:

let rec eval<'T> : Expr<'T> -> 'T = function 
    | Constant(v) -> v // Just return the constant 
    | Application(f) -> 
     // We use a bit of dirty mutable state (to keep types simpler for now) 
     let res = ref None 
     // Call the function with a 'handler' that evaluates function application 
     f { new IApplication<'T> with 
      member x.Appl<'A>(efunc : Expr<'A -> 'T>, earg : Expr<'A>) = 
       // Here we get function 'efunc' and argument 'earg' 
       // The type 'A is the type of the argument (which can be 
       // anything, depending on the created AST) 
       let f = eval<'A -> 'T> efunc 
       let a = eval<'A> earg 
       res := Some <| (f a) } 
     res.Value.Value 

wie gesagt, das ist ein bisschen wirklich extreme Abhilfe ist, so glaube ich nicht, dass ich Es ist eine gute Idee, es tatsächlich zu benutzen. Ich nehme an, der F # Weg, dies zu tun wäre, untypisierten Expr Typ zu verwenden. Können Sie etwas mehr über das Gesamtziel Ihres Projekts schreiben (vielleicht gibt es einen anderen guten Ansatz)?