David Dickson About me

Rewriting parts of an Expression Tree in F#


I am in the fortunate situation of working on a project where we make use of F# scripts to administer a production application. It’s a very compelling approach as it allows maintenance tasks to be carried out through domain objects, rather than modifying repositories directly. This ensures that when data maintenance is performed, all appropriate business rules are applied and data integrity is maintained.

For its persistence mechanism the application makes use of LINQ to SQL. Within the scripts we build adhoc queries using F# quotations that are subsequently transtated into LINQ expressions to query our repository. For example we make use of the F# power pack’s ToLinqExpression in the function below to convert a quotation into a consumable LINQ expression:

let toLinq (exp : Expr<'a -> 'b>) =
    let linq = exp.ToLinqExpression()
    let call = linq :?> MethodCallExpression
    let lambda = call.Arguments.[0] :?> LambdaExpression
    Expression.Lambda<Func<'a, 'b>>(lambda.Body, lambda.Parameters)

Recently when I upgraded the scripts to make use of the latest version of the F# power pack I found that previously working queries now caused our application to throw exceptions that LINQ to SQL had no supported translation to SQL. My investigation found that the cause of these errors were that the latest version of ToLinqExpression had been modified such that when a quotation made use of =, >, >=, <, <= or <> the created BinayExpression make use of a different method for its comparison. So for example if I have a binding like:

let example = toLinq (<@fun u -> u.FirstName = "Bob"@> : Expr<Account->bool>)

When converted to a LINQ expression the implementing method for the binary operation u.FirstName = “Bob” is set to use GenericEqualityIntrinsic whereas in the previous version it was set to use String.op_Equality. As a result the LINQ to SQL provider could no longer translate the expression tree into SQL.

Rewriting the expression tree

Having identified the issue, I decided to come up with a function to rewrite the problematic parts of the returned expression tree. Below is what I came up with.

let rec reWriteExpression  (exp:Expression) =
    let makeBinary e left right = Expression.MakeBinary(e, left, right) :> Expression 
    let modifyMethod (exp:BinaryExpression) = 
        match exp.NodeType with
        | ExpressionType.Equal as eq -> makeBinary eq exp.Left exp.Right
        | ExpressionType.GreaterThan as gt -> makeBinary gt exp.Left exp.Right
        | ExpressionType.GreaterThanOrEqual as gte -> makeBinary gte exp.Left exp.Right
        | ExpressionType.LessThan as lt -> makeBinary lt exp.Left exp.Right
        | ExpressionType.LessThanOrEqual as lte -> makeBinary lte exp.Left exp.Right
        | ExpressionType.NotEqual as ne -> makeBinary ne exp.Left exp.Right
        | _ -> makeBinary exp.NodeType (reWriteExpression exp.Left) (reWriteExpression exp.Right)
    match exp with
    | :? LambdaExpression -> 
        let l = exp :?> LambdaExpression
        Expression.Lambda(l.Type, reWriteExpression l.Body, l.Parameters) :> Expression
    | :? BinaryExpression -> modifyMethod (exp :?> BinaryExpression)
    | _ -> exp

For me, the ease by which I could come up with this rewrite highlighted two very powerful features of functional programming, namely pattern matching and recursion. Pattern matching is simply awesome. The simple syntax in modifyMethod to test for specific expression types makes expressing the program’s intent both clear and succinct. You can do all sorts of things with pattern matching, however, I won’t cover those details in this post. Similarly, routines on trees are often most easily expressed using recursion. This is natural because the tree is a recursive data type.

Considering the Command Pattern in F#

The command pattern describes a way to represent actions in an application. It is used to encapsulate actions so that they can be invoked at some later point. We often see collections of commands that specify steps of a process or operations that the user can choose from. Below is an object oriented way of implementing this pattern.

If we consider this pattern from a functional perspective, command objects are being used as functions. Indeed they are equivalent to functions. Thus it is arguable that the command pattern is more readily adopted in object oriented programming when there is a lack of support for higher order functions.

Object Oriented Example

Let’s look at a simple example. Say we are tasked to develop the software to control a robot by remote control. Following shows how we could implement this using the object oriented command pattern.

type Robot(position, rotate) =     
    let mutable (x,y) = position
    let mutable rotation = rotate
    member this.Move(distance) =
      x <- x + (distance * sin (System.Math.PI/180.0 * rotation))
      y <- y + (distance * cos (System.Math.PI/180.0 * rotation))
    member this.Rotate(angle) = 
    	let newRotation = 
    		let nr = rotation + angle
    		match nr with
    		| n when n < 360.0 -> nr
    		| _ -> nr - 360.0
    	rotation <- newRotation
type ICommand = 
    abstract Execute : unit -> unit
type Move(robot:Robot, distance) =
    interface ICommand with 
    	member this.Execute() = robot.Move(distance)
type Rotate(robot:Robot, rotation) = 
    interface ICommand with
    	member this.Execute() = robot.Rotate(rotation)
type RemoteControl(cmds: ICommand list) =
    let commands = cmds
    member this.RunCommands() = commands |> List.iter(fun c -> c.Execute())

Functional Solution

Below shows how we could implement the robot example drawing on functional constructs:

type Robot = {Position : float * float; Rotation : float}
let move distance robot = 
    let x2 = distance * sin (System.Math.PI/180.0 * robot.Rotation)        
    let y2 = distance * cos (System.Math.PI/180.0 * robot.Rotation)
    {robot with Position = (robot.Position |> fst) + x2, (robot.Position |> snd) + y2 }
let rotate angle robot = 
    let newRotation = 
      let nr = robot.Rotation + angle
    	match nr with
    	| n when n < 360.0 -> nr
    	| _ -> nr - 360.0
    {robot with Rotation = newRotation}
let remoteControl commands robot = 
    commands |> List.fold(fun w c -> c w) robot

You will notice that in the functional solution there is no command interface defined. The reason for this is because F# has support for higher order functions. An object oriented way to understand a function is to think of it is an interface with a single method. Thus in a functional language like F# the single method command interface becomes unnecessary.

Another difference is that in the provided functional solution the data (i.e. location of the robot) is independent of the functions that transform the data (move and rotate). The reason this is adopted is because one of the principles of functional programming is referential transparency. That is, for a given set of inputs at any point in time, a referentially transparent expression will return the same result. The benefit is that referentially transparent expressions are deterministic by definition. In supporting this principle the functional solution above makes variables immutable, and rather than modifying arguments, the processing functions return new variables.


The command pattern is used to represent some behaviour which you know needs done. In a functional language the need for this object oriented pattern is diminished because these behaviours can be encapsulated and passed around as functions. Design patterns are an interesting topic as they provide solutions to commonly occurring problems in software design. However, I really enjoy it when a language or framework can appropriately abstract me away from boilerplate code. In fact I think Paul Graham sums it up best:

“When I see patterns in my programs, I consider it a sign of trouble. The shape of a program should reflect only the problem it needs to solve. Any other regularity in the code is a sign, to me at least, that I’m using abstractions that aren’t powerful enough - often that I’m generating by hand the expansions of some macro that I need to write.”