The meaning of “doesn’t compose”

compositioncomputer sciencefunctional programmingterminology

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)?

Best Answer

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.

Related Topic