StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><a href="https://stackoverflow.com/questions/2887013/what-does-composability-mean-in-context-of-functional-programming/2887024#2887024">Marcelo Cantos gave a pretty good explanation</a>, but I think it can be made slightly more precise.</p> <p><strong>A type of thing is composable when several instances can be combined in a certain way to produce the same type of thing.</strong></p> <p><strong>Control structure composability.</strong> Languages like C make a distinction between <em>expressions</em>, which can be composed using operators to produce new expressions, and <em>statements</em>, which can be composed using control structures like <code>if</code>, <code>for</code> 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 <code>if</code> to choose which branch to execute), but expressions cannot make use of control structures (e.g. you can't return a <code>for</code> loop). Although it might seem crazy or meaningless to want to "return a <code>for</code> 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 <code>if</code> and <code>for</code> 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.</p> <p><strong>Thread composability.</strong> 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 <em>can</em> have threads that use multiple locks; but the important point is that we can't have threads that use multiple locks <em>with the guarantees that they are intended to have</em>.</p> <p>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 <code>x</code>, then provided that every process that calls <code>lock(x)</code> eventually calls <code>unlock(x)</code>, any call to <code>lock(x)</code> will eventually return successfully with <code>x</code> locked by the current thread/process. This guarantee vastly simplifies reasoning about program behaviour.</p> <p>Unfortunately, if there is more than one lock in the world, it is no longer true. If thread A calls <code>lock(x); lock(y);</code> and thread B calls <code>lock(y); lock(x);</code> then it's possible that A grabs lock <code>x</code> and B grabs lock <code>y</code> 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 -- <strong>not without analysing the code in detail to see how it manages locks</strong>. In other words, you can no longer afford to treat functions as "black boxes".</p> <p>Things that are composable are good because they enable <em>abstractions</em>, 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.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload