Back to Questions
1.4k
views5
comments
Some strange behavior of quotations: is it a bug or feature
f#

Hi all,
I tried to use quotations to make some code generations and came across with some strange behavior which I don't understand is it a bug or features.

Problem 1: When I write this
let rec expand_power (n : int) x =
if n = 0
then <@ 1 @>
else
<@ %x * %(expand_power n-1 x ) @>

I get
builder.fsx(88,32): error FS0003: This value is not a function and cannot be applied

Then I change like this
let rec expand_power (n : int) x =


if n = 0


then <@ 1 @>


else
let n' = n-1


<@ %x * %(expand_power n' x ) @>
val expand_power : int -> Expr<int> -> Expr<int>

Ok, I fine with this solution so it doesn't seem to be a big problem (may be it is just some minor bug).

Problem 2: When I'm trying to use the function above
let mk_power n =
<@ fun x -> %(expand_power n <@ x @>) @>
builder.fsx(93,12): error FS0191: 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

ok, lets change it a bit
let mk_power n =
<@ fun (x : Expr<int>) -> %(expand_power n x) @>
builder.fsx(93,13): error FS0191: 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

What does this mean?
Is there any way to write mk_power function which generates another function (inside quotation) based on n as argument?

Thanks,
Alex

.

To answer your second question (though note that this is just an educated guess), the problem is that it's extremely difficult to verify the soundness of splicing (see the type system for MetaML in Walid Taha's thesis, for example). There are lots of subtle difficulties that can creep in. For instance, code like <@ fun x -> %x @> is nonsensical because the variable x "escapes" - is there an easy way to syntactically recognize cases like this that are doomed to fail while allowing your code? My understanding is that F#'s quotations are not intended to provide a general multi-stage programming environment; rather, they allow introspection of quoted code, serving a purpose similar to that of expression trees in C# (Taha's thesis provides some interesting commentary about the difficulty of achieving both goals in the same language).

You can still define mk_power, though - you just have to use the rather cumbersome (and more error-prone) Quotations.Expr API.

1
2
3
4

let mk_power n : Expr<int -> int> =
  let v = Var("x", typeof<int>, false)
  Expr.Lambda(v, expand_power n (Expr.Var v |> Expr.Cast)) |> Expr.Cast

In fact, it's probably worth refactoring to pull out a nice generic combinator:

1
2
3
4
5
6

let mk_lambda (f:Expr<'a> -> Expr<'b>) : Expr<'a -> 'b> =
  let v = Var("x", typeof<'a>, false)
  Expr.Lambda(v, f (Expr.Var v |> Expr.Cast)) |> Expr.Cast

let mk_power n = mk_lambda (expand_power n)

Note that when I try to actually execute this it generates an error due to a problem with dynamically trying to execute the subtraction in expand_power - if you change (n-1) to (n + (-1)) there, then things will work as expected. I assume that this is a bug in the compiler.

-Keith

By on 7/28/2009 11:01 PM ()

Note that when I try to actually execute this it generates an error due to a problem with dynamically trying to execute the subtraction in expand_power - if you change (n-1) to (n + (-1)) there, then things will work as expected. I assume that this is a bug in the compiler.

I think in fact it's By Design, but in Beta1 it's a pretty unusable design. We'll improve some in Beta2. The problem now is that some built-in operators do support dynamic invocation, whereas other do not, but there's no way to discover which is which (other than ad-hoc trying them out and watching your program throw an exception in cases like this, where (+) works but (-) does not). In Beta2, all operators that have no dynamic invocation support will be labelled with the NoDynamicInvocation attribute, thus making it possible to write code like below (and use own logic to compensate for operators that don't support dynamic invocation). This is still somewhat tedious, but at least it becomes possible to reason about which operators need this special support. I don't recall the details of why some operators (like + and *) support dynamic invocation whereas others (like -) do not, but there is in fact some well motivated reason (something along the lines of we only support the min set of operators required for a LINQ bridge or something, I forget).

(Quotations are not my strong suit, so I hope that made some sense. :) )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

 

open Microsoft.FSharp.Quotations.Patterns

let rec eval = function
  | Call (None,m,a) ->
    let args = List.map eval a |> Array.of_list
    if(m.GetCustomAttributes(typeof<NoDynamicInvocationAttribute>, true).Length = 0) 
    then m.Invoke(null, args)
    else
        match m.DeclaringType.FullName, m.Name with
        | "Microsoft.FSharp.Core.Operators", "op_Subtraction" ->  
            match args.[0], args.[1] with
            | (:? int as i), (:? int as j) -> box (i - j)
            | _, _ -> failwith "Dynamic invcocation of '-' is only supported on 'int', here used with type %s and %s" 
                        (args.[0].GetType().FullName) 
                        (args.[1].GetType().FullName)
        | _ -> failwithf "Dynamic invocation of %s is not supported by 'eval'" m.Name
    
  | Value (o,t) -> o
  | o -> failwith (sprintf "Unsupported expression %A" o)

let plus x y = <@ x + y @>
let minus x y = <@ x - y @>

plus 3 2 |> eval |> printfn "%O"
minus 3 2 |> eval |> printfn "%O"
By on 7/29/2009 11:33 PM ()

Thanks for the info Brian - I'm glad to hear that the story will be better here in Beta 2. This thread may also be relevant here (and shows that it's possible with some effort to determine which operators will work if you're willing to dig through the source...). My confusion here, though, is why the compiler is unable to statically determine that the subtraction is operating on ints (I'd have thought that a spliced expression wouldn't need to be treated like evaluating a quoted expression, but maybe I'm missing something).

-Keith

By on 7/30/2009 5:13 PM ()

Ahh, I see my mistake, Brian, thanks!

Excellent! Keith, it's exactly what I wanted to see.

This solution is good enough for my needs, but it looks like I missed something with staged programming.
The point is that I borrowed my sample from this paper and hoped that this kind of programming is possible in F#. We have quotations and slicing operator but (as it turns out) they have limited implementation in F#.

Fortunately we have workarounds.

thanks,
Alex

By on 7/29/2009 2:39 PM ()

I don't know enough about quotations to answer your second and more interesting question, but as to the first, you need

<@ %x * %(expand_power (n-1) x ) @>

(note the parens around "n-1"). Without the parens, it was trying to parse in a way including (1 x), and of course '1' is not a function that can be applied to the argument 'x'.

By on 7/28/2009 6:32 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper