Thursday, June 3, 2010

Concurrency haiku

The first computers were mechanical and were programmed mechanically using punched cards, like Jacquard's 1801 loom

Close-up view of the punch cards used by Jacquard loom on display at the museum of science and industry. Photograph taken by George H. Williams in July, 2004.

or were not programmable at all, like Babbage's 1849 difference engine. When the first electronic computers became available, the programming tool was a soldering iron. Thus, Jacquard's loom for a long time was much better than what came thereafter. Until Zuse's 1941 Z3, which was programmed with paper punched tape.

If you ever programmed on paper punched tape, you know how tedious it is to create the tape. When you had to program a lot, a trick was to try to program using instruction patterns. You could then carry a shoe box of these patterns and when you came to a point in a program were you could reuse a pattern from your collection, you would put its tape in the reader and duplicate the instructions instead of typing them on the keyboard.

Zuse brought this box of tricks to perfection and created a mathematical formalism, inventing his Plankalkül. When the follow-up model Z4 ended up at the ETH in 1950, his colleague Rutishauser came up with a revolutionary idea: the computer could not just be used for calculations, but also to translate a high-level language into machine code using a program called a compiler.

The idea made it to the US, the country of pragmatism and big everything. At this point, informatics and computer science diverged. In the US, the availability of big funding and big iron, coupled with the pragmatic quest for quickly rigging up software solutions, brought computer science and practical languages like Fortran, Cobol, and later C. In Europe, with expensive hardware and the quest for elegance, informatics brought more formal languages like Algol, Pascal and later Ada, with constructs like the kellerspeicher (now called stack).

Having to do with smaller and slower hardware, the informaticians had to make better use of the available hardware, so concurrency was an important subject every student had to learn in the basic curriculum. Dijkstra brought semaphores and Hoare brought monitors, while the students lost many nights of sleep over deadlocks.

Meanwhile, American computer scientists learned these European concepts, but did not have to use them on their big iron, thus focusing more on applications and creating the computer industry, a detail the Europeans missed.

Scientists were continuously flying back and forth over the big pond, so the two cultures did not evolve in a vacuum, but there has been cross-pollination all the time. For example, Simula's Nygaard came to a year's sabbatical when PARC was created and his visit beget Smalltalk, which pollinated Lisp begetting Interlisp. Finally, Mesa, a descendant of Algol68, evolved into Cedar, which brought lightweight processes (now called threads) and other goodies.

This last technological breakthrough was possible because at MIT Hewitt had a big effort to extend concurrency to exploit massively parallel computers. His student Atkinson invented the serializer, then moved on to PARC, contributing the concurrency in Cedar, among other feats.

At this point in time, it was very hard to write concurrent programs. Even when you were well trained in semaphores, monitors, and serializers, it was not enough to be able to program an algorithm. You had to be able to debug your application interactively, and that meant that you had to implement a stack frame so you could unwind the stack when the application crashed. And boy, was this difficult!

chinese indian german american

In the 1970s and 1980s, the Silicon Valley demographics was very different from what it is now. Today, the local technologists are mostly Indian and Chinese trained in US universities. Back then, however, the techno-cultural background was more diverse, with half the researchers and engineers being US-trained computer scientists and half being Europe-trained informaticians.

In practice, this created a constant dialogue between the American approach of quickly rigging up a big system and the European approach of carefully architecting a lightweight system.

Maybe this demographic change at the end of the cold war is what brought us today's bloatware. However, half on Silicon Valley's brains are underemployed or unemployed, and since knowledge resides in brains not in corporations, the old dialogue is still smoldering.

This is where we come to haiku.

haiku 俳句 はいく

Hewlett-Packard's Gassée was a Frenchman who moved on to Apple. After Jobs was defenestrated, Gassée first broke the old anathema that Macintoshes could only be black and white, bringing us the Macintosh IIfx with full color (and also the Newton Message Pad and the MacBook).

However, Gassée had a flamboyant personality and got himself defenestrated too. This led to a very interesting situation. Apple had an archaic operating system and in its dysfunction had a number of blue and pink projects for American style software efforts like Copland, OpenDoc, etc. in part in-house and in part on-campus (Taligent). When the board finally came to sense, they decided to get the new OS from outside instead of dealing with the turf wars in their own stable.

Concomitantly, Jobs and Gassée had each started a company with European style elegant minimalist systems. Both systems were nicely architected, based on multiprocessor PowerPC hardware and clean concurrency in the operating systems. This gave Apple's board two choices: NeXTSTEP and BeOS. We know that NeXTSTEP became MacOS X, but what happened to BeOS?

It was sold for pocket change to Palm, where it became Palm OS Cobalt. You would think it is now dead. But as I wrote above, knowledge is in people's head, so you cannot kill a good idea.

BeOS has been reincarnated in an open source OS called Haiku. The second alpha release has just come out, and if you have an extra partition on your disk, you can download it and do some lean programming. Here is the link: http://www.haiku-os.org/