Expressive Power of Languages

tl;dr: watch this talk On the Expressive Power of Programming Languages

A few years ago, Evan wrote up A note about “expressiveness”.

If you’re not familiar with this post, Evan explains why it’s often silly to compare the “expressiveness” of two different programming languages. The short summary is that, from a technical perspective, if two languages are both Turing complete, their relative “expressiveness” is equivalent. To say it another way, they can both compute all that is computable!

I recently watched a talk that reminded me of this post, and it really helped me solidify my understanding of the topic: On the Expressive Power of Programming Languages by Shriram Krishnamurthi. The talk is from Papers We Love in 2019 about the paper “On the Expressive Power of Programming Languages” by Matthias Felleisen.

The paper by Matthias Felleisen provides a definition of both “equality” and “expressiveness” in the context of programming languages. Specifically, the paper gives us a way to understand what happens when we add features to a programming language. If you’ve ever wondered, “What does assignment do to a language?” - this talk/paper is for you.

I found this talk/paper really helpful, let me know if you do too!


Obviously Turing completeness is important for the theory but for what we do day to day I think it’s a bad metric.
There are quite a few languages out there that are not Turing complete that are really usable and on the other hand you have stuff like Game of Life and I guess you don’t really want to maintain “code” written in that.

For me it’s in parts what abstractions I am able to use or maybe better: how much boiler-plate I have to write - sadly from my favorite FP languages Elm does not really great on this front.
Is this everything? Nope - of course not - ecosystem, documentation etc. … but still … a shame


Fascinating talk, thanks for the link!

If I understand correctly though, this paper allows you to say if adding a feature to a language makes it more expressive (as well as defining what exactly that means). But the paper doesn’t provide a way to say if one language is more expressive than another (assuming one language isn’t just a superset of the other language)?

Yes, this appears to be the case. However! I think this framework is still useful in assessing how adding some feature from one language will affect another.

For example, say we’re looking to add a feature to Elm. With this definition of “expressive power”, we can better assess how big of a change said feature is. Any feature that adds expressive power has the potential to break existing Elm programs! This may be intuitively obvious, but I had never seen a precise way to talk about these things before.

And to the point made above,

I didn’t mean to indicate that these definitions are the best for every particular conversation, however, it is the case that these definitions are more precise than those used in most “day to day” settings. Comparing programming languages is hard (and often subjective)! This paper is interesting to me because it starts to gives us some objective basis of comparison.

1 Like

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.