Since this seems to be a popular topic within the OOP thread, I thought I'd break it out on its own and toss in my $2e-2 worth.

Now, it seems that expressivity has something to do with how we use languages to solve problems. In particular, it seems to be a measure of how easy it is to write a solution to a problem in a given language. "Ease" is fairly nebulous to define, so let's try some simple-minded metrics as a starting point. I argue that compressed program length is a reasonable metric. A shorter program has fewer overall symbols to parse and comprehend. If the meaning of those symbols is very intricate and codependent, very terse code might be difficult to understand (like, say, sed/awk). However, nobody can argue that a short string of symbols with lots of meaning is lacking in *expressivity*. So ease of comprehension should not really be a factor in this measure.

Now, how do we use program length to measure expressivity? First, we need a problem set. Since a Turing machine is a solution to some problem, let us simply consider the set of all Turing machines whose length is less than or equal to N. Call this set P. Next, let us suppose that we have a magical function M, a given language L and a specific Turing machine T in P. M(L, T) gives us the compressed length of the smallest program in L that is equivalent to T. To determine the average expressivity of L, we simply take the average of M(L, T) / M(T, T) for all T in P. Let us call this value E(N).

I claim that E(N) is a reasonably objective metric for the expressivity of L. It measures how many symbols are needed to solve a given problem in L. Naturally, M is most likely undecidable, so we can't actually compute it. But I hope it's apparent that if we could at least *estimate* M to a high degree of confidence, that E(N) would be computable, and possibly even useful.

Let the feeding frenzy begin.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Not a new idea

What you are talking about is computational complexity, a field/idea originating from Gregory Chaitin in the 60s. There are some interesting results in that area. I don't have any links off the top of my head, but a teeny bit of searching will suffice.


...are you sure that this exact concept is something that Chaitin cares about? My understanding is that Chaitin is more interested in the complexity of computation without regard to any specific language (at least that's how he defines omega...its value depends on the choice of language, but the choice itself is uninteresting). My point was to measure not complexity in any absolute sense, but to compare the efficiency with which different languages can express solutions with respect to each other.

If you're interested in actual programs...'re emphatically NOT interested in random Turing machines.

The programs people actually write are very, very structured, and belong to a tiny subset of the set of possible programs -- almost all of them run in time bounded by some very low-degree polynomial, and operate in very regular over the structure of the data. That's the reason that fold, map and related recursion operators are so useful -- they encompass almost all uses of recursion that occur in real programs. An "expressive" programming language is one that's optimized for the sorts of programs that people are apt to actually write.

The problem... that there is no formal way to enumerate the types of programs that people actually write. If there were, I would be more than happy to use that in place of TMs in my definition. But I invite anyone to offer such an ordering.

...and a solution?

Why not use some simple but high-level language? Like Scheme? (or Forth, for other audience :-) )

...a field/idea originating from Gregory Chaitin...

...and Kolmogorov and Solomonoff. We can't have Chaitin take all the credit here.

If I may be permitted to make another troll post:

By that measure, the most expressive language just might happen to be 99. :)

(I know, I know -- still, this post s serious enough to warrant a moment of thought.)

If it were Turing complete...

...I might be inclined to agree. However, I can write a Turing machine that will print the lyrics to "Hit Me Baby One More Time" by Britney Spears, and this program appears to be impossible to write in 99. However, if we modify my measure to provide a lower bound as well as an upper bound, and we select a value of N that corresponds to the Turing machine which implements the programs of 99, then I agree that E(99) would be maximized for L = 99 and no other language (that is not equivalent). And, in fact, this is a good point. Because E() is almost certainly not a simple linear function of N wrt any L. So there will be some regions of P where one L has a better E, and some where a different L is better. I suppose one of the goals of PL design is to create an L such that E is maximized for the regions of P most relevant to practical software demands. Which implies that it is wrong to say that one language is more expressive than another without qualifying the types of problems the language is intended to solve. But we all know that intuitively anyway, right?

potential difficultys

I also don't remember the link but I've read a paper on this where they proved that M wasn't computable except trivially. All programs with finite elements can be given some stunningly huge upper bound in program length. Anyway it turned out that E(N) could only be computed by searching the space of all possible programs until you hit upon one that worked which is only a little better then waiting for an infinite number of monkeys.

However even though an objective complexity metric elludes they did have something encouraging about language comparisons. It turns out that languages are a scaling factor to this fundamental complexity problem so you can more or less compare languages by measuring the size of a complier for one written in the other. This means that librarys are quite likely the determining comparitor of any two languages and the source of the imperive 'win' over 'superior' functional languages. Just as windows gained mindshare and device manufacturers tuned thier products to windows creating a self inforcing loop so have C,C++,Java.. come to be associated with large librarys which encourages more use and more libraries. So that tight coupleing with these languages is seen as a win even when theoretical compromises may be required.

I disagree

I doubt that problems computable by a Turing Machine of size at most N is a good approximation of problems up to the given complexity.

This set includes lots of ugly problems whose descriptions are boring lists of meaningless transition rules, but excludes various elegant problems which operate on trees and thus are hard to encode in a TM.

The metric would favor languages with a compact description of boring data, but would not reward languages with interesting high-level features, because among random Turing Machines the majority is boring and requires just faithful encoding of the TM rules.

Also, compressing the source doesn't reward languages with powerful abstraction facilities as it should, because compression compensates for redundancy in the source.

Good point

My original post was a bit hasty because I just wanted to stimulate discussion, and it looks like I succeeded at least to a small degree. However, I realize now that there is no need to include TMs as a middleman (or middleperson, depending on how PC you are).

Of course, the problem was not to look at the problem space, but at the program spaces. So instead of enumerating over TMs, let us enumerate over programs, and make the measure entirely relative. Thus, let Lr be the reference language, and Lc be the comparison language. Now we define P as the set of programs in Lr that are of length N or less, R as some program in P, and M(R, Lc) as the length of the shortest program in Lc that is equivalent to the given program R. This should eliminate many of those boring TMs that we really don't care about, and at least get to some programs that we can recognize. So now we have E(Lr, Lc, N), which is the expressivity of Lc with respect to Lr for programs in Lr up to length N. Perhaps this is a more palatable metric.

As far as compressing the source, I wanted to avoid penalizing "verbose" languages that just happen to use wordy keywords instead of, say, symbols. That would give unfair advantage to many of the FP langs over langs like Ada and COBOL. Also, I think that compressing the source would not eliminate all the redundancy in inefficient or low-level languages, because it's not true's simply unoptimized complexity, and compression can't really change the complexity measure of the data...or can it?

For instance, if you compared an assembly program to a Haskell program, you would find that most of the assembler mnemonics could be reduced to just a few bits. But even doing so would still result in those bits occurring many many times, because the entire instructions themselves would tend to be unique (due to memory references, manifest constants, etc.). I'm fairly confident that the assembly code would be considerably larger than the Haskell code for any compression scheme that just looks at the data statistically (and doesn't do something tricky like encode knowledge of assembler or Haskell).

I realize that in real life, compressed source tends to be much larger than the resulting executables, but that just says that machine code is the most expressive code in existence (which is another good argument for expressivity != usability). Also, real programs tend to contain things like comments and abstractions that make the code more maintainable, but not necessarily more expressive.

If you pile up enough over-simplifications...

eventually they will fall over.

Expressivity of language is only one component of ease-of-use, and not anywhere near the largest one. Ease-of-comprehension, ease-of-navigation, and ease-of-introspection are far more important, and are at best uncorrelated with expressivity (and at worst negatively correlated).

Or to be more blunt, there's basically no value in making programs shorter for their sake of shortness. Making programs shorter for the sake of clarity has value. Confusing terseness with clarity is a classic mistake of language design. Actually, it's probably _the_ classic mistake of language design.

Too much programming language research amounts to a drunk looking for his car keys under a streetlamp, because that's where the light is. Better to search for what is actually valuable than to measure things just because you know how to measure them.

My point...

Was not to claim that expressivity == usability. That would be reaching way too far. It was merely to argue that expressivity itself is not a completely subjective measure. I would go farther and argue that usability isn't completely subjective either, but I'm afraid that argument would require an intricate knowledge of human psychology that isn't generally available yet.


Expressivity is not subjective, but at the same time I have to agree with the previous poster. It's quite useless to attempt to measure such a thing. And the only reason for measurement would be comparison.

You simply can't compare languages in terms of expressivity, no matter how close the languages are to each other or how distant they are. Let me throw this example out there. Scheme has call/cc and dynamic-wind. Common Lisp has a condition system and unwind-protect. While similar in many respects, they are subtly different. So subtle that at certain times it looks as if they "say the same thing" (express), yet they clearly say, or express different things. And it's not possible to claim that either language could express *both* concepts, either. They are diametrically opposed.

One set of expressions says "we give you a guarantee." The other says "we place few restrictions on you." To cross the chasm you need to alter the expressivity. This does not mean one is less expressive than the other. It just means you can't have your cake and eat it too.

Now you can get both at once, but then you need a mediator. Something that says "we grant you permission." Then you're entering the realm of LanguagesAreOperatingSystems and turing tar pits.

I think a more beneficial discussion might be *how* expressivity relates to meaning and problem solving (and not the degree thereof) and ways to match problems to a suitable model of expression. Such as McCarthy's AMB, logic and constraint-based models are better suited for certain types of problems than a strict imperative/functional/OO model.

The only thing I see measuring expressivity will tell you is if you are using the wrong model for the problem at hand. And measuring this is equally flawed. You can have the most concise matrix multiplication routine in Scheme, yet it won't capture the efficiency requirement that your application might demand. Yes, it solves the problem in fewer words. But what if the requirements demand more detail? There might only be one language that can capture this requirement, such as assembly. Then it won't really matter how "expressive" Scheme is... it just isn't suitable. The language can't solve the fully defined problem.

And I think what you will find is that as you provide more details to the problem at hand, most languages simply disappear in any measurement because they can't express enough of the detail. And that's the real key, isn't it? Figuring out all the requirements of any non-trivial problem.

actual usability

While ease of use has something to do with program length, I think it's more closely related to Joel Spolsky's definition:

A user interface is well-designed when the program behaves exactly how the user thought it would.

I think that gets right at the heart of the matter. It explains why popular syntaxes become more popular and takes into account how your experience with previous computer languages changes what "easy to use" means. And a language that doesn't do what you'd expect is clearly where bugs come from. Any usability definition isn't relative to some person or target audience is fatally flawed.

It's quite fair to say that some languages are very expressive in the sense that some (programmer, language) pairs are very productive. Relative to any single programmer, some languages are clearly more expressive than others. However, this doesn't generalize to other (programmer, language) pairs.

A decent measure

Might be to judge based on the inverse of the difference in size of a program from itself compressed (preferably by something advanced, like lzma).
A language that forces a programmer to be repetitive is going to have more "compressible" programs, thus will have a high compression ratio.
This may not be an exact measure of expressiveness, since (for starters) it all depends on the program and not per se the programming language, but you get the idea.

For a formal look at expressivity of programming languages..

Matthias Felleisen has a paper which examines the comparative expressiveness of programming languages. I haven't looked at the paper in a while, but here is the link . Enjoy.

Excellent link!

That seems to nail this thread on the head. However, it seems to be the convention here to use HTML to make links live, like this. ;>

It's good to repeat it :-)

Though this paper was discussed multiple times, including quite recently on the "objective scientific" thread.

Not that repeating good stuff is a bad thing, just curious, how many links are missed this way.


Thought I followed that whole thread, and didn't see a single mention of that paper. Maybe I missed something.

There's a huge sub-thread on

There's a huge sub-thread on it. When I saw this come up as a forum topic, I thought it was an attempt to factor the whole the expressivity thing out.

Yes, exactly...

That was the point. But I never saw that paper mentioned in that sub-thread.