Brzozowski Derivatives: Exercise in Combinatory Style

2025-09-16

If you’ve never read Parsing with Derivatives, I recommend it enthusiastically. It’s a brief, readable introduction to Brzozowski Derivatives—an exceptionally simple method for evaluating regular expressions. They’re not usually a great choice for an industrial case, but they’re a tremendously elegant and pleasing construct, and they’re also a great case as a project for learning a new language or programming style.

I’ve got a collection of such exercises called the Brzozowski Variations.

I want to discuss the most recent one, which attempts to write the derivative in a combinatory style, using APCL.

Being an exercise in style, it’s artificial, even contrived. You shouldn’t write code like this. Nevertheless, we recall this series’ experimental inquiry: when removed from the context of syntax, what are the benefits (if any) of pointfree style?

Let’s look at the nullable? function. We test whether a given language (being a composition of language primitives that have a meaningful concept of derivation) contains the empty string; in our context named ε.

Here’s as compact-as-possible an implementation in Lisp Flavoured Erlang:

(defun nullable? "Test if the language contains the empty string." ([(tuple 'empty)] 'false) ([(tuple 'epsilon)] 'true) ([(tuple 'char _)] 'false) ([(tuple 'star _)] 'true) ([(tuple 'union a b)] (or (nullable? a) (nullable? b))) ([(tuple 'cat a b)] (and (nullable? a) (nullable? b))))

It’s hopefully self-explanatory: given some tuple representing a language, we pattern-match on its type (the first element of the tuple) and implement a simple definition of nullability for each possible type.

Through the use of multiple function heads we’ve avoided needing to give a name to the language. Nevertheless, in the cases involving recursion we do have to bind both children of the union and cat languages to names, which we then invoke nested in the bodies of those function heads.

We can compare the same logic in Janet, in a combinatory style:

(def get-tail (partial (flip tuple/slice) 1)) (def is-type (recombine = left (comp first right))) (defn comb-cond [& pairs] (fn [x] (label result (each [pred f] (partition 2 pairs) (if (pred x) (return result (f x))))))) (defn nullable? [x] (let [children-nullable? (comp (partial map nullable?) get-tail)] ((comb-cond (partial is-type :empty) (constant false) (partial is-type :epsilon) (constant true) (partial is-type :char) (constant false) (partial is-type :star) (constant true) (partial is-type :union) (comp any? children-nullable?) (partial is-type :cat) (comp every? children-nullable?)) x)))

A few things jump out at us immediately. First of all, even if we ignore the helper function comb-cond, it’s longer. Second is that helper function: cond, as it exists in most languages, is inherently pointful. It’s a syntactic construct, not a function, and each case body is a block to be evaluated. So we must compose comb-cond. A few notes on what, if we wanted to, could also be called the cond combinator, and theoretically even included in something like APCL:

• It is a true combinator, in that it is a function (not syntax) which nevertheless doesn’t refer to any variables that were not passed directly to it.
• Its constructor takes pairs of predicate and transformation functions, both of which are called on the single argument to the combinator itself.

Some interesting properties fall out of a completely combinatory approach: first of all we have eliminated any free variables from the body of the dispatch logic. That is, there are no named things inside the definition of nullibility. This is what I refer to as “reducing the conceptual inventory”.

Second, the business logic consists entirely of constructing functions, without evaluating any of them. Because the control flow itself expects higher-order functions, we’re able to express the entirety of our business logic without actually evaluating it.

Something that, in turn, falls out of this latter fact is that a purely combinatory style eliminates the need for macros: macros give us the ability to mention syntactic constructs without evaluating them, while the style we’re experimenting with similarly ensures that nothing in our syntax tree is evaluated unless it ought to be.

The interested reader is invited to read the rest of the implementation.

I’ll add just the very last bit, which marshals nullable? and the actual taking of the derivative to create a simple regexp engine. First, in tail-recursive style:

(defun matches? (["" l] (nullable? l)) ([(cons c rest) l] (matches? rest (derive l c))))

And in combinatory style:

(def matches? (comp nullable? (partial reduce derive)))

While in the case of nullable?, the fully combinatory version almost certainly involves jumping through too many hoops; in this simpler case we arguably gain clarity and simplicity.

In this case I want to draw the readers attention not to the use of reduce (though I will argue that we are doing the same thing—abstracting a common pattern in order to simplify our concepts—merely in a different domain), but rather to the absence of c or l from the version that relies on composition of partial functions. These names add nothing to our code. They’re simply placeholders for arguments which are immediately passed on without comment or transformation to reduce.

We can therefore, by removing them, simplify our universe without losing anything of significance. In fact, we’re able to describe the operation of our regexp perfectly by simply describing how its verbs relate to each other, without making reference to any nouns.

---

Thus, after completing the exercise, we ask ourselves: what benefits do we get from the pointfree style? Are there parts of this version that are better than their equivalents in the standard implementation, and if so, why?

I think we can claim that there are. The examples of nullable? and matches? in LFE both contain placeholder variables: meaningless names, a, b, l, c, that exist only to ensure that the parts of the program that do contain meaning are executed in the right order. I submit that code which does away with those names is better.

There is of course a cost associated with that doing-away. As we layer on combinator applications, the interaction of the underlying functions becomes harder and harder to tell at a glance. We can express nearly anything using these abstractions, but we quickly exceed the bounds of good taste.

Thus the work in front of us is to develop that sense of taste, to become sensitive to those patterns of application that map well to the tools in our library of combinators. There are some whose surfeit of names and parentheses obscure the simplicity and universality of their structure.