F# - Simple quotations transformation
This article describes very simple code that I wrote while learning how to work with the F# quotations library. Using the F# quotations you can get tree representation of the quoted expression. This allows you to write code that takes code written in F# as data and performs some code analysis or compiles/translates that code to different language. This is very similar to the new C# 3.0 expression trees where you can get expression tree from lambda expression and translate this tree for example to SQL (using DLINQ). However expression trees in C# 3.0 are very limited when compared with F# quotations, so that's one of the many reasons why F# is interesting language.
Introduction to F# quotations
If you want to see how F# represents some expressions you can try it in the FSI (F# interactive). First you need to open three modules that contain functions for working with quotations:
open Microsoft.FSharp.Quotations;; open Microsoft.FSharp.Quotations.Raw;; open Microsoft.FSharp.Quotations.Typed;;
Now you can see the internal representation of quotations by writing quoted expression (In VS.Net you can select code and hit Alt+Enter to sent selected code to F# interactive).
<@ 1 + 2 @> val it : int expr = <@ Microsoft.FSharp.MLLib.Pervasives.op_Addition (Int32 1) (Int32 2) @>
One more example with two operators:
<@ 1 + 10/5 @> val it : int expr = <@ Microsoft.FSharp.MLLib.Pervasives.op_Addition (Int32 1) (Microsoft.FSharp.MLLib.Pervasives.op_Division (Int32 10) (Int32 5)) @>
It is not difficult to understand that addition in the first example is represented
as function call (function application in the terminology of functional languages)
where the function is
op_Addition operator and parameters are
two integers. This is actually little simplification, because in functional
programming you should look at this code as two function applications.
The first application binds first parameter of
1 and the result is again function. The second application uses
the function returned by the first application and passes
parameter. You can look at F# quotations using both approaches and in the
rest of the article I will use the first one.
To demonstrate how to work with F# quotations I decided to write simple transformation of limited mathematical expressions from F# quotations to my data type. The discriminated union that I'm using as target of transformation is similar to the union in F# source file VS.Net template (as you can see it supports only four most basic mathematical operations and all values are stored as integers):
type simple_expr = | Int of int | Add of simple_expr * simple_expr | Sub of simple_expr * simple_expr | Mul of simple_expr * simple_expr | Div of simple_expr * simple_expr;;
Printing and evaluation of this structure is simple, so I won't describe these here. If you want to look at these functions see attached source code. (function for evaluation is part of VS.Net template too).
Working with quotations
Finally, let's do the interesting part :-). As I mentioned you can get
<@ ... @>. When you want to perform
analysis of quotations, you need to get the underlying raw representation
<@@ ... @@> operators. For decomposing the
quoted expression we can use
Query functions on the expression
families defined in the
Raw module. This may sound a bit confusing,
but in the simple words - the
Raw module contains several
values that define language constructs (like constants, variables, function
application and others) and you can use these values for matching and decomposing
quoted expression. Following code should clear this a bit:
let what_is x = match Raw.efInt32.Query x with | Some (_) -> "number"; | _ -> match Raw.efApps.Query x with | Some (_) -> "application"; | _ -> "something else..."; // Prints "number" print_string (what_is <@@ 1 @@>); // Prints "application" print_string (what_is <@@ 1 + 2 @@>);
Now we can start writing function that converts mathematical expression
simple_expr structure. It will be recursive function
with similar structure as previous. The first match for conversion of numbers
will be simple. In the second match we'll have to do two things. First we'll
need to determine what function is applied (whether it is addition, subtraction,
etc..) and than we'll have to loop through parameters passed to this function
and call the function recursively each parameter.
let rec parse x = match Raw.efInt32.Query x with // x contains the number so we can simply return Int(x) | Some (x) -> Int(x); | _ -> match Raw.efApps.Query x with | Some (op,args) -> // op contains quoted reference to function (operator) // so we need to extract name of applied function from it let opname = ( match Raw.efAnyTopDefn.Query op with // operators are top-level definitons so we extract name // from 'a' that contains info about the definiton | Some (a,_) -> let t1,t2 = a.topDefPath in t2 | _ -> failwith ("Function is not a top level definition."); ) in // Recursively translate arguments to simple_expr // and convert returned list to array let av = List.to_array(List.map (fun arg -> parse arg) args) in // Finally, match the operation name with basic // operator names and return according simple_expr value (match opname with | "op_Addition" -> Add(av.(0),av.(1)) | "op_Subtraction" -> Sub(av.(0),av.(1)) | "op_Multiply" -> Mul(av.(0),av.(1)) | "op_Division" -> Div(av.(0),av.(1)) | _ -> // some other operation - error failwith "Not supported operation"); | _ -> // something else than efApps and efInt32 - error failwith "Not supported construction in expression.";;
As I mentioned, the more interesting part of the code is when the quotation
efApps which in our case means that the expression is
mathematical operation. From the functional point of view
series of function applications. The result of
efApps is tuple containing expression with
information about applied function (operator in our case) and parameters of
For extracting operator name we match the first value with
which returns information about top-level definitions. Returned structure contains
assembly name as well as the function name that we need. In the second step
we recursively call
parse function to all arguments of operator.
Once we know the function name and we have arguments translated to
we can return the according
- RE: F# - Simple quotations transofration by leppie (4/17/2008 8:51:44 AM)
What is a 'transofration'?
- RE: F# - Simple quotations transofration by vijay (7/18/2009 3:01:38 PM)
Ya mistake transformation.
- RE: F# - Simple quotations transofration by Jason Yandell (2/15/2010 5:04:23 AM)
Thanks for this article, it explains a cool language feature nicely
- RE: F# - Simple quotations transofration by Tomas (3/9/2010 3:52:52 AM)
Finally fixed :-).