0 people like it.

Quotations to A-Normal form

Quotations to A-Normal form based on http://matt.might.net/articles/a-normalization/

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
// Quotations to A-Normal form
// based on http://matt.might.net/articles/a-normalization/

open System
open Microsoft.FSharp.Quotations
open Microsoft.FSharp.Quotations.Patterns
 

let rec normalize (expr : Expr) (k : Expr -> Expr) : Expr = 
    match expr with
    | Var var -> k expr
    | Value(value, _) -> k expr
    | Let (var, expr, body) -> 
        normalize expr (fun expr' -> Expr.Let(var, expr', normalize body k))
    | Lambda (var, body) -> 
        k <| Expr.Lambda (var, normalize body id)
    | Application (exprF, arg) -> 
        normalizeName exprF (fun exprF' -> normalizeName arg (fun arg' -> k <| Expr.Application(exprF', arg')))  
    | IfThenElse (pred, trueExpr, falseExpr) -> 
        normalizeName pred (fun pred' -> 
        k <| Expr.IfThenElse (pred', normalize trueExpr id, normalize falseExpr id))
    | _ -> failwithf "Not supported, expr: %A" expr

and normalizeName (expr : Expr) (k : Expr -> Expr) : Expr = 
    normalize expr (fun expr' -> 
        match expr' with
        | Var var -> k expr'
        | Value(value, _) -> k expr'
        | _ -> let var = new Var("temp", expr'.Type)
               Expr.Let(var, expr', k <| Expr.Var var))

// Examples
normalize <@ let x = let y = 1 in y in x @> id
normalize <@ if (let x = true in x) then 1 else 2 @> id
normalize <@ (fun f x -> f x) ((fun x -> x) (fun x -> x)) 1 @> id
namespace System
namespace Microsoft
namespace Microsoft.FSharp
namespace Microsoft.FSharp.Quotations
module Patterns

from Microsoft.FSharp.Quotations
val normalize : expr:Expr -> k:(Expr -> Expr) -> Expr

Full name: Script.normalize
val expr : Expr
Multiple items
type Expr =
  override Equals : obj:obj -> bool
  member GetFreeVars : unit -> seq<Var>
  member Substitute : substitution:(Var -> Expr option) -> Expr
  member ToString : full:bool -> string
  member CustomAttributes : Expr list
  member Type : Type
  static member AddressOf : target:Expr -> Expr
  static member AddressSet : target:Expr * value:Expr -> Expr
  static member Application : functionExpr:Expr * argument:Expr -> Expr
  static member Applications : functionExpr:Expr * arguments:Expr list list -> Expr
  ...

Full name: Microsoft.FSharp.Quotations.Expr

--------------------
type Expr<'T> =
  inherit Expr
  member Raw : Expr

Full name: Microsoft.FSharp.Quotations.Expr<_>
val k : (Expr -> Expr)
Multiple items
active recognizer Var: Expr -> Var option

Full name: Microsoft.FSharp.Quotations.Patterns.( |Var|_| )

--------------------
type Var =
  interface IComparable
  new : name:string * typ:Type * ?isMutable:bool -> Var
  member IsMutable : bool
  member Name : string
  member Type : Type
  static member Global : name:string * typ:Type -> Var

Full name: Microsoft.FSharp.Quotations.Var

--------------------
new : name:string * typ:Type * ?isMutable:bool -> Var
val var : Var
active recognizer Value: Expr -> (obj * Type) option

Full name: Microsoft.FSharp.Quotations.Patterns.( |Value|_| )
val value : obj
active recognizer Let: Expr -> (Var * Expr * Expr) option

Full name: Microsoft.FSharp.Quotations.Patterns.( |Let|_| )
val body : Expr
val expr' : Expr
static member Expr.Let : letVariable:Var * letExpr:Expr * body:Expr -> Expr
active recognizer Lambda: Expr -> (Var * Expr) option

Full name: Microsoft.FSharp.Quotations.Patterns.( |Lambda|_| )
static member Expr.Lambda : parameter:Var * body:Expr -> Expr
val id : x:'T -> 'T

Full name: Microsoft.FSharp.Core.Operators.id
active recognizer Application: Expr -> (Expr * Expr) option

Full name: Microsoft.FSharp.Quotations.Patterns.( |Application|_| )
val exprF : Expr
val arg : Expr
val normalizeName : expr:Expr -> k:(Expr -> Expr) -> Expr

Full name: Script.normalizeName
val exprF' : Expr
val arg' : Expr
static member Expr.Application : functionExpr:Expr * argument:Expr -> Expr
active recognizer IfThenElse: Expr -> (Expr * Expr * Expr) option

Full name: Microsoft.FSharp.Quotations.Patterns.( |IfThenElse|_| )
val pred : Expr
val trueExpr : Expr
val falseExpr : Expr
val pred' : Expr
static member Expr.IfThenElse : guard:Expr * thenExpr:Expr * elseExpr:Expr -> Expr
val failwithf : format:Printf.StringFormat<'T,'Result> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.failwithf
property Expr.Type: Type
static member Expr.Var : variable:Var -> Expr
val x : int
val y : int
val x : bool
val f : (int -> int)
val x : (int -> int)
Raw view New version

More information

Link:http://fssnip.net/7QW
Posted:1 years ago
Author:Nick Palladinos
Tags: #quotations