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 op_Addition to 1 and the result is again a function. The second application uses the function returned by the first application and passes 2 as 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 quotations using <@@ ... @@>. When you want to perform analysis of quotations, you need to get the underlying raw representation using the <@@@@ ... @@@@> 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 matches with efApps which in our case means that the expression is a mathematical operation. From the functional point of view efApps means series of function applications. The result of the Query function of efApps is a tuple containing expressions with information about the applied function (operator in our case) and parameters of this application.

For extracting the operator name we match the first value with efAnyTopDef 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 simple_expr, we can return the according simple_expr value.