Lambda the Ultimate

Wouter van Oortmerssen's thesis on Aardappel is a pretty fascinating read, and I like some of the concepts behind visual programming, but is it practical? is there any way VPL's will ever catch on?

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.