On the Goodness of Programming Languages

Since my last post on C I have been thinking a lot about what makes a programming language good. This is also motivated by my recent emersion into JavaScript that has me wondering how good of a language is JavaScript. I've had similar thoughts about C++, Java, Lisp and others in the past.

I think that the only sensible conclusion is there is no way to measure the goodness of a language in any objective way. I am certain that I can can come up with a metric that would declare C as the best language ever developed, and another that would make the winner Lisp, or Mathematica or JavaScript. For example if, to simplify things a bit, I decide that the metric for a language's goodness is that:

1. It be functional (first class functions, closures, etc.)
2. It be ubiquitous (available on almost every computing device)

Then it is clear that JavaScript is the best language ever. I can also easily derive a metric that would declare Mathematica as the best language ever (and on some days I am convinced of the absolute truth of this!).

But the truth is that there can never be the best language ever. This is not because programming language technology is constantly (or at least in fits and starts) evolving. The reason there can never be a best programming language begins with the idea of Turing Completeness but it does not end there. Any language worth learning is TC and by that metric is no better than any other. Yet, it is often argued that some languages are more expressive than others (e.g. Lisp is more expressive than Fortran) and therefore one can solve a wider class of problems faster in Lisp than Fortran. But that does not mean there are not valid metrics by which Fortran can be declared the world champion of programming languages.

Humans spend a way too much time debating what the best is. What is the best car, best restaurant, best sport, best OS and best programming language? We do this because we want to be associated with the best. I drive an X, X is the best, therefore I have superior taste. For programming languages such arguments are silly not because we each have our own tastes. They are silly because if you are a programmer and don't sometimes see the superiority of Language A over Language B (and visa versa) then my guess is you are a rank amateur (or really boring person to sit next to at the office). So next time you find yourself in one of those "my language is better than yours" debates (and I've been there too) stop yourself, pick up the best editor :-) and write some code instead!

How to mess with Comp Sci Students

Assignment: Write a compiler that compiles all programs that can't compile themselves.
Extra Credit: Use the compiler to compile assignment.

Busy Beavers

The most embarassing memory I have about my intellectual development as a computer scientist was the day I decided that maybe Turing got that halting problem thing wrong. I know, I know, what was a thinking! Blame it on youth. But I also blame it on a gap in my education on the theory of computation. See, I was taught about Turing Machines (TM) but was never exposed to Busy Beavers (BB) until much later.

My thinking at the time was that Turing pulled out a very contrived type of TM in his halting problem proof. He made the TM self referential to achieve the proof. So my thinking was that perhaps the only class of TM that could evade a halting detection algorithm was the class offered by Turing in his proof. I thought it was possible for the vast majority of other TM to be shown to halt algorithmically. My thinking went as follows:

1. A TM is a deterministic device.
2. If a TM goes through a sequence of states and at some point returns to a state already visited without halting then that TM will never halt. Here it is important to relaize I am including the tape in the state specification.

My "algorithm" for detecting a TM that did not halt was simply to run a TM in a simulator that at each step would save a snapshot of the entire state and compare to previous snapshots to find a duplicate. If a duplicate was found then it would declare the TM would not halt. For this to actually work the algorithm would have to set some bounds on how long it would run the simulation. I did not think this was a problem because I thought there was obviously a linear or at worst quadratic function based on the number of possible states in the input TM. And, of course, this is where I was wrong. Had I known about Busy Beavers I would not have gone down this road.

It turns out the the Busy Beaver function looks something like this for a two symbol TM:

States	Steps
1	1
2	6
3	38
4	>=3,932,964
5	>=1.9 × 10^704

Linear indeed!

The silver lining for me is that I learned a very important lesson (besides the one about not doubting a mathematical proof by someone of Turing's stature that withheld the scrutiny of thousands of individuals of similar stature). I learned that human intuition about the emergence of complexity from simple mechanisms is woefully poor. This lesson is repeated when we look at Cellular Automata in NKS. Its also repeated when we compute the number of possible configurations of a chessboard and compare that the estimates of the number of atoms in the known universe.

Luckily I learned my lessons while I was still quite young. Many individuals who believe themselves to be intellectuals have never learned to not always trust what they believe is intuitively reasonable. That not so bad except they use the web to infect the gullible with their intuitions. So, be careful out there! There are a lot of busy beavers with bad intuition.

Communicating Sequential Processes

My recent interest in Erlang has motivated me to reread C.A.R. Hoare's classic Communicating Sequential Processes . If you are interested in software development and concurrency then I implore you to read (and re-read) this important work. If you won't take my word for it then consider the words of Edsger W. Dijkstra.

The most profound reason [the manuscript was eagerly awaited] , however, was keenly felt by those who had seen earlier drafts of his manuscript, which shed with surprising clarity new light on what computing science could—or even should—be. To say or feel that the computing scientist’s main challenge is not to get confused by
the complexities of his own making is one thing; it is quite a different
matter to discover and show how a strict adherence to the tangible and quite
explicit elegance of a few mathematical laws can achieve this lofty goal. It
is here that we, the grateful readers, reap to my taste the greatest benefits
from the scientific wisdom, the notational intrepidity, and the manipulative
agility of Charles Antony Richard Hoare.