This is part 2 in my quotations series, following on from Tap, Tap, Tapping on the Door.
As promised in the first part of this series, here we're going to take a look at manipulating quotations. I mean, we've got this AST - now what are we going to do with it?
Let's start with something fairly straightforward; boolean algebra.
First, let's get a look at how some boolean expressions are represented in quotations.
Firing up F# Interactive, we'll feed a few in and see what happens:
1 2 3 4 5 6
Hmm. That's… not as nice as we might want. The custom attributes are being added by F# interactive for debugging purposes, but hopefully the general shape is clear: our expression consists of a single value of
I'll cut out the custom attributes from now on to make reading things a bit easier.
1 2 3 4 5
So. Looks like someone has decided to represent the
&& operator with the expression tree of an
if statement. Useful in some ways; after all, any logic we can apply to an
&& operator will equally apply to a logically equivalent
if statement. Checking the MSDN documentation for Expr.IfThenElse tells if that the 3 values above are
elseExpr. Which kind of makes sense; our
<@@ true && true @@> is being turned (loosely) into
if true then true else false - which is equivalent.
Let's put something other than plain boolean constants in to see if we can make it clearer.
1 2 3 4 5 6
Looks hopeful. As a last check, let's take advantage of the fact that quotations are structurally comparable to double check our understanding:
I'm going to take a wild punt that the
|| operator does something similar:
And it does. Excellent.
We've now got an idea what the expression trees are going to look like, but how do we go about manipulating them? The answer is the answer we always hope for when traversing data structure in F#: pattern matching.
Expr types are all recognized by a set of active patterns in the
Microsoft.FSharp.Quotations.Patterns module. The only problem is that there are about 40 cases in the active patterns, and at the moment we're only interested in one: the
That's sounding rather verbose for a language that's normally as succinct as F# and fortunately the language designers agreed. As well as the specific cases in the main
Patterns module, there are a number of other modules under the
Microsoft.FSharp.Quotations namespace that contain "broader" active patterns, and helper methods for rebuilding expressions.
Let's take the broadest set, from the
ExprShape module, and have a look at a method that takes in an expression, recursively works it way through the tree, and rebuilds it exactly as it was before:
1 2 3 4 5 6 7 8 9
So, as we recurse down there are three possibilities for our expression on any one pass through the
- We've hit a
Var: this is a leaf node holding a variable, we're done with this branch of the tree.
- We've hit a lambda function, with a variable being bound and an expression representing the body of the function. We apply
idto the body to continue recursing down.
- We've hit something else; anything else. The
ShapeCombinationpattern knows how to take the structure apart, and the
RebuildShapeCombinationmethod from the same module knows how to use the object
ShapeCombinationspits to put it back together again. In the mean time, we still apply
idto all the sub-expressions of the combination, whatever they may be.
(As an aside, don't actually call your functions
id - there's already a function called that in the standard library.)
Of course, on it's own that's not very exciting. But how about if before moving onto these very broad shapes, we first check some specific cases?
Let's see if we can detect
true literals within an expression.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Value pattern gives us an object representing a literal and it's type as a tuple. We'll add a guard condition to the pattern to specify that we're only interested when the type is
bool and (taking advantage of short circuiting to make sure we don't try and cast if it's not a bool!) when the value is
true. After that, we move back to our broader patterns, but this time we're happy to throw away most of the information at each step as we're not interested in
reconstructing the tree afterwards.
Loading up the function in F# Interactive, we can feed it some test inputs and see how we're doing.
1 2 3 4 5 6 7 8 9 10 11 12
Looks like we need just one final step before we start playing with the rules of boolean algebra; let's check we can detect the
First, let's give ourselves some helper active patterns of our own to detect literal
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Now, let's add some more for
1 2 3 4 5 6 7 8 9 10 11 12 13
Because you can nest patterns within a pattern match, here we're only matching
IfThenElse expressions where the 'then' clause (
||) is always
true or the 'else' clause (
&&) is always
And now, with all our pieces in place, let's pick one of the rules of boolean algebra and see if we can apply it. Commutativity sounds like it's probably the simplest:
1 2 3 4 5 6 7 8
Pretty simple: if we see a
&& or a
|| as the top expression in a quotation, swap the arguments. There's no recursion, so we won't go through the tree swapping every
|| expression, although we could if we wanted…
1 2 3 4 5 6 7 8 9
A nice simple function, to apply a nice simple rule. Generally you'll want to choose when to apply something like the
commute function, hence not making it recursive. But what about something like the identity law?
The identity law states that
true && x = x and
false || x = x for all x. This looks like it might allow us to remove redundant statements from our boolean expressions without changing the logical result, and if we're interested in carrying out this operation at all we almost certainly want to apply it recursively down through the expression.
Time to break out our broad
ExprShape patterns again:
1 2 3 4 5 6 7 8 9 10 11 12 13
Firstly, we check if the top of the quotation matches any of the four relevant conditions for the identity law. If any of them do, we bind the proposition that we're reducing to to the name
p, and then we carry on recursing down the tree.
Otherwise, we're back to the
id function above: a
Var is a leaf node, we
transform the body of any lambdas and if we hit a combination we
transform all of it's constituent expressions.
This is starting to reach the stage it's worth unit testing, so let's break out xUnit and add some "facts" (you'll need to reference xUnit manually or via NuGet to build the tests.)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
And there you have it, a function that takes an expression tree and manipulates it in a potentially useful fashion.
Why did we go to all this trouble? Well, I'm afraid for that, dear reader, you'll have to either wait for the next installment or come along to my session at Progressive F# London 2014 where we look at translating quotations into other languages.
If you want to look into this further yourself in the mean time, an implementation of all of the rules of boolean algebra and a basic test suite can be found in a gist on github.
If you're feeling really brave, I also highly recommend looking into "A Practical Theory of Language-Integrated Query":
- Talk by Philip Wadler
- Academic paper describing the techniques - the first few sections are very readable even without a background in programming language research, and definitely worth looking at before you get to…
- The practical implementation - if you want to watch people much cleverer than me really apply some of these principles.
That's all till next time, and I hope your brains recover sooner than mine.