WORK-IN-PROGRESS: - this material is still under development
Capture the parse tree of a code fragment to manipulate it with DSL processing code.
When you write code in a closure, that code available to be executed at some future time. Parse Tree Manipulation allows you not just to execute the code but to also examine and modify its parse tree.
In order to use Parse Tree Manipulation you need a programming environment that supports taking a code fragment and turning it into a parse tree that you can work with. This is a relatively rare feature of a programming language, rare both in that few languages support it and rare in that even when it is supported it's usually rarely used. While I've not made any kind of detailed survey of tools that support this, I can use the ones I have to give a rough picture of how might use this kind of capability. The three examples I'll talk about are C# (from version 3.0), Ruby's ParseTree library, and Lisp.
C# and ParseTree both operate in a similar way, you invoke a library call on a fragment of source code and the library returns a data structure of that code's parse tree. In C# you can only do this on an expression inside a lambda. The limitation to expressions means you can't take code with multiple statements. ParseTree allows you to take a class, a method, or a string containing ruby code.
In C# the returned data structure is a hierarchy of expression objects. These objects are purpose built for representing parse trees, with an inheritance hierarchy for different kinds of operator. ParseTree returns nested ruby arrays, with simple built in types such as symbols and strings as leaves.
In both C# and Ruby cases you then write a tree walker to walk the parse tree and examine it. In C# the parse tree is immutable, but you can transform the parse tree by copying it and modifying it as you copy. Both libraries provide a mechanism to taking a sub-tree and turning it back into executable code.
The approach Lisp takes is rather different. Lisp source is itself essentially a serialized parse tree of nested lists. Lisp provides syntactic macros that allow you to examine and manipulate any lisp expression. The programming style is different, as it uses macros, but you can achieve much the same effects.
Although Parse Tree Manipulation allows you write an expression in your host language, you usually can't use any expression you like. There are are usually limits to what you can handle in expressions. In these situations it's important fail-fast should you get an expression that you can't handle. Usually when you walk over a parse-tree, you know the nodes in that tree will conform to what you expect. With Parse Tree Manipulation your parse tree can contain any legal construct in the host language, so you have to do some checking yourself as you walk it.
Usually you won't need, or want, to walk the entire parse tree of the expression. Most cases involve walking some of the tree, but leaving substantial sub-trees for evaluation. That way you don't have to build an entire parser, just parse the bits you need to populate your semantic model, and evaluate sub-trees as soon as you don't need to do further navigation.
Parse Tree Manipulation allows you to express logic in your host programming language and then manipulate that expression with more flexibility than you otherwise would be able to. With that given, a driving reason to use Parse Tree Manipulation is when you want to use the fuller range of the host language to express something, rather than the pidgin of the usual internal DSL constructs.
Being able to make use of the host language isn't the whole point of using Parse Tree Manipulation. After all one of the advantages of internal DSLs is that you can freely intermix the full host language with DSLish constructs as much as you like. The key difference is that usually you can only manipulate the executable results of the host language - you can't dive into host language expressions and manipulate their structure.
Even so there's not that many examples when you need to use Parse Tree Manipulation for a DSL. (Like most things Parse Tree Manipulation has many uses outside of a DSL context, which I'm not going to touch on here.) One of the best ones to consider is the driving force behind .NET's support for Parse Tree Manipulation - Linq.
Linq allows you to express query conditions - essentially Boolean expressions - using the standard .NET languages. These conditions can then be evaluated on .NET data structures - that much is trivial. The interesting thing is to take a C# condition and turn it into a SQL query - this allows you to write database queries without knowing SQL, or to write queries that be executed against different data sources. In order to pull this off you need to take the C# condition, turn it into a parse tree, and then walk the parse tree and generate the equivalent SQL. Essentially you are doing source-to-source translation from C# or SQL (or some other target). Parse Tree Manipulation is good for these cases as it allows you to use a familiar syntax for your conditions when your target language is not well known or you want multiple targets.
Another way to use Parse Tree Manipulation is to change the parse tree to carry out a useful manipulation. One example is that you could change all method calls on a certain object to be redirected to another object instead. [TBD: Need to come up with a decent example for this kind of thing - preferably in the DSL context].
Some of you may be familiar with the IMAP protocol for interacting with email servers. If you use IMAP you're email stays on the server and is brought down to the client only for reading or caching. As a result if you want to search your email that search needs to be done on the server.
To search with IMAP, your email client sends a search
request. The search request is, like all IMAP commands, a
string. In the case for search there is a DSL that's used to
express the search conditions. I'll not go into all the details
here (if you want the details, go to http://tools.ietf.org/html/rfc3501.)
but just do a simple example. Let's say I want to find all emails
containing the phrase 'entity framework' send by someone other than at
ayende.com since 23rd of June 2008. Using IMAP I would encode this
query in a search command as SEARCH subject "entity
framework" sentsince 23-jun-2008 not from "@ayende.com".
IMAP's search command DSL provides a good domain specific query language for email. For this exercise however we want to express our query in C#, like this.
var threshold = new DateTime(2008, 06, 23);
var builder = new ImapQueryBuilder((q) =>
(q.Subject == "entity framework")
&& (q.Date >= threshold)
&& ("@ayende.com" != q.From));
My first step, is to create a Semantic Model for the IMAP output. This is a simple IMAP query object that contains elements for each clause in the query, these elements will be and-ed together to form the complete query.
class ImapQuery...
internal List<ImapQueryElement> elements = new List<ImapQueryElement>();
public void AddElement(ImapQueryElement element) {
elements.Add(element);
}
interface ImapQueryElement {
string ToImap();
}
I'm declaring an interface here for the query elements. This
interface has two implementations: one to handle the basic query
clauses (from "@ayende.com") and the other
to handle negations (not).
class BasicElement : ImapQueryElement {
private readonly string name;
private readonly object value;
public BasicElement(string name, object value) {
this.name = name.ToLower();
this.value = value;
validate().AssertOK();
}
class NegationElement : ImapQueryElement {
private readonly BasicElement child;
public NegationElement(BasicElement child) {
this.child = child;
}
Although this query is a conjunction, IMAP can express general Boolean expressions. Doing so is more awkward, but then most email queries can be handled very nicely as a conjunction. This is a case where IMAP makes the common case easy, but allows you to be more expressive in the relatively rare cases that need it. For my purposes, illustrating this pattern, a simple conjunction will do fine.
Each basic query element has a keyword and value, mirroring the way IMAP forms its search language. In this situation I'm adding some error checking into each element, throwing an exception should any of them be in error.
class BasicElement...
private Notification validate() {
var result = new Notification();
if (null == Name)
result.AddError("Name is null");
if (null == Value)
result.AddError("Value is null");
if (!stringCriteria.Contains(Name) && !dateCriteria.Contains(Name))
result.AddError("Unknown criteria: {0}", Name);
if (stringCriteria.Contains(Name) && !(Value is string))
result.AddError("{0} needs a string argument, got {1}", Name, Value.GetType());
if (dateCriteria.Contains(Name) && !(Value is DateTime))
result.AddError("{0} needs a DateTime argument, got {1}", Name, Value.GetType());
return result;
}
private readonly static string[] stringCriteria = { "subject", "to", "from", "cc" };
private readonly static string[] dateCriteria =
{ "since", "before", "on", "sentbefore", "sentsince", "senton"};
class Notification...
public void AssertOK() {
if (HasErrors) throw new ValidationException(this);
}
With this push-button interface, I can construct the model for my query like this
var expected = new ImapQuery();
expected.AddElement(new BasicElement("subject", "entity framework"));
expected.AddElement(new BasicElement("since", new DateTime(2008, 6, 23)));
expected.AddElement(new NegationElement(
new BasicElement("from", "@ayende.com")));
With a semantic model in place, I can now generate the code for the IMAP search command. This is very simple code generation, just pushing out the result for each IMAP element.
class ImapQuery...
public string ToImap() {
var result = "";
foreach (var e in elements) result += e.ToImap();
return result.Trim();
}
class BasicElement...
public string ToImap() {
return String.Format("{0} {1} ", name, imapValue);
}
private string imapValue {
get {
if (value is string) return "\"" + value + "\"";
if (value is DateTime) return imapDate((DateTime)value);
return "";
}
}
private string imapDate(DateTime d) {
return d.ToString("dd-MMM-yyyy");
}
class NegationElement...
public string ToImap() {
return String.Format("not {0}", child.ToImap());
}
The semantic model allows me to represent and generate search commands for IMAP queries (or at least the subset of IMAP queries I'm using here. Now lets look at the builder to create them from C#.
The builder takes an appropriate lambda in its constructor.
class ImapQueryBuilder...
private Expression<Func<ImapQueryCriteria, bool>> lambda;
public ImapQueryBuilder(Expression<Func<ImapQueryCriteria, bool>> func) {
lambda = func;
}
In order to write the expression in the closure, we need some object that can act as the receiver for the keywords of the query ("Subject", "Sent", "From"). This object won't ever do anything at run-time, it's only there to provide the methods to help me compose the query. As a result the return values of its methods are irrelevant as they'll never actually be called.
class ImapQueryBuilder...
internal class ImapQueryCriteria {
public string Subject {get { return ""; }}
public string To {get { return ""; }}
public DateTime Sent {get { return DateTime.Now; }}
public string From {get { return ""; }}
To build the query I use a lazily evaluated property.
class ImapQueryBuilder...
public ImapQuery Content {
get {
if (null == content) {
content = new ImapQuery();
populateFrom(lambda.Body);
}
return content;
}
}
private ImapQuery content;
The heart of the work is done by populateFrom -
a recursive tree walk.
class ImapQueryBuilder...
private void populateFrom(Expression e) {
var node = e as BinaryExpression;
if (null == node)
throw new BuilderException("Wrong node class", node);
if (e.NodeType == ExpressionType.AndAlso) {
populateFrom(node.Left);
populateFrom(node.Right);
}
else
content.AddElement(new ElementBuilder(node).Content);
}
At this point I confront the fact that despite my desire to
allow clients to construct IMAP queries in C# - they can't use
any C#. My semantic model can only handle a subset of
possible C# expressions. The expression must consist of one or
more element expressions connected by the
&& operator. Each of these element nodes
must be a particular binary operator for which one side must be
a keyword - a call to an IMAP query criteria object. There are
then rules about what operators go with which
keywords. String-oriented keywords ("from", "subject", "to") can
only take == and !=. Date-oriented
keywords ("sent", "date") can take any equality or comparison
operators.
As a result I know that the only elements I'll have to
navigate through are binary expressions, so
populateFrom throws an exception if it sees
anything else. If the operator in the expression is
&& I can just recurse to the children. The
interesting case is the element node - and there's enough logic
there that I've put it into a separate class.
class ElementBuilder...
private BinaryExpression node;
public ElementBuilder(BinaryExpression node) {
this.node = node;
assertValidNode();
}
These element nodes have two children: one is a keyword node
(eg q.To) and one is some arbitrary C# that will
return the value that will be compared in the query. I'm
allowing the keyword and value to appear either way around,
since that commutativity is expected in the host language.
To be a keyword, the child must have a method call on an instance of my criteria object. I'll need to be able to extract that keyword from the child node, so I write a method that takes a child node and returns the keyword if it's keyword expression, or null if it's not.
class ElementBuilder...
private string keywordOfChild(Expression node) {
var call = node as MemberExpression;
if (null == call) return null;
if (call.Member.DeclaringType != typeof(ImapQueryBuilder.ImapQueryCriteria))
return null;
return call.Member.Name.ToLower();
}
This utility method is very useful. It's first use is to allow me to check that I actually have a valid element node to work on. For this I need to ensure that one of the children is indeed a keyword node.
class ElementBuilder...
private void assertValidNode() {
if (null == keywordOfChild(node.Left) && null == keywordOfChild(node.Right))
throw new BuilderException("expression does not contain keyword", node);
if (!isLegalOperator)
throw new BuilderException("Wrong kind of operator", node);
}
Not just do I check that one of the children is a keyword node, I also need to check that I have a legal operator for the kind of keyword I have
class ElementBuilder...
private bool isLegalOperator {
get {
ExpressionType[] dateOperators = {
ExpressionType.Equal, ExpressionType.GreaterThanOrEqual,
ExpressionType.LessThanOrEqual, ExpressionType.NotEqual,
ExpressionType.GreaterThan, ExpressionType.LessThan
};
ExpressionType[] stringOperators = {
ExpressionType.Equal, ExpressionType.NotEqual
};
return (isDateKeyword())
? dateOperators.Contains(node.NodeType)
: stringOperators.Contains(node.NodeType);
}
}
private bool isDateKeyword() {
return dateKeywords.Contains(keywordMethod());
}
private static readonly string[] dateKeywords = { "sent", "date" };
private string keywordMethod() {
return keywordOfChild(node.Left) ?? keywordOfChild(node.Right);
}
You might notice here that I'm doing a bit more checking for
date keywords. For string keywords I'm relying on the Semantic Model to tell me if I try to create an element
with an illegal keyword. I have to handle the date keywords
differently since there is a mismatch between the C# expression
and the Semantic Model. If want to find
emails sent since a certain date, the natural way to say this in
C# is something like q.Sent >= aDate, however IMAP
does this with sentsince aDate. Essentially I need
the combination of the C# keyword plus the operator to determine
the correct IMAP keyword. As a consequence I have to check the C#
date keywords in the builder as they are part of the input DSL
but not the Semantic Model.
By checking I have a valid node in the constructor I can simplify my later logic to extract the right data from the node.
Now lets look at exactly that. I begin with a content property which which separates the simple string case from the more complicated date case.
class ElementBuilder...
public ImapQueryElement Content {
get {
return isDateKeyword()? dateKeywordContent() : stringKeywordContent();
}
}
For the string case, I create a basic query element using
whatever the keyword is and the value from the other side of the
node. If the operator is != I wrap that basic
element inside a negation.
class ElementBuilder...
private ImapQueryElement stringKeywordContent() {
switch (node.NodeType) {
case ExpressionType.Equal:
return new BasicElement(keywordMethod(), Value);
case ExpressionType.NotEqual:
return new NegationElement(new BasicElement(keywordMethod(), Value));
default:
throw new Exception("unreachable");
}
}
To determine the value, I don't need to parse the value node. Instead I can just toss the expression back to the C# system to get it. This allows me to put any legal C# into the value side of my elements without having to try to deal with it in my navigation code.
class ElementBuilder...
private object Value {
get {
return (null == keywordOfChild(node.Left))
? valueOfChild(node.Left)
: valueOfChild(node.Right);
}
}
private object valueOfChild(Expression node) {
return Expression.Lambda(node).Compile().DynamicInvoke();
}
Dates are more complicated, but I use the same basic approach. The IMAP keyword I'll need depends o both the keyword method in the node and the value of the operator. In addition I also need to throw in negations when I need to. As the first step I'll tease out the keyword method.
class ElementBuilder...
private ImapQueryElement dateKeywordContent() {
if ("sent" == keywordMethod())
return formDateElement("sent");
else if ("date" == keywordMethod())
return formDateElement("");
else throw new Exception("unreachable");
}
With the right date keyword sorted out, I'll then break things out by the operator type.
class ElementBuilder...
private ImapQueryElement formDateElement(string prefix) {
switch (node.NodeType) {
case ExpressionType.Equal:
return new BasicElement(prefix + "on", Value);
case ExpressionType.NotEqual:
return new NegationElement(new BasicElement(prefix + "on", Value));
case ExpressionType.GreaterThanOrEqual:
return new BasicElement(prefix + "since", Value);
case ExpressionType.GreaterThan:
return new NegationElement(new BasicElement(prefix + "before", Value));
case ExpressionType.LessThan:
return new NegationElement(new BasicElement(prefix + "since", Value));
case ExpressionType.LessThanOrEqual:
return new BasicElement(prefix + "before", Value);
default:
throw new Exception("unreachable");
}
}
Notice that I'm taking advantage here of the similar names of the date-oriented IMAP keywords that I deal with. My first code for this had separate switch statements for each keyword, but I realized by doing the prefix trick I could remove the duplication. The code's a little cleverer than I like, but I think it's worth that to avoid duplication.
That sums up the implementation of this, but there's a couple of things I need to say before I leave this example.
The first point is a difference from how I've described the example and how I built it. In describing the example I find it easier to look at each part of the implementation separately: populating the Semantic Model with a push-button interface, generating the IMAP code, walking through the parse tree. I think looking at each aspect separately makes it easier to understand - which is also why the code is separated that way.
However I didn't actually build it that way. I did the example in two stages, first I just supported simple conjunctions of basic elements, then I added the ability to handle negations. I wrote the code for all elements on the first pass and then extended and refactored each section when adding the negations. I always advocate building software feature by feature like this, but I don't think that's the best way to explain the final result. So don't let the structure of the final result and the way I explain it fool you into thinking that's how it's built.
The second point I want to share is that although walking a parse tree like this yields that geeky pleasure you get when using fancy parts of a language - I wouldn't actually build an IMAP DSL this way. An alternative is a simple dose of Method Chaining.
class Tester...
var builder = new ChainingBuilder()
.subject("entity framework")
.not.from("@ayende.com")
.since(threshold);
Here's all the implementation I need to do this.
class ChainingBuilder...
private readonly ImapQuery content = new ImapQuery();
private bool currentlyNegating = false;
public ImapQuery Content {
get { return content; }
}
public ChainingBuilder not {
get {
currentlyNegating = true;
return this; }
}
private void addElement(string keyword, object value) {
ImapQueryElement element = new BasicElement(keyword, value);
if (currentlyNegating) {
element = new NegationElement((BasicElement) element);
currentlyNegating = false;
}
content.AddElement(element);
}
public ChainingBuilder subject(string s) {
addElement("subject", s);
return this;
}
public ChainingBuilder since(DateTime t) {
addElement("since", t);
return this;
}
public ChainingBuilder from(string s) {
addElement("from", s);
return this;
}
It's not utterly trivial - including the negation makes me use a messy Context Variable - but it's still small and simple. I'd need to add more methods to support more keywords, but they would be simple methods.
Of course one of the main reasons this is so much simpler is that the structure of the internal DSL is more similar to the IMAP query itself. In fact it's really just the IMAP query expressed as Method Chaining. It's advantage over using IMAP itself boils down to IDE support. Some people might prefer the more C#y syntax that the Parse Tree Manipulation example gives you, but I must admit I'm happier with the IMAPy version.
[TBD: Can I do something like this C# operator overloading without using parse tree manipulation?]