5 ms·

On compositionality (2017)

70 points by mathgenius 8y ago

olooney 8y ago
My go-to example for high vs. low compositionality is JSON vs. HTTP. JSON has high compositionality - if you want to replace an atomic value with a more complex value, you can use JSON itself to structure the new complex value. Whereas HTTP Headers were originally defined as key-value pairs, one per line, and had to introduce new syntax in an ad-hoc fashion. That's why User-Agent uses semicolon, which Accept-Encoding uses comma, Set-Cookie often uses Base64 encoding, normal form submits use URL encoding, but file uploads use the multipart form encoding which uses MIME boundaries. Each time the same problem came up (encoding multiple values, or values which may include delimiters from one level up in some kind of structured way) a new solution is invented. A natural language analogy to the HTTP approach would be a grammar rule saying, "when you want to use a subclause or a noun phrase, switch from English to Japanese." So you would say: The woman is pretty. But if you wanted to nest the statment "pretty woman" you would "encode" it by switching to Japanese like so: The kirei onna is nice. This example is absurd, but how is it any different than HTTP's ad-hoc approach to nesting, really? The HTTP approach quickly bogs down, while formats with high compositionality like JSON or YAML can be extended even to very complex structures; for example, the docker-compose.yml file or package.json.
- smadge 8y ago
  I do see your point, but you are comparing two very different things. HTTP is a protocol, JSON is a data format. In a lot of ways HTTP is highly composable because along with hypertext media types like HTML or JSON-LD it allows for composition of documents and applications across hosts and networks into the World Wide Web. Vanilla JSON can’t do this without a hypermedia extension like JSON-LD.
ckaygusu 8y ago
This could be one of the most well-written contemporary text on computer science. Congratulations to the author.
ssivark 8y ago
Phil Anderson (Nobel-prize winning physicist) wrote a thought-provoking take on emergence in "More is different" [1] talking about how interactions between collections of components can lead to emergent behavior that is qualitatively very different. Anderson was arguing against the reductionist perspective, and pointing out that emergent effects are as important (and worthy of being considered "fundamental") as reducing a system to its components. Thinking about it some more, I think that emergence is not something to be avoided, but embraced. Emergence is what gives rise to abstractions. Embracing abstractions is the reason we need compositionality -- the ability to translate from one level of abstraction to another, and glue together different abstractions/pieces [2]. If you didn't have emergent behavior, and all your pieces have the same level of abstraction, then there's not much structure to be exploited in how you combine them. Concretely, think of emergence as the reason why a function can become an atomic unit in a new effective description, even though it is composed of other units (statements/functions). [1] http://robotics.cs.tamu.edu/dshell/cs689/papers/anderson72more_is_different.pdf http://robotics.cs.tamu.edu/dshell/cs689/papers/anderson72mo... [2] John Hughes demonstrates how higher order functions and lazy evaluation are useful tools to glue together pieces, in "Why functional programming matters" -- https://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf https://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.p...
- 3rdAccount 8y ago
  I see what you're saying and think it makes sense in a physics context where things like cellular automata could represent some important aspect of mathematics/physics that we only barely understand. On the coding side I think abstraction has pros/cons. Yes it is nice to just use a module without really needing to peek behind the scenes, but there is an elegant way to abstract things (think of Linux commands as simple compiled applications that absorb and emit text that can be chained together with pipes versus the nodeJS leftpad fiasco. The latter showed that a lot of packages were just hacked together in a web. Again, contrast the original Smalltalk implementation of IDE, compiler, word processor, games, graphics, audio, networking...etc, that had a good bit of what Windows can do in 10k loc versus Windows which has an order of magnitude of additional code in just Microsoft Word alone. Clearly we've been abusing abstraction as these systems are beyond anyone's understanding when that doesn't need to be so. Chuck Moore of FORTH fame has a great interview where he points out that an OS is a non-thing that shouldn't be as critical as it is. I don't think he is 100% right, but he is onto something.
sriku 8y ago
Why are Haskell type classes identified as non compositional in this post when interfaces are talked about as necessary for compositionality?
- lgas 8y ago
  I think maybe he's not saying that type classes themselves aren't composable but rather they interfere with the composability of more fundamental things like functions which are easier to compose in the absence of type class constraints. For example it's easy to compose two functions of type a -> b and b -> c but two functions of type MonadX m => a -> m b and MonadY m => b -> m c suddenly require you to weave together something that provides the full context. And obviously in practice the tangle of constraints can be more complex... especially with (even common and useful) complications like MultiParamTypeClasses.
- js8 8y ago
  I think he uses the word "interface" in more general sense than e.g. Java interfaces, that is as thing that you interact with when you're using the component.
ur-whale 8y ago
This is really worth a read, easily one of the best articles in HN in the last month or so. Not sure why this is sinking so fast.
snaky 8y ago
> Clearly interfaces are a crucial aspect of compositionality, and I suspect that interfaces are in fact synonymous with compositionality. That is, compositionality is not just the ability to compose objects, but the ability to work with an object after intentionally forgetting how it was built. Well, it's complicated. Quoting Gerald Sussman from https://wingolog.org/archives/2018/01/11/spectre-and-the-end-of-langsec https://wingolog.org/archives/2018/01/11/spectre-and-the-end... > The work of engineers used to be about taking small parts that they understood entirely and using simple techniques to compose them into larger things that do what they want. > But programming now isn't so much like that. Nowadays you muck around with incomprehensible or nonexistent man pages for software you don't know who wrote. You have to do basic science on your libraries to see how they work, trying out different inputs and seeing how the code reacts. This is a fundamentally different job.

70 points by mathgenius 8y ago

My go-to example for high vs. low compositionality is JSON vs. HTTP. JSON has high compositionality - if you want to replace an atomic value with a more complex value, you can use JSON itself to structure the new complex value. Whereas HTTP Headers were originally defined as key-value pairs, one per line, and had to introduce new syntax in an ad-hoc fashion. That's why User-Agent uses semicolon, which Accept-Encoding uses comma, Set-Cookie often uses Base64 encoding, normal form submits use URL encoding, but file uploads use the multipart form encoding which uses MIME boundaries. Each time the same problem came up (encoding multiple values, or values which may include delimiters from one level up in some kind of structured way) a new solution is invented. A natural language analogy to the HTTP approach would be a grammar rule saying, "when you want to use a subclause or a noun phrase, switch from English to Japanese." So you would say: The woman is pretty. But if you wanted to nest the statment "pretty woman" you would "encode" it by switching to Japanese like so: The kirei onna is nice. This example is absurd, but how is it any different than HTTP's ad-hoc approach to nesting, really? The HTTP approach quickly bogs down, while formats with high compositionality like JSON or YAML can be extended even to very complex structures; for example, the docker-compose.yml file or package.json.

smadge 8y ago
I do see your point, but you are comparing two very different things. HTTP is a protocol, JSON is a data format. In a lot of ways HTTP is highly composable because along with hypertext media types like HTML or JSON-LD it allows for composition of documents and applications across hosts and networks into the World Wide Web. Vanilla JSON can’t do this without a hypermedia extension like JSON-LD.

ckaygusu 8y ago

This could be one of the most well-written contemporary text on computer science. Congratulations to the author.

ssivark 8y ago

Phil Anderson (Nobel-prize winning physicist) wrote a thought-provoking take on emergence in "More is different" [1] talking about how interactions between collections of components can lead to emergent behavior that is qualitatively very different. Anderson was arguing against the reductionist perspective, and pointing out that emergent effects are as important (and worthy of being considered "fundamental") as reducing a system to its components. Thinking about it some more, I think that emergence is not something to be avoided, but embraced. Emergence is what gives rise to abstractions. Embracing abstractions is the reason we need compositionality -- the ability to translate from one level of abstraction to another, and glue together different abstractions/pieces [2]. If you didn't have emergent behavior, and all your pieces have the same level of abstraction, then there's not much structure to be exploited in how you combine them. Concretely, think of emergence as the reason why a function can become an atomic unit in a new effective description, even though it is composed of other units (statements/functions). [1] http://robotics.cs.tamu.edu/dshell/cs689/papers/anderson72more_is_different.pdf http://robotics.cs.tamu.edu/dshell/cs689/papers/anderson72mo... [2] John Hughes demonstrates how higher order functions and lazy evaluation are useful tools to glue together pieces, in "Why functional programming matters" -- https://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf https://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.p...

3rdAccount 8y ago
I see what you're saying and think it makes sense in a physics context where things like cellular automata could represent some important aspect of mathematics/physics that we only barely understand. On the coding side I think abstraction has pros/cons. Yes it is nice to just use a module without really needing to peek behind the scenes, but there is an elegant way to abstract things (think of Linux commands as simple compiled applications that absorb and emit text that can be chained together with pipes versus the nodeJS leftpad fiasco. The latter showed that a lot of packages were just hacked together in a web. Again, contrast the original Smalltalk implementation of IDE, compiler, word processor, games, graphics, audio, networking...etc, that had a good bit of what Windows can do in 10k loc versus Windows which has an order of magnitude of additional code in just Microsoft Word alone. Clearly we've been abusing abstraction as these systems are beyond anyone's understanding when that doesn't need to be so. Chuck Moore of FORTH fame has a great interview where he points out that an OS is a non-thing that shouldn't be as critical as it is. I don't think he is 100% right, but he is onto something.

sriku 8y ago

Why are Haskell type classes identified as non compositional in this post when interfaces are talked about as necessary for compositionality?

lgas 8y ago
I think maybe he's not saying that type classes themselves aren't composable but rather they interfere with the composability of more fundamental things like functions which are easier to compose in the absence of type class constraints. For example it's easy to compose two functions of type a -> b and b -> c but two functions of type MonadX m => a -> m b and MonadY m => b -> m c suddenly require you to weave together something that provides the full context. And obviously in practice the tangle of constraints can be more complex... especially with (even common and useful) complications like MultiParamTypeClasses.
js8 8y ago
I think he uses the word "interface" in more general sense than e.g. Java interfaces, that is as thing that you interact with when you're using the component.

ur-whale 8y ago

This is really worth a read, easily one of the best articles in HN in the last month or so. Not sure why this is sinking so fast.

snaky 8y ago

> Clearly interfaces are a crucial aspect of compositionality, and I suspect that interfaces are in fact synonymous with compositionality. That is, compositionality is not just the ability to compose objects, but the ability to work with an object after intentionally forgetting how it was built. Well, it's complicated. Quoting Gerald Sussman from https://wingolog.org/archives/2018/01/11/spectre-and-the-end-of-langsec https://wingolog.org/archives/2018/01/11/spectre-and-the-end... > The work of engineers used to be about taking small parts that they understood entirely and using simple techniques to compose them into larger things that do what they want. > But programming now isn't so much like that. Nowadays you muck around with incomprehensible or nonexistent man pages for software you don't know who wrote. You have to do basic science on your libraries to see how they work, trying out different inputs and seeing how the code reacts. This is a fundamentally different job.