Sunday, April 06, 2008 2:00 AM bart

Pattern Matching in C# - Part 0

Last week I blogged about a functional-inspired (type)switch expression in C# and in a reaction on some comments I mentioned I'm playing around with something bigger. Let me set the record straight, this post isn't that bigger thing, it's just a related piece of the puzzle. But what's up this time? Pattern matching. Not as in regular expressions or so, but more of a language construct as one can find in the ML camp including Haskell and F# (amongst others).

In fact, this blog series is not just about bringing this concept to the world of C# - and allow me to point out I'm not going to take this all the way, rather I want to discuss some implementation patterns - it's also about the bigger picture, outlining what one can do with expression trees and the such.

 

Introduction

What's a pattern match in this context? Much like a complicated switch. But where a switch simply checks for equality (either of the value or the type, as outlined in the aforementioned post), a pattern match goes much further. Here's a simple example from F#:

let rec fib x =
   match x with
   | 1 -> 1
   | 2 -> 1
   | x -> fib(x - 1) + fib(x - 2)

First of all, the whole thing is an expression: it produces a value. This is a core difference with a-functional statements (an overstatement) such as if and switch, something our functional switch solves. But there's more. In fact you couldn't really write the code above in terms of a typical switch (without cheating with the default clause) since the last matching clause doesn't compare against a constant but rather a symbolic variable. in hear you scream "This isn't too fancy, is it?" and you're absolutely right (for now).

But first an exercise: something is missing in the fragment above (tip: rabbits freeze below zero).

Nothing too fancy so far indeed, but what about this?

let orElse left right =
   match left, right with
   | true, _ -> true
   | _, true -> true
   | _ -> false

We're still matching constants, but have punched a few holes in the patterns. For example, the first pattern says: if left == true (and I don't care about right), the result is true. The last clause is rather the fall-through case that matches everything. So, an important take-away is the ordered nature of a match (as opposed to a regular switch where one should be able to reorder the case blocks at will).

Still not too mind-blowing I imagine, so let's add another piece to the picture:

let rec calc x =
   match x with
   | Constant a -> a
   | Add a b -> (calc a) + (calc b)
   | Sub a b -> (calc a) - (calc b)
   | Mul a b -> (calc a) * (calc b)
   | Div a b -> (calc a) / (calc b)
   | _ -> failwith "Unknown node"

Here we're matching x with certain shapes of objects, while extracting data from those objects before entering the clause body. Such matches can be pretty complex and the language emits code that knows how to do the matching and extract the right data to bind it to the free variables in the clause (e.g. a and b).

There's even more, like matching lists using the cons operator ::, matching union and record types as well as regular .NET type checks but let's stay with this for now. As mentioned before, the goal of this series is not to provide a full-blown pattern match in C#, but rather an exploration of the journey that takes us there.

 

Goals

Let's take a pick and decide what we want to provide. The last sample above matching objects with a certain "shape" is pretty attractive. Given an object that has been constructed to embed certain data, we want to match and extract that data given a set of patterns. For example, consider a Person object:

class Person
{
   public Person(string name, int age)
   {
      Name = name;
      Age = age;
   }

   public string Name { get; private set; }
   public int Age { get; private set; }
}

which I'll abbreviate in PC# (pseudo C#) as:

class Person(string Name, int Age)

We can think of this as a record type that simply holds a few values and plays the rules of immutability. Feel free to think about the realization of such types, possibly based on things as simple as tuple types but the definition above should be good enough for our purposes. We'll refine the realization as we go along in order to make the implementation of our pattern match possible.

Now that we have such a type (and others), we can start to do some matching. Ideally we'd have some integrated syntax that looks like this in PC#:

string message = pattern (x) {
   match Person(name, 25) => name + " is 25 years."
   match Person("John", age) => "John is " + age + " years."
   else => "Unmatched object"
};

or even, if we know we're about to match only persons:

string message = pattern (Person x) {
   match (name, 25) => name + " is 25 years."
   match ("John", age) => "John is " + age + " years."
   else => "Unmatched person"
};

Of course there are many assumptions on types and syntax to make such a thing possible, and one can think of many alternatives that feel more C#-ish:

string message = switch (x)
{
   case Person(name, 25):
      return name + " is 25 years.";
  
case Person("John", age):
      return "John is " + age + " years.";
   default:
      return "Unmatched person";
};

which comes close to our type switch. In fact, the type switch presented before was a rude simplification of the one I have that's layered on top of the pattern match we'll be talking about (which, by itself is simplified for the purpose of this blog series).

 

Realization

Time to talk a little about how we're going to realize this, at least from the API level. We'll have to stick with an API for sure since we don't have a language to build on top of right now. Mirrored after the type switch, it will look like this:

string message = new Pattern<string>(x)
   .Match((string name) => new Person(name, 25), name => name + " is 25 years.")
   .Match((int age) => new Person("John", age), age => "John is " + age + " years.")
   .Else(() => "Unmatched object");

Notice you shouldn't necessarily match against Person objects only. Variable x can be anything, so you can match anything, as shown in the next hypothetical sample:

public static XElement ToXml(this Control c)
{
   return new Pattern<string>(c)
      .Match((string text) => new Button(text),
         text => new XElement("Button", new XAttribute("Text", text))
      )
      .Match((int value) => new Slider(value),
         value => new XElement("Slider", new XAttribute("Value", value))
      )
      .Else(
         () => new XElement("Control", c.ToString()) // Closures at work!
      );
}

There's room for lots of refinements (such a a Pattern<Person, string> that would only accept matches against Person objects) but here's how you read it:

Match x with the following, producing a string:
- if x is a person with age 25, the result is name + " is 25 years."
- if x is a person with name John, the result is "John is " + age + " years."
- else, the result is "Unmatched object"

Notice the way the matching works: given a constructor (we aren't really constructing Person objects as we'll see the next time) certain parameter values are bound, resulting in the condition (like age == 25) which is made implicit. Other parameters are bound to a symbolic name which - only on a match - is extracted from the underlying object and bound to the corresponding parameter in the match body. In fact, the sample above simply reuses the same parameter name but (with alpha-conversion) that shouldn't be the case:

string message = new Pattern<string>(x)
   .Match((string bar) => new Person(bar, 25), foo => foo + " is 25 years.")
   .Match((int bar) => new Person("John", bar), foo => "John is " + foo + " years.")
   .Else(() => "Unmatched object");

This reflects a restriction from the implementation (ideally we'd reuse the parameter for both the match clause and body) that has a very specific reason.

Exercise: Can you infer (or guess?) the public contract of our Pattern`1 class from the above? The answer will follow in the next post.

 

Enjoy!

Del.icio.us | Digg It | Technorati | Blinklist | Furl | reddit | DotNetKicks

Filed under: , ,

Comments

# Reflective Perspective - Chris Alcock &raquo; The Morning Brew #67

Pingback from  Reflective Perspective - Chris Alcock  &raquo; The Morning Brew #67

# Dew Drop - April 7, 2008 | Alvin Ashcraft's Morning Dew

Pingback from  Dew Drop - April 7, 2008 | Alvin Ashcraft's Morning Dew

# Pattern Matching in C# - Part 0

Monday, April 07, 2008 7:17 AM by LINQ Recipes

Pattern Matching in C# - Part 0

# Pattern Matching in C# - Part 0

Saturday, April 12, 2008 1:02 AM by DotNetKicks.com

You've been kicked (a good thing) - Trackback from DotNetKicks.com

# Adventures in F# - F# 101 Part 8 (Mutables and Reference Cells)

Tuesday, April 15, 2008 4:08 PM by Matthew Podwysocki's Blog

Time for another adventure in F#, covering some of the basics of functional programming and F# in particular

# Propecia.

Sunday, June 15, 2008 7:01 AM by Hair doctors in calgary propecia.

Propecia blood pressure. Propecia. Propecia generic. Buy propecia buy cheap propecia online.

# Ultracet.

Wednesday, July 02, 2008 5:32 AM by Ultracet.

Ultracet.

# Morning Coffee 162 &#8211; DevHawk

Sunday, April 17, 2011 4:01 PM by Morning Coffee 162 – DevHawk

Pingback from  Morning Coffee 162 &#8211; DevHawk

# switch / pattern matching idea - Programmers Goodies

Friday, July 08, 2011 12:01 PM by switch / pattern matching idea - Programmers Goodies

Pingback from  switch / pattern matching idea - Programmers Goodies

# switch / pattern matching idea | Everyday I&#039;m coding

Wednesday, April 17, 2013 10:59 AM by switch / pattern matching idea | Everyday I'm coding

Pingback from  switch / pattern matching idea | Everyday I&#039;m coding