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!

(more…)

February 4, 2008

DispsoseAfter

Filed under: csharp, extension methods — Jacob @ 9:17 am

My development team at work has recently started a technical blog: http://code.logos.com.

I just contributed my first (real) post: DisposeAfter.

Enjoy.

The Shocking Blue Green Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.