To re-use code is to build an abstraction with some composition operator in mind. There’s always a composition operator involved: you can’t put two pieces together without something to hold them together. And that operator has some properties—some truths that hold about the parts—even if we’ve gotten so used to them we’ve forgotten what they are.

I’ve previously written about a couple of specific examples of composable designs. We saw how compilers are constructed as a pipeline of smaller transformations. And we looked at the shell and the Unix philosophy and how we can break a problem down into smaller, already solved problems.

Today, I’d like to try to give a broader overview of many different ways we routinely go about composing things together. I want to think specifically about what the composition operator is, and what properties it has.

Linking

The most straight-forward way to re-use code is to wrap it up into a library. It’s what we intend when we create a library, after all.

For native code, the composition operator tends to take the form of the C (static or dynamic) linker, which offers a single global symbol table namespace for the process. So one of the properties we have to deal with is the possibility of name collisions between two libraries, the linker does nothing for us here. Worse still, the semantics of the dynamic linker is usually to take the first name found in the first loaded library that has it, which means you can get bizarre crashes with this inexplicable, silent failure mode. (The only mitigation for this problem is that usually the executable linker will warn you when a name clash happens, so to experience this problem you usually need to drop in a new version of a dynamic library that adds a conflicting symbol, after the compile.)

Aside: Interestingly, it does not have to be the C linker for native code. You can certainly invent a new native language, with a new linker. (Perhaps to, just spitballing here, add a proper namespace resolution mechanism?) But, you’d probably run into the problem of wanting to link your code with C code eventually, which means you may need to re-implement that platform-native C linker in a compatible way.

As a result, pretty much every language has chosen to build on top of the C linker instead. C++’s name mangling is a giant hack to maintain C linker compatibility, not really a sensible design choice on its own.

For languages that have module systems, import semantics can vary. Sometimes, it’s always completely safe to import any set of modules you want. Sometimes, it’s possible that two modules can conflict with each other if both imported. (Perhaps even for extra-lingual reasons, like the initialization code that get runs by importing a Python module.)

Sometimes, multiple different versions of the same module can be loaded and used in different parts of the program. (For example, OSGi in Java.) Other times, such situations are erroneous.

All of these things are the properties that arise from the semantics of the composition operator, import. We build a larger program out of a smaller parts. How that operator works determines what we have to worry about, and how things can go wrong.

Function calls

While libraries are the most obvious attempt at code re-use, they’re far from the most basic. The humble function deserves that title. Every day we’re building bigger functions (or procedures) out of smaller ones.

It can be slightly odd to think of the mere function call as a composition operator, but it might help if we look at the history of programming languages where it wasn’t always. Or at least, where the properties of a function call weren’t up to par, so it was a much worse composition operator.

When we first started transitioning from machine languages to something higher-level like Basic, we pretty much kept the original programming style. Basics almost routinely consisted of a series of line-numbered code, and control flow consisted of goto linenum. This is pretty much the same model as machine code, where you had bytes in memory and control flow consisted of jmp pointer.

Dijkstra’s famous excoriation of goto was because of this naive style. This style didn’t support structured programming, nor function calls of any kind. Sometimes, there was a gosub-like command that stored the line number to return to in a special global variable. Since it was a global variable, it you couldn’t call any other subroutines from your subroutine. (But since it was a variable, you could maybe save its value first, in another global variable, letting you go a whole two subroutine calls deep!)

Later on, when the idea of functions/subroutines was getting more traction, their “local variables” were nothing more than global variables. You could call functions from other functions, but if you came back around to the same function, you’d stomp on your previous call’s variables. It wasn’t until a proper program stack was introduced, with return addresses and local variables stored within, that we actually got proper support for functions. That is to say, a function call composition operator with tolerable properties. Dijkstra’s essay, with this context forgotten, looks like negative argument (against goto), but it’s historical context makes it a positive argument for structured programming with functions.

Richer abstractions with function values

While the humble C function is still composable in the above sense (we can build functions by calling functions), there are further function composition operators we could support besides just calls. But the C function type isn’t rich enough to encapsulate these notions.

The missing ingredient is the ability to construct closures. A C function type is a pointer to instructions to execute on the machine. A closure pairs that with even just one extra piece of data, though that’s enough to raise many data lifetime and allocation concerns, which is why C doesn’t support them.

On the one hand, we can compose the behavior of functions just fine. On the other hand, we’re not able to compose function values without a richer function type that supports closures. I find this observation rather interesting. So even with “just functions” there’s two senses in which we can go about composing them. Procedural languages content themselves with just the former form of composition, while functional languages are largely defined by their additional support for the latter.

If we want to define h(x) = f(g(x)), we have to actually define such a function with a procedural language. But with a functional language, we can define a function composition operator of our own, and we can then write f . g (to pick Haskell notation). To be able to define such an operator, we need closures. The reason we need closures is that we need partial application, in order to write these composition operators. The function composition function is one that takes three arguments (f, g, x) and has the first two pre-applied.

Aside: Lambdas and partial application are equivalent. I think this is well-known among compiler developers, but perhaps less so among other programmers.

If you start with partial application, but not lambdas, you can implement lambdas via a technique called “lambda lifting.” Lambdas in nested scopes can be lifted up to the top level, and any captured variables they use from the local scope can be supplied to the function via partial application instead.

Likewise, if you have lambdas, you can implement partial application. Instead of writing f(_, x) you write \y -> f(y, x). The shorthand notation is still immensely useful, especially when combined with curried function types, but from a language semantics point of view, these two features are the same.

Bigger types from smaller types

We’re familiar with primitive types: integers and floats, the basic machine types we generally start with. From these primitive types, we can construct more complex types. With C, that’s pointers to other types. Function types. Array types. And, we can start to compose several types into a struct.

I’ve mentioned before that C-like type systems have poor support for plain data. In this case, we’re missing the support for alternatives, or sum types, that you get from languages with algebraic data types. Sum types are important for representing trees, which allow us to start creating our own composable data types.

Consider what happens when we start trying to define a JSON representation:

data JSValue =
    JSNull
  | JSBool  Bool
  | JSNum  Double
  | JSString  String

If we stopped here, it’d be a pretty piss-poor data structure. A JSON value could be: a number, boolean, string, or nothing. Big deal, totally uninteresting. But add two more self-referential variants:

  | JSArray  [JSValue]
  | JSObject  [(String, JSValue)]

And suddenly you have the data type that’s all the rage all across the web. While the previous constructors were uninteresting, these last two are composition operators that let us build a bigger JSValue from smaller ones. Just these two are all it takes to get a pretty rich structure.

Almost every type system is defined by how it’s able to construct types from other types. We very rarely care about a particular primitive type that a language has, except in the basic cases (like primitive number types) or in very rare and specialized cases. (For instance, databases will side-step supporting richer type languages by adding a specific primitive JSON type.)

Further, type composition has a similar thing going on with multiple notions of composition, just as we saw functions had. While functions can be divided into the “behavior” and “value” forms of composition, I don’t have similarly handy words to use for types. But we can start to define types that are composition operators for other types using parametric polymorphism (aka generics).

A basic example is a Pair type that operates on two other types. These combinator types can get as rich as the type system allows, but just how rich that should be (and in what ways) is an area of active research. Going all the way, and making the type system just as capable as the “term language,” including allowing terms to be embedded inside types, is called dependent types. But going this way costs us in other properties we might want, such as reliable and predictable type inference. Fully down this route lies theorem proving languages like those of Coq or Agda, where we start adding additional restrictions (like ensuring all functions terminate) in order to gain the necessary logical properties for sound reasoning. Where the future of mainstream programming will go… who knows.

Object composition

We can build objects from smaller objects (and primitives) by simply including them as fields. This is very similar to building a struct from smaller types.

But once again we see a duality between behavior and values. Object composition lets us construct values, but we don’t have a mechanism to compose together the behavior of a class from other classes, except for inheritance. And I’ve previously written about how inheritance is a composition operator with extremely poor properties.

Where objects do go usefully beyond structs, however, is their ability to form composition operators, even without generics. In fact, this is frequently what’s going on when we reach for dependency injection. At its most basic, dependency injection involves taking (as arguments to the constructor) instances of objects that implement a certain interface, instead of hard-coding a concrete class. This makes the “parameterized” class a composition operator, much in the same way JSArray was a composition operator for the JSValue type. Dependency injection doesn’t get more complicated until frameworks are involved that adds some occasionally convenient helpers for finding application-global instances of certain interfaces.

But in the end, just about any time an object takes another object (in my sense of the word object, which is to say, an interface or class intended to be subclassed) we’re designing a type in a composable way, at least somewhat.

Language grammars are composable

Types are built out of other types. Statements are built from other statements. Expressions are built from other expressions. The way language grammars are defined today is inherently composable.

Structured programming introduced control flow statements like if/then/else blocks and various loop forms. It was a revolution in how programs get constructed. And it mostly boils down to thinking about statements in a recursive way, constructing statements from other statements. We start with primitive statements (perhaps calling a function), then we layer additional composition operators on, like if(Expr) Stmt else Stmt conditional blocks, and while(Expr) Stmt loops. This structure gives us composition operators with good enough properties to enable a system for reasoning about the behavior of programs, starkly contrasting with the blob of code we had before.

Many functional languages have tried to do away with statements entirely, and instead concentrate everything into expressions. This frequently increases the amount of inter-operation possible, by making the language constructs more composable with each other. This is especially beneficial when operators are stratified between statements and expressions for no good reason, in retrospect. However, this sometimes happens over-zealously. I think Rust, for example, gained little by not distinguishing between statements and expressions, and may have caused itself a few infamous problems, like all the strange behavior with semicolons.

But everyday coding itself is composing a more complex program text from structurally smaller elements.

End notes

Some of today’s post surprised me, which usually means I need to think about it some more. I wasn’t expecting to find “two levels” of composition in almost every example above, like behavior and value composition for functions. I also thought that contrasting the composition operators available in functional and object-oriented languages was somewhat illuminating. It’s not the perspective I usually take in thinking about them.