Tour of a pattern matcher: core patterns and the AST

Alright! Last time we looked at the mouth of extensible-match and how it chews up patterns in order to make them digestible. Before we take a look into the stomach,¹ we should look at what that chewed-up form of patterns looks like. This is an episode with a bit less how and a lot more what than the last one. I’ll explain and justify the core pattern structure we just got out of the expansion process, how and why it’s different from the AST that we eventually like to work on, but also one further transformation on that AST that makes it easier for the rest of the system to digest.

We’re still in the (extensible-match match) library, which we’ll keep dipping back up into because it contains this long chain of procedure calls which actually co-ordinates the whole of the rest of the process of compilation.

Subject variables vs pattern variables

The idea of a pattern variable is simple, and is a concept exposed to the user. In a pattern like (cons x '()), x is a pattern variable. This pattern deconstructs a pair which could previously have been constructed by the same code used as an expression: the expression form takes a variable and makes it the only element of a 1-list; the pattern form takes a 1-list and puts its element in a variable. This is the essence of the equational reasoning property which makes pattern matching such a nice style to work with and think in.

Subject variables are pattern variables’ twin from the dark side. In the above example, there’ll be three subject variables: one for the pair itself; one for its car, and one for its cdr. The upshot is that the pattern matcher doesn’t generate code like (if (equal? (cdr p) '()) ...); it will always extract the thing it’s interested in to a variable first: (let ((g1234 (cdr p))) (if (equal? g1234 '()) ...)). This simplifies things because it means that the kind of thing we’re testing against is always a simple variable expression no matter what the nesting level of patterns is.

(Obiter dictum: this doesn’t affect the efficiency of the final generated code; it anticipates the Scheme compiler’s own pass which will un-nest expressions, namely CPS or ANF conversion.)

Subject variables are always generated identifiers; their precise names are only interesting to the internals of the pattern matcher. I mention them here because they’re important for understanding the structure of expanded patterns and the first few stages of compilation we’ll look at today. The first thing that %core-match-lambda does to patterns, in fact, is to generate subject variables for each of the values it will be examining. (Recall that %core-match-lambda has multiple sets of patterns, but each such set has to match the same number of values. The values for all clauses get the same subject variables.) Although these subject variables are the entry-point for the pattern match, this is in fact the last set of new subject variables generated, because all of the others (in the example above, the ones for the car and cdr of the pair) are generated during expansion.

Core patterns

Behold, a grammar:

I won’t dwell on the first six rows (core:wildcard, core:var, core:quote, core:and, core:or, core:not) because they’re not very interesting. Core:wildcard is spelled _ in the high-level pattern language, core:var is just written as a variable name; core:and and core:or are now restricted to two subpatterns each. Otherwise, you can pretty much find everything you need to know about these from the documentation of the high-level forms in SRFI 262.

Core:row is where things start to get slightly more interesting. This pattern isn’t directly exposed to high-level forms, but it’s used for the patterns which can come after the procedure expression in a high-level ? pattern and the value patterns of a => pattern. They’re also used for each of the individual values at the top-level of a multiple-pattern %core-match-lambda form.

In a row pattern, all the subpatterns have to match, but the compiler is allowed to test them in any order. While a full rationale will have to wait until the next episode, in general the order in which it makes most sense to test subpatterns is not always the left-to-right order in which they appear in the source code. In the (cons x '()) example, we’re far more interested in the cdr of this pair than we are in the car, because the cdr can tell us whether the pattern matches or not; only once we know that the cdr is the empty list should we bother trying to load the car.

Core:apply corresponds directly to the high-level => pattern (which was called apply in earlier drafts of the SRFI) but has a different structure, to do with the need to give each value its own subject variable. The ⟨expression⟩ gives the procedure which is to be applied to the pattern’s subject; the ⟨identifier⟩s are subject variables to which each respective returned value will be bound; finally, the ⟨core pattern⟩ will be matched in an environment which includes those subject variables.

Core:subject is the last piece of the puzzle; it simply says which subject variable names the subject of its own subpattern.

How this all fits together is probably best illustrated by example. Our (cons x '()) example expands, within the high-level pattern matching language, to this:

(? pair?
   (=> car x)
   (=> cdr '()))

which in core patterns expands to this:

(core:and (core:? pair?)
          (core:row
           (core:apply car (g1) (core:row (core:subject g1 (core:var x))))
           (core:apply cdr (g2) (core:row (core:subject g2 (core:quote ()))))))

A single-subpattern core:row isn’t very useful, but an equivalent expansion using SRFI 1’s car+cdr² would be:

(? pair?
   (=> car+cdr x '()))

which in core patterns is:

(core:and (core:? pair?)
          (core:row
           (core:apply car+cdr (g1 g2)
            (core:row
             (core:subject g1 (core:var x))
             (core:subject g2 (core:quote ()))))))

Something to note here is what core:var actually, formally does: it takes its subject variable and turns it into a pattern variable. g1 is a hidden, generated variable; x is bound within its clause to the exact same value.

That’s more or less it for the core pattern language; I hope it’s more-or-less clear how it works. I’ve omitted core:seq from this description. If this series ever covers core:seq and the implementation of the pattern matcher’s functionality for running simple regular expressions over sequences of Scheme values, it will be in a bonus episode, possibly quite a bit later. I’m leaving it out here because the implementation is still an unhappy mess, much more so than any other part; also, Wolfgang Corcoran-Mathe has pointed out that the current API mixes idioms in a confusing way, and fixing that might involve some other deep changes to how it’s implemented.

The Abstract Syntax Tree (AST)

As covered in a previous missive, core patterns are pseudo-record syntax objects; accessing fields from such syntax objects is slow; real records are much faster; so to make decision tree generation go faster, there’s an additional layer, called the abstract syntax tree, implemented as real Scheme records.

Actually, though, there’s (at least) one more reason besides speed that the AST is better to work with going forward – see if you can spot it in the definition:

(define-record-type primitive-pattern
  (fields (immutable expr-table pattern-expr-table)))
(define-record-type pattern
  (fields subject)
  (parent primitive-pattern))
(define-record-type wildcard-pattern
  (parent pattern))
(define-record-type var-pattern
  (fields name)
  (parent pattern))
(define-record-type quote-pattern
  (fields datum)
  (parent pattern))
(define-record-type and-pattern
  (fields subpat_1 subpat_2)
  (parent primitive-pattern))
(define-record-type or-pattern
  (fields subpat_1 subpat_2)
  (parent primitive-pattern))
(define-record-type row-pattern
  (fields subpats)
  (parent primitive-pattern))
(define-record-type not-pattern
  (fields subpat)
  (parent primitive-pattern))
(define-record-type ?-pattern
  (fields predicate-id)
  (parent pattern))
(define-record-type apply-pattern
  (fields procedure-id vars subpat)
  (parent pattern))

I’ve omitted the AST equivalent of core:seq for simplicity.

There are a couple of improvements here. I was so determined to kill free-identifier=? from the decision tree generator entirely that the expressions naming the procedures for ? and =>/apply patterns are now interned into a table, giving them each a unique integer for the decision tree generator to use as a proxy for whether they are the same identifier. (This was probably a premature optimization, in hindsight.)

But the big improvement is in the (not very well-named) distinction between a pattern and a primitive-pattern. Notice that core:subject is gone from the AST! In its place, every pattern that needs to know the name of its subject variable has it stored directly within it.

In the core pattern language, you don’t actually know what (core:quote ()) means without looking for a lexically enclosing core:subject: in our (cons x '()) example, (core:quote ()) alone could be looking at the pair (no match), the car (not intended, but might incorrectly match), or the cdr (as intended).

Making this change made the decision tree generator much simpler, apart from the speed boost from using records instead of syntax objects.³ It no longer has to track a lexically implicit subject for each pattern.

You might wonder why the code doesn’t do this already during pattern expansion, and why core patterns don’t include their subjects in the same way the AST does. Well, maybe ideally it would do this, but in the sense of having everything in its right place at the right time, it’s probably the right thing for simplicity. Doing it this way lets the expansion of patterns happen completely independently of any context; we add that context to each individual subpattern later.

Tracking just the state of each expansion in continuation-passing style is tricky enough; adding the current lexical subject variable as extra state to pass around would make it more complicated. Moreover, continuation-passing expansions imply that the expander’s final result has to be a syntax object anyway – it’s not safe to go straight from unexpanded patterns to AST records – so let’s take the opportunity afforded by the need to have a slightly redundant layer in order to at least make the process of creating that redundant layer easier. That said, if Scheme does one day grow a way to call a transformer and apply marks independently of the expander’s main loop, it will probably then be time to get rid of core patterns and track the current subject variable implicitly while expanding directly into AST records.⁴

The other half of the clause

We’re not quite done with the AST. We’ve talked a lot about the left-hand side of each pattern matching clause – the pattern – and we’ll continue to do so. But there is another side, which is what happens when the pattern of a clause is known to have matched.

(define-record-type action
  (fields procedure args))
(define failure-action (make-action #'fail '()))

(define-record-type patact
  (fields pattern action))

There’s not too much to say here. When a top-level pattern matches, its corresponding action is called. It’s a procedure, named by a generated identifier for each clause, plus a list of the variables bound by the corresponding pattern (which become arguments of the procedure). If no pattern matches, we call a special action called fail which just raises an exception.

A pattern and an action together make a clause, but here we call it a patact.

Unifying subject variables

That’s all the what; let’s finish up with a quick look at another bit of how. We’ll talk a lot more about what it takes to generate optimal code for a pattern match next time, but there’s one step that takes place to get the patterns in a form that’s easier to optimize.

Recall that each (sub)pattern expansion happens independently, without knowledge of the context from other expansions; and also that the expansion of => patterns into core:apply patterns. What this means is that equivalent applications generate distinct subject variables; we really want equivalent applications to create equivalent subject variables!

To see how, let’s put the example we’ve used so far into context:

(define (last ls) ; returns the last element in a list
  (match ls
    ((cons x '())  x)
    ((cons _ ls*)  (last ls*))))

These two patterns will expand, respectively, into the same core pattern we saw above and another very similar one:

(core:subject ls
 (core:and (core:? pair?)
           (core:row
            (core:apply car (g1) (core:row (core:subject g1 (core:var x))))
            (core:apply cdr (g2) (core:row (core:subject g2 (core:quote ())))))))
;; action: (g3 x)

(core:subject ls
 (core:and (core:? pair?)
           (core:row
            (core:apply car (g4) (core:row (core:subject g4 (core:wildcard))))
            (core:apply cdr (g5) (core:row (core:subject g5 (core:var ls*)))))))
;; action: (g6 ls*)

We applied car and cdr to ls in each pattern, but the result was called g1 and g2 in the first pattern and g4 and g5 in the second one. We only want to call each procedure once – if at all – in the generated code, so it would be nice to only generate one variable. This is what the pattern subject unification pass does: for every application of the same procedure to the same subject, the created subject variables should have the same name. The result is that the first pattern will still look the same, but the second will be (the AST-level equivalent of) this:

(core:subject ls
 (core:and (core:? pair?)
           (core:row
            (core:apply car (g1) (core:row (core:subject g1 (core:wildcard))))
            (core:apply cdr (g2) (core:row (core:subject g2 (core:var ls*)))))))
;; action: (g6 ls*)

It does this in a recursive pass which looks for combinations of subject, procedure, and number of output values⁵ it’s not seen before; when it finds one, it puts the variable names that were generated for that pattern’s version into a hash table. When it sees the same combination of subject, procedure, and co-arity again, it replaces that AST apply pattern with a version whose subject variables are renamed, and recursively traverses the apply pattern’s subpattern to change instances of those subject variables appearing within quote-patterns, var-patterns, other apply-patterns etc. to the unified name.

This is also something that could be done during expansion, but it’s just simpler to do it as an extra pass after expansion because it makes expansion independent of external context.

Potential future AST transformations

Subject variable unification is the currently the only optimization pass that’s done on the AST of the patterns before handing over to the decision tree generator, which is responsible for most of the work of finding an efficient way to match a set of patterns. But there are a couple of other passes the pattern match compiler could make at this point to improve the quality of generated code, or make the decision tree generator simpler.

Rewrite complex not patterns

At the moment, using a not pattern will completely frustrate the optimizer. It’s not too bad if you only put not around a datum or a predicate – but if you put it around an (implicit) and, the optimizer will only know how to compile it and its entire subpattern at once, and be unable to avoid potentially repeating equivalent computations for multiple similar patterns. Being able to mix in patterns which do match when they don’t match anywhere arbitrarily would just add too much complexity to the decision tree generator.

Fortunately, in 1846, compiler engineer Augustus De Morgan formalized an intuition about the relationship between negations, conjunctions, and disjunctions, which could eventually be applied here to ensure that the not pattern never appears outside of an and or or pattern. Ensuring it also never appears outside of row would be ideal, but the obvious solution – turning e.g. (not (row pat1 pat2)) into (or (not pat1) (not pat2)) – may be an accidental pessimization because or has an order-of-evaluation restriction which row doesn’t.

This AST transformation alone would be an improvement for the decision tree generator, but the real improvement would come with recognizing common not operations and being able to fully optimize them. Another benefit of this transformation would be the ability, in theory, to (sometimes) issue compile-time warnings about patterns like (not _) which will never match.

Remove quote patterns from the AST

A (core:quote val) pattern can be rewritten as (core:? (lambda (x) (equal? x 'val))), but I don’t do this during expansion because it makes it harder to recognize that two quote patterns are equivalent. Since conversion from core patterns to the AST includes the recognition of equivalent expressions in order to give them unique integer IDs, it could generate an appropriate lambda expression for each mentioned datum then.

This would be good to do together with the previous one, because adding support for explicitly recognizing not patterns in the decision tree generator would add complexity there; removing quote patterns from the AST would remove some related complexity to balance that out. The cp0-equivalent pass of the Scheme compiler will then get rid of the lambda expression again.

Re-chain and patterns to only be nested on the right-hand side

Another way to frustrate the optimizer at the moment is to write something like (and (and a b) c) instead of (and a (and b c)). The optimizer will look for things it can do in the left-hand side of an and, but if it sees another and it isn’t smart enough to be able to look again at that and’s left-hand side, mostly because reconstructing the leftwardly-nested and after deciding to take action on its contents would be too much of a pain. The ordering relationship for these two nesting structures is the same, so an AST transformation should rewrite them all into a form that’s friendlier for the decision tree generator.

Or patterns, on the other hand, don’t have this problem, because the decision tree generator will flatten those out into entirely separate patterns while it’s working, and that process can handle any nesting structure it finds.

Next time

The decision tree generator! This will probably be the third of a four-part series, before the final part – a short coda on turning decision trees into executable code.