Thursday, March 30, 2023

'Modules Matter Most' for the Masses

The title of this post should be in double quotes, but it seems parts of Google have not learned about abstracting sanitization. Screenshots of bug here.

As systems grow, they become more complex, overwhelming the mind. And yet we humans have a trick to build objects of far greater power than could be understood by any one person. That trick is modularity: the ability to create something out of parts which exist independently yet combine into a far greater whole.

A funny thing happens when a system is broken into modules. A new object appears, something separate from and longer lived than the system itself: the interface.

The most powerful explanation I've found of the primacy of the interface is Bob Harper's Modules Matter Most. According to Harper, the world has successfully taught that good interfaces have multiple implementations, but so few know the other half of the story. The essence of modularity is a simple theory, with the formalism fitting in just two lines. Yet it's obscured in most languages; only two are suitable for teaching it. And if you're thinking it's some academic language like Haskell, then you're half wrong.

And there were zero suitable blog posts for explaining that. Because:

Rumor has it that Professor Bob Harper's second career choice would have been a priest. Judging from his lectures: what a priest he would be! He rains fire from the pulpit about how the idea of a variable is mankind's greatest invention, how homotopy type theory is “the mother theory” and mathematics is a subfield of computer science, and how a single type rule contains the secrets of software engineering, all while he preaches the gospel of the “Holy Trinity” of type theory, proof theory, and category theory.

Alas, in contrast to his lectures, Harper's writings lack the incendiary power to catch on in those not already stuffed with the proper kindling. Much as I personally enjoy Modules Matter Most, many students find it impenetrable thanks to its casual references to deep ideas in type theory, and we field questions from students confused about it several times per year.

For the first time, I shall now explain the ideas in Harper's article for a broader audience.

Modularity means module types

We are told that “modules should depend on the interfaces of other modules, not their implementations.” There's a lot that can be said about what it means to depend on something. But there are some subtleties as well to what goes into an interface.

But wait! Lots of languages have interfaces built in. Here's an interface for a stack in TypeScript.

interface Stack {
   isEmpty : () => boolean;
   push    : (x: number) => Stack;
   pop     : () => [number, Stack];

It is true that TypeScript has a keyword “interface” and an associated language construct. As do Java, Objective-C, and many other languages. But these are far more limited and restrictive than the general concept in software engineering. Confuse them at your peril.

The TypeScript code may look straightforward, but it actually falls far short of being an interface to an arbitrary stack implementation. I'll explain how in full later. But for now, I'll point out a more basic failing: This is the interface for a class, not a module. I will be sticking with stacks as my running example, but we want something that can generalize to, say, the Node Filesystem module. This module contains multiple distinct classes, such as file handles, directories, and output streams. It also contains top-level functions with special access to these classes; the classes also have special access to each other. They are interrelated in a way where giving an interface to just one class at a time will be missing something. There is a module boundary, in that code inside the module is given capabilities denied to code outside.

Now, go try to write a TypeScript interface that lets you share information with other classes in the same module but not in other modules. You just can't.1

We need to talk about the interface of the file system module as a whole. And the interface keyword just won't cut it.

Lots of languages, including TypeScript, have a construct they call “modules.” Yet when we look at the documentation, it only speaks about imports and scoping. There is nothing about modularity, information hiding, or any of the other properties we've learned to associate with the word “module.” They are empty shells containing a bundle of definitions. In the right hands, they can bundle together cohesive functionality with shared secrets. But I prefer to call them what they are: namespaces.

Real Modules

But there is another construct that better captures what a module is: a bundle of functions and types whose internals may be hidden from the outside world. And that construct is, appropriately, called “modules.” Proper modules. But sadly, they can be found only in the ML family of languages, particularly OCaml and SML. Here's the interface for a stack module in OCaml:

module type Stack = sig
  (* Types *)
  type stack
  (* Functions *)
  val mkEmpty : () -> stack
  val isEmpty : stack -> bool

  val push : int * stack -> stack
  val pop  : stack -> int * stack

This does resemble that TypeScript interface. And it should, as the bulk is defining the same set of functions (plus one missing from any object interface). But there are some extra features it has that the object interface does not.

First, notice how that opaque stack type is declared separately from its operations. We could easily add more types, and their operations would have full access to each other. For the file system, I could go

module type FileSystem = sig
  type filehandle
  type dir
  type fs_watcher


and the internal representations of file handles, directories, and watchers would be freely accessible within any module implementing the FileSystem type, but hidden without. The abstraction barrier is placed around the module, not around each type.

Another feature is the ability to write programs not tied to any single implementation of the Stack interface. To do this, we write a function which takes a stack implementation as input, and returns as output a module containing the rest of the program.

module MyProgram (S : Stack) = struct
  (* Definitions go here *)

Thanks to these module-valued functions2, OCaml programmers can write modules which are not bound to any particular implementation of their dependencies. The general term for this is “dynamic architecture,” and most languages support it poorly. They rely on #ifdef's to do this — or worse, the build system. Dependency injection is a common antidote, but only part of the answer. You can parameterize the Stack implementations in Java, but the easy way is wrong, and the correct way is complicated. As I'll explain later, to do it properly, you must first stuff everything about a module, including multiple types, into a single injected object.

Realer Modules

But, even in a language with real modules, there is still something missing.

Let's do away with these special words “push” and “pop,” and just call the operations “add” and “remove.” Now we can create a Queue interface that also has “add” and “remove.” How would it compare to the Stack interface? It would be identical! And yet I expect that people who want the two interfaces merged are about as common as people who demand to be served first because they entered the line last.

This shows that, when we think about interfaces, we are not just thinking about whether a module contains functions with certain names and certain shapes of inputs and outputs. We are also thinking about the specification — the behaviors we expect these functions to have. Perhaps there is a comment next to pop() saying that it's the inverse of push(). This fact can be considered part of the module type every bit as much as the types of each constituent function because knowing this is necessary to actually use the module. So let's make it actually part of the type.

There are a few languages with type systems powerful enough to express the relation between push() and pop(). Coq, Agda, Idris. I can show you what it looks like in one of these, but there are already enough uncommon notations in this post. So here's what it looks like in a hypothetical extension of OCaml. In this example, I've extended the Stack module type with two properties: that isEmpty returns true on a freshly-created empty list, and that pop is the inverse of push. I can add more, but this is enough for illustration purposes.

module type Stack = sig
  (* Types *)
  type stack

  (* Functions *)
  val mkEmpty : () -> stack
  val isEmpty : stack -> bool
  val push    : int * stack -> stack
  val pop     : stack -> int * stack

  (* Properties *)
  property mkEmptyIsEmpty : isEmpty(mkEmpty ()) = true
  property popPush        : forall s n, pop (push (n, s)) = (n, s)

You may have noticed that I used the same colon (:) syntax when stating the properties that I used when giving the types of functions. That is not a coincidence. In a sense, I can think of the isEmpty value as a proof that it's possible to take a stack and produce a boolean.3 Similarly, mkEmptyIsEmpty is a value whose type is a proof that: isEmpty(mkEmpty ()) = true. In a language that can do this, the expected properties of each function in a module are physically part of the module's type. In other languages, they are still morally part of its type. We put these expectations into our documentation as a simulacrum of languages that can do this first-class.

When we talk about only relying on the signature or interface of a module, it means to only rely on representations and properties which are exposed in the module type. In this post, I am primarily using the term “module type” to avoid preconceived notions about what “interface” and “signature” mean. But, in correct usage, the type, signature, and interface of a function or module are the same thing. 4 And types are the end-all be-all of interactions between program components. For, in a sufficiently powerful type system, every useful fact that can be stated about a function or module can be stated as part of its type.

And now we are ready to explain the type-theoretic account of modularity.

Modularity in One Rule

Type theory is the science of taking all the beauty of programming and compressing it down to a few opaque lines full of Greek letters. Alternatively, type theory is the art of discovering how subtle aspects of mathy definitions give rise to strange new universes of programming models.

I've written before how a single rule explains why mutable and immutable data models act differently. And Bob Harper claims that modularity is characterized by a single rule. Rather than relying on me interpreting it for you, I think it's worth diving in and facing this source of truth directly. After developing the idea that everything you might want to say about a program can be reduced to a type, modularity becomes astonishingly simple.

So here's the rule. Rules like this are read: if each part on the top is true, then each part on the bottom is true. Each of these parts is called a “judgment.” I'll break it down for you.

And now, an explanation of each judgment in the rule:

This part means that the module M has module type (i.e.: interface) A. This judgment is read “gamma entails M has type A.” Here, Γ is called the context, and contains everything else that has been declared in scope. It doesn't change much, so we usually don't need to talk about it. Also, let me remind you that a sufficiently powerful type system lets you stuff arbitrary correctness requirements in the type, so we can read “M has type A” as saying “M is correct.”

This means that module N has module type B. Within the definition of N, it may use an unspecified module x that has module type (interface A). This must be true for any module that satisfies that interface.

This part introduces some new notation: “[M/x]N” is read “M substituted for x in N.” Taken together, this judgement means: We take N from above, which used some unknown module x that has module type A. Now, we replace x with M, the actual module definition that has module type A. After doing that, this new module, the composition of M and N, still satisfies that same type B, and is hence correct.

Now, bringing it all together, this rule means: We have a module N which uses some module M, but only through its type (interface) A. M can be replaced by any other module with the same type, and N will continue to work. That's modularity.

Many to many

The relation between module types and modules — more generally, between interfaces and implementations — is many-to-many. One direction of this is pretty common knowledge: an interface can have multiple implementations. But the other direction is equally important and less appreciated: implementations satisfy multiple interfaces. 5 This is a succinct statement of a special case of the lesson in my post The Design of Software is a Thing Apart: it is not possible to look at an implementation and recover its intended interface because there are multiple possible such interfaces.

This is such a general idea that it applies in the physical world too. If you see someone baking cookies with coconut oil instead of butter and using dairy-free chocolate chips (implementation), it's not possible to determine what dietary restrictions (interface) they are trying to satisfy: vegan, dairy allergy, or unrestricted but just prefer the taste. And going further: vegans can arrive at the exact same set of dietary restrictions for completely different reasons (design intentions), be it out of concern for animals, religious practice, or belief in health or environmental benefits.

Now back to software. To see that the stack interface satisfies multiple design intentions, just think of two different applications of stacks; anyone working on either could reinvent the idea of a stack if they had never encountered it before. Now, to show you an implementation satisfying multiple interfaces, I'll need to give you a concrete implementation of a stack. I am going to give the full definition in OCaml, but you do not need to understand it. If the syntax is unfamiliar to you, you can take my word for it that this is the normal implementation of a stack based on linked lists.

module ListStack : Stack = struct
  (* Types *)
  type stack = int list

  (* Functions *)
  let mkEmpty () = []

  let isEmpty s = match s with
    | [] -> true
    | _ -> false

  let push (x, s) = x :: s

  let pop s = match s with
    | [] -> failwith "Cannot pop from an empty stack"
    | x :: xs -> (x, xs)

  let size = List.length
  let iter = List.iter


This implementation contains way more information than the interface. Just as you could write pages describing the dust specks on your doorknob, you can write endless facts that are true of this implementation. You can explain that the error message when popping from an empty stack starts with “C” and ends with “ck,” for instance. And I've added on a few extra functions, size and iter, to make it easier to actually write useful facts about this implementation not guaranteed by the Stack module type, even the version augmented with properties. Here are six other module types the ListStack implementation also satisfies:

  • An extension of the Stack module type that also guarantees all functions run in constant time.
  • An Iterable module type of modules with an iter function.
  • A Sizeable module type of modules with a size function.
  • A module type giving everything in the Stack module type along with the presence of the iter and size functions, but no additional properties about the new functions
  • A module type with a property giving the relation between the size, push, and pop functions
  • A module type containing everything in the Stack module type along with additional properties giving the relations between push, pop, size, and iter.

We see there are multiple ways to find a new module type. We can focus on functions of the implementation not present in Stack. We can omit some of the functions. We can add extra facts about the functions in Stack. And, when we add new functions, we can add properties about how they relate to the old. No realistic caller of ListStack will rely on everything that can be said about it. And that means that each caller would still function if ListStack was exported through the minimal interface containing exactly what that caller relies on.

And we can actually do this, for, not only does ListStack satisfy all these module types, but it does so with no prior arrangement. If I want to export ListStack through a CheckEmpty module type that only contains the isEmpty function, I do not need to go back and make sure the Stack module type is declared as a subtype of CheckEmpty, as I would for a Java class. I just write ListStack : CheckEmpty and it works.6

The Perils of Java (and Haskell) Schools

Harper names OCaml and SML's support for modules as a reason to have one of them supplant Java in CMU's undergraduate curriculum. When I first read this piece as a CMU undergrad over 10 years ago, I thought Harper was just making excuses to foist his favorite language onto everyone else. Now, I think he's right.

Java is just bad at giving multiple interfaces to the same implementation. They've tried teaching this kind of modularity in Java for years and failed. I now face this myself: when I ask students to give examples of a single implementation with multiple interfaces, around half the time I get an example of a single interface with multiple implementations.

But Java has objects, and objects at least make it easy to give multiple implementations to the same interface. Right?

In the hands of a skilled user, yes. But even demonstrating that is not easy.

Let's try translating the Stack module type into a Java interface. Here's the obvious way:

interface Stack {
  Stack push(int x);
  int pop();
  boolean isEmpty();

This may look like a straightforward translation, but it's actually very wrong. The pop() method doesn't return a new stack, so this implementation has to be imperative. There is no mkEmpty() function, meaning there must still be a constructor invocation new ListStack() somewhere in the code, tying it to a specific stack implementation. And push() actually loses some important information: there's nothing saying that the Stack it returns must be the same implementation. The version I gave in TypeScript earlier is slightly better (thanks to TS having tuples), but still suffers from most of these problems.

Here's the correct translation. We need to use the Factory pattern to parameterize over implementations of mkEmpty(), a type parameter to tie the factories to their corresponding Stack's, and something called F-bounded polymorphism to make sure the Stack's going out and in have the same implementation.

interface StackFactory<S extends Stack<S>> {
  S mkEmpty();

interface Stack<S extends Stack<S>> {
  S push(int x);
  Pair<S, Integer> pop();
  boolean isEmpty();

So now we have some Java idioms — the Factory pattern and this funky S extends Stack<S> business — getting in the way of just trying to explain how a program can use a stack without knowing which implementation it is. If you had to give this lesson to sophomores, you might be tempted to do it in OCaml to avoid this nonsense, even if you don't know OCaml.

Maybe we can teach it in Haskell, a language with far more industrial use than either OCaml or SML. Haskell's typeclasses do make it straightforward to write an interface for many different stack implementations.

class Stack s where
  mkEmpty :: () -> s
  push    :: (Int, s) -> s
  pop     :: s -> (Int, s)
  isEmpty :: s -> Bool

And yet, even this invites confusion about the relationship between implementation and interfaces. Typeclasses may be cool, but they come with a dark side. Consider the Read typeclass:

class Read a where
  read :: String -> a

With Read, the compiler will automatically pick the right read function based on how the result is used. So if you type read str + x, where x is an Int, then it will run an integer-parsing routine on str. But if you type getEmployeeName (read str), then it will pick and run an Employee-parsing routine. The downside though is that, without doing some super-advanced stuff, there can be only one such read function for each type. If you want to have two different ways of serializing Employee's, then, sorry! Go back to having separate readEmployeeFormat1 and readEmployeeFormat2 functions like a pleb.

Back to stacks. Say you had a kind of list data structure that can add and remove items from the end just as easily as it could from the beginning. There are two obvious ways to implement a stack using it: by adding and removing things from the beginning, or by adding and removing them from the end. 7

We'd like to explain that there can be multiple ways for this double-ended list to implement the stack interface. The best demonstration would be showing both ways in a single program, but we can't do that. Students are at risk of walking away thinking that “implementation” just means “representation.” For the language cannot express the concept being taught.

So when Harper says that the only languages they could use to teach these concepts to undergrads were SML and OCaml, he's not just being a snooty type theory professor. He's being a snooty type theory professor with a point.

Not Just for ML Programmers

Understanding real modules is worthwhile even if you never intend to work in a language that has them. Modules are fundamental, and so much of what is done in other languages, from build configurations to dependency injection to the Adapter pattern, are in large part an attempted encoding of things easily expressed with modules. To write namespaces in other languages worthy of being called “modules,” you need to understand what representational secrets are shared internally and hidden externally. To properly parameterize a Java program over which stack implementation it uses, you need to do dependency injection on the StackFactory type defined above, something which is much easier to do if you first think about how to do it with modules and then translate.

Modules have so many little pieces which are important in programming and yet which few programmers have encountered except in obfuscated form. I naively thought when I started writing this that I could do it in under 1000 words, but I'm rapidly approaching 3x the length of the original. Harper will throw out a sentence like “It is absolutely essential that a given module satisfy many distinct types , without prior arrangement” and I'll take a page to explain what that means. It's a fundamental idea, and it's trivial in OCaml or SML. It's a tragedy that, to most, it's so alien.

After understanding this post, I encourage you to have a read of the original. I believe I've captured everything important, but Harper has his own unique fire, and he's mixed in some tasty rants about the “machine vs. language” models of code and teaching parallel programming as the default.

Understanding modules fits into a larger mission. Programming shapes the world. But, as programmers, programming languages shape our lives. I'll let Harper himself finish. 

Dijkstra used to say “beauty is our business”, to which I would add that life is too short, and bright minds too precious, to waste on ugly things.  And if you take this point of view seriously, the best and the brightest are drawn to, rather than repulsed by, the field.  [...] students absolutely do love to program and do love the beauty of code, provided that the code you ask them to write is, in fact, beautiful.  There is little more dreary than the corporate bureaucracy of OOP, and few things more lovely than the mathematical elegance of FP.

1 Java has a seldom-used “package-private” visibility specifier which fits the bill a little bit, but stops working once you get a folder of 100 classes and you decide to move a few into a subdirectory.

2 Another name for module-valued functions is “functors.” This is really confusing because “functor” has a grand total of four meanings in programming, each completely different from the others. See Wikipedia's disambiguation page.

3 If you've heard of the Curry-Howard “proofs-as-programs'” correspondence, this is it. Every program's type encodes a theorem, but usually they're not interesting theorems.

4 I actually initially wrote this post using SML, but changed it to OCaml purely because it uses the keyword “module type” instead of “signature.” I want to emphasize: the signature of a module is its type.

5 A salient example: In Objective-C, it’s common to pass an object as its own listener or observer.

6 This would also work in TypeScript, thanks to its structural subtyping.

7 This may be familiar to JavaScript programmers, where there are two ways to treat an array as a stack: using shift()/unshift() and using push()/pop().

Thanks to Alex Rozenshteyn, Emmanuel Genard, Tikhon Jelvis, and William Gottschalk for comments on earlier drafts of this post.

Appendix and FAQ

Nils Eriksson, who previously shocked the world by getting TypeScript's type-inference to play tic-tac-toe, has taken up the challenge of building secret-sharing in TypeScript. It's unusual for TyypeScript, but it has me thinking that maybe this should become a well-known pattern.

Q: You seem to undersell typeclasses. Typeclasses get you 90% of the way to modules, and Haskell's newtype covers the other 10%. Meanwhile, Modules and module-valued functions (functors) may have great theoretical advantages, but they have way too much boilerplate to take advantage.


This is a "Haskell inside baseball" answer and likely a difficult read for anyone not a serious Haskeller. Original context: here.

Yeah, this post probably does sound like it was written by an ML afficionado. It was actually written by a hardcore Haskeller of over 10 years who was even on the PC of the Haskell Symposium last year, although I was explaining a blog post by an SML maximalist.

But actually, the lack of ML-style modules has been at the top of my Haskell wishlist for about as long as I’ve been using it, next to the ability to have finer-grained control of typeclass instantiation at use-sites. I was pretty disappointed by Backpack for that reason; they missed their chance to fix this problem, and Backpack is still little used a decade later.

A big difference between typeclasses and modules is that typeclass instances are chosen per function and need to be specified. Module implementations can be chosen at the top level.

So here’s an example of where I want modules: This for my implementation of equality-constrained tree automata (ECTAs), from my ICFP ’22 paper Searching Entangled Program Spaces.

I have two implementations of the memoization library, and expect at some point to add a third based on concurrent hash tables. I switch between them by commenting out an import statement at the top. There is nothing in the type system that forces these two modules to have the same interface. If I wanted better support for switching between them, I would add a build flag and #ifdef’s.

How would I do this with typeclasses? The normal way is to add a typeclass constraint to every single function that needs it. I would go further and add said parameter to many that don’t, because it’s an implementation detail whether a given operation is memoized, and interfaces should be stable. Now my choices are to either wrap each ECTA in an ECTAUsingSingleThreadedMemoization or ECTAUsingConcurrentMemoization newtype, to add a new proxy parameter to every function, or to go full on AllowAmbiguousTypes and force every caller to give a type parameter specifying the memoization library used. Also, did I mention that memoization libraries are based on global state (either “not very Haskelly” or “extremely Haskelly,” depending on your perspective), and that if you supply different instances at different call-sites, the code will function fine, but have a silent performance bug. This puts a burden on the caller to maintain consistency in which the easiest solution is for the caller to….use a module system! The final option is to make the ECTA data structure itself have a phantom type parameter used to select the memoization implemenatiton. E.g.: instead of passing around an ECTA, you always pass around an ECTA Concurrent or an ECTA SingleThreaded.

In any of these, you are exposing implementation details to callers, or even to transitive callers. They are based on universally-quantified types, when I need existentially-quantified types, synonymous with information-hiding.

How to get existentials? I can go object-oriented. In Haskell, that can look like stuffing a typeclass instance inside a GADT. But that doesn’t work for binary functions; I wouldn’t be able to guarantee that, when intersecting two ECTAs, they use the same memoization library (and they would thus use different global state when they need to use the same).

But, yeah, I totally agree about the poor ergonomics of actually writing all your code as a module-valued function (functor) over all its dependencies. I think this could be fixed rather easily using a new kind of import or open statement, but the MLers haven’t yet.