Árbol sintáctico sintetizado con la aplicación de función

Question

Estoy tratando de escribir un tipo de árbol de sintaxis abstracta tipado que pueda representar la aplicación de función .

Hasta ahora he

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

no creo que hay una manera en Fa # para escribir algo como 'para todos b' en la última línea - Me estoy acercando a este problema erróneamente?

Answer 1

En general, el sistema de tipo F # no es lo suficientemente expresivo como para definir (directamente) un árbol de sintaxis abstracto tipado como el de su ejemplo. Esto se puede hacer usando generalized algebraic data types (GADTs) que no son compatibles con F # (aunque están disponibles en Haskell y OCaml). Sería bueno tener esto en F #, pero creo que hace que el lenguaje sea un poco más complejo.

Técnicamente hablando, el compilador se queja porque la variable de tipo 'b no está definida. Pero, por supuesto, si lo defines, obtienes el tipo Expr<'a, 'b> que tiene un significado diferente.

Si quería expresar esto en F #, tendría que usar una solución basada en interfaces (una interfaz puede tener un método genérico, que le da una forma de expresar la restricción como exists 'b que necesita aquí). Esto probablemente se pondrá muy fea muy pronto, así que no creo que es un buen enfoque, pero sería algo como esto:

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

para representar un árbol de expresión de (fun (n:int) -> string n) 42, podría escribir algo como:

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

una función para evaluar la expresión puede escribirse así:

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 

como ya he dicho, esto es un poco solución realmente extrema, así que no creo que me Es una buena idea usarlo realmente. Supongo que la forma F # de hacer esto sería usar el tipo Expr sin tipo. ¿Puedes escribir un poco más sobre el objetivo general de tu proyecto (quizás hay otro buen enfoque)?