What does it mean that non pure functions break composability?

Question

Can someone give an example that explains what it means in practice when people say that non pure functions breaks composability in functional languages?

I would like to see an example of composability and then see that same example assuming non pure functions and how the unpurity has violated composability.

Answer 1

The answer is actually quite simple: If you have impure functions, that is functions with side effects, the side effects can interfere with each other. An elementary example is a function that stores something in an external variable during its execution. Two functions that use the same variable won't compose - only one result will be preserved. This example might seem trivial, but in a complex system with multiple impure functions collisions when accessing various resources might be very hard to trace.

A classical example is protecting mutable (or otherwise exclusive) resources in a multi-threaded environment. A single function accessing a resource works without problems. But two such functions running in different threads) don't - they don't compose.

So we add a lock to each resource and acquire/release the lock as needed to synchronize the operations. But again, the functions don't compose. Running functions that take only a single lock in parallel works fine, but if we start combining our functions into more complex ones and each thread can acquire multiple locks, we can get deadlocks (one thread obtains Lock1 and then asks for Lock2, while another obtains Lock2 and then asks for Lock1).

So we require that all threads acquire locks in a given order to prevent deadlocks. Now the framework is deadlock free, but unfortunately again functions don't compose for a different reason: If f1 takes Lock2 and f2 needs the output of f1 to decide which lock to take, and f2 asks for Lock1 based on the input, the order invariant is violated, even though f1 and f2 separately satisfy it ....

A composable solution to this problem is Software transactional memory or just STM. Each such computation is executed in a transaction and is restarted, should its access to shared mutable state interfere with another computation. And here it's strictly required that the computations are pure - the computations can be interrupted and restarted at any time, so any their side-effects would be executed only partially and/or multiple times.

Answer 2

Some examples where mutable state has bitten me in the past:

• I write a function to scrape some information out of a mess of text. It uses a simple regex to find the right place in the mess and grab some bytes. It stops working, because another part of my program turned on case sensitivity in the regex library; or turned on the "magic" mode that changes the way the regex parses; or any of a dozen other knobs that I forgot were available when I wrote the call to the regex matcher.

  This is not a problem in pure languages, because the regex options appear as explicit arguments to the matching function.

• I have two threads that want to do some computation on my syntax tree. I go for it, without thinking about it. Since both computations involve rewriting pointers in the tree, I end up segfaulting when I follow a pointer that was good before but went stale because of changes the other thread made.

  This is not a problem in pure languages, where the tree is immutable; the two threads return trees that live in different parts of the heap, and both get to see the pristine original without interference from the other.

• I don't personally have experience with this, but I've heard other programmers whinging about it: basically every program that uses OpenGL. Managing the OpenGL state machine is a nightmare. Every call does something stupidly wrong if you get any part of the state a little bit wrong.

  It is tough to say what this would look like in a pure setting, as there are not so many widely used pure graphics libraries. For the 3d side, one could look at fieldtrip, and on the 2d side, perhaps diagrams, both from Haskell-land. In each, scene descriptions are compositional in the sense that one can easily combine two small scenes into a larger one with combinators like "put this scene left of that one", "superimpose these two scenes", "show this scene after that one", etc. and the backend makes sure to munge the underlying graphics library's state in between the calls that render the two scenes.

The common thread in the non-pure scenarios described above is that one cannot look at a chunk of code and figure out what it does locally. One must have a global understanding of the entire code base to be sure they understand what the chunk of code will do. This is the core meaning of compositionality: one can compose small chunks of code and understand what they do; and when they are slotted into a larger program, they will still do that same thing.