Qit - Quotation toolkit

A collection of utilities for building, inspecting, transforming and executing F# quotations.

Installation

Install from nuget at https://www.nuget.org/packages/Qit/

#r "nuget:Qit"

Quick Tour

Splicing

Splicing operators !% and !%% combined with Quote.expandOperators extend what can be spliced. Consider the quoted function f:

open Qit
open FSharp.Quotations

type MyType = |A of int | B of double

let f = 
    <@
        fun x -> 
            match x with 
            | A v -> A(v + 1)
            | B v -> B(v + 1.0)
    @>

Now, a bit contrived, but lets say we need to use the Tag property of MyType in a quoted expression. We can't just use %(Expr.PropertyGet(<@x@>, pinfo)) because x is bound in the quotation. We can use !% to splice in the expression x and then use Quote.expandOperators to expand the spliced expression:

let f2 = 
    <@ 
        fun (x : MyType) -> 
            let tag = !%%(Expr.PropertyGet(<@x@>, typeof<MyType>.GetProperty("Tag")))
            printfn "Tag: %d" tag
            match x with 
            | A v -> A(v + 1)
            | B v -> B(v + 1.0)
    @>
    |> Quote.expandOperators

<@ (%f2) (A 1) @> |> Quote.evaluate

Tag: 0

A 2

Note that !% and !%% are also available as functions QitOp.splice and QitOp.spliceUntyped respectively.

Matching

Simplified pattern matching:

let uselessIf = 
    <@ 
        let a = 34
        if true then
            a + 1
        else
            a - 2
    @>


let rec removeTrivialIfs expr = 
    expr
    |> Quote.traverse
        (fun q -> 
            match q with 
            | BindQuote <@if true then Quote.any "body" else Quote.any "" @> 
                (Marker "body" body)
            | BindQuote <@if false then Quote.any "" else Quote.any "body" @> 
                (Marker "body" body) -> 
                    Some(removeTrivialIfs body)
            | _ -> None
        )

Quote.any is matching any expression and binding it to a name which can then be extracted with the Marker pattern. Quote.traverse traverses the quotation and applies the given function to each subexpression optionally replacing it with the result of the function. If we simply wanted to match with no binding we could have done

uselessIf
|> Quote.exists 
    (function 
     | Quote <@if true then Quote.any "body" else Quote.any "" @> -> 
        true 
     | _ -> false)

true

Again, Quote.any is matching any expression, but what about an expression of specific type? For that there's Quote.withType<'t>:

uselessIf
|> Quote.exists 
    (function 
     | Quote <@if true then Quote.withType<int> "" else Quote.withType<int> "" @> -> 
        true 
     | _ -> false)

true

uselessIf
|> Quote.exists 
    (function 
     |Quote <@if true then Quote.withType<double> "" else Quote.withType<double> "" @> -> 
        true 
     | _ -> false)

false

When binding to markers , the Marker pattern will extract both Quote.any and Quote.withType bindings. To be specific we could use the AnyMarker and TypedMarker patterns. We used an empty string to signify that we're not interested in binding the matched expression. When specifying a name we expect bindings with the same name to be equivalent.

uselessIf
|> Quote.exists 
    (function 
     | Quote <@if true then Quote.withType<int> "myMarker" else Quote.withType<int> "myMarker" @> -> 
        true 
     | _ -> false)

false

Looking at uselessIf we can see that the true/false cases are different and so the match fails. Now when they're the same:

let uselessIf2 = 
    <@  
        let a = 32
        if a > 100 then 
            a + 1
        else
            a + 1
    @>

uselessIf2
|> Quote.exists 
    (function 
     | Quote <@ 
        if Quote.withType"" then 
            Quote.withType<int> "myMarker" 
        else Quote.withType<int> "myMarker"
       @> -> true 
     | _ -> false)

true

Variable names must also match unless prefixed with __.

uselessIf 
|> Quote.exists 
    (function 
     | Quote <@let a = Quote.any "" in Quote.any ""@> -> true 
     | _ -> false)

true

Original code has let a and so it matches.

uselessIf 
|> Quote.exists 
    (function 
     |Quote <@let b = Quote.any "" in Quote.any ""@> -> true 
     | _ -> false)

false

Original code has let a which does not match let b

uselessIf 
|> Quote.exists 
    (function 
     | Quote <@let __b = Quote.any "" in Quote.any ""@> -> true 
     | _ -> false)

true

Now that we've prefixed the variable name with __, the name of the variable is no longer relevant and it matches.

Reflection tools

As motivation say we have,

let q0 = 
    <@ 
        let a = ResizeArray()
        a.Add 10
        a.Add 20
        a.Add 30
        a.ToArray()
    @>

and we want to replace the ResizeArray.Add method calls with ResizeArray.AddRange([arg]). The strategy encouraged here is to create a function with type parameters, use reflection once to apply the Type arguments, and invoke.

So we create a function with a type parameter that is otherwise not present in the function signature.

let addRange0<'a> (o : Expr) (arg : Expr) = 
    let ra  : 'a ResizeArray Expr = o |> Expr.Cast
    let arg : 'a Expr = arg |> Expr.Cast
    <@@ (%ra).AddRange([%arg]) @@>

val addRange0<'a> : o: Expr -> arg: Expr -> Expr

We can then use TypeTemplate.create to create a function that takes Type arguments and applies them to addRange0.

let addRange = TypeTemplate.create addRange0
// addRange : Type list -> Expr -> Expr -> Expr

Now instead of the typical reflection mess we can just call the new addRange function. The call itself is a compiled expression which is cached on the type arguments given, reducing call overhead compared to MethodInfo.Invoke. Note: We're also introducing the operator equivalents to Quote.any (!@@) and Quote.withType (!@).

let result = 
    q0
    |> Quote.traverse
        (fun q -> 
            match q with 
            | BindQuote <@ (!@"ra" : _ ResizeArray).Add(!@@"v1") @> 
                (Marker "ra" ra & Marker "v1" v1) -> 
                    Some(addRange [v1.Type] ra v1)
            | _ -> None
        )

// Did this do what we wanted? 

let expected = 
    <@
        let a = ResizeArray()
        a.AddRange [10]
        a.AddRange [20]
        a.AddRange [30]
        a.ToArray()
    @>

Quote.isEquivalent result expected

true

If we wanted to inline this concept and forgo the caching provided by TypeTemplate.create, ITypeTemplate<'ReturnType>.Def<'typeParameters> can be used. Here 'typeParameters would be either a single type or a tuple representing the needed type parameters. The Make method is used to apply the type parameters.

q0
|> Quote.traverse
    (fun q -> 
        match q with 
        | BindQuote <@ (Quote.withType<AnyType ResizeArray> "ra").Add(Quote.any "v1") @> 
            (Marker "ra" ra & Marker "v1" v1) -> 
                { new ITypeTemplate<Expr> with 
                    member _.Def<'a>() = <@@ (%%ra : 'a ResizeArray).AddRange([%%v1]) @@>
                }.Make [v1.Type]
                |> Some
        | _ -> None
    )

namespace Qit

Multiple items
namespace FSharp

--------------------
namespace Microsoft.FSharp

Multiple items
namespace FSharp.Quotations

--------------------
namespace Microsoft.FSharp.Quotations

type MyType = | A of int | B of double

union case MyType.A: int -> MyType

Multiple items
val int: value: 'T -> int (requires member op_Explicit)

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

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

union case MyType.B: double -> MyType

Multiple items
val double: value: 'T -> double (requires member op_Explicit)

--------------------
type double = System.Double

--------------------
type double<'Measure> = float<'Measure>

val f: Expr<(MyType -> MyType)>

val x: MyType

val v: int

val v: double

val f2: Expr<(MyType -> MyType)>

val tag: int

Multiple items
type Expr = override Equals: obj: obj -> bool member GetFreeVars: unit -> Var seq member Substitute: substitution: (Var -> Expr option) -> Expr member ToString: full: bool -> string 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 static member Call: methodInfo: MethodInfo * arguments: Expr list -> Expr + 1 overload static member CallWithWitnesses: methodInfo: MethodInfo * methodInfoWithWitnesses: MethodInfo * witnesses: Expr list * arguments: Expr list -> Expr + 1 overload ...

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

static member Expr.PropertyGet: property: System.Reflection.PropertyInfo * ?indexerArgs: Expr list -> Expr
static member Expr.PropertyGet: obj: Expr * property: System.Reflection.PropertyInfo * ?indexerArgs: Expr list -> Expr

val typeof<'T> : System.Type

val printfn: format: Printf.TextWriterFormat<'T> -> 'T

Multiple items
active recognizer Quote: Expr -> Expr -> unit option
<summary>
Match quoted expression.
</summary>
<param name="expr">Expr to match</param>
<param name="x">Expr matching against</param>

--------------------
module Quote from Qit
<summary>
Functions for transforming, evaluation, and inspecting <c>Expr</c> and <c>Expr<'a></c> objects.
</summary>

val expandOperators: expr: Expr<'a> -> Expr<'a>
<summary>
Expand all Qit operators in Expr.
</summary>
<param name="expr">Target Expr</param>
<returns>Transformed Expr</returns>

val evaluate: expr: Expr<'a> -> 'a
<summary>
Evaluate a ('a Expr)
</summary>
<param name="expr">('a Expr) to evaluate</param>
<returns> Result of evaluation </returns>

val uselessIf: Expr<int>

val a: int

val removeTrivialIfs: expr: Expr -> Expr

val expr: Expr

val traverse: f: (Expr -> Expr option) -> expr: Expr -> Expr
<summary>
Traverse quotation applying function to each subexpression, if the function returns None the subexpression is left unchanged.
</summary>
<param name="f">Traversal function</param>
<param name="expr">Target Expr</param>
<returns>Transformed Expr</returns>

val q: Expr

active recognizer BindQuote: Expr -> Expr -> (System.Collections.Generic.Dictionary<string,Expr> * System.Collections.Generic.Dictionary<string,Expr>) option
<summary>
Match quoted expression and extract bindings.
</summary>
<param name="expr">Expr to match. Can contain <c>Quote.any name</c> and <c>Quote.withType name</c> which will be extracted.</param>
<param name="x">Expr matching against</param>

val any: name: 'a -> AnyType
<summary>
Used within a quotation to match an Expr of any type.
</summary>
<param name="name">Name of the marker to later retreive the match</param>

active recognizer Marker: string -> System.Collections.Generic.IDictionary<string,Expr> * System.Collections.Generic.IDictionary<string,Expr> -> Expr option
<summary>
Match marker by name in extracted bindings. Untyped markers are matched first.
</summary>
<param name="markerName"></param>

val body: Expr

union case Option.Some: Value: 'T -> Option<'T>

union case Option.None: Option<'T>

val exists: predicate: (Expr -> bool) -> expr: Expr -> bool
<summary>
Tests if any sub-Expr of the Expr satisfies the predicate
</summary>
<param name="predicate">(Expr -> bool) to be applied to each sub-Expr</param>
<param name="expr">Target Expr</param>

val withType: name: string -> 'a
<summary>
Used within a quotation to match an Expr of specific type.
</summary>
<param name="name">Name of the marker to later retreive the match</param>

val uselessIf2: Expr<int>

val a: AnyType

val b: AnyType

val __b: AnyType

val q0: Expr<int array>

val a: ResizeArray<int>

type ResizeArray<'T> = System.Collections.Generic.List<'T>

System.Collections.Generic.List.Add(item: int) : unit

System.Collections.Generic.List.ToArray() : int array

val addRange0<'a> : o: Expr -> arg: Expr -> Expr

val o: Expr

val arg: Expr

val ra: Expr<ResizeArray<'a>>

static member Expr.Cast: source: Expr -> Expr<'T>

val arg: Expr<'a>

val addRange: (System.Type list -> Expr -> Expr -> Expr)

type TypeTemplate<'a> = static member create: [<ReflectedDefinition (false)>] f: Expr<'a> -> (Type list -> 'a)
<summary>
Utility for mapping <c>System.Type</c> to type parameters of arbitrary functions.
</summary>

static member TypeTemplate.create: [<ReflectedDefinition (false)>] f: Expr<'a> -> (System.Type list -> 'a)
<summary>
Constructs a function given a generic function and a list of Type arguments
</summary>
<param name="f">Generic function to apply type arguments to</param>

val result: Expr

val ra: Expr

val v1: Expr

property Expr.Type: System.Type with get

val expected: Expr<int array>

System.Collections.Generic.List.AddRange(collection: System.Collections.Generic.IEnumerable<int>) : unit

val isEquivalent: a: Expr -> b: Expr -> bool
<summary>
Check for equivalence between Exprs.
</summary>
<param name="a">Expr to check</param>
<param name="b">Expr to check</param>

Multiple items
type AnyType = new: unit -> AnyType static member (&&&) : a: AnyType * AnyType -> AnyType static member ( * ) : a: AnyType * AnyType -> AnyType static member (+) : a: AnyType * AnyType -> AnyType static member (-) : a: AnyType * AnyType -> AnyType static member (/) : a: AnyType * AnyType -> AnyType static member (<<<) : a: AnyType * AnyType -> AnyType static member (|||) : a: AnyType * AnyType -> AnyType
<summary>
Type used in pattern matching to allow for wildcard type matching. See also <see cref="M:Qit.Quote.any"/> and <see cref="M:Qit.Quote.withType"/>.

</summary>

<example>
The following example shows how to use the AnyType type to match a list of any type.
<code>
match <@ [] : int list @> with
| Quote <@ [] : AnyType list @> -> printfn "Matched!"
| _ -> printfn "No Match!"
</code>
</example>

<example>
Basic operator overloads allow to match generally over certain operators.
<code>
match <@ 23.0 + 2.0 @> with
| Quote <@ Quote.any "a" + Quote.any "b" @> -> printfn "Matched!"
| _ -> printfn "No Match!"
</code>
</example>

--------------------
new: unit -> AnyType

type ITypeTemplate<'b> = abstract Def: unit -> 'b
<summary>
Facilitates the use of inline type parameters. For non-inline use cases, refer to <see cref="M:Qit.TypeTemplate.create"/>.

</summary>

<example>
Suppose we have an object of type <c>obj</c>. Let's define it for illustrative purposes:
<code>
let myObj = box "hi"
</code>
If we wish to create a function that produces a typed tuple of <c>myObj, [myObj]</c>, it would typically require tedious reflection. With <c>ITypeTemplate</c>, this can be achieved as:
<code>
let myNewObj =
     { new ITypeTemplate<obj> with
         member _.Def<'t>() =
             let t = myObj :?> 't
             t, [t]
     }.Make [myObj.GetType()]
</code>
We use <c>ITypeTemplate<obj></c> since the actual returned type is <c>obj</c> (the type of <c>myNewObj</c>). The <c>Def<'t></c> method defines a type parameter to work with (the actual type of <c>myObj</c>). Although <c>myNewObj</c> is of type <c>obj</c>, it can be used in functions/methods that accept a <c>string * (string list)</c> tuple.
</example>

<remarks>
Note that the complexity of this approach arises from the F# limitation that doesn't allow defining functions with type parameters within another function or method. Using an interface serves as a workaround.
</remarks>