LispCast

People talk a lot about programming language expressivity. Why is it important?

Simplifying a bit, a highly expressive language lets you write the same program with fewer lines of code (LOC). Fewer lines of code means easier to write, easier to extend, and easier to maintain. Software cost is not directly proportional to LOC. If you want to change a feature, bigger code means looking through more lines that aren't the code you want to change. It means more lines to change. It means more time to understand how the system works before you change things. It's not linear. So it's vitally important to reduce the LOC of your app. One way to do that is to use a more expressive language.

So, let me give a little formal theory about what I mean by expressivity. First of all, expressivity is relative to a given feature (piece of functionality). There is no general or absolute expressivity. So we can say Java is more expressive in terms of web service programming than Common Lisp is. That's debatable (though very possible). Visual Basic is (potentially) more expressive for GUI's than Erlang. The point is that the language we use can help us solve a particular problem better than other languages.

Second of all, expressivity has a metric. Some quantitative or qualitative comparison. Very often, people talk about expressivity being inversely proportional to the number of lines of code. As long as the feature is the same, you can use the metric to compare the implementations in two different languages.

Lots of people on the internet show one single piece of functionality to prove the expressive superiority of their language. For example, a Scheme guy will say "my language can express a lambda in two lines, but Java needs at least 10." That's an expression of Scheme's expressivity versus Java's for the domain of anonymous functions.

This approach is flawed for at least two reasons. Since a program only containing one feature isn't very useful, the Scheme versus Java example isn't very practical. It doesn't talk about real-world programming. The second reason is that often these single features are features for which the language was designed. Scheme was designed to make lambda easy to do. The Java designers optimized other things.

Now that I think about it, another flaw is that this kind of comparison annoys people. But that's beside the point.

But I propose a better metric of expressivity. It's better because it's more fair. It still has the disadvantage of being pretty unlikely to actually be used. Here it is:

The number of features n used in the expressivity needs to be set arbitrarily large. The choice of metric is still open. So, for example, in the Scheme vs. Java example above, the n = 1 (creating a lambda). The metric is LOC.

The real measure of expressivity is how well it helps you write large, real-world programs. That means n=100, n=1,000, or n=1,000,000, etc. As long as the apps implemented in both languages are matched feature for feature, you can compare them with the same metric.

In the graph, I've taken a very conservative curve for the two languages. Java increases linearly with the number of features. Really, I don't think Java can do better than this. Scheme, on the other hand, starts off at a disadvantage because of all of the Java libraries. Scheme has to catch up. But as the Schemers develop macros to abstract away their code, their code can actually get smaller. Adding a new feature can actually be done with fewer lines of code than the last feature. Therefore, it's less than linear.

So, since software cost increases more than linearly, it is extremely important to improve expressivity to avoid skyrocketing software costs. Bottom line: use the most expressive language that can get the job done.

So that's the framework I propose. Of course, I don't really expect any real comparison like this to happen. I mean, the real way to figure out who is more expressive, Java or Scheme, is to implement something big in both, like a web browser. And they both have to work exactly the same way. And to be fair, you need to include features that are considered easy in Java and features that are considered easy in Scheme. But I think it's a good way to think about it.

Now what's left is to pick a metric.

Possible metrics

• Lines of code.
  This is the classic metric, though some people think it's unfair. For instance, it favors languages with large libraries. However, with a sufficiently large and well-selected feature set, this should not be a significant problem
• Duplicated lines/duplicated blocks.
  The idea here is that expressivity means you don't have to repeat yourself. You need a way to count lines that are basically the same, except for a small difference.
• Size of code minus gzip of the source code.
  The idea here is that a compressed version of the source code will be a good measure of the code without duplication. The difference between the size of the code and a compressed version shows how much code was duplicated.
• information theory measure of bits of information
  Use information theory to calculate the number of bits contained in the source code. This doesn't mean the number of bytes in the files, but rather how many bits could not be predicted. If it can be predicted (for instance, you know that a semi-colon is going to come next), it is, in theory, not necessary to include it in the code.
• Size of expression.
  This counts the number of tokens. The advantage of this is that it does not disfavor languages that prefer long variable names. It also does not favor languages that cram lots of code onto one line. This is how Paul Graham has been measuring the expressivity of Arc.
• # of keys to presses.
  It has been proposed that languages like Perl are not more expressive when you take into acount the number of times you have to press the Shift key---Perl uses a lot of symbols, and those are typically in the shifted position. This is also kind of a joke on Perl.
• closeness of match between problem definition and source code representation.
  This one is qualitative---not quantitative. Haskell list comprehensions look very similar to the mathematical notation for defining sets. The closeness of match measure requires that both programs follow the same problem definition. This is not really feasible since it's impractical to read large code bases and compare them to a standard. However, it is--in my opinion--the ultimate test of a language. How well can you describe what is supposed to happen according to your spec. How well does your Java program follow the UML spec? Could I reconstruct the UML from your Java code? Can you say "Feature X is like feature Y except with one small difference"?