I’ve posted a lot on Mastodon (and a little bit here) about the adventures I’ve had implementing an extensible pattern matcher in Scheme. Well, the SRFI isn’t too far off finalization now, and the implementation is unlikely to change dramatically, so I reckoned it might be worthwhile to take readers on a tour of how the implementation works: for one thing, for those who want to be able to dive in and understand the code in future and maybe hack on it; for another, as a further propaganda piece in favour of a style of programming still under-used in Scheme; but also I think there’s a lot the budding Schemer can learn about Scheme, and a lot the budding functional programmer can learn about this central construct of functional languages, from studying the implementation. There’s still a lot of mess in the code that I’m moderately embarassed about (we’ll deal with one such embarassment today, albeit a less immediately avoidable one). But I hope that will get cleaned up over time; like visiting a newly-furnished building where they haven’t yet discovered that putting that cabinet there will make the door handle hit the wall and damage the wallpaper, you can see the idea of the place, and those little things will get sorted eventually.

As mentioned last time I talked about the implementation, extensible-match is a Scheme macro complex enough that it can be seen as a compiler unto itself. There’s a sense in which this is a truism – every Scheme macro is a compiler from a dialect of Scheme containing that macro’s syntactic extension into a dialect that doesn’t use it, at least locally – and attempting to define what makes a macro a compiler beyond that is somewhat impressionistic. But extensible-match has intermediate representations, multiple passes, an optimizer, and a code generator to turn all of that back into Scheme code: it’s definitely on the side of a compiler, taken as a whole. But today, following the path that your patterns actually take when the compiler digests them and turns them into running Scheme code, we’ll just take a look at the front end, which looks more like a traditional Scheme macro definition. Even here, there are a few things worth pointing out along the way!

The match forms

We start our journey in the uncreatively named (extensible-match match) library, which provides all the Scheme expression forms with which pattern match programmers actually use to interact with the pattern matcher. There are a dozen distinct macros for getting access to the pattern matcher – from the very basic match itself (which will probably consistute about 90% of real-world uses) to the somewhat obscure match-letrec*.

Under the hood, though, all of them ultimately expand into a use of match-lambda. Partly this is for party reasons – one thing to name them all, one thing to define them and so on – but also match-lambda is, in fact, the fundamental pattern matching form, in that it offers almost everything that all of the subordinate pattern matching forms need. Specifically, unlike match it handles multiple values without consing them up into a list first; unlike match-let and friends it has multiple clauses which it tries in succession.

Match-lambda in turn is implemented in terms of case-lambda, the Scheme way of making a procedure which takes varying number of arguments by simply dispatching to different code based on the number of them. Case-lambda is built in to Scheme, so the first bit of pattern matching – discerning what to do based on the number of values given – is done for us. All match-lambda does is group the pattern matching clauses (which of course can discern more finely) by the number of values they expect, creates a case-lambda clause for each of those groups, and puts a %match-lambda inside each of those clauses. This %match-lambda handles the next stage: it still handles multiple clauses, but each of them expect the same number of values.

This is a good moment to take a short diversion into macro efficiency, or rather into deliberate inattention to efficiency. An ideal macro expansion will look different depending on the exact forms it receives. In this case, you might think it would somehow optimize the macro if it treated the (common!) case where every match-lambda clause takes the same number of values specially, and expanded directly into a single lambda instead of a case-lambda with only one clause, which itself is going to turn into a call to a lambda expression once this %match-lambda is expanded. Not so!

When writing Scheme macros, it’s always better to just handle the general case and let the compiler itself deal with the redundant code you might generate in special cases. This is the essence of the Guaranteed-Optimization Clause of the Macro-Writer’s Bill of Rights. A case-lambda with only one clause is usually treated by the expander as identical to a lambda even before any optimization begins; resulting structures like (lambda (x y z) ((lambda (x* y* z*) ...) x y z)) are trivial for the compiler itself to remove and turn into a more sane form. Adding it into the macro implementation directly would add more lines of code, but would bring no benefit at all the moment the expansion got out of the expander: in a Scheme compiler, getting rid of pointless make-work code like this is usually the first pass done after macro expansion, a combined inlining/partial evaluation/constant folding pass which Chez Scheme calls ‘cp0’ and Guile calls ‘peval’.1 Compiler optimizations which, in a language without macros, seem fairly pointless – ‘who’d ever write code like that?’ – become valuable with macros, and become more valuable the more powerful the macro system is – ‘oh, code generated by other code looks like that!’

This is the point of the ‘guaranteed-optimization clause’: it lets us be laudably lazy as macro authors by guaranteeing us that our code will still run fast even if we don’t take the time to deal with redundant expressions; and it lets the users of macros know that they don’t have to worry about the performance impact of using a higher-level syntactic construct. Macros generate all sorts of silly code structures, not only because their authors don’t bother to deal with special cases, but also because there’s a lot that macros don’t know about the context they’re being used in. But that information which is trivially accessible for the Scheme optimizer once it has a fully-expanded abstract syntax tree. An example of not needing to worry about special cases is that, even in performance-sensitive code, if your macro takes in an expression but only wants to evaluate it once, you might be tempted to try to recognize if the expression is a single identifier to avoid redundantly generating a let expression giving it a name local to your macro. But you don’t need to: the Scheme compiler can just take care of it! An example which isn’t just laudable laziness is when the expansion of a macro includes code which treats its input specially if it’s a certain type – but the Scheme compiler with the fully-expanded program at hand can run a type propagation pass and change the code to reflect its knowledge of the possible types a variable might have at the specific point of each individual use of the macro.

We’ll see a few more examples of this philosophy of ‘just let the Scheme compiler deal with it later’ throughout our tour. In general: ask not what you can do for your optimizer, ask what your optimizer can do for you! The expand/optimize procedure in Chez and Loko, or the ,optimize REPL command in Guile, is your friend whenever you’re trying to work out what special cases it’s worth writing extra code to deal with vs. which would be wasted effort on something the compiler itself could do better anyway.

Anyway, %match-lambda turns out not to be the end of the chain of delegating to yet more primitive forms called lambda, although this final one doesn’t generate a redundant expression in the final code. This is an extensible pattern matching library, so patterns can be forms that the matcher itself doesn’t natively know how to interpret. In order to deal with those forms, we have to expand them into forms which it can natively deal with. That’s right, it’s a macro expander within a macro! (Kind of!)

Pattern expansion

So we move on to the (extensible-match expand) library, which contains the expand-pattern form which %match-lambda delegates to. The job of this library is to turn unexpanded patterns, containing all the weird and wonderful pattern syntax that users defined themselves, into ‘core patterns’ that the rest of the pattern match compiler can deal with directly. We’ll deal with the structure and rationale of core patterns in the next installment; for now, if you’re familiar with the structure of SRFI 262 patterns, they should look pretty familiar with an extra core: at the beginning of their name. For disambiguation, variables are now spelled (core:var name-of-the-var) and _ is spelled (core:wildcard), but they’re generally pretty similar in structure.

The interpretation of non-core patterns is actually done by yet another library, (extensible-match pattern-syntax), but this was a fairly late change which I made in order to be able to write an implementation-specific version of only that functionality for Guile, which doesn’t yet support identifier properties. Potentially in future, implementation-specific versions could appear for other Schemes which provide enough access to their internals to allow correct (or nearly correct) pattern syntax semantics to be impemented in some way other than actually using SRFI 213. Anyway, the two libraries still work together pretty much as one.

The forms in these two libraries are, surprisingly, themselves macros and not procedures, and they’re used in a bit of an unusual way. The problem is applying macro hygiene to the pattern syntax expansions. Put (very) roughly, macro hygiene works by the expander creating a new, unique token every time one expansion of one macro use takes place; when the user-written code which writes the expansion has returned, the expander goes in and changes the names of all the identifiers in the returned code by adding that magic token.

Well, extensible-match itself is a macro, and doesn’t have a way to create one of those magic tokens to apply to identifiers. We have to let the macro expander of the Scheme implementation itself do it for us – but there’s no standard Scheme API for that. What do?

The answer is macros in continuation-passing style. Hilsdale and Friedman’s paper, linked, is a little obscure and doesn’t really make a compelling case for using this in practice apart from hinting at the possibility of some really dirty tricks (Petrofsky extraction, Kiselyov defilement, etc.). It’s a well-known trick, though, for implementing Scheme macros which can expand to a language other than Scheme (embedded within Scheme). Patterns are an example of such a language; Alex Shinn’s loop macro clauses are another (Taylor R. Campbell’s version of this looping macro is more popular, but I’ve linked Shinn’s original implementation as it’s shorter and shows the continuation-passing trick more clearly).

The idea is that a continuation-passing macro matches code of the form

(the-keyword input-of-the-macro ... next-keyword . next-arguments)

and always transforms it into the form

(next-keyword output-of-the-macro . next-arguments)

So the macro receives the name of another macro which will further process its own output. Because the whole output after this transformation goes back into the expander, which thinks a complete expansion is finished, it will apply a new magic token to everything in the output-of-the-macro. If output-of-the-macro is itself a macro use in the sublanguage being expanded into, next-keyword can again recursively transform it into a continuation-passing style macro use at the Scheme level, referring back to itself as the continuation.

You can do this entirely in syntax-rules! Shinn’s loop does exactly this – macro-extensible macros don’t have to involve the most advanced expander features available. But offering direct access to an extension API based on continuation-passing macros has some disadvantages:

It exposes implementation details of the sublanguage to writers of extensions to the sublanguage, failing to maintain an appropriately opaque abstraction barrier between usage and implementation. One can imagine that someone might come along and decide to actually destructure the next-arguments, thinking that they can understand what the sublanguage implementation is packing in there and re-use that information for a nifty feature. In so doing they create a Hyrumesque nightmare for the developer of the sublanguage, who will break their nifty feature the next time they decide that this internal continuation structure needs changing.

The problem is only exacerbated by continuation-passing macro extension APIs which provide more than one continuation, or more information, to their writers. Olin Shivers’s loop macro and Taylor R. Campbell’s implementation of foof-loop both do this: the result may be powerful, but from the point of the designer of the sublanguage, it is inflexible, hemming in future extensions of the power of the sublanguage itself. 1.

It fails to establish a distinct namespace for extension keywords to safely live in, outside of which uses of those keywords are either errors (as in (chibi loop)) or have distinct but related semantics (as in the pattern matcher). It also fails to prevent unrelated keywords being accidentally, mistakenly used as keywords within the sublanguage, which can expand into unrelated forms with unexpected behaviour. 1.

It makes error reporting for incorrect uses of extensions to the sublanguage confusing, since upon failure to match any syntax-rules clause, it has no idea which parts of the macro are implementation details of the sublanguage and which are parts written in the sublanguage and directly entered by the programmer. 1.

Macro writers have to be careful to always return to the continuation they were given. (On the other hand, providing quote or quote-syntax as the continuation keyword makes it easy to debug more complex expansions by single-stepping; whereas most Scheme implementations unfortunately do not provide macroexpand-1 for forms in the Scheme language itself.)

The extensible pattern matcher side-steps all of this by capturing the transformer procedures of its extension macros directly (in identifier properties) and calling them only on the user input, then embedding the output of the transformer procedure into a continuation-passing macro. The only information the transformer for pattern syntax has access to is the syntax object representing the pattern use itself; if there’s an error, it’ll be expressed in terms of this only and not in terms of some low-level form the pattern syntax user isn’t interested it. All the pattern syntax transformer has to do is return its expansion, and what the pattern expander does with it after that is none of its business: a clean abstraction barrier, just like real Scheme macros.

You might ask why, having thus eliminated the usual reasons for writing continuation-passing macros, the pattern syntax expander isn’t just a simple procedural recursion like this:

(define (expand-pattern-syntax stx)
(syntax-case stx (core-pattern)
;; Base case, a fully expanded pattern identified by some special head:
((core-pattern expansion) #'expansion)
;; Recursive case of a pattern with a pattern syntax keyword:
((keyword . _)
(expand-pattern-syntax ((look-up-pattern-transformer #'keyword) stx)))))

Indeed, Sam Tobin-Hochstadt’s paper on extensible pattern matching in Racket presents it as if it did work this way.

As mentioned above, the reason is hygiene: we want to go back into the Scheme expander after each step and apply a unique magic token to any inserted identifiers for each individual use of pattern syntax, so that the names don’t collide with one another. This is, admittedly, somewhat pedantic: there’s no real point to introducing identifiers with the current structure of patterns, but with future extensions there might be, and it’s possible that some unusual pattern macro implementation might have a reason to do it anyway – so it’s worth taking the effort to do the right thing.

All of (extensible-match expand) is thus concerned with implementing a recursive expansion of pattern syntax while maintaining this hygienic property, which it has to do in continuation-passing style. For example, expanding a core:and or core:or means each of their sides have to be expanded recursively, then those expanded forms placed back in a new core:and or core:or which is then deemed fully expanded. If the core:and or core:or is actually a subpattern of some larger pattern – another core:and or core:or even (the core versions of these forms can only be two-armed, as a simplification) – they then have to pass this fully-expanded form back to the ongoing expansion of that larger pattern, so that it in turn can continue and reconstruct its input.

Tobin-Hochstadt’s presentation in his paper is actually something of a pedagogical lie, although it’s not much of one since Racket does have a way to apply its expander’s magic tokens without going all the way back into the expander, and Racket’s pattern matcher uses that to avoid this continuation-passing macro malarkey. This is therefore all a bit embarassing for a Schemer who can look across the aisle and see that Racket has always had better ways of doing this; hopefully, one day, Scheme will too, and all this continuation-passing nonsense will be gone.

As one last point, we don’t expand only one pattern at once – in match-lambda we have a number of clauses, each of which has a number of patterns (for each of the values handled by that clause). So we have not only an expand-pattern in continuation-passing style, but an expand-patterns too, which expands all the patterns in a list of patterns and passes them all on as a list of core patterns; then an expand-patternses which expands all the patterns in a list of list of patterns, passing them on as a list of lists of core patterns, which is what %core-match-lambda actually uses directly. These, of course, work by invoking expand-pattern with a continuation which keeps track of the already-expanded patterns and the ones yet to be expanded. Phew!

All of that gets bundled up and, as %match-lambda requested, the final continuation of the expansion process is %core-match-lambda, the form which co-ordinates the whole pipeline of the actual compilation of patterns into Scheme code.2 We’ll start talking about the stages %core-match-lambda puts the patterns through next time – from here on in, it’s all procedures, and no more expanding match macros into yet more macros!

One last thing: that ‘almost’

There’s one wrinkle in using match-lambda for everything: the forms which do recursive binding – match-letrec, match-letrec*, and match-define – practically speaking need access to something that match-lambda doesn’t give them: they need to know the names of all the variables bound by the pattern match. In order to know that, they have to expand the patterns and extract the list of variables before match-lambda does.

Racket actually expands the patterns twice for this functionality, but I think this is unnecessarily nondeterministic. There is no guarantee that any syntax transformation has to be a pure function; while every expansion of a macro should have the same effect, if you throw in generated identifiers and the possibility of seeded hash functions used in a macro implementation and similar such things, there’s no guarantee that every expansion will be detectably identical. So my view is that it’s better to expand the patterns only once. Match-letrec and match-define therefore invoke expand-patterns or expand-pattern themselves, skip around the publically-exposed match-lambda, and go directly to %core-match-lambda. Match-letrec* is implemented in terms of match-define, letting the Scheme implementation take over the implementation of letrec* semantics.

Next time

I’m not sure exactly how much it will make sense to cover in each individual entry in this series, and thus also not sure how many entries there’ll be. But next time we’ll certainly look at the structure of core patterns and the abstract syntax tree, and maybe start to look at the real meat in the decision tree generator.

---

Most compiler courses: ‘Here is 90% on parsing and a tiny bit on register allocation; good luck and have fun!’

Kent Dybvig: calls the pass of his compiler which comes right after parsing and macro expansion ‘Compiler Pass Zero’, because parsing and expansion aren’t really compiling.↩︎ 1.

That’s right – just like Chez Scheme, the architecture of extensible-match is such that it doesn’t really consider expansion per se to be compilation.↩︎