Albero di sintassi astratto con funzione con applicazione di funzione

Question

Sto tentando di scrivere un tipo di dati sintattico dell'albero della sintassi che può rappresentare l'applicazione di funzione .

Finora ho

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

Non credo ci sia un modo in F # per scrivere qualcosa di simile 'per tutti i b' su quella ultima riga - sto avvicinando questo problema torto?

Answer 1

In generale, il sistema di tipo F # non è abbastanza espressivo per definire (direttamente) un albero di sintassi astratto digitato come quello nell'esempio. Questo può essere fatto usando generalized algebraic data types (GADTs) che non sono supportate in F # (sebbene siano disponibili in Haskell e OCaml). Sarebbe bello avere questo in F #, ma penso che renda la lingua un po 'più complessa.

Tecnicamente parlando, il compilatore si lamenta perché la variabile di tipo 'b non è definita. Ma naturalmente, se lo si definisce, si ottiene il tipo Expr<'a, 'b> che ha un significato diverso.

Se si desidera esprimere questo in F #, è necessario utilizzare una soluzione alternativa basata su interfacce (un'interfaccia può avere un metodo generico, che consente di esprimere un vincolo come exists 'b di cui si necessita qui). Questo sarà probabilmente ottenere molto brutto molto presto, quindi non penso che sia un buon approccio, ma sarebbe simile a questa:

// 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) 

per rappresentare un albero di espressione di (fun (n:int) -> string n) 42, si potrebbe scrivere qualcosa di simile:

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

una funzione di valutare l'espressione può essere scritta in questo modo:

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 

come ho detto, questo è un po 'davvero estremo soluzione, quindi non credo che i è una buona idea usarlo effettivamente. Suppongo che il modo F # di fare questo sarebbe usare il tipo Expr non tipizzato. Puoi scrivere un po 'di più sull'obiettivo generale del tuo progetto (forse c'è un altro buon approccio)?