Functors, Signature Families, and ML Modules in Practice
The last post was about sealing a module so clients cannot see the representation. This half of Harper and Pierce is the thing you want next: write the dictionary once, then plug in a different ordered key type.
Functors are modules that take modules. They are still the cleanest story I know for a map library parameterized by an ordered type. They are also how you get error messages that feel like a war crime.
Book: Advanced Topics in Types and Programming Languages Editor: Benjamin C. Pierce Chapter author(s): Robert Harper and Benjamin C. Pierce ISBN: 0-262-16228-8
This is post 15 in my ATTAPL series, covering sections 8.7 through 8.11 of Chapter 8.
Signature families are the missing copy-paste button
Here’s the thing. You have a Dict signature. One implementation uses key1. Another uses key2. Write Dict1 and Dict2 by hand and every later change to Dict has to be replicated. That is how library code rots.
They isolate the pattern as a family of signatures, indexed by the key type. Two representations show up.
Parameterization is the functional programmer’s first instinct. Lambda-abstract the key type, then apply: Dict1 = DictP(key1.X), where DictP is a signature that takes a type Y and plugs it in as key.X.
Fibration is the where-clause version. Start from generic Dict and patch it: Dict where key.X = key1.X. Both recover the same explicit Dict1. The patched signature still matches generic Dict, which is a kind of signature inheritance.
But here’s the problem. Indexing only by a type is theoretically enough and pragmatically annoying. Strings can be ordered lexicographically or by prefix. You want the type glued to its comparison. So they generalize: families indexed by a whole Ordered module, not a bare type.
Parameterization makes you decide up front what is a parameter. Fibration is after the fact. Any type or submodule can become the argument later. That sounds like a taste fight until you get to sharing.
Functors are the module version of lambda
Same story for implementations. A functor is a lambda over a module variable. Apply it to an Ordered module, get a dictionary.
The naive function type Ordered → Dict is not enough. The key type in the result has to be exactly the argument’s type. That is a dependent function type, written Πkey:Ordered. J.
Chapter 2 already set you up for pi types. Same idea, now at the module level. Arguments have to be determinate, because the range signature may mention key.X.
Here’s what I found. The hard part is not “modules that take modules.” The hard part is when two functor arguments have to agree on a type.
Sharing is the actual design fight
Suppose you have transformers. Module ab maps A to B. Module bc maps B to C. You can compose them by hand because you can see that ab.Out is bc.In.
A compose functor cannot see that. n.f expects n.In. m.f returns m.Out. Nothing says those are the same type.
Sharing by specification is the ML style. Refine the second argument: λm:Tr. λn:(Tr where In = m.Out). Or package both into one argument with a sharing declaration, which is just sugar for where. The argument is not a pair of transformers. It is a coherent pair.
Sharing by construction is the Pebble style (Burstall and Lampson, 1984). Factor the shared types out as extra parameters. Compose takes In, Mid, Out, then a pair that already mentions Mid. Jones (1996) pushed this too.
It feels clean if you grew up on higher-order functions. It does not scale. Compose four layers and the internal Mid types crawl out as nuisance parameters. MacQueen (1984) saw this early.
And that’s why it matters. Fibered signatures let you add a sharing equation after the fact. Parameterized signatures force sharing by construction, so every higher functor repeats the plumbing. FoxNet and Ensemble protocol stacks are the real-world version. Each layer is a transformer. TCP/IP is a composition.
Why bother, and the 8.9 pile-up
Three honest reasons to want functors. Libraries parametric in a type plus its operations. Architectures that are already functorial, like FoxNet layers or SML/NJ’s code generator parameterized by target architecture. And extra-linguistic linker tricks (ld -r, class loaders) that already act like functors, except they do not know about abstract types.
Then they tell you not to go fully functorized. Abstracting every import invents fake sharing problems. Experience said this made programs worse.
If a functor body has per-instance state, it should be generative. Two symbol tables from two applications of stFun must not share a Symbol type, or you index the wrong hash table.
If the argument is just a type and the body is pure, applicative is nicer: setFun(int).Set is the same type every time. Sealing inside the body usually forces generativity.
Section 8.9 is the remaining pile. First-class modules: store a module in a data structure, pull it back out. Collapse core and modules entirely and type checking can go undecidable (Harper and Lillibridge, 1994). Dreyer, Crary, and Harper (2003) later got first-class modules without that.
Higher-order functors: apply(f)(m) should match f(m), except if f is generative you lose the type identity. Recursive modules can invent a type A = A → Int if you are sloppy.
What actually shipped
SML and OCaml both do sharing by specification. Official SML: first-order generative functors, no official separate compilation, no principal signatures because elaboration invents type names you cannot write. Moscow ML has recursive and first-class structures, plus both applicative and generative functors.
OCaml: higher-order applicative functors, real separate compilation, and it sometimes rejects well-formed programs when avoidance fails. They wanted f(m).X in sharing specs, so applicative was the commitment.
Haskell modules are basically namespaces. Type classes do the modular work, with one type allowed at most one instance. That is why Int has one Ord, and why two string orderings need newtypes.
C outsources modules to the filesystem. Java has classes, packages, and loaders, and still no clean sharing story for two related abstract types. Objects are roughly first-class modules with one abstract type (TAPL chapter 24). Binary methods hurt because there is no sharing of representations.
History, lightly: Parnas, Wirth, Hoare, CLU, Modula. MacQueen 1984 for ML modules. Mitchell and Plotkin existentials, then MacQueen saying existentials are not enough. Translucent sums, manifest types, singleton kinds. Garcia et al. (2003) compared generic programming across popular languages if you want the tour.
What I actually think
Functors are still the cleanest design I have for a module of maps parameterized by an ordered type. You keep the key type glued to leq. You can instantiate twice with two different orders. Haskell will fight you. Java will give you a generic class and then shrug at the binary method.
The sharing story is why this chapter is worth the headache. Fibered signatures plus where clauses scale. Parameterized plumbing does not.
The error messages are a war crime. One missed sharing constraint and you get a page of functor signatures that mention types you never wrote. That is not a reason to throw the design away. It is a reason to treat full functorization as a smell, the way Harper and Pierce already told you to.
Next up, Christopher A. Stone on type definitions. After functors, the question is what it even means for a type name in a signature to have a definition.
Previous: ML-Style Modules: Abstraction and the Phase Distinction