The Book of F#: Breaking Free with Managed Functional Programming (2014)
Chapter 9. Can I Quote You on that?
Another feature introduced to the .NET Framework with LINQ is expression trees. Often using the same syntax as lambda expressions, expression trees compile not to executable code but instead into a tree structure that describes the code and can be parsed for translation to other forms. This type of programming is often called metaprogramming. Just as we can think of metadata as data that describes data, we can think of metaprogramming as code that describes code.
This chapter isn’t about expression trees, though; it’s about a similar construct in F# called a quoted expression, also known as a code quotation. Quoted expressions address the same basic problem as expression trees, but they take a fundamentally different approach. Let’s quickly compare expression trees to quoted expressions before diving into how to compose and parse quoted expressions within your F# code.
Comparing Expression Trees and Quoted Expressions
Expression trees are commonly used with LINQ providers to translate certain C# or Visual Basic expressions into SQL, but they aren’t only useful for translating code between languages. Sometimes expression trees are employed to add an extra degree of safety or readability to code that would otherwise be confusing or error-prone. Consider the INotifyPropertyChanged interface commonly used in WPF and Silverlight.
INotifyPropertyChanged defines a single member: an event with a string parameter, PropertyName, that identifies the property that changed and triggered the event. You raise the PropertyChanged event by creating a PropertyChangedEventArgs instance and passing the property name to the constructor as a string. This approach is error prone, though:Because there are no inherent checks around the string passed to the PropertyChangedEventArgs constructor, it’s possible to provide an invalid name. Expression trees can help avoid problems like this, as shown in the following C# class, which employs an expression tree to safely identify the changed property without resorting to obscene amounts of reflection code:
// C#
public class PropertyChangedExample
: INotifyPropertyChanged
{
public event PropertyChangedEventHandler PropertyChanged;
private string _myProperty = String.Empty;
public string MyProperty
{
get { return _myProperty; }
set
{
_myProperty = value;
RaisePropertyChangedEvent(①() => MyProperty);
}
}
protected void RaisePropertyChangedEvent<TValue>(
② Expression<Func<TValue>> propertyExpr)
{
if(PropertyChanged == null) return;
var memberExpr = ③(MemberExpression)propertyExpr.Body;
var ea = new PropertyChangedEventArgs(④ memberExpr.Member.Name);
PropertyChanged(this, ea);
}
}
The preceding example shows a twist on the typical pattern for implementing INotifyPropertyChanged. Instead of passing a magic string to the RaisePropertyChangedEvent method ①, it uses a lambda expression. This lambda expression isn’t compiled to a delegate, however. Instead, the C# compiler infers through the signature that it should compile the lambda expression to an expression tree ②. Inside the method, we then cast the expression’s body to MemberExpression at ③ so we can extract the property name and pass it to PropertyChangedEventArgsat ④.
Quoted expressions serve a similar purpose in F#, but unlike expression trees, they were designed with an emphasis on functional programming, not only with how they’re constructed but also with how they’re parsed. Furthermore, expression trees don’t support many important F#concepts. By contrast, quoted expressions are fully aware of concepts like currying, partial application, and recursive declarations (let rec). Finally, quoted expressions are designed for recursive parsing, which makes it almost trivial to walk the entire quoted structure.
You can rewrite the preceding C# class in F# using quoted expressions as follows:
// F#
open Microsoft.FSharp.Quotations
open Microsoft.FSharp.Quotations.Patterns
open System.ComponentModel
type PropertyChangedExample() as x =
let pce = Event<_, _>()
let mutable _myProperty = ""
① let triggerPce =
function
| ② PropertyGet(_, pi, _) ->
let ea = PropertyChangedEventArgs(pi.Name)
pce.Trigger(x, ea)
| _ -> failwith "PropertyGet quotation is required"
interface INotifyPropertyChanged with
[<CLIEvent>]
member x.PropertyChanged = pce.Publish
member x.MyProperty with get() = _myProperty
and set(value) = _myProperty <- value
triggerPce(③ <@@ x.MyProperty @@>)
This revised version of the PropertyChangedExample class is structured much like the C# version. As in the C# version, PropertyChangedEvent isn’t published directly. Instead, the triggerPce function at ①accepts a quoted expression and uses pattern matching to determine whether the supplied quoted expression represents getting the value of a property at ②. Finally, instead of a lambda expression in the call to triggerPce at③, the quoted expression is represented as a property reference enclosed within <@@ and @@>. By using a quoted expression, we allow the compiler to determine whether the supplied property is valid, rather than crossing our fingers and hoping we’ve entered the correct name. Using a quoted expression in this manner also protects us against future refactorings where we remove or rename a property but forget to update the string.
Despite their many similarities, quoted expressions and expression trees aren’t quite the same. First, there’s no built-in way to evaluate quoted expressions, nor is there any built-in way to translate between quoted expressions and expression trees. Should you need to perform either task, you’ll need to turn to the F# PowerPack, or another library that provides these capabilities. With the inclusion of query expressions (Chapter 10) in F# 3.0, however, these needs should be diminished.
Composing Quoted Expressions
Quoted expressions can take one of two forms: strongly typed and weakly typed. The distinction between the two forms is a bit of a misnomer because all quotation expressions are ultimately based upon either the Expr<'T> or Expr types found in the Microsoft.FSharp.Quotationsnamespace. In this context, strong and weak typing really indicates whether the quotation carries information about the expression type as opposed to describing the expression through its constituent parts. You can get a weakly typed quoted expression from a strongly typed one through itsRaw property.
In addition to the Expr and Expr<'T> types, the Microsoft.FSharp.Quotations namespace also includes the Var type. The Var type is used inside quoted expressions to describe binding information including a binding name, its data type, and whether the binding is mutable.
Regardless of whether a quoted expression is strongly or weakly typed, all quoted expressions are subject to a few constraints. First, object expressions are forbidden within quotations. Next, the quotation cannot resolve to a generic expression. Finally, the quotation must be a complete expression; that is, a quotation must do more than define a let binding. Attempting to create a quoted expression that violates any of these criteria will result in a compiler error.
Quoted Literals
To create a quoted expression, you simply need to enclose an expression within <@ and @> or <@@ and @@>, where the first form creates a strongly typed quoted expression and the second creates a weakly typed quoted expression. For example, to create a strongly typed quoted expression that represents multiplying two values, you could write something like this:
> open Microsoft.FSharp.Quotations
let x, y = 10, 10
let expr = <@ x * y @>;;
val x : int = 10
val y : int = 10
val expr : ① Expr<int> =
Call (None, op_Multiply, [PropertyGet (None, x, []), PropertyGet (None, y, [])])
In the preceding snippet, the underlying type of the quoted expression is ① Expr<int>. In this case, the compiler infers the quoted expression’s type as int and carries that type along with the expression. The expression’s value is a listing of the source expression’s constituent elements. We’ll dive into what the pieces mean and how to use them to decompose quoted expressions a bit later in this chapter.
Quoted expressions can be simple like the one in the preceding example, but they can also represent more complex expressions including lambda expressions. For instance, a lambda expression that multiplies two integers could be quoted like this:
> open Microsoft.FSharp.Quotations
let expr = <@ fun a b -> a * b @>;;
val expr : Expr<(int -> int -> int)> =
Lambda (a, Lambda (b, Call (None, op_Multiply, [a, b])))
Similarly, you can include multiple expressions in a single quoted expression. Here, a let bound function is defined and applied to two integer values:
> let expr = <@ let mult x y = x * y
mult 10 20 @>;;
val expr : Quotations.Expr<int> =
Let (mult, Lambda (x, Lambda (y, Call (None, op_Multiply, [x, y]))),
Application (Application (mult, Value (10)), Value (20)))
.NET Reflection
Another way to create a quoted expression is through standard .NET reflection. Normally, quoted expressions are created from nonexecutable code, but on occasion you may find that you’ve already defined a function that includes the code you want to quote. Rather than duplicating the code, you can decorate the function with the ReflectedDefinition attribute:
type Calc =
[<ReflectedDefinition>]
static member Multiply x y = x * y
Here, Multiply is compiled normally so it can be invoked directly, but the ReflectedDefinition attribute instructs the compiler to also generate a weakly typed quoted expression and embed the result within the compiled assembly. To access the generated quoted expression, you need to obtain a standard reflection MethodInfo object that represents the compiled method and pass it to the Expr class’s static TryGetReflectedDefinition method:
> let expr =
typeof<Calc>
.GetMethod("Multiply")
|> Expr.TryGetReflectedDefinition;;
val expr : Expr option =
Some Lambda (x, Lambda (y, Call (None, op_Multiply, [x, y])))
When you need to quote multiple values within a type, decorating each one with the ReflectedDefinition attribute can get tedious. Fortunately, you can also apply the attribute to modules and types to generate quoted expressions for each of their values or members, respectively.
Manual Composition
The final way to compose a quoted expression is to manually construct one by chaining the results of calls to the Expr type’s static methods. The Expr type defines over 40 methods that create new Expr instances, each representing the various constructs that can appear in a quoted expression.
The Expr methods are defined such that their purpose should be clear now that you know about the data structures and language constructs available to you in F#, so I won’t go into detail about each of them. There are two important things to note about the methods, though.
First, the method parameters are tupled so instead of currying multiple parameters, they must be provided in tupled form. Second, many of the methods—nearly 50 percent of them—use .NET reflection to construct the corresponding expression.
Building quoted expressions manually can be tedious, but it gives you the most control over how expressions are constructed. Perhaps more important, however, is that these methods allow you to build quoted expressions based on code that you don’t control and therefore can’t decorate with the ReflectedDefinition attribute.
To demonstrate the process of manually constructing a quoted expression, let’s walk through constructing a method that multiplies two values using the multiplication operator. To begin, we need to use reflection to access the Operators module where the multiplication operator is defined, like this:
let operators =
System.Type.GetType("Microsoft.FSharp.Core.Operators, FSharp.Core")
This binding uses a partially qualified name to identify the type we’re looking for. (We had to use reflection here because typeof<'T> and typedefof<'T> don’t work on modules.) Now that we have a reference to the Operators module, we can obtain a reference to the multiplication operator method by its name, op_Multiply, with the GetMethod method:
let multiplyOperator = operators.GetMethod("op_Multiply")
Next, we inspect the returned MethodInfo to retrieve each of the operator’s parameters. To include these parameters in our expression, we need to create Var instances from the corresponding PropertyInfo instances. We can easily perform this transformation by mapping each parameter through the Array.map function. For convenience, we can also use an Array pattern to convert the resulting array into a tuple, as shown here:
let varX, varY =
multiplyOperator.GetParameters()
|> Array.map (fun p -> Var(p.Name, p.ParameterType))
|> (function | [| x; y |] -> x, y
| _ -> failwith "not supported")
We now have enough information to construct the quoted expression:
let call = Expr.Call(multiplyOperator, [ Expr.Var(varX); Expr.Var(varY) ])
let innerLambda = Expr.Lambda(varY, call)
let outerLambda = Expr.Lambda(varX, innerLambda)
The preceding bindings incrementally construct a quoted expression representing a curried function that multiplies two values. As you can see, the quoted expression contains a method call for the multiplication operator, an inner lambda expression that applies the y value, and an outer lambda expression that applies the x value. If you were to inspect the value of outerLambda, you should see the resulting expression represented like this:
val outerLambda : Expr =
Lambda (x, Lambda (y, Call (None, op_Multiply, [x, y])))
After all this work, we finally have a quoted expression that’s equivalent to this weakly typed expression:
<@@ fun x y -> x * y @@>
For your convenience, I’m including the previous examples in their entirety here so you can see all the parts working together.
let operators =
System.Type.GetType("Microsoft.FSharp.Core.Operators, FSharp.Core")
let multiplyOperator = operators.GetMethod("op_Multiply")
let varX, varY =
multiplyOperator.GetParameters()
|> Array.map (fun p -> Var(p.Name, p.ParameterType))
|> (function | [| x; y |] -> x, y
| _ -> failwith "not supported")
let call = Expr.Call(multiplyOperator, [ Expr.Var(varX); Expr.Var(varY) ])
let innerLambda = Expr.Lambda(varY, call)
let outerLambda = Expr.Lambda(varX, innerLambda)
Splicing Quoted Expressions
If you need to combine multiple quoted expressions, you could manually construct a new quoted expression by passing each one to the appropriate static method on the Expr class (typically Call), but there’s a much easier way: You can create a new literal quoted expression by splicing them together using the splicing operators. For example, suppose you have the following sequence and strongly typed quoted expressions:
let numbers = seq { 1..10 }
let sum = <@ Seq.sum numbers @>
let count = <@ Seq.length numbers @>
You can combine sum and count into a third quoted expression that represents calculating the average from a sequence using the strongly typed splice operator (%) like this:
let avgExpr = <@ %sum / %count @>
Weakly typed quoted expressions can be spliced, too. If sum and count had been defined as weakly typed quoted expressions (via the <@@ ... @@> syntax), you could splice them with the weakly typed splice operator (%%) like this:
let avgExpr = <@@ %%sum / %%count @@>
Decomposing Quoted Expressions
While code quotations can be useful for helping you understand the structure of code, most of their power comes from decomposition. F# includes three modules, also within the Microsoft.FSharp.Quotations namespace, that define a plethora of complete and partial active patterns that you can use todecompose a quoted expression to its constituent parts at varying degrees of granularity.
§ Pattern module. The partial active patterns in the Pattern module match the elementary F# language features such as function calls, function applications, looping constructs, raw values, binding definitions, and object creation. They correspond nearly one-to-one with the functions defined on the Expr type, helping you identify which pattern to use for the most common expressions.
§ DerivedPatterns module. The DerivedPatterns module includes partial active patterns that primarily match quoted expressions representing primitive literals, basic Boolean operators such as && and ||, and constructs decorated with ReflectedDefinition.
§ ExprShape module. The ExprShape module defines a complete active pattern with three cases: ShapeVar, ShapeLambda, and ShapeCombination. It’s designed for use in recursive pattern matching so you can easily traverse a quoted expression, matching every expression along the way.
Parsing Quoted Expressions
Rather than going into detail about the specific active patterns defined in each module, I think it’s more helpful to see how they work together. We’ll start with a typical example, where a sampling of patterns from each module is used to build a string that represents the quoted F# syntax.
open System.Text
open Microsoft.FSharp.Quotations.Patterns
open Microsoft.FSharp.Quotations.DerivedPatterns
open Microsoft.FSharp.Quotations.ExprShape
let rec showSyntax =
function
| Int32 v ->
sprintf "%i" v
| Value (v, _) ->
sprintf "%s" (v.ToString())
| SpecificCall <@@ (+) @@> (_, _, exprs) ->
let left = showSyntax exprs.Head
let right = showSyntax exprs.Tail.Head
sprintf "%s + %s" left right
| SpecificCall <@@ (-) @@> (_, _, exprs) ->
let left = showSyntax exprs.Head
let right = showSyntax exprs.Tail.Head
sprintf "%s - %s" left right
| Call (opt, mi, exprs) ->
let owner = match opt with
| Some expr -> showSyntax expr
| None -> sprintf "%s" mi.DeclaringType.Name
if exprs.IsEmpty then
sprintf "%s.%s ()" owner mi.Name
else
let sb = StringBuilder(showSyntax exprs.Head)
exprs.Tail
|> List.iter (fun expr ->
sb
.Append(",")
.Append(showSyntax expr) |> ignore)
sprintf "%s.%s (%s)" owner mi.Name (sb.ToString())
| ShapeVar var ->
sprintf "%A" var
| ShapeLambda (p, body) ->
sprintf "fun %s -> %s" p.Name (showSyntax body)
| ShapeCombination (o, exprs) ->
let sb = StringBuilder()
exprs |> List.iter (fun expr -> sb.Append(showSyntax expr) |> ignore)
sb.ToString()
The preceding example may look intimidating, but despite including a number of match cases, it’s really not particularly complicated when you break it down. The first thing to note is that the showSyntax function is recursive, which allows us to traverse the tree with any nested expressions we encounter. Each of the match cases belongs to one of the three quoted expression modules and matches a particular type of expression. I won’t go into detail about the bodies of each case since they don’t introduce any new concepts, but I encourage you to experiment with them.
The first two cases, Int32 and Value, match individual literal values. The Int32 pattern is a derived pattern that matches only integer values, whereas Value is a basic pattern that matches any literal value. As you can see from the definitions, both of these patterns extract the literal value. The Value pattern also extracts the corresponding data type, but since we’re not using it here we simply discard it with the Wildcard pattern.
Following the Value case are two SpecificCall cases and a generalized Call case. The SpecificCall cases are derived patterns that match calls to the addition and subtraction operators (as inline weakly typed quoted expressions), respectively. The Call case, on the other hand, is a basic pattern that matches any function call. The SpecificCall cases are much simpler than the Call case because we can make certain assumptions about the code given that we know more about what constitutes a match. The Call case needs to do more work to expand the expression.
Finally, we reach the last three cases: ShapeVar, ShapeLambda, and ShapeCombination. The simplest of these, ShapeVar, matches any variable definition. (Note that the term variable is preferable to binding here because it represents a placeholder within the code.) The value captured by ShapeVar includes information such as the variable name, its data type, and mutability. ShapeLambda matches any lambda expression, capturing its parameter definition and body as a nested expression. The last case, ShapeCombination, matches any other expression and is included here for completeness.
To see the showSyntax function in action, you can pass in any quoted expression. Just remember that this implementation hardly covers every possible case, so with more complex expressions your results will probably be less than stellar. For starters, though, here are a few sample inputs and results:
> showSyntax <@ fun x y -> x + y @>;;
val it : string = "fun x -> fun y -> x + y"
> showSyntax <@ fun x y -> x - y @>;;
val it : string = "fun x -> fun y -> x - y"
> showSyntax <@ 10 * 20 @>;;
val it : string = "Operators.op_Multiply (10,20)"
> showSyntax <@@ System.Math.Max(10, 20) @@>;;
val it : string = "Math.Max (10,20)"
Substituting Reflection
Just as you can use expression trees to enable reflection-like capabilities (as you saw at the beginning of this chapter), you can use quoted expressions to achieve a similar effect. To demonstrate, I’ll use an adapted version of a sample I found extremely helpful when I was first learning about quoted expressions.
This example, found in its original form at http://fssnip.net/eu/, defines a module that makes extensive use of higher-order functions, partial application, and quoted expressions, letting you define ad hoc validation functions for your types. We’ll start with the full listing and break it down after you’ve had a chance to digest it.
module Validation =
open System
open Microsoft.FSharp.Quotations
open Microsoft.FSharp.Quotations.Patterns
type Test<'e> = | Test of ('e -> (string * string) option)
① let private add (quote : Expr<'x>) message args validate (xs : Test<'e> list) =
let propName, eval =
match quote with
| PropertyGet (_, p, _) -> p.Name, fun x -> p.GetValue(x, [||])
| Value (_, ty) when ty = typeof<'e> -> "x", box
| _ -> failwith "Unsupported expression"
let test entity =
let value = eval entity
if validate (unbox value) then None
else Some (propName, String.Format(message, Array.ofList (value :: args)))
Test(test) :: xs
② let notNull quote =
let validator = (fun v -> v <> null)
add quote "Is a required field" [] validator
③ let notEmpty quote =
add quote "Cannot be empty" [] (String.IsNullOrWhiteSpace >> not)
④ let between quote min max =
let validator = (fun v -> v >= min && v <= max)
add quote "Must be at least {2} and greater than {1}" [min; max] validator
⑤ let createValidator (f : 'e -> Test<'e> list -> Test<'e> list) =
let entries = f Unchecked.defaultof<_> []
fun entity -> List.choose (fun (Test test) -> test entity) entries
The Validation module’s heart is the private add function at ①. This function accepts five parameters that each participate in the validation. Of primary interest are the first parameter, quote; the third parameter, validate; and the final parameter, xs. These represent the quotation that identifies the property being validated, a validation function, and a list of test functions, respectively.
Inside add, we first attempt to match quote against the PropertyGet and Value active patterns to appropriately extract the value from the source object so it can be passed to the validation function later. Next, we define a function, test, that invokes the supplied validate function and returns an option indicating whether the extracted value is valid. Finally, the test function is wrapped inside the Test union case and prepended to xs, and the entire list is returned.
With the add function in place, we define a variety of functions that return partially applied versions of add, giving us an expressive validation syntax. In this example, we’ve defined notNull ②, notEmpty ③, and between ④. Each of these functions accepts a quoted expression that’s applied to add along with the next three parameters, resulting in new functions that accept only a list of Test union cases and return the same.
The createValidator ⑤ function is the primary entry point into the Validation module. createValidator accepts a curried function whose arguments include a generic value and a list of Test union cases (of the same generic type), and ultimately returns another list of Test union cases. Notice how the second parameter and return value correspond to the functions returned by the notNull, notEmpty, and between functions. The implication here is that we can compose a validation function to pass into createValidator for arbitrary invocation later.
Now that the Validation module is fully defined, we can see how to use it. Let’s begin by opening the Validation module and defining a simple record type definition that we can validate against.
open Validation
type TestType = { ObjectValue : obj
StringValue : string
IntValue : int }
There’s nothing particularly notable about this type; it merely includes three labels we can reference for validation. Now we can create a validation method by calling createValidator like this:
let validate =
createValidator <| fun x -> notNull <@ x.ObjectValue @> >>
notEmpty <@ x.StringValue @> >>
between <@ x.IntValue @> 1 100
Here, we’ve chained together calls to notNull, notEmpty, and between using the composition operator within the function we pass to createValidator. The resulting function (returned from createValidator) is then bound to validate. Each of the chained calls includes a quoted expression that identifies one of TestType’s labels. You can even see here how F#’s type inference has played a role in determining the type of x in this expression.
All we need to do now is invoke the validate function by passing it instances of TestType. When all values satisfy the validation, validate simply returns an empty list like this:
> { ObjectValue = obj(); StringValue = "Sample"; IntValue = 35 }
|> validate;;
val it : (string * string) list = []
On the other hand, when one or more values fail validation, the validate function returns a list including the name of the member that failed along with a failure message, as shown here where all three values fail:
> { ObjectValue = null; StringValue = ""; IntValue = 1000 }
|> validate;;
val it : (string * string) list =
[("IntValue", "Must be at least 100 and greater than 1");
("StringValue", "Cannot be empty"); ("ObjectValue", "Is a required field")]
Summary
Although quoted expressions serve much the same purpose as the expression trees introduced with LINQ, F#’s quoted expressions are more finely tuned for functional programming. As you’ve seen, you can construct quoted expressions as literal expressions, directly through reflection with the ReflectedDefinition attribute, or programmatically with reflection and the static methods on the Expr class. Quoted expressions derive their true power from their decomposition, however. By using the active patterns defined in the Patterns, DerivedPatterns, and ExprShapemodules, you can decompose a quoted expression at varying degrees of granularity to accomplish a variety of tasks such as language translation or even flexible validation.