Visitor Revisitted: LINQ, Function Composablity and Chain of Responsibility

  • Article

Jomo Fisher—Last time, I wrote about constructing an inline visitor using new C# language features. It worked fine for what it did, but it completely falls down when you want to extend existing visitors that you’ve created. What if I wanted to modify the PrintTree delegate to print negative numbers inside parentheses? There’s not a way to do it. This is a serious limitation, especially when you have hundreds of node types in your tree structure.

In order to fix this problem I went back to first principles. Without worrying about how to implement it, how do I really want functions to compose and recurse in C#? Here’s what I sketched out using the venerable Fibonacci sequence:

var fib = n => n > 1 ? self(n - 1) + self(n - 2) : n

var fib2x = fib chainto n => last(n) * 2;

var fib6x = fib2x chainto n => last(n) * 3;

Here, I’m pretending to add two new keywords to C#—self and last—which are analogous to this and base for classes. Also, I’m pretending to add a third keyword—chainto—which is used for composing functions. The last keyword is only valid on the right side of a chainto and it causes a call to the left side. The call to self always calls the outermost function into which it is composed.

The thing I want is a language encoding of the Chain of Responsibility pattern with a twist. The twist is that the nested responsibility handlers can call the outermost level through self.

Back to Reality

I’m not free to add keywords to C# so I need a way to work with what I have. Here’s a literal transcoding of my idealized functionality into C# 3.0.

var fib = FuncOp.Create<int, int>(

    (self, n) => n > 1 ? self(n - 1) + self(n - 2) : n

);

var fib2x = fib.Chain(

    (self, last, n) => last(n) * 2

);

var fib6x = fib2x.Chain(

    (self, last, n) => last(n) * 3

);

The pretend keywords self and last become lambda expression parameters who’s type is a delegate. The chainto becomes an extension method named Chain.

To my eyes, it’s nicely concise.

Now that I know what I want it to look like, I have to figure out a way to make it work. This turned out to require all kinds of non-obvious plumbing. I think it needs some explaining.

Smuggling Baggage in Static Delegates

First, I want the fib delegate to be directly callable, so the return type from Create(...) needs to be a delegate that takes an int and returns an int. Something like Func<int,int>.

So that means that the Chain method needs to operate on Func<int,int>. At this point, I’m already in trouble. The reason is that I need to repoint fib’s calls to self(...) to call the result of the call to Chain. The problem is that I have a Func<int, int> and what I want is the original Func<Func<int,int>, int, int> that was originally passed in to Chain. I need to smuggle the ‘unbound’ version of fib around with the regular fib but hide it from the user.

The trick is to realize that fib is a static delegate. So this means that its Delegate.Target member is always null. Since its not being used for its intended purpose (to hold the delegate’s calling target for non-static calls) I’ll use it for my own purposes. To see what I mean, here’s an example of smuggling a random string around with a static delegate:

var addOne = new Func<int, int>(

new Smuggler("My totally random string.", n => n + 1).Invoke);

Console.WriteLine(addOne(5));

Console.WriteLine(((Smuggler)addOne.Target).MyString);

class Smuggler {

    private Func<int, int> f;

    public string MyString { get; private set; }

    public Smuggler(String myString, Func<int, int> f) {

        this.f = f;

        this.MyString = myString;

    }

    public int Invoke(int n) { return f(n); }

}

Using this trick, I smuggle around the unbound version of the delegate along with a pointer to the prior function (thus forming a linked list of delegates that have been composed).

Simulated ref Lambda Expression

Each call to Chain needs to repoint all calls to ‘self’ for all prior functions in the chain. In order to do this, I needed to curry a lambda expression against a refto delegate:

void Function(ref Func<int,int> self) {

    Func<int, int> f = (n) => self(n);

}

Unfortunately for me, the C# language doesn’t allow ref parameters inside delegates. I’m not sure why, there’s no obvious technical reason.

This problem can be solved by making a RefOf class to hold the delegate.

private class RefOf<T> {

    public T Ref { get; set; }

}

void Function(RefOf<Func<int, int>> self) {

    Func<int, int> f = (n) => self.Ref(n);

}

Putting it all Together

Now that we have the tools, let’s put it all together:

static class FuncOp {

    private class Binding<T, TResult> {

        public Func<T, TResult> Bound { get; private set; }

        public Func<Func<T, TResult>,

Func<T, TResult>, T, TResult> Unbound { get; private set; }

        public Binding<T, TResult> LastBinding { get; private set; }

        public Binding(Func<T, TResult> bound,

            Func<Func<T, TResult>,

Func<T, TResult>, T, TResult> unbound,

         Binding<T, TResult> lastBinding) {

            Bound = bound;

            Unbound = unbound;

            LastBinding = lastBinding;

        }

        public TResult Invoke(T t) { return Bound(t); }

    }

    private class RefOf<T> {

        public T Ref { get; set; }

    }

    public static Func<T, TResult> Create<T, TResult>(

        Func<Func<T, TResult>, T, TResult> function) {

        var selfRef = new RefOf<Func<T,TResult>>();

        var unbound = new Func<Func<T, TResult>,

Func<T, TResult>, T, TResult>(

            (s, l, t) => function(s, t)

        );

        selfRef.Ref = Chain(selfRef, unbound, null);

        return selfRef.Ref;

    }

    private static Func<T, TResult> Chain<T, TResult>(

        RefOf<Func<T, TResult>> selfRef,

        Func<Func<T, TResult>,

  Func<T, TResult>, T, TResult> unbound,

        Binding<T, TResult> lastBinding) {

        Func<T, TResult> last = null;

        Func<T, TResult> bound = (t) => unbound(selfRef.Ref, last, t);

        if (lastBinding != null)

            last = Chain(selfRef, lastBinding.Unbound,

lastBinding.LastBinding);

        var binding = new Binding<T, TResult>(bound, unbound,

lastBinding);

        return new Func<T, TResult>(binding.Invoke);

    }

    public static Func<T, TResult> Chain<T, TResult>(

  this Func<T, TResult> lastFunction,

        Func<Func<T, TResult>,

  Func<T, TResult>, T, TResult> selfFunction) {

        var selfRef = new RefOf<Func<T, TResult>>();

        var lastBinding = (Binding<T, TResult>)lastFunction.Target;

        selfRef.Ref = Chain<T, TResult>(selfRef, selfFunction,

lastBinding);

        return selfRef.Ref;

    }

}

Composing Functions in Action

Ok, now I want to see how well this solves my original problem: reusing the PrintTree delegate while putting negative numbers in parenthesis. Here’s the original PrintTree transcoded into the new form:

Node addNumbers = Node.Add(

    Node.Add(Node.Constant(-1), Node.Constant(-2)),

    Node.Add(Node.Constant(3), Node.Constant(5)));

var UnhandledNode = FuncOp.Create<Node, Node>(

    (self, n) => { throw new Exception("Unhandled node type "

+ n.NodeType); }

var PrintTree = UnhandledNode.Chain(

    (self, last, n) => {

        switch (n.NodeType) {

            case NodeType.Add:

                BinaryNode bn = (BinaryNode)n;

                self(bn.Left);

                Console.Write("+");

                self(bn.Right);

                return n;

            case NodeType.Constant:

                ConstantNode cn = (ConstantNode)n;

                Console.Write(cn.Value);

                return n;

            default:

                return last(n);

        }

    }

);

PrintTree(addNumbers);

I like this a lot better than the prior solution. Aside from being composable, I also get to use the plain old C# switch\case instead of inventing my own parallel mechanism. Also, the code pretty much looks like what it does.

Here’s the code that will extend PrintTree to parenthesize negative numbers:

var PrintParens = PrintTree.Chain(

    (self, last, n) => {

        switch (n.NodeType) {

            case NodeType.Constant:

                ConstantNode cn = (ConstantNode)n;

                if (cn.Value is int) {

                    int v = (int)cn.Value;

                    if (v < 0) Console.Write("(" + v + ")");

                    else Console.Write(v);

                } else {

                    Console.Write(cn.Value);

                }

                return n;

            default:

                return last(n);

        }

    }

);

PrintParens(addNumbers);

As expected, there’s no need to handle NodeType.Add at this level.

It's interesting to me that turning a Visitor inside-out gives you a Chain of Responsibility. I wonder if there are other OO<-->Functional design pattern dualities like this.

This posting is provided "AS IS" with no warranties, and confers no rights.

 (Note 5-24-2007: I put this pattern to good use here: https://blogs.msdn.com/jomo_fisher/archive/2007/05/23/dealing-with-linq-s-immutable-expression-trees.aspx)

kick it on DotNetKicks.com

Comments

  • Anonymous
    May 07, 2007
    PingBack from http://blogs.msdn.com/jomo_fisher/archive/2007/05/04/inline-visitor-construction-using-linq.aspx

  • Anonymous
    May 07, 2007
    You've been kicked (a good thing) - Trackback from DotNetKicks.com

  • Anonymous
    May 07, 2007
    I see that you continue to enjoy yourself with Design Pattern and LINQ :-). Very good job!

  • Anonymous
    May 21, 2007
    This is beautiful! I think I'll frame it and hang it on my living room wall!

  • Anonymous
    May 23, 2007
    Jomo Fisher --I recently got a question via my blog that dovetailed nicely with something I’ve been working

  • Anonymous
    May 23, 2007
    I tried to build on the idea of using the Target of the delegate. I would propose the following implementation :    public static class Recursive    {        private class Binding<T, TResult>        {            public Func<T, TResult> Bound { get; private set; }            private readonly Func<Func<T, TResult>, Func<T, TResult>, T, TResult> Unbound;            private readonly Binding<T, TResult> LastBinding;            private readonly Binding<T, TResult> SelfBinding;            public Binding(Func<Func<T, TResult>, Func<T, TResult>, T, TResult> unbound, Binding<T, TResult> selfBinding, Binding<T, TResult> lastBinding)            {                Unbound = unbound;                Bound = t => Invoke(t);                if (selfBinding == null)                    SelfBinding = this;                else                    SelfBinding = selfBinding;                if (lastBinding == null)                    LastBinding = null;                else                    lastBinding = new Binding<T, TResult>(lastBinding.Unbound, SelfBinding, lastBinding.LastBinding);            }            private TResult Invoke(T t)            {                return Unbound(SelfBinding.Bound, LastBinding == null ? null : LastBinding.Bound, t);            }        }        public static Func<T, TResult> Create<T, TResult>(this Func<Func<T, TResult>, T, TResult> function)        {            return new Binding<T, TResult>((s, l, t) => function(s, t), null, null).Bound;        }        public static Func<T, TResult> Chain<T, TResult>(             this Func<T, TResult> lastFunction,            Func<Func<T, TResult>, Func<T, TResult>, T, TResult> selfFunction)        {            if (lastFunction == null)                throw new ArgumentNullException("lastFunction");            var lastBinding = lastFunction.Target as Binding<T, TResult>;            if (lastBinding == null)                throw new ArgumentException("the function is not recursive", "lastFunction");            return new Binding<T, TResult>(selfFunction, null, lastBinding).Bound;        }    }

  • Anonymous
    August 06, 2007
    And readability goes down the drain. Conceptually a great demonstration of the power of new C# 3.0 features. However if I saw code like this from anyone on my team, it'd be time for a serious talk.

  • Anonymous
    February 14, 2008
    Hmmm... What's wrong with static Func<T, U> Create<T, U>(Func<Func<T, U>, T, U> f) {    return t => f(Create(f), t); } static Func<T, V> Chain<T, U, V>(this Func<T, U> fn, Func<Func<T, V>, Func<T, U>, T, V> f) {    return t => f(Chain(fn, f), fn, t); }