Partial applications of F# Quotations

Question

Let's say I have this Quotation of type Quotations.Expr<(int -> int -> int)>

<@ fun x y -> x + y @>

I want to create a function fun reduce x expr that when called as reduce 1 expr would essentially yield

<@ fun y -> 1 + y @>

i.e. I want to partially apply a quotation to produce another quotation.

I'm sure this is doable, does anyone have any thoughts? Has this been attempted before? Can't seem to find anything.

Also I'm not very familiar with LISP -- but is this essentially similar to what I can achieve with LISP macros?

UPDATE: While reducing the quotation, I would like to evaluate parts that can be evaluated in the resulting expression tree.

For example: reduce true <@ fun b x y -> if b then x + y else x - y@> should result in <@ fun x y -> x + y @>.

Answer 1

If you know that your quotation is of the form fun x ... then it's easy:

let subst (v:'a) (Patterns.Lambda(x,b) : Expr<'a->'b>) =
    b.Substitute(fun x' -> if x = x' then Some (Expr.Value v) else None)
    |> Expr.Cast<'b>

subst 1 <@ fun x y -> x + y @>

If you additionally want to simplify expressions, then there are some slightly tricky questions you'll need to answer:

• Do you care about side effects? If I start with <@ fun x y -> printfn "%i" x @> and I substitute in 1 for x, then what's the simplified version of <@ fun y -> printfn "%i" 1 @>? This should print out 1 every time it's invoked, but unless you know ahead of time which expressions might cause side effects then you can almost never simplify anything. If you ignore this (assuming no expression causes side effects) then things become much simpler at the cost of fidelity.
• What does simplification really mean? Let's say I get <@ fun y -> y + 1 @> after substitution. Then, is it good or bad to simplify this to the equivalent of let f y = y+1 in <@ f @>? This is definitely "simpler" in that it's a trivial expression containing just a value, but the value is now an opaque function. What if I have <@ fun y -> 1 + (fun z -> z) y @>? Is it okay to simplify the inner function to a value, or bad?

If we can ignore side effects and we don't ever want to replace a function with a value, then you could define a simplification function like this:

let reduce (e:Expr<'a>) : Expr<'a> =
    let rec helper : Expr -> Expr = function
    | e when e.GetFreeVars() |> Seq.isEmpty && not (Reflection.FSharpType.IsFunction e.Type) -> // no free variables, and won't produce a function value
        Expr.Value(Linq.RuntimeHelpers.LeafExpressionConverter.EvaluateQuotation e, e.Type)
    | ExprShape.ShapeLambda(v, e) -> Expr.Lambda(v, helper e) // simplify body
    | ExprShape.ShapeCombination(o, es) -> // simplify each subexpression
        ExprShape.RebuildShapeCombination(o, es |> List.map helper) 
    | ExprShape.ShapeVar v -> Expr.Var v

    helper e |> Expr.Cast

Note that this still might not simplify thing as much as you'd like; for example <@ (fun x (y:int) -> x) 1 @> will not be simplified, although <@ (fun x -> x) 1 @> will be.

Answer 2

Splicing is a convenient way of embedding quotations in quotations:

let reduce x expr =
    <@ (%expr) x @>

reduce has type 'a -> Expr<('a -> 'b)> -> Expr<'b>

Usage:

let q = <@ fun x y -> x + y @>
let r = reduce 1 q // Expr<int -> int>
let s = reduce 2 <| reduce 3 q // Expr<int>
let t = reduce "world" <@ sprintf "Hello %s" @> // Expr<string>