Programmers love to debate the merits of programming languages, but these debates often devolve into personal preference and hand waving.

One of the factors that frequently crops up in such debates is whether language A is more “powerful” or “expressive” than language B. It turns out that computer science provides us with the tools to formalize this concept, meaning we don’t need to just rely on vague ideas of terseness or elegance, but can rigorously prove whether one language is more powerful than another, or likewise whether a given “feature” actually adds expressive power to a language.

I came across this paper–”On the expressive power of programming languages” by Matthias Felleisen (Science Direct seems to prevent direct linking, but you can easily search for it)–a few years ago via a great youtube recording of a presentation from a 2019 Papers We Love conference, by Shriram Krishnamurthi, and it demonstrates precisely how to do the above, assuming of course you accept that Felleisen’s formalization sufficiently captures your intuitive sense of “expressive power”.

I’m providing a compact summary (of the video, not the paper) here for myself, since I find writing something down is a good way to cement your understanding, and also so that my future self has a reference.

Briefly:

  • from Church we have a formal way of distinguishing the power of languages, but with Turing it seems like we get “eh, language are all the same, if they are turing complete”. can we get Church-level rigor here?
  • say you have a language with “for” loops; does adding “while” loops add expressive power? it seems like “no”, but why? intuitively we might say because you can easily rewrite or translate while “while” loops into “for” loops, have a macro for it.
  • what makes something trivially rewritable? local vs global rewrite.
  • formalizes this via “L -> F + L”: is F expressive relative to L? prove that there is no macro that accomplishes F.
  • to prove this we need to define/formalize “equality”. has relevant for compiler optimizers (among many others).
  • observational equivalence: “is there a way in the language of telling the two things apart: if there is, they are not equal; it not, they are equivalent”
  • for all contexts in a language C, if we plug in e1 and e2, and the results are always the same, e1 and e2 are equal. but this still assumes a definition of equality!
  • an even more general definition: e1 and e2 are equivalent if in all contexts C[e1] halts iff C[e2] halts.
  • is there something you can add to 3 = (+ 1 2) that would make it false? e.g. operator overloading.
  • key theorem: suppose F can be written as a local macro, then for every C where e1=e2, then by adding F, e1 will still = e2, and F has not added power to L
  • then, we can show expressiveness by finding a C in which e1 and e2 are no longer equal (i.e. one halts but the other does not), and F cannot be expressed as a local macro.
  • example, take a language without exceptions and add halt. imagine e1 takes an argument f, ignores it and loops; e2 takes an argument f, applies 0, ignores the result, then loops forever. they are equivalent. but if we add halt, then f in e2 can halt, and we can distinguish them. so halt adds power.
  • example 2, take a pure language and add state. imagine e1 applies f to 0 once, e2 applies f to 0 once, then again. we can use state so that the 2nd application of 0 to f in e2 adds to a stateful counter. this adds power.
  • example 3 involves “lispy ifs” which for this review I skipped over, since I already have enough examples and want to eat breakfast

We now can say both that a new feature F a) adds expressive power, and b) cannot be expressed by a local macro, if it can be shown to violate observational equivalance in any context.

I framed this paper as providing a way of injecting some rigor into the programming language wars, which I think it can, but it certainly does not mean that all such debates can be resolved hereby or considered moot, for a variety of reasons.

  1. You may reasonably object that this concept of expressive power is too narrow to capture programmers’ intuitive and common sense way of using that term.
  2. The merits of language A vs B do not all come down to expressive power, even in a broad sense, e.g. speed, compatibility, ecosystem, community, and so on are arguably in some cases more relevant than “expressive power” as defined here.
  3. Mutable state, Krishnamurthi’s second example, is proven to increase expressive power, but perhaps you precisely don’t want that extra expressive power and have chosen a pure functional language to avoid it. So “more expressive power” != “better”.