Can I get an identity of an F# quotation?
<p>F# quotation is a wonderful feature, it allows us to treat F# expression as normal F# value. In my context, I use F# quotation to code Gpu kernel, and compile it into Gpu bitcode module.</p>

<p>There is one problem. I don't want to compile Gpu kernel each time, I would like to cache the compiled Gpu bitcode module. Thus I need a key, or identity from an F# quotation value. I would like to have a cache system like:</p>

<pre><code>let compile : Expr -&gt; GpuModule

let cache = ConcurrentDictionary&lt;Key, GpuModule&gt;()

let jitCompile (expr:Expr) =
    let key = getQuotationKey(expr)
    cache.GetOrAdd(key, fun key -&gt; compile expr)
</code></pre>

<p>There is one solution, to use the quotation expr instance as the key. But look at this piece of code:</p>

<pre><code>open Microsoft.FSharp.Quotations

let foo (expr:Expr) =
    printfn "%O" expr

[&lt;EntryPoint&gt;]
let main argv = 

    for i = 1 to 10 do
        foo &lt;@ fun x y -&gt; x + y @&gt;

    0
</code></pre>

<p>If I check the compiled IL code, I got these IL instructions:</p>

<pre><code>IL_0000: nop
IL_0001: ldc.i4.1
IL_0002: stloc.0
IL_0003: br IL_00a2
// loop start (head: IL_00a2)
    IL_0008: ldtoken '&lt;StartupCode$ConsoleApplication2&gt;.$Program'
    IL_000d: call class [mscorlib]System.Type [mscorlib]System.Type::GetTypeFromHandle(valuetype [mscorlib]System.RuntimeTypeHandle)
    IL_0012: ldc.i4.5
    IL_0013: newarr [mscorlib]System.Type
    IL_0018: dup
    IL_0019: ldc.i4.0
    IL_001a: ldtoken [mscorlib]System.Int32
    IL_001f: call class [mscorlib]System.Type [mscorlib]System.Type::GetTypeFromHandle(valuetype [mscorlib]System.RuntimeTypeHandle)
    IL_0024: stelem.any [mscorlib]System.Type
    IL_0029: dup
    IL_002a: ldc.i4.1
    IL_002b: ldtoken [FSharp.Core]Microsoft.FSharp.Core.Operators
    IL_0030: call class [mscorlib]System.Type [mscorlib]System.Type::GetTypeFromHandle(valuetype [mscorlib]System.RuntimeTypeHandle)
    IL_0035: stelem.any [mscorlib]System.Type
    IL_003a: dup
    IL_003b: ldc.i4.2
    IL_003c: ldtoken [mscorlib]System.Tuple`2
    IL_0041: call class [mscorlib]System.Type [mscorlib]System.Type::GetTypeFromHandle(valuetype [mscorlib]System.RuntimeTypeHandle)
    IL_0046: stelem.any [mscorlib]System.Type
    IL_004b: dup
    IL_004c: ldc.i4.3
    IL_004d: ldtoken [mscorlib]System.String
    IL_0052: call class [mscorlib]System.Type [mscorlib]System.Type::GetTypeFromHandle(valuetype [mscorlib]System.RuntimeTypeHandle)
    IL_0057: stelem.any [mscorlib]System.Type
    IL_005c: dup
    IL_005d: ldc.i4.4
    IL_005e: ldtoken [mscorlib]System.Tuple`5
    IL_0063: call class [mscorlib]System.Type [mscorlib]System.Type::GetTypeFromHandle(valuetype [mscorlib]System.RuntimeTypeHandle)
    IL_0068: stelem.any [mscorlib]System.Type
    IL_006d: ldc.i4.0
    IL_006e: newarr [mscorlib]System.Type
    IL_0073: ldc.i4.0
    IL_0074: newarr [FSharp.Core]Microsoft.FSharp.Quotations.FSharpExpr
    IL_0079: ldc.i4 372
    IL_007e: newarr [mscorlib]System.Byte
    IL_0083: dup
    IL_0084: ldtoken field valuetype '&lt;PrivateImplementationDetails$ConsoleApplication2&gt;'/T1805_372Bytes@ Program::field1806@
    IL_0089: call void [mscorlib]System.Runtime.CompilerServices.RuntimeHelpers::InitializeArray(class [mscorlib]System.Array, valuetype [mscorlib]System.RuntimeFieldHandle)
    IL_008e: call class [FSharp.Core]Microsoft.FSharp.Quotations.FSharpExpr [FSharp.Core]Microsoft.FSharp.Quotations.FSharpExpr::Deserialize40(class [mscorlib]System.Type, class [mscorlib]System.Type[], class [mscorlib]System.Type[], class [FSharp.Core]Microsoft.FSharp.Quotations.FSharpExpr[], uint8[])
    IL_0093: call class [FSharp.Core]Microsoft.FSharp.Quotations.FSharpExpr`1&lt;!!0&gt; [FSharp.Core]Microsoft.FSharp.Quotations.FSharpExpr::Cast&lt;class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2&lt;int32, class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2&lt;int32, int32&gt;&gt;&gt;(class [FSharp.Core]Microsoft.FSharp.Quotations.FSharpExpr)
    IL_0098: call void Program::foo(class [FSharp.Core]Microsoft.FSharp.Quotations.FSharpExpr)
    IL_009d: nop
    IL_009e: ldloc.0
    IL_009f: ldc.i4.1
    IL_00a0: add
    IL_00a1: stloc.0

    IL_00a2: ldloc.0
    IL_00a3: ldc.i4.s 11
    IL_00a5: blt IL_0008
// end loop

IL_00aa: ldc.i4.0
IL_00ab: ret
</code></pre>

<p>This is a large code, but basically it does these things in the loop:</p>

<ul>
<li>Load byte array for the quotation from some static field</li>
<li>Setup type informations</li>
<li>Call <code>FSharp.Quotations.FSharpExpr::Deserialize40</code> to re-create the quotation object;</li>
</ul>

<p>So from this observation, my questions are:</p>

<ol>
<li>Although quotation are stored in one static field, but each time we write <code>&lt;@ ... @&gt;</code>, they will create a new <code>Expr</code> instance, even when the static field is same. So I cannot use the <code>Expr</code> instance as the key, it would be good to get the static field token and use that as the key. But I don't know how to get that information;</li>
<li>We saw there are lots of IL instructions to just re-create an quotation instance, even when they are the same quotation. This might have some performance issues, can F# compiler be optimized here?</li>
</ol>

<p>Regards,
Xiang.</p>

<p>@kvb gave a wonderful answer. Looks like we just need to fix the <code>Var</code> compare in the quotations (when var has a counterpart and has the same type). Follow his answer I made the following tests and it works:</p>

<pre><code>let comparer =
    let rec compareQuots vs = function
        | ShapeLambda(v,e), ShapeLambda(v',e') -&gt;
            compareQuots (vs |&gt; Map.add v v') (e,e')
        | ShapeCombination(o,es), ShapeCombination(o',es') -&gt;
            o = o' &amp;&amp; (es.Length = es'.Length) &amp;&amp; List.forall2 (fun q1 q2 -&gt; compareQuots vs (q1, q2)) es es'
        | ShapeVar v, ShapeVar v' when Map.tryFind v vs = Some v' &amp;&amp; v.Type = v'.Type -&gt;
            true
        | _ -&gt; false

    let rec hashQuot n vs = function
        | ShapeLambda(v,e) -&gt;
            hashQuot (n+1) (vs |&gt; Map.add v n) e
        | ShapeCombination(o,es) -&gt;
            es |&gt; List.fold (fun h e -&gt; 31 * h + hashQuot n vs e) (o.GetHashCode())
        | ExprShape.ShapeVar v -&gt;
            Map.find v vs

    { new System.Collections.Generic.IEqualityComparer&lt;_&gt; with 
        member __.Equals(q1,q2) = compareQuots Map.empty (q1,q2)
        member __.GetHashCode q = hashQuot 0 Map.empty q }

type Module = int

let mutable counter = 0

let compile (expr:Expr) =
    counter &lt;- counter + 1
    printfn "Compiling #.%d module..." counter
    counter

let cache = ConcurrentDictionary&lt;Expr, Module&gt;(comparer)

let jitCompile (expr:Expr) =
    cache.GetOrAdd(expr, compile)

[&lt;Test&gt;]
let testJITCompile() =
    Assert.AreEqual(1, jitCompile &lt;@ fun x y -&gt; x + y @&gt;)
    Assert.AreEqual(1, jitCompile &lt;@ fun x y -&gt; x + y @&gt;)
    Assert.AreEqual(1, jitCompile &lt;@ fun a b -&gt; a + b @&gt;)
    Assert.AreEqual(2, jitCompile &lt;@ fun a b -&gt; a + b + 1 @&gt;)

    let combineExpr (expr:Expr&lt;int -&gt; int -&gt; int&gt;) =
        &lt;@ fun (a:int) (b:int) -&gt; ((%expr) a b) + 1 @&gt; 

    // although (combineExpr &lt;@ (+) @&gt;) = &lt;@ fun a b -&gt; a + b + 1 @&gt;
    // but they are treated as different expr.
    Assert.AreEqual(3, jitCompile (combineExpr &lt;@ (+) @&gt;))
    Assert.AreEqual(3, jitCompile (combineExpr &lt;@ (+) @&gt;))
    Assert.AreEqual(4, jitCompile (combineExpr &lt;@ (-) @&gt;))
</code></pre>