25 people like it.

Traverse quotation

Shows how to use the 'ExprShape' module to recursively traverse an entire quotation and how to write quotation transformations. As an example, the snippet replaces all numeric constants in the quotation and then runs the transformed code.

Quotation transformation

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
open Microsoft.FSharp.Quotations

/// Traverse an entire quotation and use the provided function
/// to transform some parts of the quotation. If the function 'f'
/// returns 'Some' for some sub-quotation then we replace that
/// part of the quotation. The function then recursively processes
/// the quotation tree.
let rec traverseQuotation f q = 
  let q = defaultArg (f q) q
  match q with
  | ExprShape.ShapeCombination(a, args) -> 
      let nargs = args |> List.map (traverseQuotation f)
      ExprShape.RebuildShapeCombination(a, nargs)
  | ExprShape.ShapeLambda(v, body)  -> 
      Expr.Lambda(v, traverseQuotation f body)
  | ExprShape.ShapeVar(v) ->
      Expr.Var(v)

// Sample quotation (written explicitly using <@ .. @>)
let quot = 
 <@ let a = 10 
    let b = 32 / a
    a / b @>

Example: Finding constants

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
/// Find all constants in the quotation and print them...  
let findConstants quot =
  quot |> traverseQuotation (fun q -> 
    match q with 
    | Patterns.Value(v, typ) -> printfn "Constant: %A" v
    | _ -> ()
    None ) 
  |> ignore

findConstants quot  

Example: Multiply constants by two

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
/// Multiply all integer constants by two and compile the 
/// returned quotation & evaluate it
let quotTwoTimes quot = 
  quot |> traverseQuotation (fun q -> 
    match q with 
    | Patterns.Value(v, typ) when typ = typeof<int> ->
        Some(Expr.Value((unbox v) * 2))
    | _ -> None )

// Compile & run modified quotation
#r "FSharp.PowerPack.Linq.dll"
open Microsoft.FSharp.Linq.QuotationEvaluation
    
let quotTwoTimesTyped = Expr.Cast<int>(quotTwoTimes quot)    
quotTwoTimesTyped.Eval()
namespace Microsoft
namespace Microsoft.FSharp
namespace Microsoft.FSharp.Quotations
val traverseQuotation : f:(Expr -> Expr option) -> q:Expr -> Expr

Full name: Script.traverseQuotation


 Traverse an entire quotation and use the provided function
 to transform some parts of the quotation. If the function 'f'
 returns 'Some' for some sub-quotation then we replace that
 part of the quotation. The function then recursively processes
 the quotation tree.
val f : (Expr -> Expr option)
val q : Expr
val defaultArg : arg:'T option -> defaultValue:'T -> 'T

Full name: Microsoft.FSharp.Core.Operators.defaultArg
module ExprShape

from Microsoft.FSharp.Quotations
active recognizer ShapeCombination: Expr -> Choice<Var,(Var * Expr),(obj * Expr list)>

Full name: Microsoft.FSharp.Quotations.ExprShape.( |ShapeVar|ShapeLambda|ShapeCombination| )
val a : obj
val args : Expr list
val nargs : Expr list
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val map : mapping:('T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map
val RebuildShapeCombination : shape:obj * arguments:Expr list -> Expr

Full name: Microsoft.FSharp.Quotations.ExprShape.RebuildShapeCombination
active recognizer ShapeLambda: Expr -> Choice<Var,(Var * Expr),(obj * Expr list)>

Full name: Microsoft.FSharp.Quotations.ExprShape.( |ShapeVar|ShapeLambda|ShapeCombination| )
val v : Var
val body : 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<_>
static member Expr.Lambda : parameter:Var * body:Expr -> Expr
active recognizer ShapeVar: Expr -> Choice<Var,(Var * Expr),(obj * Expr list)>

Full name: Microsoft.FSharp.Quotations.ExprShape.( |ShapeVar|ShapeLambda|ShapeCombination| )
static member Expr.Var : variable:Var -> Expr
val quot : Expr<int>

Full name: Script.quot
val a : int
val b : int
val findConstants : quot:Expr -> unit

Full name: Script.findConstants


 Find all constants in the quotation and print them...
val quot : Expr
module Patterns

from Microsoft.FSharp.Quotations
active recognizer Value: Expr -> (obj * System.Type) option

Full name: Microsoft.FSharp.Quotations.Patterns.( |Value|_| )
val v : obj
val typ : System.Type
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
union case Option.None: Option<'T>
val ignore : value:'T -> unit

Full name: Microsoft.FSharp.Core.Operators.ignore
val quotTwoTimes : quot:Expr -> Expr

Full name: Script.quotTwoTimes


 Multiply all integer constants by two and compile the
 returned quotation & evaluate it
val typeof<'T> : System.Type

Full name: Microsoft.FSharp.Core.Operators.typeof
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
union case Option.Some: Value: 'T -> Option<'T>
static member Expr.Value : value:'T -> Expr
static member Expr.Value : value:obj * expressionType:System.Type -> Expr
val unbox : value:obj -> 'T

Full name: Microsoft.FSharp.Core.Operators.unbox
namespace Microsoft.FSharp.Linq
val quotTwoTimesTyped : Expr<int>

Full name: Script.quotTwoTimesTyped
static member Expr.Cast : source:Expr -> Expr<'T>

More information

Link:http://fssnip.net/1i
Posted:5 years ago
Author:Tomas Petricek
Tags: quotations , traversal , transformation , compilation