26 people like it.
Like the snippet!

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>

Previous Version Raw view Test code New version

More information

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