F# quotations: variable may escape scope

Question

I have this bit of code:

let rec h n z = if n = 0 then z
                else <@ (fun x -> %(h (n - 1) <@ x + %z @>)) n @>

converted from a MetaOcaml example in http://www.cs.rice.edu/~taha/publications/journal/dspg04a.pdf

In the paper there is explained that the above example will yield the following with the parameters 3 and .<1>. (in MetaOcaml notation):

.<(fun x_1 -> (fun x_2 -> (fun x_3 -> x_3 + (x_2 + (x_1 + 1))) 1) 2) 3>.

As you can see the x´s gets replaced by x_1, x_2 etc. because the x would otherwise only refer to the x in the innermost fun.

But in F# this isn't allowed. I get the compile-time error: "The variable 'x' is bound in a quotation but is used as part of a spliced expression. This is not permitted since it may escape its scope." So the question is: how can this be changed so it will compile and have the same semantic as the MetaOcaml output?

Update to comment: I use the PowerPack to actually evaluating the quotation. But I don't think this have anything to do with it because the error is at compile-time. So far QuotationEvaluation works. However, I do know it may not be the most efficient implementation.

Update to Tomas´ answer: I really don't want the x to be global, or to escape scope. But I want is the equivalent to

let rec h n z = if n = 0 then z
                else (fun x -> (h (n - 1) (x + z))) n

with quotations. Your answer gives (h 3 <@ 1 @>).Eval() = 4 where the above yields h 3 1 = 7. And here, I want 7 to be the answer.

Answer 1

F# quotation syntax doesn't support variables that could potentially escape the scope, so you'll need to construct the tree explicitly using the Expr operations. Something like this should do the trick:

open Microsoft.FSharp.Quotations

let rec h n (z:Expr<int>) = 
  if n = 0 then z                
  else 
    let v = new Var("x", typeof<int>)
    let ve = Expr.Var(v)
    Expr.Cast<int>
        (Expr.Application( Expr.Lambda(v, h (n - 1) <@ %%ve + %z @>), 
                           Expr.Value(n)))

However, this is quite artificial example (to demonstrate variable capturing in MetaOCaml, which isn't available in F#). It just generates expression like (2 + (1 + ...)). You can get the same result by writing something like this:

let rec h n (z:Expr<int>) = 
  if n = 0 then z                
  else h (n - 1) <@ n + %z @>

Or even better:

[ 1 .. 4 ] |> List.fold (fun st n -> <@ n + %st @>) <@ 0 @>

I also came accross this limitation in F# quotations and it would be nice if this was supported. However, I don't think it is such a big problem in practice, because F# quotations are not used for staged meta-programming. They are more useful for analyzing existing F# code than for generating code.