The expression problem

Now we get to ML’s defining tradeoff, the one your OO instincts will fight.

The expression problem, named by Philip Wadler in 1998 but observed long before: a program manipulates data of various cases using operations. You want to extend in two directions: add new cases, and add new operations. OO makes it easy to add new cases (subclass) and hard to add new operations (touch every class). ML makes it easy to add new operations (write a new function with a match) and hard to add new cases (touch every match).

Neither is wrong. They’re dual. The question is which axis your problem extends along.

The two axes

Visualize it as a 2D grid:

Each cell is “what op N does on case X.” The grid is the full specification of the program’s behavior. The question is: how is the code organized?

Object-oriented organization puts the rows together. Each class (Case A, Case B, …) is a unit that includes all of its operations. Adding a new case is local: write a new class with all its operations. Adding a new operation is global: touch every class and add the new method.

ML organization puts the columns together. Each function (Op 1, Op 2, …) is a unit that includes all of its cases. Adding a new operation is local: write a new function with a match over all cases. Adding a new case is global: touch every function and add a new match clause.

The grid is the same; the orientation differs. Each orientation rewards extension along one axis and punishes extension along the other.

For systems work, the columns win

For most systems work — protocol parsers, schedulers, control planes, compilers, anything where the shape of the data is fixed by an external specification and the operations multiply — ML’s choice is exactly right.

The shape of HTTP doesn’t change weekly. The shape of TCP segments doesn’t change weekly. The shape of an x86 instruction doesn’t change weekly. The shape of a process state machine doesn’t change weekly. But you’re constantly adding new operations: a new serialization format, a new analyzer pass, a new metric, a new optimization, a new debugger view.

ML rewards this. Define the sum type once; write a new function per operation; the compiler tells you if you missed a case. The data type is the spec, and the spec is stable. The operations are the surface area, and the surface area grows.

OO punishes this. Adding a new operation requires touching every class. The visitor pattern exists specifically to make this less painful, and the visitor pattern is a clumsy reinvention of pattern matching, with worse ergonomics and worse type safety. When you find yourself reaching for visitor in an OO codebase, you’re trying to write ML through a keyhole.

For UI and plugin systems, the rows win

The opposite shape applies to UI code, plugin architectures, and anything where new cases arrive constantly and the operations are roughly fixed.

A widget toolkit has a fixed set of operations: render, handle input, layout, focus. But the cases — Button, TextField, Image, custom Widget3 your user wrote — multiply continuously. OO’s row-orientation handles this gracefully: each new widget class implements the four operations, and the rest of the system never notices it.

ML can handle this case too, with first-class modules or records-of-functions (we’ll see this in chapter 5), but the support is less ergonomic than OO’s built-in class hierarchy. You wouldn’t write a UI toolkit in stock ML for the same reason you wouldn’t write a compiler in stock Java: the language’s grain doesn’t fit the problem.

The lesson, generalized

Know which axis your problem extends along, and pick the language whose grain runs the same way. Your instinct to reach for inheritance is, for the systems work you’re describing, almost always wrong here. Reach for a sum type and a function instead.

This is not a “ML is better” claim. It’s a “the orientations are duals, and most problems lean one way or the other” claim. The orientation a language commits to is its single most consequential decision; everything else in the language flows from it.

OCaml’s pragmatism

OCaml — the largest ML in production use — has objects. They’re not the same as Java’s; they’re more like structural records of methods with their own type system. But they exist, and they exist for the cases where row-orientation is the right answer within an otherwise column-oriented language. They’re rarely used in idiomatic OCaml because rarely is column-orientation wrong, but when you need them, they’re there.

CML in this book doesn’t have objects. The cases we care about — kernels, protocols, schedulers — are all column-oriented. If we ever wanted to write a plugin system on top of CML, we’d reach for records-of-functions (which are a less-pretty form of objects) or first-class modules (which are a more powerful form). For the body of the book, sum types and functions suffice.

The duality in design

The duality reaches into the design of effect systems too. An effect handler is, structurally, a column: it provides a set of operations (the handler clauses) for a fixed set of cases (the effect’s operations). When you write a new handler, you’re writing a new column for the existing effect. When you add a new effect, you’re adding a new row.

In CML, effects are declared once, and the operations of an effect are fixed by that declaration. Adding a new operation to an existing effect would require touching every handler for that effect. So effects are cases-stable, operations-stable, with handlers as the extension point. This is the column orientation extended to control flow itself.

We’ll come back to this when we get to effects formally in chapter 7. For now, the seed is planted: ML’s design philosophy is column-oriented all the way down, including its concurrency model.

What this chapter committed to

The duality between case-oriented and operation-oriented program organization. Why systems work tends to be operation-oriented and ML therefore fits. The honest acknowledgment that the opposite shape exists and ML is not the right tool for it. A preview that the duality reaches into effect systems too.

The next chapter is about polymorphism, which is what lets ML write code generic over the case axis without giving up on either type safety or performance.