Are all programming languages equally powerfull? January 10, 2008 | 05:47 pm

So this post from Raganwald is going to cause a couple of responses (none of which involving static typing). The one involving the “intuitive” features of modern vr.s postmodern languages (ala Larry Wall) will have to wait, because one line in the post completely gobstopped me:

All programming languages are equally powerful.

Wait- are you seriously going to look me in the eye and say, with a straight face, that GW Basic is as powerfull a language (even ignoring things like memory limitations) as Haskell? Give me a d20, I want to roll to disbelieve.

The normal argument that all languages are equally powerfull uses Turing completeness as it’s basis. Since anything that can be computed can be computed on a Turing machine, once you have the same expressive power of a Turing machine, you can (theoretically) compute anything that it is possible to compute- in other words, you can solve any problem any other programming language can solve.

In theory, at least- and, as we all know, everything works in theory. The problem is that programs aren’t written in theory. They’re written in the real world, by fallible, limited, human beings. And so, I argue, that while in some abstract and totally useless sense all programming languages are equally powerfull, in the practical usefull sense, there are large classes of programs which are writtable by human beings in reasonable amounts of time in some languages, and not in others. Which means that in practical terms, some languages are more powerfull than others. While it might be theoretically possible to write in some less powerfull language, it’s not practically doable by we mere mortals. Certainly not in any reasonable amount of time.

This is where programming diverges from pure mathematics. We can prove that a given large number is a composite, and that thus it must have prime factors. But actually being able to find one of those prime factors is a much harder problem (and the basis for a lot of cryptography). Likewise, mathematics can prove the existance of programs, but actually creating those programs is (often) a much harder proposition.

This is an interesting point for two reasons. One, it explains why some languages being more powerfull is a good thing- the very definition of “more powerfull” is exactly that- there are problems we can solve in the more powerfull language that we simply can not in the less powerfull language. And, more productively, it allows us to replace the (hard to answer) question “what makes a language more powerfull?” with two (easier to answer) questions: “what limitations do human programmers have?” and “how does a given language aid in overcomming those limitations?

So let’s start with the first question (I’ll leave the second question as an exercise to the student)- what are the limitations of a human programmer? Well, first off there’s time. And then there’s complexity- there is only so much complexity a human can “hold in their head” at one time. Some can hold more complexity in their heads than others, but the important point is the amount of finite. Then there’s the likelyhood, even the gaurentee, of making mistakes, and the need to be able to avoid mistakes and mitigate their consequences. And remember that mistakes are both small (misplaced commas) and large (creating Skynet), and all sizes in between. One might be tempted to define a sort of “minimum Hamming distance” of programs, such that small changes (like misplaced commas) don’t accidentally turn one valid program into another apparently valid program. But this only helps for small errors. There are also network effects of multiple humans working together- what I think of as the “spoonful of sewage problem”. If you add a spoon full of sewage to a barrel of fine wine, you get sewage. But if you add a spoonful of fine wine to a barrel of sewage, you get sewage. It is possible for a single programmer to add that spoonfull of sewage code to the otherwise project full of fine wine, thus turning the whole thing into sewage. And the more people you have, the more likely you’ll have someone adding sewage. It’s just human nature.

Another important consequence of this idea is that the true power of a language can not be demonstrated in a blog post/email/usenet post. I mean, think about this- by definition, examples in a blog post are small. They have to be. If I were to say “well, first you have to read and understand this hundred thousand lines of code to get my point”, you’d never finish. Probably you’d never start. So it’s small examples, a dozen lines, maybe two. And a lot of handwaving. But this is just silly palor tricks. “Congratulations,” you might say, “you’ve turned 20 lines of code into 10, maybe 3. So you’ve turned a hundred thousand line project into a 99,983 line project. Woo hoo.” Even if it turned a 100,000 line project into a 90,000 line project, there still isn’t that big of a difference between the real power of the language. And anyone whose been around for a while has experienced, there are a lot of “features” in a language which look like they might add to the power of a language (especially in making the code shorter), but end up reducing the power of the language, generally by exacerbating some other limitation (such as making even small mistakes hard to find). But that only becomes apparent when programming in the large.

The hope with this missive is to change not only the tone and approach of language advocacy, but also the tone and approach of language design. Because this is what the language designer should be thinking about- what human limitations does this feature adress, and how? What human limitations might this feature exacerbate (especially in conjunction with other features in the language), and how? Because if we don’t adress our limitations, we might as well stick with the tried and true Blub language du jure, because then all languages really will be equally powerfull.

Also, I want world peace, and a pony.


  • Reg Braithwaite

    Let me see if I understand this correctly: I wrote a post wherein I said that some languages are better than others, and you have seized upon the statement that all languages are equally powerful as a point of contention?

    If that is the case, I suspect we are in violent agreement, and we just need to sort out what we each mean when we use words like powerful and better.

    I especially find the last paragraph to resonate with what I was saying. The difference between languages is exactly in their design. This is why I decided to experiment with Ruby in early 2003k, having heard Matz speak about it in November of 2002: he spoke about designing Ruby in Industrial Design terms.

  • Michael Ekstrand

    Here is where I think it’s useful to introduce a new term. “Powerful” has a well-defined meaning in computer science – any Turing-equivalent system is as powerful as any other, and is more powerful than a push-down automata, which in turn is more powerful than a state machine, etc. Overloading the term to talk about the relative practical “power” of languages clouds the meaning, IMO, and obscures the important and beautiful concept of tiers of computational ability (and if anything, we should be encouraging more awareness of the theoretical foundations of the field, not less). Therefore, I think we should continue to say that all programming languages are equally powerful.

    We can, however, say that programming languages differ in *expressiveness*. I think that the concept of expressiveness can capture well the human-productive facets of a language. To use an extreme example, Common Lisp is more expressive than BASIC – I can express a concept more clearly and directly in CL.

    That said, I agree with most of what you’re saying; I just think that we would do well to hone our terminology.

  • Pingback: Upped The Recent Post/Popular Post Widget Count | Enfranchised Mind