Is there a formalization for the trade-off between the expressiveness and the speed of a programming language?

Question

I do not have a strong background in theoretical computer science, so the terminology I use may not be the most ideal.

Basically the "trend" across programming languages I have noticed is that there appears to be an trade-off in the speed of a programming language (how long it takes to execute a program) and its expressiveness (saying you want something done vs saying you how you want something done, more expressive languages focus less on the "how", from this definition).

For example, in "higher-level" languages like Python or Java - it is very easy to do something like finding the index of an item in a list with a single line like list.indexOf(item). In comparison, doing the same action in a "lower-level" language like C can result in code that is much faster, but at the cost of having write the code yourself which may be several times as long.

Again, this is really just a trend I have noticed and not a hard and fast rule. Languages like C++ that are both very fast yet can also be pretty expressive at times blur the lines.

So I am curious, is there any sort of formalization in programming language theory - or even just rough rules of thumb backed by empirical studies - explicitly listing out the trade off between the expressiveness and execution speed of a programming language?

Or perhaps I am just overthinking it, and having slower code is just a unavoidable byproduct of having a more expressive language as more things are taken care of "behind the scenes" / abstracted away from during compilation, interpretation, etc.?

Answer 1

This is a really interesting problem and I don't think there are definitive answers. There are two important, and distinct dimensions to this problem.

• What does expressivity actually mean? In the light of the Church-Turing thesis, which states that all programming languages are the same (can be compiled into each other). Nevertheless it seems pretty clear that e.g. assembler programming is quite different from programming in Python. There is a research field that studies this. It was pioneered by (1), but much ink has been spilled since.

• In computational complexity theory speedup theorems show that for any algorithm solving a problem, there is a faster algorithm solving the same problem. Examples are Blum's speedup theorem and the linear speedup theorem. Basically, what those speedup theorems tell you is that you can always speed up computers (Turing machines) a bit by adding more powerful commands. In processors we went from 4 bit CPUs to 8 bit, then 16 bit, the 32 bit and nowadays 64 bit.

Neither quite answers your question, I'm afraid!

---

(1) M. Felleisen, On the Expressive Power of Programming Languages.