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.

Answer 3

I don't think you're going to "see that same example assuming non pure functions and how the unpurity has violated composability". Any situation where side-effects are a problem for composability is one that isn't going to arise with pure functions.

But here's an example of what people mean when they say "non-pure functions break composability":

Let's say you have a POS system, something like this (pretend this is C++ or something):

class Sale {
private:
    double sub_total;
    double tax;
    double total;
    string state; // "OK", "TX", "AZ"
public:

    void calculateSalesTax() {
        if (state == string("OK")) {
            tax = sub_total * 0.07;
        } else if (state == string("AZ")) {
            tax = sub_total * 0.056;
        } else if (state == string("TX")) {
            tax = sub_total * 0.0625;
        } // etc.
        total = sub_total + tax;
    }

    void printReceipt() {
        calculateSalesTax(); // Make sure total is correct
        // Stuff
        cout << "Sub-total: " << sub_total << endl;
        cout << "Tax: " << tax << endl;
        cout << "Total: " << total << endl;
   }

Now you need to add support for Oregon (no sales tax). Just add the block:

        else if (state == string("OR")) {
            tax = 0;
        }

to calculateSalesTax. But suppose someone decides to get 'clever' and say

        else if (state == string("OR")) {
            return; // Nothing to do!
        }

instead. Now total isn't getting calculated any more! Because the outputs of the calculateSalesTax function aren't all clear, the programmer has made a change that doesn't produce all the correct values.

Switching back to Haskell, with pure functions the above design simply doesn't work; instead, you have to say something like

calculateSalesTax :: String -> Double -> (Double, Double) -- (sales tax, total)
calculateSalesTax state sub_total = (tax, sub_total + tax) where
    tax
        | state == "OK" = sub_total * 0.07
        | state == "AZ" = sub_total * 0.056
        | state == "TX" = sub_total * 0.0625
        -- etc.

printReceipt state sub_total = do
    let (tax, total) = calculateSalesTax state sub_total
    -- Do stuff
    putStrLn $ "Sub-total: " ++ show sub_total
    putStrLn $ "Tax: " ++ show tax
    putStrLn $ "Total: " ++ show total

Now it's obvious that Oregon has to be added by adding a line

    | state == "OR" = 0

to the tax calculation. The bug is prevented since the inputs and outputs to the function are all explicit.

Answer 4

One aspect is that purity enables lazy evaluation and lazy evaluation enables some forms of composition you can't do in a strictly evaluated language.

For example, in Haskell you can create pipelines of map and filter that only spend O(1) memory and you have more freedom to write "control-flow" functions such as your own ifThenElse or the stuff on Control.Monad.