Last week, I surveyed a few differents kinds of composition that programmers are familiar with. This was the start of an effort to figure out how to talk about designing software in a composable way. My plan was to first survey what we’ve got, and then second try to make sense of it. This strategy seems to be working because I found two things interesting from last week’s post:

  • I didn’t expect to see a “two-level” stratification to the kinds of composition we saw. This was perhaps best exemplified by function calls: we had behavioral composition (functions can call other functions) and value composition (higher-order functions and partial application).
  • I didn’t expect how good this lens would be for differentiating between different programming “paradigms.” Sometimes “paradigms” can be eclectic jumbles of different ideas, so finding more clean, sharp ways of clearly distinguishing them is cool.

So today I wanted to give this stuff a little more thought:

  • I’m still not completely sure of this, but one possible source of the “two-level” stratification are languages that offer you a fixed set of available composition operators, and languages that let you go further and construct your own custom composition operators. In any case, I think this is worth looking into in its own right.
  • I wanted to explore more the idea that paradigms can be distinguished by their support for various forms of composition.

In essence, I think we can look to programming paradigms and see three different levels of support for a new feature:

  1. You have a new Thing you can use.
  2. A built-in set of composition operators are offered to allow you to construct bigger Things from smaller Things.
  3. You can now define your own composition operators.

This isn’t the only lens we can use of course. I’ve previously looked at paradigms in terms of their preferred corners of the type extensibility space. This let us directly contrast functional and object-oriented languages and the designs they tend to produce. But composition is a very important perspective, too.

The evolution of languages by composition, at a glance

I pretty much want to spend the rest of this post elaborating on the following table. For each thing on the left, we can see different kinds of programming languages that have progressed from left to right, introducing more support for composition.

Feature Non-composable Things Fixed Composition Operators Custom Composition Operators
Grammars Pre-structured programming (ASM) Structured programming Macros, Extensible languages
Functions Pre-call stack (early Basic) Call-stack languges Functional languages
Types Early languages C-like static types Parametric polymorphism and beyond
Classes N/A Traditional OO Metaobjects?

Languages and their grammars

The basic way in which we construct a programming language displays this progression rather nicely, I think. We had early “languages” with minimal structure (e.g. ASM). Then we got more linguistic languages that had actual grammatical structure with things like “declarations,” “statements,” and “expressions.” Probably starting with just minimal expressions in the early line-numbered Basics, and then introducing statements and structured programming later.

For the most commonly-used languages today, that’s where we are: at level 2, with a fixed language grammar. All further composition we make use of in typical programming languages isn’t of the linguistic variety.

So our programming languages offer us a few basic kinds of (for example) expressions, and then offers a fixed set of composition operators we can use to glue expressions together. We can take two expressions, glue them together with + and get one expression summing the subexpressions. Not too complicated.

While languages typically stop here at level 2, there’s also a reason why we stop here too. Again taking expressions as the example, while we can’t introduce our own expressions into a language like Java, we can write new functions. I’ve previously called these kinds of things abstraction mechanisms: fixed interfaces that nevertheless offer extensibility to something that otherwise isn’t extensible. Function calls have a pretty fixed semantics (e.g. consider evaluation order, strictness); they’re not exactly the same as an arbitrary new expression. But if all we need is the common case—needing to create our own way of combining several subexpressions into a single whole—well, a function call can do that.

So abstraction mechanisms are one way we can avoid needing extensible syntax, but that doesn’t stop us from trying to go beyond this, too. Macro systems are attempts to allow user-defined (abstract) syntax. I’ve mentioned my own Ph.D. thesis on this blog before, the premise of which can be thought of as trying to come up with a composition operator with better properties than any macro system offers. But for the most part, the existence of abstraction mechanisms, like functions, are enough for us.

Functions and their composition

So while languages typically stop short of letting us introduce new composition operators in the form of new expressions (and so forth), they’re able to justify doing so by introducing a new concept. And now that we have a new concept, we can look at how it composes. So let’s consider function composition.

Last week, I told a short story about the early history of programming languages. I won’t repeat it too much. To summarize, there was definitely an era before we had functions in our programming languages, and then once introduced there was an era before we had acceptable properties from the “function call” composition operator. To the point where you could argue they shouldn’t count as functions at all. But with modern call stacks, we’re pretty freely able to define the behavior of a functions in terms of other functions, and compose their behavior naturally.

And if we go further and create a sophisticated enough function type, then we can start to define our own function composition operators. And any language that can do that seems justifiably called a functional programming language.

So here we get our first pretty sharp distinction: procedural to functional. Procedural languages go as far as level 2, while functional languages go to level 3. The observation has certainly been made before (“first-class functions” are another way of putting this difference), but I’m not sure I’ve seen this pointed out from a purely compositional perspective.

Types from other types

But functions are not the only abstraction mechanism. They let us extend expressions (and statements to an extent, too), but there are other linguistic phenomenon we might want to extend too. For instance, languages give us abstraction mechanisms for types.

This, too, was not always the case. Back in 1970, there was a conference called the “Extensible Languages Symposium” with a number of papers that focused on the ability to extend languages with new types. The idea of constructing an abstraction mechanism, instead of making the language extensible, eventually took the winds out of the sails of that research direction. (As far as I can tell, at least.)

In this case, the abstraction mechanism is simply rich enough ways to construct new types from old types. The idea is, essentially, defining new types from old types… at all. Going from level 1 to level 2, in other words.

The popularity and persistence of C demonstrates that it’s enough to have even just some struct-like aggregation types (though we also have to consider the way C breaks its own type system, void* and casts and all that). But there’s quite a variety of the kinds of types we need to be able to construct. I’ve complained before that languages lack support for sum types, and this has implications for our ability to construct differently extensible abstractions. Without those, we’re constrained.

But by introducing rich enough composition operators for types, we get a language with a powerful enough abstraction mechanism that perhaps we do not miss the ability to extend the language with new types. Then we can consider what it means to go from level 2 to level 3 and permit custom composition operators. This commonly takes the form of parametric polymorphism. For types, this should a bit like it does for functions: we can produce types that take other types as arguments.

However, type systems are generally more limited than what functions are capable of. For a variety of reasons, we want composition operators with good properties for types, and it’s hard to do that. So type constructors usually aren’t able to do just anything with their type arguments. There’s a reason academic programming languages researchers are pretty obsessed with types these days. It’s an active area of research to design this well.

Classes: not objects

Last week, I thought of composition in terms of objects and classes. I think this was somewhat confused. Or at least, this week’s perspective is different.

The things with object composition is that it’s pretty much the same as type composition. Classes and records/structs are not so different in that regard. So “favor composition over inheritance” is really more “favor one form of composition over this other composition operator with crummier properties.”

If we instead think about classes as the new “Thing,” (and treating objects as just another type) then what classes introduce is the behavior associated with a type. And then we can start to fit them into this story. We can declare a new class with a new behavior, and that alone would fit into level 1 of the progression: we have a new Thing, but no way to compose them together.

But in that table above I left the first category blank, because as far as I can tell, classes sprang forth with inheritance from the beginning. For all that inheritance is a composition operator with poor properties, object-oriented languages never really existed (that I’m aware of) without it or something like it.

But after that we can start to see some deficiencies. There isn’t really any notion of a custom composition operator in any common OO language I’m aware of, though some kinds of mixins/traits come somewhat close. Java in particular definitely does not allow one to write class Foo<T> extends T, which is the kind of language construct you’d need to start producing new behaviors from old behaviors. (At least, that’s the kind of feature you’d need if you wanted to use the inheritance and generics features that are already there. As an aside, my old post on OO without inheritance using proxying/forwarding lets you start constructing your own composition operators, thanks to the ability to proxy to dynamic objects. Neat.) Instead, common OO languages generally just fall back on on type and function composition instead.

But just because it’s not popular doesn’t mean it doesn’t exist. Metaobjects are all about creation and manipulation of classes in programmatic ways. Metaobjects aren’t common in part because they’re complexity minefields. I’ve written before about how programmers love power too much and ignore short comings in properties. Metaobject protocols are another good example of a powerful feature where the power comes at the expense of reasonable properties. Unfortunately, I’m not aware of any active work trying to find a better design for metaobjects.

Other “things”

We sure do run out of different words to mean “thing” in computer science, don’t we?

Last week, another form of composition we looked at was linking. Certainly this is a form of composition, but I’m not sure about “user-defined” forms of linking. I suppose perhaps Java’s Classloaders fit the mold? OSGi is pretty much just a library, after all.

Other kinds of languages have different “things.” Prolog has relations, but these aren’t especially more enlightening to look at than functions, as far as I can tell. There’s just a different semantics to the composition operator.

Haskell has type classes. Instances show off the level stepping again: regular instances show off ordinary composition, and implication instances (instance Eq a => Eq [a]) show off user-defined composition. So certainly there we can define how to construct behavior from other behavior.

I wonder what other things I’m not thinking of. Monads are compositional ways of thinking about effects. There’s probably interesting things to say about compositional approaches to concurrency. (Especially contrasting with non-compositional approaches to concurrency, like threads and mutexes.) Hm.