F# - Simple quotations transofration

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 op_Addition to 1 and the result is again function. The second application uses the function returned by the first application and passes 2 as 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 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 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 quotation to 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 matches with efApps which in our case means that the expression is mathematical operation. From the functional point of view efApps means series of function applications. The result of Query function of efApps is tuple containing expression with information about applied function (operator in our case) and parameters of this application.

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

Tags: F# and MSR
(Published: May 28, 2006 15:58)

RE: F# - Simple quotations transofration by leppie (4/17/2008 8:51:44 AM)

What is a 'transofration'?

Send comments to this article

Hyperlinks are detected automatically and you can use **bold** and __italic__ to format your comment.

Title:
Name:
Url:

Remember me