Lambda the Ultimate

A few years back (back around the year 86 or 87 to those who really care) when I worked at Digital Equipment Corporation, I caused a bit of a stir by entering a new "Note" in the Languages notesfile (which was one of many VAXNotes notesfiles paving the corporate intranet of DEC back in the days before the internet really existed to any meaningful extent).

The note was entitled "Battle of the Languages" and the idea was that people would have the opportunity to prove the superiority of their particular favorite language by posting the source code for the now somewhat famous computer simulation called "Life" which was invented by the Cambridge mathematician John Conway, and which consisted of the following rules:

For a space that is 'populated':
Each cell with one or no neighbors dies, as if by loneliness.
Each cell with four or more neighbors dies, as if by overpopulation.
Each cell with two or three neighbors survives.
For a space that is 'empty' or 'unpopulated'
Each cell with three neighbors becomes populated.

In an matter of days, there were upwards of twenty different languages represented as replies to the intitial posting (note). I think the language "C" was the first to post a solution followed by Pascal (my current language of choice), as well as many others (sans Java and a few other more recent languages for obvious reasons).

I think I may still even have a backup tape of this and other notesfiles which was made on a VAXstation 2000 back around 1990 or so if anyone is interested, but I digress...

My main point in posting this is to state that I always enjoyed conducting that little experiment and I am not real sure what was really proven (other than the fact that people can certainly be passionate about their favorite computer programming languages).

I am half tempted to conduct the same experiment today, although I imagine that, due to the wonders of Google and other search engines, that the source code listings of some of the more popular languages would appear within minutes rather than hours or days. This would especially be true for a common mathematical simulation like Life, which has already been posted to death many times over.

It might be interesting to see what were to happen if the same contest were conducted using a different simulation candidate however... any takers on what to use for such an experiment and what parameters to set as rules (graphics or text output only, etc.)?

Thanks

-dav0 (aka David McLure - DEC employee from 1984 to 1992)

I am pondering over some non-serious application of Curry-Howard isomorphism (CHI). Let's take any typical text in a natural language. What is its contents? Propositions or proofs? My judgement is that (almost?) exclusively propositions. Applying CHI, we can see that humans write mostly types. Already sounds strange.

Now, instead of a static text, let's analyze an interaction in a natural language (e.g., a conversation over a phone). People are still exchanging propositions, i.e., types. From this point I am trying to get back to computer science. Why isn't it so common that programs exchange types over the wire? Or rather, why cant we naturally see any programmatic interaction as an exchange of (exclusively) types? I suspect we can argue that transmitted values are just witnesses of the corresponding types, but still it is not natural, or at least traditional way to look at the issue. Why? Or did I make some mistake during my analysis of natural language part of the problem?

I know that "programmatic interaction" can be seen as a proof-reduction, but I am currently wearing more message-oriented hat.

I've been reading a lot about various new languages like Ruby, Haskell, Python, etc. But none of them seem suitable for programming say, an Operating System, or performing really low level work on an embedded device. First, these languages (understandably) sacrifice efficiency for ease of use (but I don't think these are always mutually exclusive). Second, a lot of times these languages simply don't provide any mechanism for getting at the hardware.

Has there been any research into new languages that would be as suitable for an OS as C?

Hi there,

Sorry to pester y'all, but I was hoping I might get some citation-type help. I realized for my little pet language that I'm working on that need to do some homework on conjunction types, but I can't find any publicly-available articles on the topic. Does anyone know off of the top of their heads any friendly introductions to these types that doesn't require IEEE or ACM membership to read?

Thanks in advance,

JimDesu

Lock -Free Data Structures using STMs in Haskell. Anthony Discolo, Tim Harris, Simon Marlow, Simon Peyton Jones, and Satnam Singh. Submitted to FLOPS'06.

This paper explores the feasibility of re-expressing concurrent algorithms with explicit locks in terms of lock free code written using Haskell's implementation of Software Transactional Memory (STM). Preliminary experimental results are presented which show that for multi-processor systems the simpler lock free implementations offer competitive or superior performance when compared to their corresponding the lock based implementations.

The ArrayBlockingQueue class from JSR-166 is the basis for this experiment. A selection of representative methods from the three interfaces supported by this class is reimplemented in Haskell. Two implementations are provided: one using mutexes and semaphores from the IO monad and one based on STMs.

The performance of the two versions is compared and discussed.