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 a tree representation of a 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 a different language. This is very similar to the new C# 3.0 expression trees where you can get an expression tree from lambda expressions 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 an 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 a quoted expression (In VS.Net you can select code and hit Alt+Enter to send the 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 the addition in the first example is represented
as a function call (function application in the terminology of functional languages)
where the function is the
op_Addition operator and the parameters are
two integers. This is actually a little simplification, because in functional
programming you should look at this code as two function applications.
The first application binds the first parameter of
1 and the result is again a function. The second application uses
the function returned by the first application and passes
a 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 transformations of limited mathematical expressions from F# quotations to my data type. The discriminated union that I'm using as target of the transformation is similar to the union in the 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 the 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 the
Query functions on the expression
families defined in the
Raw module. This may sound a bit confusing,
but in 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 expressions. Following code should clarify 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 a function that converts a mathematical expression
quotation to a
simple_expr structure. It will be a recursive function
with similar structure as the previous one. The first match for the 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 then we'll have to loop through parameters passed to this function
and call the function recursively for 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 a
mathematical operation. From the functional point of view
series of function applications. The result of the
efApps is a tuple containing expressions with
information about the applied function (operator in our case) and parameters of
For extracting the operator name we match the first value with
which returns information about top-level definitions. The returned structure contains
the assembly name as well as the function name that we need. In the second step
we recursively call the
parse function to all arguments of the operator.
Once we know the function name and we have the arguments translated to
we can return the according
Published: Sunday, 28 May 2006, 3:58 PM
Author: Tomas Petricek
Typos: Send me a pull request!
Tags: meta-programming, f#