When talking about reducing complexity in a software system, we often talk about making it "modular" by breaking it up into multiple modules that are all linked together to form the overall system. But in similar contexts, we talk about "compositionality" being a nice property. I suspect there's a more formal definition for that, but I roughly understand it as being able compose different pieces into a whole (often with the same "shape" as the underlying pieces, like GUI widgets).

So is there a meaningful difference between the terms "modular" and "compositional"?

I'm particularly interested when it comes to describing reasoning methods and how programmers reason about programs. For example, say I have these two methods with the following contracts:

  • abs(double x): returns the absolute value of x (as a double)
  • sqrt(double x): returns an approximation of the square root of x if x is non-negative, otherwise throws an exception

Then consider the expression sqrt(abs(y)). With those two contracts, I know that for all possible (double-valued) ys, that expression will never throw an exception, because abs(y) is always non-negative. As a programmer, I don't need to read the code of abs and sqrt to make that inference: I can figure it out purely from the given properties and the way the functions are composed. So is that modular reasoning, compositional reasoning, or both? Is there a difference?

  • $\begingroup$ In my experience, both terms are informal and may be used almost interchangeably. ("Almost" because I'm sure someone can came up with a context in which it would be linguistically weird to use one instead of the other, kind of like the words "liberty" and "freedom"). And yes, I would say that the one you give is a simple example of modular/compositional reasoning: the correctness proof exactly follows the structure of the program it is proving correct. This is, for instance, the underlying idea of Floyd-Hoare logic. I let other people contradict me if I'm wrong... $\endgroup$ Apr 23, 2023 at 7:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.