Using delegates to simplify a type safe abstract syntax tree in C# (2.0) currently using the Visitor pattern.

Question

Hi guys, I have some "input" that gets parsed a number of different ways.

I'm trying to abstract out the parsing code from the various downstream engines that need the parsed result (some parts will display it, other parts actually execute it, etc. etc.).

So far, I have this:

interface IParsedNode
{
    // Visits this node, returns whatever the appropriate IVisitor function
    // returned.
    T Visit<T>(IVisitor<T> visitor);
}

interface IVisitor<T>
{
    T Load(Aspect aspect);
    T LoadFile(string group, string filename);
    T Process(PluginProperties pluginProperties, IParsedNode input);
    T Aggregate(List<IParsedNode> children);
    T Rename(string newName, string oldName, IParsedNode input);
    T Filter(string keep, IParsedNode input);
    T Cache(IParsedNode input);
}

class Cached : IParsedNode
{
    private readonly IParsedNode input;

    public Cached(IParsedNode input)
    {
        this.input = input;
    }
    #region IParsedNode Members
    public T Visit<T>(IVisitor<T> visitor)
    {
        return visitor.Cache(input);
    }
    #endregion
}

class Filter : IParsedNode
{
    private readonly string keep;
    private readonly IParsedNode input;

    public Filter(string keep, IParsedNode input)
    {
        this.keep = keep;
        this.input = input;
    }

    #region IParsedNode Members
    public T Visit<T>(IVisitor<T> visitor)
    {
        return visitor.Filter(keep, input);
    }
    #endregion
}

etc.

As you can see, this allows me to have a completely "abstract" parse tree, that's also type safe. I also like the fact that everything's immutable.

I abstract out the type of "T" because different downstream systems will in turn create their own concrete graphs out of the abstract parse tree.

For example, here's one implementation of IVisitor:

// Used to convert the abstract tree into an actual tree that can then be post-processed.
class NodeTreeBuilder : IVisitor<Node>
{
    private readonly NodeFactory nodeFactory;

    public NodeTreeBuilder(NodeFactory nodeFactory)
    {
        this.nodeFactory = nodeFactory;
    }

    #region IVisitor<Node> Members
    public Node Load(Aspect aspect)
    {
        return nodeFactory.CreateRaw(aspect);
    }

    public Node LoadFile(string group, string filename)
    {
        return nodeFactory.CreateFile(group, filename);
    }

    public Node Process(PluginProperties pluginProperties, IParsedNode input)
    {
        ProcessInfo processInfo = new ProcessInfo();
        processInfo.AssemblyPath = pluginProperties.AssemblyPath;
        processInfo.ClassName = pluginProperties.ClassName;
        processInfo.Config = new PluginConfig(pluginProperties.Config, pluginProperties.HashConfig, pluginProperties.DeltaType);
        PluginInfo pluginInfo = Registry.CreatePluginInfo(pluginProperties.Id, processInfo);
        return nodeFactory.CreatePostProcess(pluginInfo, input.Visit(this), pluginProperties.RunOnEmpty);
    }

    public Node Aggregate(List<IParsedNode> children)
    {
        Node[] convertedChildren = children.ConvertAll<Node>(delegate(IParsedNode child) { return child.Visit(this); }).ToArray();
        return nodeFactory.CreateAggregated(convertedChildren);
    }

    public Node Rename(string newName, string oldName, IParsedNode input)
    {
        return nodeFactory.Rename(oldName, newName, input.Visit(this));
    }

    public Node Filter(string keep, IParsedNode input)
    {
        return nodeFactory.Filter(keep, input.Visit(this));
    }

    public Node Cache(IParsedNode input)
    {
        return input.Visit(this).Cache(true);
    }
    #endregion
}

For the actual concrete implementations of IVisitor this all works nicer than I dared hope.

However, implementing IParsedNode itself (as you saw my doing initially) is proving a bit tedious. I'm providing a whole bunch of implementations of an interface that only contain one method.... which got me thinking that perhaps I could use a delegate to reduce the bloat:

class ParsedNode : IParsedNode
{
    delegate T NodeType<T>(IVisitor<T> visitor);

    private readonly NodeType nodeType;

    public ParsedNode<T>(NodeType<T> nodeType)
    {
        this.nodeType = NodeType;
    }

    public T  Visit<T>(IVisitor<T> visitor)
    {
        return nodeType(visitor);
    }
}

But the above doesn't compile. Is there no way for me to implement IParsedNode in terms of some sort of generic delegate? It would be nice if there was a way to make this work as things would be less verbose.

Perhaps if the IParsedNode interface was itself just a delegate, this could be made to work?

Answer 1

I recommend reading Judith Bishop's (author of C# 3.0 Design Patterns) paper titled On the Efficiency of Design Patterns Implemented in C# 3.0.

She specifically addresses the Visitor pattern using delegates, and walks through a basic implementation (at least algorithmically). Her implementation is very fast, and quite flexible.

This is my favorite implementation of the Visitor pattern in C#, to date.