33

I see a lot of texts, especially functional programming texts, claim that certain CS concepts "don't compose". Examples are: locks don't compose, monads don't compose.

I've been having a hard time tracking down exactly the meaning of this phrase. When I think of composition, I think of either function composition or object aggregation (as in "favor composition over inheritance"), but that doesn't seem to be the sense in which people are using it here.

Can someone explain what this phrase means when used in expressions like the two examples above (that is, locks and monads)?

  • It's closer in meaning to function composition than to object aggregation. – Andres F. Jul 17 '15 at 20:41
  • Roughly and informally, if you have two separate things that use locks, it's hard to stick them together. (in the case of locks, it's hard to do without introducing deadlocks; in the case of monads, the types can get complicated) – immibis Jul 18 '15 at 0:28
33

When people say "X doesn't compose", what they mean by "compose" really just means "put together", and what and how you put them together can be very different, depending on what exactly "X" is.

Also, when they say "doesn't compose", they can mean some slightly different things:

  1. You can't put two Xs together at all, period.
  2. You can put two Xs together, but the result might not be an X (IOW: X is not closed under composition.)
  3. You can put two Xs together, but the resulting X might not work the way you expect it to.

An example for #1 is parsers with scanners/lexers. You might hear the phrase "scanners/lexers don't compose". That's not actually true. What they mean is "parser which use a separate lexing stage do not compose".

Why would you want to compose parsers? Well, imagine you are an IDE vendor like JetBrains, the Eclipse Foundation, Microsoft, or Embarcadero, and you want to build an IDE for a web framework. In typical web development, we often mix languages. You have HTML files with <script> elements containing ECMAScript and <style> elements containing CSS. You have template files containing HTML, some programming language, and some template language metasyntax. You don't want to write different syntax highlighters for "Python", "Python embedded in a template", "CSS", "CSS within HTML", "ECMASCript", "ECMAScript within HTML", "HTML", "HTML within a template", and so on and so forth. You want to write a syntax highlighter for Python, one for HTML, one for the template language, and then compose the three into a syntax highlighter for a template file.

However, a lexer parses the entire file into a stream of tokens, which only makes sense for that one language. The parser for the other language can't work with the tokens the lexer passes it. For example, Python parsers are typically written in such a way that the lexer keeps track of indentation and injects fake INDENT and DEDENT tokens into the token stream, thus allowing the parser to be context-free even though Python's syntax actually isn't. An HTML lexer however will completely ignore whitespace, since it has no meaning in HTML.

A scannerless parser, however, which simply reads characters, can pass the character stream off to a different parser, which can then hand it back, thus making them much easier to compose.

An example for #2 is strings with SQL queries in them. You can have two strings, each of which has a syntactically correct SQL query in it, but if you concatenate the two strings, the result may not be a syntactically correct SQL query. That's why we have query algebras like ARel, which do compose.

Locks are an example of #3. If you have two programs with locks, and you combine them into a single program, you still have a program with locks, but even if the two original programs were completely correct, free of deadlocks and races, the resulting program does not necessarily have this property. Correct usage of locks is a global property of the entire program, and a property that is not preserved when you compose programs. This is different from, for example, transactions, which do compose. A program which correctly uses transactions can be composed with another such program and will yield a combined program which correctly uses transactions.

  • 1
    In other words, “doesn’t compose” means “doesn’t form a semigroup” (or, slightly more strongly, a monoid). – Jon Purdy Jul 19 '15 at 8:38
  • I'm not sure of associtaivity is required, so more like a Magma (which I learned about literally 3 seconds ago :-D ) – Jörg W Mittag Jul 19 '15 at 8:56
  • However, if you ask somebody what they mean when they say "locks don't compose", I'm pretty sure they won't answer "I mean that the set of correct concurrent programs with locks and the composition operation form a Magma". – Jörg W Mittag Jul 19 '15 at 8:57
  • Hah, of course not. Just an alternate phrasing. I have the sense that associativity is required to maintain the “flat” feeling of composition, but no strong argument to back that up. – Jon Purdy Jul 19 '15 at 17:52
19

Composability means that you can easily and reliably combine program components together to produce larger components and more complex functionality.

Some things that help make components more composable:

  1. Idempotence. An idempotent function will always produce the same output or side effects, if called multiple times with the same parameter values. This improves composability because the result of a function call is predictable.

  2. Referential Transparency. A referentially-transparent expression will always evaluate to the same result. This improves composability by allowing identical expressions to be substituted for each other, and by allowing expressions to be calculated independently of each other (i.e. on different threads) without using locks.

  3. Immutability. An immutable object's state cannot be changed once it is created. This improves composability because you can rely on a stable value of the object, without worrying if some function or object somewhere has changed the state of the object after it was created.

  4. Purity. Pure functions do not have side effects. They only have an input and an output, which makes them more composable because you can put the output of one function into the input of another function without worrying about whether or not something outside of the function has changed.

Locks don't compose because they are an outside element which you must rely on when combining two operations together that share some state, and for all sorts of reasons which have to do with the complexity inherent in using locks.

The phrase "monads don't compose" doesn't make much sense to me. The whole point of a monad is to take some stateful thing like keyboard input or screen output, and turn it into a purer, mathematical form that is, in fact, more composable.

  • 4
    I think stackoverflow.com/questions/7040844/… does a good job explaining what "monads don't compose" probably means, though I agree that monads are much more composable than locks. – Ixrec Jul 17 '15 at 20:30
  • Your bullet points for "referential transparency" and "purity" are actually the two requirements for purity. The term "referential transparency" should be avoided because it is not well-defined. – BlueRaja - Danny Pflughoeft Jul 18 '15 at 3:58
  • 1
    A monad is an algebraic structure with certain operations. What you described in your final paragraph is the IO type which captures "stateful actions" like keyboard input. Values of the IO type do, indeed, compose, but it's the whole type IO that is a monad. This type doesn't compose with other types that are monads like, say, the list type. That is, we can't systematically produce a type IO . List which behaves like both IO and List simultaneously. Does that make sense? I'm not sure I explained it well. – Tikhon Jelvis Aug 20 '15 at 0:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.