A note about "expressiveness"

Show and Tell
1

@Maldus512 asked about “expressiveness” in this thread recently. I actually prepared a note about “expressiveness” recently, and I guess this is a fine time to share it. I want to use this like a quick easy blog post, so if folks want to comment, do it in another thread!

Expressiveness

The term “expressiveness” has a technical meaning in programming languages. For example, a context-free grammar can describe all strings with balanced parentheses, whereas a regular expression cannot. [1] Therefore context-free grammars are “more expressive” than regular expressions. There are programs that literally cannot be written with regular expressions. Once you are dealing with something that is turing complete, the concept of expressiveness is not so useful. Is the lambda calculus “more expressive” than a turing machine? No. The whole reason the lambda calculus is neat is that it is equivalently expressive!

So imagine we had three different ways to multiply a vector by a scalar:

  1. scale 3 (vector 1 2 3)
  2. 3 * vector 1 2 3
  3. 3 |*| vector 1 2 3

Which is more expressive? That question does not make sense. These are three ways to express the same thing. A language that can do one of them is equally expressive to one that can do all three.

All this is to say that almost all language features are not a matter of expressiveness, but of how to express the same thing in different ways.

Cultural Aside

It personally bugs me when people say “language X is less expressive than language Y” when it is almost always more accurate to say “that would be expressed differently in language X than in language Y and that makes me very angry”. It feels like a cheap way to make personal preferences sound like they are rooted in computer science and therefore more objective.

I think most arguments along these lines can benefit from being reformulated as discussions about efficiency. For example, C has pointers and Java does not. One could simulate pointers in Java, but it would be much less efficient. So saying “Doing X is more efficient in C than in Java” is reasonable. Now you can ask “Do I care about X a lot?” and “How does it balance against Y?” and start doing the actual analysis on whether a language will work well for your particular scenario.

There may also be differences in the efficiency of formal verification. [2] For example, you can verify that an Elm program will never cause a crash by using a String as an Int quite cheaply, usually O(n) in the length of the program. It is much more difficult to do something similar in Ruby, maybe O(n^3) in the very best case. [3] Does that mean that Elm is more expressive because you cannot write programs like that? Or does it mean that Ruby is more expressive because you can write programs like that? Neither! This is not a question of expressiveness! I can write a Ruby interpreter in Elm (or an Elm interpreter in Ruby) and program either way. Ease of verification is a separate topic! And it is not so simple as just maximizing ease of verification at all costs. What if it makes it harder for humans to write, understand, or modify programs?

My larger point here is mainly that any “language X is better than language Y” argument is pretty silly. At what? How long do you have? Who is working on it? What is their background? What are their personal preferences? Is work a place for code golf? Is work a place for self-expression? How can you distinguish between code golf and self-expression objectively?

Notes:

  1. In the README of elm/regex I go through what I mean by “regular expression” in the “History” section.

  2. It may be good to check out On the Bright Side of Type Classes which talks about replicating the functionality of type classes with implicit arguments. Neither feature is fundamentally related to formal verification at all, just to leaving arguments off! You can look more into dependently typed languages (which interestingly are often not turing complete) if you are curious about formal verification beyond ML-style type inference.

  3. You can detect “type errors” in languages like Ruby with a “Control-Flow Analysis” as described nicely by Matt Might here. It is quite expensive though! The very interesting paper Resolving and Exploiting the k-CFA Paradox suggests O(n^3) or O(n^8) as a baseline for a 1-CFA.

21 Likes