Traversing and transforming F# quotations: A guided tour

There seems to be some lack of information about quotations – most is either short, a specific example, or is a bit outdated. The most comprehensive example is probably Tomáš Petříček’s Quotations Visualizer in the  F# samples. His site is also one of the better resources about quotations that I’ve found. Another one with some recent activity is Alex Pedenko’s blog. Furthermore, even the otherwise excellent Expert F# book has little to say about it, and predates the major changes that were made in the September CTP.

Here I’ll focus on the important general patterns of using quotations. That is, I’m going to show how to traverse and transform quotations, independent of any specific example. I’m going to focus more on the API and programming aspects, than on introductory concepts, so this assumes some intermediate-level knowledge of F#. Basic knowledge about quotations doesn’t hurt either, as I‘ll make explanations terse.

Either way, this post represents some knowledge that took me a while to figure out on my own, piecing together scattered sources.

I would like to point out that once you get over the learning curve, working with quotations is actually enjoyable. I’ve been refraining from using them because I was put off by some bad experiences with System.Reflection (I think System.Reflection truly sucks as an API) and because I felt that to do anything useful, you’d almost be forced to support (i.e. at the very least provide default implementations of) every single construct in F#. It turns out that the quotations API is very enjoyable to work with and that there are built-in means to start small and focus on the things that are interesting to you.

The basics

In short, a quotation is metadata that represents the code of a particular function or code snippet, that gets compiled into the dll (along with the actual executable code, in some cases) by the F# compiler. To those of you who are familiar with LINQ Expression trees, it’s the same concept only F#’s quotations cover the entire reach of the F# language.

There are three ways to obtain a quotation:

1) Use the <@  @> operation around a code snippet to get a typed quotation of type Expr<’a>, where ‘a is the type of the actual value you put into the snippet. The Expr “wrapper” essentially indicates that we’re not dealing with an actual value of type ‘a, but instead with a reified representation of that value – the quotation:

let typedExpr = <@ 1 + 5 @>

let typedExpr2 = <@ fun i -> i + 5 @>

Sending these to FSI gives:

val typedExpr : Quotations.Expr<int> =
  Call (None, Int32 op_Addition[Int32,Int32,Int32](Int32, Int32),
      [Value (1), Value (5)])
val typedExpr2 : Quotations.Expr<(int -> int)> =
  Lambda (i,
        Call (None, Int32 op_Addition[Int32,Int32,Int32](Int32, Int32),
              [i, Value (5)]))

First notice the types: the first is Expr<int> because 1 + 5 of course is an int value. The second example illustrates a function value, of type Expr<int->int>.

FSI has printed the values of the quotations: a representation of the code! In fact, as we’ll soon see, the Expr type is nothing more than a discriminated union with one case for each possible language construct in F# (it’s not actually a discriminated union under the covers, but that’s how it’s abstracted, and the abstraction is very clean. It doesn’t hurt to think about it that way.)

2) Use the <@@  @@> operator around a code snippet to get an untyped quotation, of type Expr. Expr<’a> is a subtype of Expr, and every Expr<’a> can be converted to an Expr by calling .Raw:

let untypedExpr = <@@ 1 + 5 @@>

let untypedExpr2 = <@@ fun i -> i + 5 @@>

Sending to FSI gives:

val untypedExpr : Quotations.Expr =
  Call (None, Int32 op_Addition[Int32,Int32,Int32](Int32, Int32),
      [Value (1), Value (5)])
val untypedExpr2 : Quotations.Expr =
  Lambda (i,
        Call (None, Int32 op_Addition[Int32,Int32,Int32](Int32, Int32),
              [i, Value (5)]))

Pretty much exactly the same information, except for the type. For library writers, the Expr type does all the heavy lifting of inspecting and transforming quotations: since in a library you almost always want to write some code for any quotation, you cannot write this code in a generic way with typed quotations.

3) Using the ReflectedDefinition attribute on a top level function gives you the best of both worlds: the function can be called and executed as normal, but it can also be inspected as a quotation:

[<ReflectedDefinitionAttribute>]
let quotation i = i + 5

Based on a MethodInfo, the Expression.TryGetReflectedDefinition method allows you to get to the Expr associated with the function. The necessary metadata is actually marshaled into the dll when this function is compiled.

The Microsoft.FSharp.Quotations namespace

This namespace in the FSharp core libraries contains three modules and three types. The types are Expr, Expr<’a> and Var. The first two we’ve discussed already, the third one is just the representation of a variable.

The meat of quotations processing is in the module Quotations.Patterns and the static methods on Expr. If you compare these two, you’ll notice that for every active pattern in the Patterns modules, there is a static method on Expr. For example, you have Patters.Call(…) and Expr.Call(…), with equivalent signatures. This is no coincidence: the Patterns module contains all the patterns you’ll need to deconstruct a quotation expression. Together, these patterns can traverse any F# abstract syntax tree. It contains 32 active patterns (that’s a lot, but don’t despair yet: it gets better. ).

Its dual, the static methods on the Expr type, construct quotation expressions programmatically.

If you know F#, it shouldn’t be too hard to figure out what the arguments mean. For example:

Expr.Call : obj:Expr * methodInfo:MethodInfo * arguments:Expr list –> Expr

constructs an expression that represents a method call (defined by a methodInfo) on a target object (i.e. it’s an instance method), taking the given  arguments. Conversely,

( |Call|_| ) : Expr -> (Expr option * MethodInfo * Expr list) option

is an active pattern that matches a method call, with an (optional) target, methodinfo and a list of arguments.

This duality makes it fairly easy to get started with constructing and deconstructing quotations. Try to make some quotations and print them using fsi – it will give you a good idea of what code constructs the patterns represent. Alternatively, use the quotation visualizer mentioned above.

Another module, Quotations.DerivedPatterns, contains additional active patterns that are not needed in the strict sense, but that represent some common use cases for deconstructing a quotation. An example is

( |SpecificCall|_| ) : Expr -> (Expr -> (Type list * Expr list) option)

which is a variant of Call that takes an expression and matches if the quotation is the given method or function call. The beauty of this particular active pattern is that you can use quotations to match on the given quotation:

let recognizePlus quotation =
    match quotation with
    | SpecificCall <@ (+) @> (types,exprs) -> printfn "Plus! types=%A  exprs=%A" types exprs
    | _ -> printfn "something else"

> recognizePlus <@ 1 + 2 @>;;
Plus! types=[System.Int32; System.Int32; System.Int32]  exprs=[Value (1); Value (2)]

Come on, this is still a lot of work, isn’t it?

That last example has one major shortcoming, which will hit you pretty hard when you’re trying to do anything useful with quotations. Even when you’re only interested in one particular kind of node (say, you’re interested in doing something with all (+) calls), you still have to walk the whole expression tree in order to be sure that you’ve seen all the method calls. Consider:

> recognizePlus <@ 1 * (2 + 3) @>;;
something else

Why? Because the tree looks like:

Call (None, Int32 op_Multiply[Int32,Int32,Int32](Int32, Int32),
      [Value (1),
       Call (None, Int32 op_Addition[Int32,Int32,Int32](Int32, Int32),
             [Value (2), Value (3)])])

so we’re calling multiply first – and our function doesn’t do anything with that. In order to find all plus calls, we need to look through the whole tree recursively – including the multiply call’s children. But doesn’t that mean that we’ll have to rewrite our recognizePlus function to incorporate a match on all of the 32 active patterns in Quotations.Patterns (or at least those that return child expressions, which is pretty much all of them) just to be able to traverse the whole expression tree looking for a plus call?

Luckily, no. This is were the third module in the Quotations namespace comes in.

The secret sauce: Quotations.ExprShape

This module is really the workhorse of pretty much anything you’ll do with quotations. Now, I believe this will come as a surprise to most people – in fact, it took me a bit of luck (when I saw it being used in passing, in a post on hubfs) to really understand what this module was all about. It was one of those moments for which a beautiful German word exists: Aha-Erlebnis.

This module’s mystery is in no small part thanks to its“terse” documentation. In fact, it’s so short I’ll reproduce it completely here:

val RebuildShapeCombination : obj * Expr list -> Expr	Re-build combination expressions. The first parameter should be an object returned by the ShapeCombination case of the active pattern in this module.
val ( |ShapeVar|ShapeLambda|ShapeCombination| ) :   Expr -> Choice<Var,(Var * Expr),(obj * Expr list)>	An active pattern that performs a complete decomposition viewing the expression tree as a binding structure.

First, look at the active pattern. The key thing is that this active pattern is complete: every quotation will match with one of the three cases of the active pattern: either it is a variable (ShapeVar), a lambda (ShapeLambda)  or a “combination” (ShapeCombination). So, we now have a general and complete decomposition of any quotation, and it is short:

let workhorse quotation =
    match quotation with
    | ShapeVar v -> ()
    | ShapeLambda (v,expr) -> ()
    | ShapeCombination (o, exprs) -> ()

Notice if you paste this in an .fs file that the compiler does not complain about any missing match cases, reinforcing my point. So, now we can do this recursively, which gives us:

let rec traverse quotation =
    match quotation with
    | ShapeVar v -> ()
    | ShapeLambda (v,expr) -> traverse expr
    | ShapeCombination (o, exprs) -> List.map traverse exprs |> ignore

Here’s the beauty: this simple function traverses all the expressions and sub-expressions in any quotation. You don’t have to deal with all 32 cases in order to do something with one node. This function should be the basis of all your work with traversing quotations: anything you want to do, as far as inspecting the tree goes, can be built on top of this simple structure. Let’s revisit our earlier example:

let rec recognizePlus' quotation =
    match quotation with
    | SpecificCall <@ (+) @> (types,exprs) -> 
        printfn "Plus! types=%A  exprs=%A" types exprs
        List.map recognizePlus' exprs |> ignore
    | ShapeVar v -> ()
    | ShapeLambda (v,expr) -> recognizePlus' expr
    | ShapeCombination (o, exprs) -> List.map recognizePlus' exprs |> ignore

Let’s run this on our failing example of earlier:

> recognizePlus' <@ 1 * (2 + 3) @>;;
Plus! types=[System.Int32; System.Int32; System.Int32]  exprs=[Value (2); Value (3)]

It sure found the plus now.

Transforming quotations

So far, we’ve just been inspecting the quotation. Now let’s actually do something with it. Again, the ExprShape module will be a big win: the workhorse here is the ShapeCombination and RebuildShapeCombination duality.

You might have noticed the o parameter in the ShapeCombination; this is an opaque marker that stores how the sub-expressions in a shape combination can be put back together , i.e. whether it is a function call, a let binding, or anything else that has child expressions. This is were the function RebuildShapeCombination comes into play: given an o marker and the right number and type of child expressions, it can put an expression deconstructed by ShapeCombination back together . So, whereas above we wrote a general traversal function for quotations, a general transformation function looks like:

let rec transform quotation =
    match quotation with
    | ShapeVar v -> Expr.Var v
    | ShapeLambda (v,expr) -> Expr.Lambda (v,transform expr)
    | ShapeCombination (o, exprs) -> RebuildShapeCombination (o,List.map transform exprs)

This function takes any quotation and transforms it into itself, visiting, deconstructing and reconstructing every node in the expression tree along the way.

If you’re familiar with a zipper data structure, this reminds me of it: the active patterns “open the zipper” and the RebuildShapeCombination function “closes the zipper”. (Actually, I’m not sure that the sub-expressions get reused or are made anew, but it seemed familiar anyway.)

So, let’s do some transformation: let’s replace all calls to (+) with calls to (-). (Maniacal laugh and organ playing):

let rec evilTransform quotation =
    let minus l r = <@@ %%l - %%r @@>
    match quotation with
    | SpecificCall <@ (+) @> (types,l::r::[]) -> 
        minus (evilTransform l) (evilTransform r)
    | ShapeVar v -> Expr.Var v
    | ShapeLambda (v,expr) -> Expr.Lambda (v,evilTransform expr)
    | ShapeCombination (o, exprs) -> RebuildShapeCombination (o,List.map evilTransform exprs)

Ignoring the specifics of the actual transformation, which I’ll get to in a moment, notice that the structure of the transformation is exactly the same as above, except now we’ve added one pattern to deal with the case we’re interested in: a call to addition.  Essentially, this is saying: do something special for addition, and just traverse the tree, leaving it unchanged, for all the rest.

Splicing

Now, I know I said earlier that the Expr.Call static method is the dual of the Call active pattern, so you’d expect that I would have used that in the result of the SpecificCall match above. I could have done that, but instead I chose to demonstrate another useful technique for constructing expressions: splicing, denoted by the % or %% operator, for typed and untyped splicing respectively. All this operator does is insert an expression in a certain place (or places) into a quotation. So the minus function constructs a quotation that represents the subtraction of two given expressions (this doesn’t always make sense – in that case we’ll get a runtime exception with untyped quotations). Splicing is a very readable and versatile way of constructing expressions, because you can actually write your expressions in F# instead of using Expr.Call and friends.

The proof of the pudding

In the F# powerpack, there are some useful (but somewhat experimental) functions to actually compile and evaluate any F# quotation. The process is somewhat convoluted: the quotation trees are first translated to .NET Expressions, and then that API is used to compile them. This comes with a significant performance hit: code compiled using that route can be a factor of 5 slower. So don’t use it for optimization. So far, I haven’t run into any limitations yet, and it’s a nice way to check whether everything works:

let before = <@ 1 + 2 * 3 + 5 @>
let after = evilTransform <@ 1 + 2 * 3 + 5 @>
printfn "%A" <| before.EvalUntyped()
printfn "%A" <| after.EvalUntyped()

Shows:

12
-10

val evilTransform : Expr -> Expr
val before : Expr<int> =
  Call (None, Int32 op_Addition[Int32,Int32,Int32](Int32, Int32),
      [Call (None, Int32 op_Addition[Int32,Int32,Int32](Int32, Int32),
             [Value (1),
              Call (None, Int32 op_Multiply[Int32,Int32,Int32](Int32, Int32),
                    [Value (2), Value (3)])]), Value (5)])
val after : Expr =
  Call (None, Int32 op_Subtraction[Int32,Int32,Int32](Int32, Int32),
      [Call (None, Int32 op_Subtraction[Int32,Int32,Int32](Int32, Int32),
             [Value (1),
              Call (None, Int32 op_Multiply[Int32,Int32,Int32](Int32, Int32),
                    [Value (2), Value (3)])]), Value (5)])

Pretty cool, and it opens up all kinds of interesting possibilities. For example, you can write a lazy transformer, which inserts lazy and force in the appropriate places to simulate call-by-need semantics in F#. You can add side-effects to print the result of each call as it is evaluated. Or you can transform the expression in something completely different – SQL, PHP, FPGA instructions, whatever you want.

Conclusions

The three main things you should know about the quotations API:

1. Quotations.Expr and Quotations.Patterns are each other’s dual: they are used for constructing and deconstructing Expr types respectively;
2. Quotations.ExprShape contains the workhorse of any quotations-using implementation: a zipper-like pattern for traversing and transforming any quotation in a straightforward way;
3. Splicing is used to effectively and readably construct parameterized expressions as an alternative to Expr.Whatever calls.

Like I said before, I think the API strikes an excellent balance between simplicity and abstraction. F#’s features come together nicely to provide a clean development experience. I was somewhat afraid of quotations before, because I had an image in my mind that it would be messy, lots of work, and lots of special cases. Turns out it isn’t, and I hope this post will do its part in getting some more attention to this aspect of F#.

Download the example .fs file. Don’t forget to add references to FSharp.PowerPack and FSharp.PowerPack.Linq, if you want to run the dynamic compilation examples.

Technorati: F# quotations

Share this post :

Technet!

del.icio.us it!

del.iri.ous!

digg it!

dotnetkicks it!

reddit!

technorati!

How to deal with out parameters in F#

This is the third installment of my modest 'how to' series, where I try to highlight some in my opinion unappreciated (or under-marketed) gems of F#: little language features that pleasantly surprised me when I first learned about them.

Don't you hate out parameters? It's such a chore to use them: you need to declare a variable, pass it in the method with the out parameter modifier, and then check the results. Out parameters suck: they're just a poor excuse for not having to add a decent tuple type to your language. Unfortunately, some methods in the .NET framework use out parameters, and you might be dealing with some legacy code that uses them (some developers, apparently, think out parameters are the greatest idea since sliced bread).

Luckily, calling methods with out parameters is very easy in F#: they are converted to a tuple type automatically. For example, the Math.DivRem method has the following signature:

public static int DivRem(  int a,  int b,  out int result )

which calculates the quotient of two numbers and also returns the remainder in an output parameter (in F#, this is a byref parameter).

Using this method in F# is simple:

let (q,r) = Math.DivRem(n,d)

The out parameter has been automatically converted to the second element of the resulting tuple.

Technorati: F#,out parameters

How to change the accessibility of a constructor using implicit object construction

The recommended way to define a class in F# is by using so-called implicit object construction.  The more traditional (for C# programmers, that is) but typically more tedious explicit object construction syntax feels distinctly less "functional". In short, implicit construction relieves you of writing an explicit constructor for your class, and also allows you to use let and do clauses in the body of your class that take the place of static or instance initializers. Check out Robert Pickering's F# wiki for a nice overview.

The other day I was writing a class that needs only factory methods to construct it, a not so uncommon pattern. In C#, I wouldn't think twice about how to do this: just add a private or internal constructor, and a few public factory methods. This is also straightforward to do using F#'s explicit object construction syntax, but I wondered if it is possible using implicit construction. Turns out it is!

The trick is simple:

type Foo internal()=

static member FactoryMethod = new Foo()

Notice the position of the 'internal' modifier. Modifying the accessibility of the 'Foo' class proper is done in the usual way, by putting the modifier right after the 'type' keyword. You can even mix these up:

type internal Foo private()=

This defines an internal class with a private constructor.

Thanks to Brian and Tomas for helping me out on this one!

Technorati: F#,implicit object construction,syntax,accessibility modifier

How to use named arguments in F#

Named arguments are a little-known feature of F#, that is actually very useful when calling heavily overloaded members. The DateTime constructor is one such example: it has twelve overloads, and I can never remember what (in C#) DateTime d = new DateTime(2008,11,12) means. Is it December 11th or 11 November (as we would say it in Dutch)? Fortunately, in F# there is a nice solution for this: you can always use the names of the formal arguments to specify a named argument. This not only clarifies what overload you're calling, you can also easily change the order of the arguments. For example:

let d = new DateTime(month=12, day=11, year=2008)

makes it very clear that we're talking about December 11th here. If you're from the US, it even looks 'normal'. Europeans may like:

let d' = new DateTime(day=11, month=12, year=2008)

For F#, it's all the same.

You can also mix positional with named arguments, and if the object has setters, you can use these to. For details, read Section 8.4.5 in the F# (draft) language spec.

Technorati: F#,named arguments

How to invoke a method with type parameters using reflection (in F#)

Methods with type parameters arise naturally in F# code, for example:

type Example =
    static member Test l = List.rev l

'Test' has one type parameter 'a, the type of the elements of the list that is being reversed.

In F# you can call the Test method with a list of any type, and the compiler infers the type parameters for you:

let result = Example.Test [1;2;3]

The compiler infers that 'a must be an int.

Mainstream languages such as C# and VB.NET only infer the type arguments at the call site. The programmer needs to declare all the type parameters of a method explicitly. Consider the type signature of the following method:

type Example =
    static member Test2 (a,b) = (fst a = snd b)

Test2 has three type arguments: it takes two tuples a and b as its arguments, which is a total of four types. But since Test2 compares the first element of a with the second element of b, these two are inferred to have the same types. In C#, a programmer would have to infer this for herself, and write:

public static bool Test2<T, U, V>(Tuple<T, U> a, Tuple<V, T> b)
{
   return a.Fst == b.Snd;
}

(of course, assuming that a type Tuple would be defined in .NET, which is not the case if you're not using the F# core libraries)

Because it is obvious that such type annotations require much more work by the programmer, in C# and VB.NET type arguments to methods are in my experience much less common, and much less complex, than what is written without a second thought in F#.

However, recently I faced the problem of calling a number of static methods such as the above using reflection. I had the actual arguments to the method available, so for Test2 above I would have the (type-correct, of course) arguments (true,2.0) and ("whatever", false) available.

To call a method using reflection, you can use MethodInfo.Invoke, on a MethodInfo object obtained using typeof<Example>.GetMethod("Test2") or some such. Executing a non-generic method is easy - just call Invoke() with the actual arguments. However, System.Reflection refuses to call Invoke on a method with unspecified generic arguments (T,U and V for Test2) . You need to specify the actual arguments (bool, float and string for Test2 resp.) manually. So, I had to deduce these from the actual arguments given to the method. The following two functions demonstrate how to do this:

let rec resolve (a:Type) (f:Type) (acc:Dictionary<_,_>) =
    if f.IsGenericParameter then
        if not (acc.ContainsKey(f)) then acc.Add(f,a)
    else 
        Array.zip (a.GetGenericArguments()) (f.GetGenericArguments())
        |> Array.iter (fun (act,form) -> resolve act form acc)

let invokeMethod (m:MethodInfo) args =
    let m = if m.ContainsGenericParameters then
                let typeMap = new Dictionary<_,_>()
                Array.zip args (m.GetParameters()) 
                |> Array.iter (fun (a,f) -> 
                    resolve (a.GetType()) f.ParameterType typeMap)  
                let actuals = 
                    m.GetGenericArguments() 
                    |> Array.map (fun formal -> typeMap.[formal])
                m.MakeGenericMethod(actuals)
            else 
                m
    m.Invoke(null, args)

The second function, invokeMethod, can be used as a replacement for MethodInfo.Invoke that also works for methods with generic arguments. The function above only works for static methods, but taking away this restriction should be straightforward.

invokeMethod takes a MethodInfo m(which should be a static method) and the arguments you want to call the method with. First we check if m is a generic method. If not, nothing needs to be done and we can just call Invoke.

If m is a generic method, we build a a typeMap which maps the formal type arguments to their actual types, for which we can use the signature of the method on the one hand (i.e. as given by the MethodInfo), and the types of the actual arguments args. The function 'resolve' does most of the heavy lifting here, building up the typeMap by comparing actual and formal arguments in a pairwise fashion. 'resolve' needs to be called recursively, since type arguments may be nested arbitrarily deeply. For example,   the formal argument list<'a*option<'b>> should resolve with the actual argument list<int*option<bool>> by mapping 'a to int and 'b to bool.

Once we've determined the actual type arguments to the generic method, System.Reflection lets us instantiate an invoke-able method using MethodInfo.MakeGenericMethod(), which takes an array of actual types that fill in the generic type arguments to the method. If we've determined the type arguments correctly, the result of MakeGenericMethod() is another MethodInfo object that can be invoked as usual.

The interested reader can figure out the details.

Some notes:

• 'resolve' is not tail-recursive. I just didn't bother since you would need to write some extremely convoluted method arguments to blow the stack. list<list<list<list<(repeat x 1000 000)>>>> anyone? Also for the same reason I didn't worry about performance - I don't actually expect to have very deeply nested types. (if type classes were ever added to F#, I guess I would  need to start worrying about that...)
• I dislike that I used a Dictionary in there, though it seemed to be the most elegant solution. I tried using a Map, but then I had to merge maps when the recursive call to resolve returned. It seemed easier with a (non-functional) Dictionary. If anyone can do better, I'd like to hear about it.

Technorati: F#,System.Reflection