Comparing code quotations in F# for equality fails

Question

I have the beginnings of a calculus toolbox in f#. It's as much about learning f# as having something useful at the end to use in some other projects I have in mind. The basic and incomplete code is

namespace BradGoneSurfing.Symbolics

open Microsoft.FSharp.Quotations
open Microsoft.FSharp.Quotations.Patterns
open Microsoft.FSharp.Quotations.DerivedPatterns
open System
open Microsoft.FSharp.Reflection
open Microsoft.FSharp.Quotations

open FSharpx.Linq.QuotationEvaluation
open Microsoft.FSharp.Linq.RuntimeHelpers

module Calculus =

    let rec der_impl param quotation =

        let (|X|_|) input = if input = param then Some(X) else None

        match quotation with

        | SpecificCall <@ (*) @> (_,types,l::r::[]) -> 
            let dl = der_impl param l
            let dr = der_impl param r
            <@@ (%%dl:double) * (%%r:double) + (%%l:double) * (%%dr:double) @@>

        | SpecificCall <@ Math.Sin @> (_,_types, arg::_) ->
            let di = der_impl param arg
            <@@ Math.Cos( (%%arg:double) ) @@> 

        | ExprShape.ShapeVar v -> 
            match v with 
            | X -> <@@ 1.0 @@>
            | _ -> (Expr.Var v)

        | ExprShape.ShapeLambda (v,expr) -> Expr.Lambda (v,der_impl param expr)
        | ExprShape.ShapeCombination (o, exprs) -> ExprShape.RebuildShapeCombination (o,List.map (fun e -> der_impl param e ) exprs)

    let rec der expr =
        match expr with
        | Lambda(param, body) ->
            Expr.Lambda(param, (der_impl param body))
        | _ -> failwith "oops"

and I have an NUnit / FSUnit test proving my first bits of code

namespace BradGoneSurfing.Symbolics.Test

open FsUnit
open NUnit.Framework
open Microsoft.FSharp.Quotations
open BradGoneSurfing.Symbolics.Calculus
open FSharpx.Linq.QuotationEvaluation
open System
open Microsoft.FSharp.Linq.RuntimeHelpers

[<TestFixture>]
type ``This is a test for symbolic derivatives`` ()=

    [<Test>] 
    member x.``Derivative should work`` ()=

        let e = <@ (fun (y:double) -> y * y) @>
        let d = der e

        let x = <@ fun (y:double) -> 1.0 * y + y * 1.0 @>
        d |> should equal x   

The test sort of works but doesn't. The result says

Expected:
Lambda (y,
        Call (None, op_Addition,
              [Call (None, op_Multiply, [Value (1.0), y]),
               Call (None, op_Multiply, [y, Value (1.0)])]))

But Was:               
Lambda (y,
        Call (None, op_Addition,
              [Call (None, op_Multiply, [Value (1.0), y]),
               Call (None, op_Multiply, [y, Value (1.0)])]))

Now to my eye these two are identical but its seems not. I'm guessing I've made some sort of mix up with Expr vs Expr<'t> but I'm not sure. Some of the implementation code was trial and error to get it compiling.

Any ideas what the subtle error might be here?

Update With Solution

@Jack was correct that Var implements reference equality and makes it difficult to use standard equality checks with code quotations. For testing purposes it is ''correct enough`` to compare strings. To make this palatable I created a custom matcher for FsUnit/NUnit as below

type EqualsAsString (e:obj)= 
    inherit NUnit.Framework.Constraints.Constraint()

    let expected = e

    override x.Matches(actual:obj)=
        x.actual <- actual
        x.actual.ToString() = expected.ToString()

    override x.WriteDescriptionTo(writer)=
        writer.WriteExpectedValue(expected)

    override x.WriteActualValueTo(writer)=
        writer.WriteActualValue(x.actual)

and an FSUnit wrapper

let equalExpr (x:Expr<'t>) = new EqualsAsString(x)

so I can do

d |> should equalExpr <@ fun y -> y * y @>

and it will work as expected.

Answer 1

The Var type used with F# quotations doesn't support structural equality. In fact, it doesn't implement IEquatable<'T> either -- it only provides an override of the Equals method which checks for reference equality:

https://github.com/fsharp/fsharp/blob/master/src/fsharp/FSharp.Core/quotations.fs#L122

So, it looks like the reason your test is failing is because the y variables in your quotations aren't recognized as 'equal'. The first solution that comes to mind would be to create a custom implementation of IEqualityComparer<'T> which does handle the variable equality in the way you want, then use it to check the expected value against the generated value.