In response to a Keanu moment I recently had, Arjun recommended I read On the expressive power of programming languages. The paper is divided into roughly two parts: in the first part, Felleisen sets up the formal framework for describing the expressiveness of programming languages. In the second part, he illustrates the repercussions with Scheme.

Let \( \mathbb{F}_1,\ldots,\mathbb{F}_n,\ldots \) be a set of constructs we wish to add to a language \( \mathcal{L}_0 \). Let this new language be denoted by \( \mathcal{L}_1 \). These languages have equivalent expressiveness if (a) adding the constructs does not change the semantics of the subset of \( \mathcal{L}_1 \) that can be expressed with just the constructs in \( \mathcal{L}_0 \) and (b) the newly added constructs can be expressed using local changes in the program. An important enforcement of the locality requirement is that the mapping between the original language and the extension must be the identity on the formulae in the language and a homomorphism on the local connectors. The formalism that he defines enforces these requirements. The main conclusion of the paper is that "...an increase in expressive power comes at the expense of less 'intuitive' semantic equivalence relations."

The proofs are quite nice and clear. It's a journal article, so it's long, but thorough. There's an interesting discussion in the second half about how introducing abort and call/cc mess up the semantics of the program. I had had difficulty imagining concrete examples to illustrate some of the issues that showed up as abstractions in the first half, so the Scheme section was helpful.

It isn't clear to me whether there was a big, definitive result that came out of this work. I'll have to investigate more.