Jacob Carpenter’s Weblog

February 20, 2008

Generic abuse: Pattern matching in C#

Filed under: csharp — Jacob @ 1:59 pm

Sorry it’s been so long since a post, dear faithful aggregator. Apart from working, I’ve been busily readying my entry for the WPF in Finance contest (which, coincidentally has inspired a potential post or two).

Yesterday, however, I encountered Dustin’s post on pattern matching in F#. Go read it; I’m not going to reiterate the concepts, and you need to be familiar with the feature for this post to possibly begin to make any sense.

His post inspired the most creative (perhaps twisted) use of generics I’ve ever written. And I have to share.

A couple of caveats though: pattern matching is built into F#. It is therefore much, much cooler than the following experiment. Please don’t comment telling me that mine is lamer than F#’s.

Also, I’m usually morally opposed to screenshots of code (rather than the actual code, itself), but I need to visually highlight some stuff to help explain it. I’ve attached the full source at the bottom of the post.

Intro

If I were writing a pattern matching API in C#, one of my first thoughts would be “fluent interface“. At it’s simplest, pattern matching needs to support:

  1. Some variable number of guard clauses (only at the beginning of the pattern match).
  2. Some variable number of pattern expressions (a predicate of some sort and an associated action).
  3. A single final catch-all expression (action only).

Fluent interfaces can represent this type of constrained chaining pretty nicely. In fact, LINQ sort of supports constrained chaining with OrderBy/ThenBy. OrderBy returns an IOrderedEnumerable, which supports ThenBy (via extension). You can’t call ThenBy on an ordinary IEnumerable; you have to call OrderBy first.

The problem with fluent interfaces for solving this problem, though, is that successive method calls don’t really feel like adding expressions to a pattern match:

image

Note that it’s only whitespace (which the compiler ignores) that communicates that .When(…).Return(…) adds one expression, whereas .Guard(…) and the last .Return(…) each correspond to a single expression.

Also, we haven’t looked at the object model yet, but note that a final call to .Compile is required to transform whatever type the last .Return returns into a Func<int, int>. I hate that.

There are other options. We could write a method that took a params array of loosely typed pattern expressions. But we would sacrifice compile-time expression order constraint.

My crazy solution

Through numerous rewrites and after going around in circles for some time, I decided on the following pattern:

  1. Define an object model of “match contexts” that (similar to LINQ’s OrderBy/ThenBy) return strongly typed contexts defining what operations are supported from the current context.
  2. In my pattern match building method, use Funcs and generics (with type constraints) to allow the strongly typed contexts to flow from parameter to parameter.

Let’s look at the object model:

public abstract class ClosedMatchContext<T, TResult>
{
}

public abstract class MatchContext<T, TResult> : ClosedMatchContext<T, TResult>
{
    public abstract IntermediateMatchResultContext<T, TResult> When(Func<T, bool> condition);
    public abstract ClosedMatchContext<T, TResult> Return(TResult result);
    public abstract ClosedMatchContext<T, TResult> Return(Func<T, TResult> resultProjection);
}

public abstract class OpenMatchContext<T, TResult> : MatchContext<T, TResult>
{
    public abstract OpenMatchContext<T, TResult> Guard(Func<T, bool> failWhen, Func<T, TResult> failWith);
}

public abstract class IntermediateMatchResultContext<T, TResult>
{
    public abstract MatchContext<T, TResult> Return(TResult result);
    public abstract MatchContext<T, TResult> Return(Func<T, TResult> resultProjection);
}

Beginning with OpenMatchContext, we have a context that supports: Guard, When, and Return operations. Moving up the hierarchy, the more general MatchContext supports only When and Return. Finally at the top level, ClosedMatchContext doesn’t support any further operations.

When, defined on MatchContext, returns an IntermediateMatchResultContext which requires a call to Return to get back to a MatchContext.

Now it’s getting interesting…

Or perhaps, difficult to understand?

public static class Match<T, TResult>

… defines a number of On methods that take series of Func arguments. Let’s look at the signature of the 4 parameter one:

image

Now take a deep breath.

The first parameter is a Func<OpenMatchContext, TCtx1>. An open context comes in and some MatchContext (according to the constraint) comes out.

The second parameter takes a Func<TCtx1, TCtx2>. The context returned by the first parameter is given to the second parameter, and some new MatchContext comes out. The third parameter is very similar.

Finally, the last parameter takes a Func<TCtx3, ClosedMatchContext>. That is, we expect to get some closed context as the final output.

Let’s see if a little highlighting can help?

image

My graphic design skillz could use some work, but do you follow the flow of the types?

This means that when you’re using On the parameters are strongly typed:

image

Following a Guard expression, you can add an additional Guard. But…

image

Following a When+Return, you can no longer Guard.

There’s more interesting type stuff going on in this example, but I’ll have to discuss it in a following post.

I hope reading this has produced a pleasantly painful sensation. If not, go read Wes Dyer’s post on Monads.

Source listing

I’ve attached the source to this post, but I have to lie about the extension. Rename the attached Program.cs.REMOVE.DOC to Program.cs.

UPDATE: I’ve made the source more accessible by simply including it after the “more” link.

I’d encourage you to copy it into a ConsoleApplication’s Program.cs and play around with it. Let me know what you think.

Enjoy!

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;

namespace PatternMatching
{
    class Program
    {
        static void Main(string[] args)
        {
            Func<int, int> fib = null;
            fib = Match<int, int>.On(
                m => m.Guard(n => n < 0, n => { throw new ArgumentOutOfRangeException(); }),
                m => m.When(0, 1).Return(n => n),
                m => m.Return(n => fib(n - 1) + fib(n - 2)));

            var fibs = Enumerable.Range(0, 10).Select(n => fib(n));
            foreach (int n in fibs)
                Console.WriteLine(n);
        }
    }

    public abstract class ClosedMatchContext<T, TResult>
    {
    }

    public abstract class MatchContext<T, TResult> : ClosedMatchContext<T, TResult>
    {
        public abstract IntermediateMatchResultContext<T, TResult> When(Func<T, bool> condition);
        public abstract ClosedMatchContext<T, TResult> Return(TResult result);
        public abstract ClosedMatchContext<T, TResult> Return(Func<T, TResult> resultProjection);
    }

    public abstract class OpenMatchContext<T, TResult> : MatchContext<T, TResult>
    {
        public abstract OpenMatchContext<T, TResult> Guard(Func<T, bool> failWhen, Func<T, TResult> failWith);
    }

    public abstract class IntermediateMatchResultContext<T, TResult>
    {
        public abstract MatchContext<T, TResult> Return(TResult result);
        public abstract MatchContext<T, TResult> Return(Func<T, TResult> resultProjection);
    }

    public static class MatchContextExtensions
    {
        public static IntermediateMatchResultContext<T, TResult> When<T, TResult>(this MatchContext<T, TResult> ctx, T value)
            where T : IEquatable<T>
        {
            var comp = EqualityComparer<T>.Default;
            return ctx.When(t => comp.Equals(t, value));
        }

        public static IntermediateMatchResultContext<T, TResult> When<T, TResult>(this MatchContext<T, TResult> ctx, T value1, T value2)
            where T : IEquatable<T>
        {
            var comp = EqualityComparer<T>.Default;
            return ctx.When(t => comp.Equals(t, value1) || comp.Equals(t, value2));
        }
    }

    public static class Match<T, TResult>
    {
        public static Func<T, TResult> On<TCxt>(
            Func<OpenMatchContext<T, TResult>, TCxt> cond1,
            Func<TCxt, ClosedMatchContext<T, TResult>> cond2)
            where TCxt : MatchContext<T, TResult>
        {
            ClosedMatchContext<T, TResult> ctx = cond2(cond1(new ContextImpl()));
            return ((ContextImpl) ctx).Compile();
        }

        public static Func<T, TResult> On<TCtx1, TCtx2>(
            Func<OpenMatchContext<T, TResult>, TCtx1> cond1,
            Func<TCtx1, TCtx2> cond2,
            Func<TCtx2, ClosedMatchContext<T, TResult>> cond3)
            where TCtx1 : MatchContext<T, TResult>
            where TCtx2 : MatchContext<T, TResult>
        {
            ClosedMatchContext<T, TResult> ctx = cond3(cond2(cond1(new ContextImpl())));
            return ((ContextImpl) ctx).Compile();
        }

        public static Func<T, TResult> On<TCtx1, TCtx2, TCtx3>(
            Func<OpenMatchContext<T, TResult>, TCtx1> cond1,
            Func<TCtx1, TCtx2> cond2,
            Func<TCtx2, TCtx3> cond3,
            Func<TCtx3, ClosedMatchContext<T, TResult>> cond4)
            where TCtx1 : MatchContext<T, TResult>
            where TCtx2 : MatchContext<T, TResult>
            where TCtx3 : MatchContext<T, TResult>
        {
            ClosedMatchContext<T, TResult> ctx = cond4(cond3(cond2(cond1(new ContextImpl()))));
            return ((ContextImpl) ctx).Compile();
        }

        public static Func<T, TResult> On<TCtx1, TCtx2, TCtx3, TCtx4>(
            Func<OpenMatchContext<T, TResult>, TCtx1> cond1,
            Func<TCtx1, TCtx2> cond2,
            Func<TCtx2, TCtx3> cond3,
            Func<TCtx3, TCtx4> cond4,
            Func<TCtx4, ClosedMatchContext<T, TResult>> cond5)
            where TCtx1 : MatchContext<T, TResult>
            where TCtx2 : MatchContext<T, TResult>
            where TCtx3 : MatchContext<T, TResult>
            where TCtx4 : MatchContext<T, TResult>
        {
            ClosedMatchContext<T, TResult> ctx = cond5(cond4(cond3(cond2(cond1(new ContextImpl())))));
            return ((ContextImpl) ctx).Compile();
        }

        class MatchExpression
        {
            public MatchExpression(Func<T, bool> isMatch, Func<T, TResult> getResult)
            {
                m_isMatch = isMatch;
                m_getResult = getResult;
            }

            public bool Matches(T value)
            {
                return m_isMatch(value);
            }

            public TResult Evaluate(T value)
            {
                return m_getResult(value);
            }

            readonly Func<T, bool> m_isMatch;
            readonly Func<T, TResult> m_getResult;
        }

        class IntermediateContextImpl : IntermediateMatchResultContext<T, TResult>
        {
            public IntermediateContextImpl(ContextImpl baseContext, Func<T, bool> condition)
            {
                m_baseContext = baseContext;
                m_condition = condition;
            }

            public override MatchContext<T, TResult> Return(TResult result)
            {
                return new ContextImpl(m_baseContext, new MatchExpression(m_condition, t => result));
            }

            public override MatchContext<T, TResult> Return(Func<T, TResult> resultProjection)
            {
                return new ContextImpl(m_baseContext, new MatchExpression(m_condition, resultProjection));
            }

            ContextImpl m_baseContext;
            Func<T, bool> m_condition;
        }

        class ContextImpl : OpenMatchContext<T, TResult>
        {
            public ContextImpl()
            {
                m_matches = Enumerable.Empty<MatchExpression>().ToList().AsReadOnly();
            }

            public ContextImpl(ContextImpl baseContext, MatchExpression newExpr)
            {
                m_matches = baseContext.m_matches.ConcatSingle(newExpr).ToList().AsReadOnly();
            }

            public override OpenMatchContext<T, TResult> Guard(Func<T, bool> failWhen, Func<T, TResult> failWith)
            {
                return new ContextImpl(this, new MatchExpression(failWhen, failWith));
            }

            public override IntermediateMatchResultContext<T, TResult> When(Func<T, bool> condition)
            {
                return new IntermediateContextImpl(this, condition);
            }

            public override ClosedMatchContext<T, TResult> Return(TResult result)
            {
                return new ContextImpl(this, new MatchExpression(t => true, t => result));
            }

            public override ClosedMatchContext<T, TResult> Return(Func<T, TResult> resultProjection)
            {
                return new ContextImpl(this, new MatchExpression(t => true, resultProjection));
            }

            public Func<T, TResult> Compile()
            {
                return value => m_matches.First(expr => expr.Matches(value)).Evaluate(value);
            }

            // TODO: use immutable queue
            readonly ReadOnlyCollection<MatchExpression> m_matches;
        }
    }

    public static class EnumerableExtensions
    {
        public static IEnumerable<T> ConcatSingle<T>(this IEnumerable<T> sequence, T element)
        {
            foreach (T item in sequence)
                yield return item;

            yield return element;
        }
    }
}
Advertisements

6 Comments »

  1. […] argument dependence revisited Filed under: Uncategorized — jacobcarpenter @ 6:36 pm My last post had a fatal flaw: it looked like it was about F# and pattern […]

    Pingback by Chained generic argument dependence revisited « Jacob Carpenter’s Weblog — March 3, 2008 @ 9:30 pm

  2. Cool stuff!

    Comment by Kirill Osenkov — March 15, 2008 @ 5:22 pm

  3. […] through Generics and Lambda abuse to reproduce the same actions.  You can read more about that here. But, that’s easy stuff that can be easily done by C#, albeit differently.  Let’s try for […]

    Pingback by Adventures in F# - F# 101 Part 5 (Pattern Matching) - Matthew Podwysocki's Blog — March 17, 2008 @ 3:09 pm

  4. […] Of course, it’s completely hypocritical of me to say so, since I’ve abused C# to make it exhibit F#-like behavior in the past. […]

    Pingback by Euler 14 « Jacob Carpenter’s Weblog — April 4, 2008 @ 12:51 pm

  5. […] While this is certainly no pattern matching, it didn’t seem like terrible C#: […]

    Pingback by C# abuse of the day: SwitchOnType « Jacob Carpenter’s Weblog — April 23, 2008 @ 5:30 pm

  6. Very interesting article and I have spent the past few days trying to modify your example for the following purpose but it is beyond me. Here is my challenge:

    I need to take an incoming set of numbers (or varying lengths) and find patterns within those numbers that builds up a hierarchy of matches with the lower levels representing the most finite matches (no less than 3 numbers) and the higher levels representing higher levels of organization.

    Take the following line:

    1 21 319 3 4 5 319 43 5 2 1 21 319 3 4 5 3 4 5 87 90 31 76 42 1 21 319

    The first level of matching would find 2 groups:

    Group 1 = 1 21 319
    Group 2 = 3 4 5

    This transforms the line into
    [Group 1] [Group 2] 319 43 5 2 [Group 1] [Group 2] [Group 2] 87 90 31 76 42 [Group 1]

    A new group can then be formed

    Group 3 = Group 1 + Group 2

    [Group 3] 319 43 5 2 [Group 3] [Group 2] 87 90 31 76 42 [Group 1]

    Over time I might find this entire pattern is repeated across groups of numbers and thus it can be consolidated further but I need to resolve this first issue right now. I have tried using your methods above but I cannot figure out how to extend what you wrote – any thoughts?

    Comment by Ken — August 6, 2009 @ 5:21 am


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: