What does composability mean in context of functional programming?

What do functional programmers mean when they say a certain thing is composable or not composable?

Some of the statements of this sort that I've read are:

• Control structures are not composable.
• Threads do not compose.
• Monadic operations are composable.

Marcelo Cantos gave a pretty good explanation, but I think it can be made slightly more precise.

A type of thing is composable when several instances can be combined in a certain way to produce the same type of thing.

Control structure composability. Languages like C make a distinction between expressions, which can be composed using operators to produce new expressions, and statements, which can be composed using control structures like if, for and the "sequence control structure" that simply performs statements in order. The thing about this arrangement is that these two categories are not on an equal footing -- many control structures make use of expressions (e.g. the expression evaluated by if to choose which branch to execute), but expressions cannot make use of control structures (e.g. you can't return a for loop). Although it might seem crazy or meaningless to want to "return a for loop", in fact the general idea of treating control structures as first-class objects that can be stored and passed around is not only possible but useful. In lazy functional languages like Haskell, control structures like if and for can be represented as ordinary functions, which can be manipulated in expressions just like any other term, enabling such things as functions that "build" other functions according to the parameters they are passed, and return them to the caller. So while C (for example) divides "the things that a programmer might want to do" into two categories and limits the ways in which objects from these categories can be combined, Haskell (for example) has just one category and imposes no such limits, so in this sense it provides more composability.

Thread composability. I'll assume as Marcelo Cantos did that you are really talking about the composability of threads that use locks/mutexes. This is a slightly trickier case because on the face of it we can have threads that use multiple locks; but the important point is that we can't have threads that use multiple locks with the guarantees that they are intended to have.

We can define a lock as a type of thing that has certain operations that can be performed on it, which come with certain guarantees. One guarantee is: suppose there is a lock object x, then provided that every process that calls lock(x) eventually calls unlock(x), any call to lock(x) will eventually return successfully with x locked by the current thread/process. This guarantee vastly simplifies reasoning about program behaviour.

Unfortunately, if there is more than one lock in the world, it is no longer true. If thread A calls lock(x); lock(y); and thread B calls lock(y); lock(x); then it's possible that A grabs lock x and B grabs lock y and they will both wait indefinitely for the other thread to release the other lock: deadlock. So, locks are not composable, because when you use more than one, you cannot simply claim that that important guarantee still holds -- not without analysing the code in detail to see how it manages locks. In other words, you can no longer afford to treat functions as "black boxes".

Things that are composable are good because they enable abstractions, meaning that they enable us to reason about code without having to care about all the details, and that reduces the cognitive burden on the programmer.

A simple example of composability is the Linux commandline, where the pipe character lets you combine simple commands (ls, grep, cat, more etc.) in a virtually unlimited number of ways, thereby "composing" a large number of complex behaviors from a small number of simpler primitives.

There are several benefits to composability:

• More uniform behavior: As an example, by having a single command that implements "show results one page at a time" (more) you get a degree of paging uniformity that would not be possible if every command were to implement their own mechanisms (and command line flags) to do paging.
• Less repeated implementation work (DRY): Instead of having umpteen different implementations of paging, there is just one that is used everywhere.
• More functionality for a given amount of implementation effort: The existing primitives can be combined to solve a much larger range of tasks than what would be the case if the same effort went into implementing monolithic, non-composable commands.

As the Linux command line example shows, composability is not necessarily restricted to functional programming, but the concept is the same: Have smallish pieces of code that do restricted tasks, and build more complex functionality by routing the outputs and inputs appropriately.

The point is that functional programming is well suited to this: With immutable variables and restrictions on side effects you can compose more easily as you need not worry about what happens under the hood in the function being called - like updating a shared variable so the result will be invalid for certain sequences of operations, or accessing a shared lock so certain call sequences will give a deadlock.

That's functional programming composability - any function depends only on its input parameters, and the output can be passed to any function that can handle the type of the return value.

By extension, having fewer data types gives more composability. Rich Hickey of Clojure said something along the lines of

> every new object type is inherently > incompatible with all the code ever > written

which is certainly a point well made.

Practical composability also depends on a standardizing on a small set of data types, like the Unix commands do with their "tab-delimited line-based text" standard.

Postscript

Eric Raymond wrote a book about the Unix Philosophy, two of the design principles he listed were

• Rule of Modularity: Write simple parts connected by clean interfaces.
• Rule of Composition: Design programs to be connected with other programs.

From http://catb.org/~esr/writings/taoup/html/ch01s06.html#id2877537

Composability in functional programming can be said to bring those principles down to the level of individual functions.

Composition in computer science is the ability to assemble complex behaviour by aggregating simpler behaviour. Functional decomposition is an example of this, whereby a complex function is broken up into smaller easy-to-grasp functions and assembled into the final system by a top-level function. The top-level function can be said to have "composed" the pieces into the whole.

Certain concepts don't easily compose. For instance, a thread-safe data structure may allow safe insertion and removal of elements, and it does this by locking the data structure or some subset of it so that one thread can perform the necessary manipulations without having its changes intruded upon — and the data structure corrupted — while it works. However, a business function might require the removal of an element from one collection, followed by its insertion into another, and for the entire operation to be performed atomically. The problem is that locking only occurs per data structure. You can safely remove an element from one, but then you might find that can't insert it into the other because of some key violation. Or you might try inserting it into the one second and then removing it from the first, only to find that another thread has stolen it from under your nose. On realising that you can't complete the operation, you could try to put things back the way they were, only to find that the reversal fails for similar reasons, and you are now in limbo! You could, of course, implement a richer locking scheme that covers multiple data structures, but that only works if everyone agrees to the new locking scheme, and wears the burden of using it all the time, even when all their operations are on a single data structure.

Mutex-style locking is thus a concept that doesn't compose. You can't implement higher-level thread-safe behaviour simply by aggregating lower-level thread-safe operations. The solution in this case is to use a concept that does compose, such as STM.

I agree with Marcelo Cantos's answer, but I think it may assume more background than some readers have, which is also related to why composition in functional programming is special. Functional programming function composition is essentially identical to function composition in mathematics. In math, you may have a function f(x) = x^2, and a function g(x) = x + 1. Composing the functions means creating a new function, in which the function arguments are given to the "inner" function, and the "inner" function's output serves as input to the "outer" function. Composing f outer with g inner could be written f(g(x)). If you provide a value of 1 for x, then g(1) == 1 + 1 == 2, so f(g(1)) == f(2) == 2^2 == 4. More generally, f(g(x)) == f(x + 1) == (x+1)^2. I described composition using the f(g(x)) syntax, but mathematicians often prefer a different syntax, (f . g)(x). I think this is because it makes clearer that f composed with g is a function in its own right, which takes a single argument.

Functional programs are built entirely using compositional primitives. A program in Haskell is, to possibly oversimplify, a function that takes as an argument a run-time environment, and returns the result of some manipulation of that environment. (Grokking this statement will require some understanding of monads.) Everything else is done with http://en.wikipedia.org/wiki/Function_composition">composition in the mathematical sense.

Here's a real-world example. The names of all of the people that live in your house is the list of names of all the males in your house combined with the list of all females in your house.

This is composable, as each of those two subproblems can be solved independently and without interfering with solving the other one.

On the other hand, many recipes are not composable, as the steps must be done in a particular order and rely upon the results of other steps. You have to break the eggs before you whisk them!

Another example: consider async programming in .NET. If you use a language like C# and need to make a series of asynchronous (non-blocking) I/O calls via Begin/End APIs, then in order to call two operations, Foo and Bar, in sequence, you have to expose two methods (BeginFooAndBar, EndFooAndBar), where BeginFooAndBar calls BeginFoo and passes a callback to Intermediate, and Intermediate then calls BeginBar, and you have to thread the intermediate values and IAsyncResult state information through, and if you want a try-catch block around the whole thing, then good luck, you need to duplicate the exception handling code in three places, yikes, and it's an awful mess.

But then with F#, there's the async type, built atop functional continuations that are composable, and so you can write e.g.

let AsyncFooAndBar() = async {
    let! x = Async.FromBeginEnd(BeginFoo, EndFoo)
    let! y = Async.FromBeginEnd(BeginBar, EndBar, x)
    return y * 2 }

or what have you, and it's simple, and if you want to put a try-catch around it, great, the code is all in one method, rather than spread across three, you just put a try-catch around it and it works.

Composability allows for the developer community to continually raise the level of abstraction, multiple levels, without being chained to the base layer.