Inline Visitor Construction using LINQ
Jomo Fisher—My current job is in the C# team working on LINQ to SQL. Because of nature of programming languages, very few days go by that I don’t deal with syntax trees and the visitor pattern. Occasionally, it would be convenient to create a quick one-off visitor for doing a manipulation on a tree. It would be nice to create a simple in-place visitor—say in a delegate--without going through the trouble of creating an internally-visible class.
One of the problems you run into right away is that the visitor pattern requires recursion and it’s not apparent how to create recursive delegates. Fortunately, smart people have figured this out already and we can just make use of the fruits of their labor: See this for example.
After some additional head-scratching, I managed to come up with a system for creating in-place visitors. Here’s an example of an inline visitor that just prints the contents of a node tree that I defined:
Node addTwo = Node.Add(Node.Constant(1), Node.Constant(2));
var PrintTree = Visitor.Create<Node>(visit => node =>
Visitor.Case(node == null, () => node,
() => Visitor.Case(node.NodeType == NodeType.Add, () => {
BinaryNode b = (BinaryNode)node;
visit(b.Left);
Console.Write(" + ");
visit(b.Right);
return node;
},
() => Visitor.Case(node.NodeType == NodeType.Constant, () => {
ConstantNode cn = (ConstantNode)node;
Console.Write(cn.Value);
return node;
}
)))
);
PrintTree(addTwo);
It’s not exactly the prettiest thing you can imagine, but it does do the job. It works by chaining Visitor.Case calls together, each with a delegate block to execute if there’s a match. Notice the call to visit in the 'Add' case--that's the recursion I was talking about. Here’s the supporting code that makes it work:
static class Visitor {
public static T Case<T>(bool match,
Func<T> matched, Func<T> notMatched) {
return match ? matched() : notMatched();
}
public static T Case<T>(bool match, Func<T> matched) {
if (match) {
return matched();
}
throw new Exception("Unhandled case");
}
private delegate Func<A, R> Recursive<A, R>(Recursive<A, R> r);
public static Func<TNode, TNode> Create<TNode>(
Func<Func<TNode, TNode>, Func<TNode, TNode>> f) {
Recursive<TNode, TNode> rec = r => a => f(r(r))(a);
return rec(rec);
}
}
And for completeness, here’s the example Node tree that I used:
enum NodeType {
Add,
Constant
}
abstract class Node {
public Node(NodeType type) { NodeType = type; }
public NodeType NodeType { get; private set; }
public static BinaryNode Add(Node left, Node right) {
return new BinaryNode(left, right, NodeType.Add);
}
public static ConstantNode Constant(object value) {
return new ConstantNode(value);
}
}
sealed class BinaryNode : Node {
public BinaryNode(Node left, Node right, NodeType type)
: base(type) {
Left = left;
Right = right;
}
public Node Left { get; private set; }
public Node Right { get; private set; }
}
sealed class ConstantNode : Node {
public ConstantNode(object value)
: base(NodeType.Constant) {
Value = value;
}
public object Value { get; private set; }
}
I don’t see a direct way to make the calling pattern simpler. Maybe one of you will have an idea for improving it. I do think there may be an indirect way to make it better: represent the whole visitor as an Expression tree that is rewritten (using...a visitor) and then using Expression.Compile. I think I may try that next.
(Update 5/7/2007--I found a better way to solve this whole problem class. See https://blogs.msdn.com/jomo_fisher/archive/2007/05/07/visitor-revisitted-linq-function-composablity-and-chain-of-responsibility.aspx )
This posting is provided "AS IS" with no warranties, and confers no rights.
Comments
Anonymous
May 05, 2007
Nice job! It is always interesting to see how use specificities of a language to modify Design Pattern classic implementation.Anonymous
May 06, 2007
The biggest news in the C# community is the official announcement of Silverlight at the MIX conference.Anonymous
May 07, 2007
Jomo Fisher— Last time , I wrote about constructing an inline visitor using new C# language features.Anonymous
December 13, 2007
Not to nag, but we all know what the "real" solution to this type of problem is... cough...anonymous inner classes...ahem...please include in the next version of C#...cough...