Friday, May 9, 2008

Parrot, Forgotten Bird

If you need to do client-side programming in web browsers, you have to learn JavaScript. Google's App Engine requires Python (at least for the moment). To benefit from the encyclopedic CPAN, you need to know Perl. Wikipedia relies on PHP, the Rails framework is written in Ruby.

Those, among many others, are dynamic languages: agile and well-suited for rapid development. Such language diversity is a good thing to have.

What is not so great is that you are forced to use different languages in different environments. We already suffer from information overload - and many times we can't afford to ignore the latest fads. The duplication and wasted time involved are simply too much.

Ideally, we should be able to stick to our preferred language in a project. Having to remember the details of several languages, and context-switch between them, is an unwelcome distraction. Also, the choice of a language shouldn't become a restriction later on.

Those are problems that could be solved by Parrot, at least in theory. Parrot is a language agnostic virtual machine, especially designed for dynamic languages. This is in contrast to the Java VM, which can be quite unforgiving to non-static languages, as I am led to believe.

Beautiful plumage

Decoupling the language from the VM makes a lot of sense. Systems can embed the VM and be amazingly flexible, programmers can use their language of choice and have a plethora of libraries available, language designers can focus on the language proper and use the nice compiler tools provided.

Pushing up the daisies

Despite all those advantages, I see almost no mention of Parrot outside its community. I wonder why. The project has been long in coming, but so were other successful Free Software projects. Perhaps people think its goals aren't technically feasible? The NIH syndrome, language chauvinism?

Does it talk?

Parrot and Perl 6 development seem to be gaining steam, and perhaps we shall see alpha releases by the year's end.

What could it bring in the future? Anything scriptable (eg browsers) using the same stable, optimized VM. A further push against proprietary formats (Flash, Silverlight et al). World peace? :-)

Anyway, here's hoping that Parrot becomes hugely successful.

Saturday, May 3, 2008

Halting Taboo

There are limits people are comfortable with. No one would suggest that you could go faster than light, or that ignoring the second law of thermodynamics may be a good idea.

Unfortunately, when it comes to problems a computer can't solve, undecidability can prove to be a misunderstood, if not downright unpopular, limit.

For instance, it is impossible to write a program that receives an arbitrary program as input and determines if it stops in a finite amount of time. This is known as the Halting Problem; in the 1930's Alan Turing proved that it isn't decidable. [1]



If you can't programatically decide if a program stops, automated tests can't prove that it has no bugs. Surprisingly, say it aloud,

You can't prove that a program is correct.


and the conversation can turn sour. "Of course it can be done, you test every state, even if it takes months or years. We are talking about real machines!"

How do you know if a program isn't stuck in an infinite loop? Besides, even if the number of states is finite, it can be huge. Testing every possible state is not feasible.

"Ok, but you're forgetting about formal methods."

Formal methods are applied to individual algorithms, written in pseudo-code. The running program is a different beast. I think it is no coincidence that Knuth once said:

Beware of bugs in the above code; I have only proved it correct, not tried it.


Software is hard. There are lots of descriptions of things going wrong. It is not like catastrophic failures are unheard of. Why the state of denial?


Notes:

[1] Incidentally, Turing used a diagonalization argument to construct his proof by contradiction. This technique was previously used by Cantor to show that the set of the Reals is uncountable (there are many different infinites). Gödel used it to prove his famous incompleteness theorem.