InvalidOperationException on conversion from F# quotation to Linq Expression

Question

I'm trying to substitute types in a F# Expr, before converting it to an Expression for consumption by a c# lib. But upon the call to LeafExpressionConverter.QuotationToExpression I receive the error

InvalidOperationException: The variable 't' was not found in the translation context

Basically I'm trying to substitute the equivalent of

<@ fun (t: Record) -> t.A = 10 @> to

<@ fun (t: Dict) -> t["A"] = 10 @>

Here is the code

type Record = {
    A: int
}
type Dict () = //this is the type the c# lib wants (a dictionary representation of a type)
    inherit Dictionary<string, obj>()

let substitute<'a> (ex: Expr<'a->bool>) = 
    let replaceVar (v: Var) = if v.Type = typeof<'a> then Var(v.Name, typeof<Dict>) else v
    let tEntityItem = typeof<Dict>.GetProperty("Item")
    let isATypeShapeVar = function | ShapeVar var -> var.Type = typeof<'a> | _ -> false
    let rec substituteExpr = 
        function
        | PropertyGet(exOpt, propOrValInfo, c) -> 
            match exOpt with
                | None -> Expr.PropertyGet(propOrValInfo)
                | Some ex -> 
                    let args = c |> List.map substituteExpr
                    let newex = substituteExpr ex
                    match isATypeShapeVar ex with
                    | true -> 
                        let getter = Expr.PropertyGet(newex, tEntityItem, [Expr.Value(propOrValInfo.Name)] )
                        Expr.Coerce(getter, propOrValInfo.PropertyType)
                    | false -> Expr.PropertyGet(newex, propOrValInfo, args)
        | ShapeVar var -> Expr.Var (var |> replaceVar)
        | ShapeLambda (var, expr) -> Expr.Lambda(var |> replaceVar, substituteExpr expr)
        | ShapeCombination(shapeComboObject, exprList) ->
            RebuildShapeCombination(shapeComboObject, List.map substituteExpr exprList) 
        substituteExpr ex |> LeafExpressionConverter.QuotationToExpression

substitute<Record> (<@ fun t -> t.A = 10 @>)

I suspect I've missed something in the substitution, but I'm stumped as to what.

The the .ToString() result of the substituted F# Expr is

Lambda (t, Call (None, op_Equality, [Coerce (PropertyGet (Some (t), Item, [Value ("A")]), Int32), Value (10)]))

which looks correct. And other than the coersion, is the equivalent of <@ fun (t: Dict) -> t["A"] = 10 @>.ToString()

Why is the QuotationToExpression failing ?

Answer 1

Every time you call replaceVar, you return a different instance of Var. So when you replace the lambda parameter, it's one instance of Var, and later, when you replace newex, that's another instance of Var.

Lambda (t, Call (None, op_Equality, [Coerce (PropertyGet (Some (t), ... ))
        ^                                                       ^
        |                                                       |
        ---------------------------------------------------------
        These are different `t`, unrelated, despite the same name

To make this work, you have to make it the same t. The dumbest, most straightforward way would be this:

let substitute<'a> (ex: Expr<'a->bool>) =
    let newArg = Var("arg", typeof<Dict>)
    let replaceVar (v: Var) = if v.Type = typeof<'a> then newArg else v
    ...

This will make your particular example work as expected, but it is still unsound, because you're replacing not just specifically the lambda parameter, but any variable of the same type. Which means that if the expression happens to contain any variables of the same type as the parameter, you'd still hit the same problem. For example, try converting this:

<@ fun t -> let z = { A = 15 } in z.A = 15 && t.A = 10 @>

You'll get a similar error, but this time complaining about variable z.

A better way would be to maintain a map of variable substitutions as you go, insert new variables as you encounter them for the first time, but get them from the map on subsequent encounters.

---

An alternative approach would be to fish out specifically the lambda parameter and then replace only it, rather than comparing variable types.

---

But then there's the next level of weirdness: you're converting any property accessor to an indexer accessor, but in my example above, z.A shouldn't be thus converted. So you have to somehow recognize whether the object of property access is in fact the argument, and that may not be as trivial.

If you're willing to settle for just the case of t.A and fail on more complicated cases like (if true then t else t).A, then you can just match on the lambda argument and pass through any other expression:

let substitute<'a> (ex: Expr<'a->bool>) =
    let arg = 
          match ex with 
          | ShapeLambda (v, _) -> v
          | _ -> failwith "This is not a lambda. Shouldn't happen."

    let newArg = Var("arg", typeof<Dict>)
    let replaceVar (v: Var) = if v = arg then newArg else v

    let tEntityItem = typeof<Dict>.GetProperty("Item")
    let isATypeShapeVar = function | ShapeVar var -> var.Type = typeof<'a> | _ -> false
    let rec substituteExpr =
        function
        | PropertyGet(Some (ShapeVar a), propOrValInfo, c) when a = arg ->
            let getter = Expr.PropertyGet(Expr.Var newArg, tEntityItem, [Expr.Value(propOrValInfo.Name)] )
            Expr.Coerce(getter, propOrValInfo.PropertyType)
        | ShapeVar var -> Expr.Var (var |> replaceVar)
        | ShapeLambda (var, expr) -> Expr.Lambda(var |> replaceVar, substituteExpr expr)
        | ShapeCombination(shapeComboObject, exprList) ->
            RebuildShapeCombination(shapeComboObject, List.map substituteExpr exprList)
        | ex -> ex

    substituteExpr ex |> LeafExpressionConverter.QuotationToExpression

> substituteExpr <@ fun t -> let z = { A = 15 } in z.A = 15 && t.A = 10 @>

val it: System.Linq.Expressions.Expression =
  ToFSharpFunc(arg => z => ((z.A == 15) AndAlso (Convert(arg.get_Item("A"), Int32) == 10)).Invoke(new Record(15)))