Pattern matching is a very powerful tool used to destructure and perform case analysis on data. It’s commonly found in more academic functional languages and has recently made its way into Python. In this post, we’ll discover pattern matching and implement it in Racket.

I will assume that you have some familiarity with Racket. We’re going to be writing some macros, but general familiarity with macros should be enough, we’re not doing anything fancy.

1  Motivation

If you’re already familiar with pattern matching, feel free to skip to the implementation.

Before we get to pattern matching, let’s talk about trees. Let’s say we’re trying to find the largest element in a binary tree. You can do this with predicates and accessors:

Easy enough. Now, let’s reflect a binary tree to create its mirror image:

This looks pretty similar to the previous function. In fact, it’s not hard to imagine pretty much every function on trees looking just like this: Check if it’s a node with node? use field accessors to get the left and right subtrees, check if its a leaf with leaf?, and use field accessors to get the data.

Let’s be good little programmers and avoid repeating ourselves by creating an abstraction:

This is a little cleaner. It got rid of the predicates and accessors, but there is still a little boilerplate with those lambdas. To fix this, we can go one step further and make a macro!

Very nice! We have a concise syntax for defining functions on binary trees. One limitation is that we can’t look deeper than one level into the data structure. If we were doing something like tree rotations, we’d need to look 2 levels into the structure, but these tools wouldn’t support that. Another limitation is that this only works for binary trees! Do we have to make this every time we work with union data?

Let’s look at some examples with lists. First, let’s split a list into pairs:

Now let’s zip two lists together:

There is a similar pattern, but more general: We have a few possible cases for the shape of our data. We check the possible cases, and based on the shape, we extract pieces of our data and operate on them. Except this isn’t as straightforward and abstract-able as our very repetitive binary tree operations. There is still an abstraction to be made, but it’s a much more general and powerful one. This abstraction is, of course, pattern matching.

2  match

Here is how we would implement a tree operation with pattern matching:

It’s pretty much the same as our bt-match, except now we have to specify which constructor we’re matching in which case.

The general form for using match is (match val [pattern body] ...) where val is the value you’re destructuring, pattern is a pattern, which specifies the shape of the data for this case and may bind variables to its fields, and body has access to these fields. A match form can have many cases. The first case with a pattern that matches the shape of the data binds the variables in its pattern to the corresponding pieces of val and runs that case’s body.

In this example, we have a node pattern which binds the subtrees to variables called left and right. This pattern matches when the value being matched is a node and matches the sub-patterns against the sub-trees. Variable patterns like left match any type of value and bind the value to that variable for use in the body.

Here is how we would implement the list operations with pattern matching:

In the to-pairs example, we first check for the case of a list with at least two elements by using two cons patterns. A cons matches values that are cons pairs and matches the first sub-pattern agains the car and the second against the cdr of the value.

We also see the underscore pattern _, which matches against any value, like a variable pattern, and ignores the value. It is often used like else in a cond, but can also be used to ignore a field as a subpattern.

Here, we have a usage of a nested pattern. We have the pattern (cons x (cons y lst)). The pattern that matches the cdr of lst is another cons pattern. The ability to nest patterns like this allows us to check deeply into data structures, which is something we couldn’t do with our bt-match macro.

In the zip example, we’re matching against two values xs and ys. A simple trick for doing this is creating a list with two values and matching the list. Here, we use the list pattern which can take an arbitrary number of sub-patterns. Intuitively, it matches values which are lists with length equal to the number of sub-patterns and matches each element of the list on its corresponding sub-pattern. In this case, since we’re matching against the value (list xs ys), we use two sub-patterns (cons x xs) and (cons y ys). If they are both conses, we can cons both elements to the zipped list by recurring. Otherwise, one of the lists must be empty, so we just return the empty list.

Pattern matching is very powerful. We can check the shape of our data structures, reach deeply into them, check multiple cases, and even perform case analysis on multiple values at once.

Let’s do one more example just for fun. Let’s take in a list of left/right steps representing a path in a binary tree and get the data at the leaf specified by the path:

We are using list patterns and tree patterns at the same time to do case analysis on two values of two different types. Imagine how annoying this would’ve been to write without match!

The first pattern covers the case where we should go left and the tree is a node. We don’t care about the right sub-tree, so we ignore it with an underscore pattern. We check for the symbol 'left using a literal symbol pattern, which only matches if the value is equal to the symbol. Numbers, strings, etc. can be matched with literal patterns in a similar way. Here, the pattern does most of the heavy lifting. All we have to do is recur on the sub-tree and the rest of the path. The next case is the same, but for going to the right. Next, we have the case where the path is empty and we’re at a leaf. In this case, we return the data.

Any other case is an error. If the path is empty, then the tree must be a node. Otherwise, the leaf case would’ve run. This means the path was too short. Similarly, if the list is non-empty, the tree must be a leaf, which means the path was too long.

You should always cover all possibilities when using match. If none of the patterns match, we get an error. Really, we should always have an absolute fallback case where the whole pattern is the underscore pattern. But for this function, we’ll assume that the inputs are actually trees and paths.

Alright, hopefully I’ve sold you on the power of pattern matching by now if you weren’t already familiar with it. Without further ado, let’s implement it!

3  Implementation

Since we’re going to be binding variables, we’re going to need a macro. And this isn’t going to be some simple define-syntax-rule, it’s going to be a full-on compiler! The main part of the implementation is going to be a compiler from patterns to condition checks, field accesses, and variable bindings.

To start off, let’s write minimatch, which only handles a single case and only supports cons and variable patterns.

To match a cons pattern, we’ll check that the value is a pair and recur, matching the sub-patterns on the car and cdr of the pair. To match a variable pattern, we just bind it with a let.

The main macro just simplifies things for the helper macro which does most of the work. We make a local variable for the value and wrap up the multi-expression body as a single expression. The helper expects that the value expression is a variable and the body is a single expression.

The helper macro is recursive on the pattern. To match a cons pattern, we recur on the two sub-patterns. To match two patterns, we match the first pattern, and in the body of that case, we match the second pattern, and that case gets the real body. The rest is just shape checking and "field access". Since we are only supporting one case here, we just error if the pattern doesn’t match. In the full version, we’ll go to the next case instead.

The variable pattern is super simple. To match a variable pattern, we just bind the value to the variable and run the body.

Side note: We’re implementing our macro using syntax-rules, which allows us to do pattern matching on syntax. This is kind of cheating, but it doesn’t take away from the core ideas of how to implement pattern matching, which is the translation into checks, field accesses, and variable bindings. If you were making a language like Lisp from scratch and wanted to implement match as a macro, you would have to do case analysis on the syntax the hard way.

Let’s see the expanded form of some examples:

Since matching patterns like cons ends up wrapping the body in more calls to do-minimatch, we end up wrapping the body with ifs and lets. And we only run the body if the value matches the pattern and all the bindings are in scope.

Now, let’s graduate to match and handle multiple cases!

All we did was add an on-fail argument to the helper macro. Instead of that default error, any time a pattern fails to match, it’ll just go to the next case if there is one and error if there isn’t one.

Now, let’s talk about some more pattern types.

(and pat ...) matches all the patterns on the value. It succeeds if they all match and fails if any fail. For example:

It’s commonly used when you want a whole value and also want to take it apart.

(or pat ...) matches the first successful pattern on the value and fails if none of the patterns match.

This is a silly example, but if we used it in bt-get, it would’ve cleaned it up a little:

Instead of there being two node cases, we can combine them into a single case using an or pattern. Regardless of which pattern matches, we do essentially the same thing. It’s just with different values based on which case we’re in. Generally, when two cases have the same body, you can usually use an or pattern to turn it into one case.

When you use an or pattern, all sub-patterns must bind the same variables.

Keeping with the logic trend, we also have (not pat), which succeeds to match when pat fails to match and fails when it succeeds. Anything variables bound in pat are not bound when the not matches.

The variables in the list pattern are not bound in the body.

We also have the quote pattern which matches against literal values:

It succeds if the value is equal to the quoted datum.

Before we implement, let’s clean up our macro a little:

It’s doing the same thing as before, but now we don’t have to repeat the val, body, and on-fail stuff everywhere.

Now, let’s implement these new patterns:

For list patterns, we pretty much just translate them into cons and quote patterns and recur.

For and patterns, if there are no sub-patterns, we succeed. After all, every sub-pattern succeeded! If there is at least one sub-pattern, we match it and if it succeeds, we match the same value against the and of the rest of the sub-patterns. If any of the patterns fail, the whole and ends up failing because we pass on-fail to every recursive call.

For or patterns, we do "the opposite". If there are no sub-patterns, we fail. If there is at least one, we match it. If it succeeds, we immediately run the body. If it fails, we try matching on an or of the rest of the sub-patterns. Instead of duplicating the on-fail like and, we duplicate body.

Remember how or patterns can be used to turn two cases with the same body into one? This clearly automates that because we use the body twice! And since we’re essentially putting the body in two cases, if one of the patterns binds a variable that isn’t in the other, the other’s copy of the body is going to have an unbound variable. That’s why they all need to bind the same variables.

For not patterns, we just fail if the sub-pattern matches and run the body otherwise. Since the body isn’t run in the case with the pattern, it doesn’t have access to the variables bound by the pattern.

Lastly, quote patterns simply check the value for equality. And datum doesn’t have to be a symbol, as we see in the last example. It could be any datum, including lists, numbers, etc.

We also threw in underscore patterns which just run the body.

And there we have it! We have created a very useful little pattern matcher. The real Racket match form has many more patterns that we didn’t implement like quasiquote patterns, struct patterns, predicate patterns, etc. With this framework, we could implement most of those pretty straightforwardly. Many of them boil down to predicate checks and "field accesses" like the patterns we’ve implemented.

Struct patterns like for matching on node are a little complicated. You need to use some more powerful macro tools to detect a struct name and use struct reflection to get the predicate and field accessors. It’s totally doable, but I just want to focus on the big ideas in this post and that doesn’t really shed more light on the essence of pattern matching.

4  Bonus: Core Patterns

You know how we implemented the list pattern by translating to other patterns? It turns out that the patterns we implemented can be translated into a pretty small core language of patterns.

That core language includes and, or, not, variable patterns, and some new patterns we didn’t implement.

One of the new patterns is ?. The pattern (? predicate) matches if we apply predcate to the value and it returns a non-#f value.

The other is app. The pattern (app func pat) applies func to the value and matches the result against pat.

We applied car to '(1 2), got 1, and matched that against the pattern x.

These two new patterns directly express our shape checks and field accesses! For example, the pattern (cons car-pat cdr-pat) is the same as (and (? cons?) (app car car-pat) (app cdr cdr-pat)). The pattern 'datum is the same as (? (lambda (value) (equal? value 'datum))). Underscore patterns are just (? (lambda (value) #t)). Using these translations, it’s super easy to add patterns for other data structures like vectors, hashes, etc. without having to write the boilerplate of doing a shape check and field accesses.

One very cool thing the real match system supports is pattern expanders, which are macros for patterns. Using this, we could add new patterns in terms of existing ones without even having to change our match macro! And not just us, anybody can extend match by writing a pattern expander. Just like the Racket language itself.