Lambda the Ultimate

Peter Seibel's book Coders at Work is apparently available for purchase, so this is a good time to say a few words about it here.

The book consists of interviews with several illustrious programmers about their personal histories, programming style, likes and dislikes and so on. Among the interviewees are several who are well known in programming language circles and are mentioned regularly on LtU, for example Brendan Eich, Joe Armstrong, Simon Peyton Jones, Peter Norvig, Guy Steele, Dan Ingalls, and Ken Thompson. The interviews go into more detail and depth than I dared hoped for or expected, though as is inevitable you end up annoyed that a question you really wanted answered did not come up.

I am sure LtU readers will want to read these interviews for themselves and revel in the technical miscellanea (I read them on a long flight from the US to Australia...), so I am not going to post a detailed review with spoilers. It would be more fun to hear the questions you guys would have asked had you conducted the interviews (and to know which answers you want to quibble with!) So in lieu of a long and tedious review, here are a few LtU-worthy things that caught my attention in a couple of the interviews that I think will interest LtU members.

For some reason I started by jumping to the interview with Dan Ingalls. It turned out to contain many nice morsels to chew on. Dan emphasizes an attribute that might be called programmability all the way down (he is a Smalltalk guy, so that's not such a surprise, I guess): "You should be able, in a computing environment, to zero in on music and musical synthesis and sound and just understand how the whole thing works. It should be accessible. The same thing with graphics." Not surprisingly, Ingalls admits to having an exploratory programing style (in contrast to Knuth who wrote TeX in a notebook...), which probably influenced the types of language he found himself working on. This seems to be the case for several other interviewees as well. Interestingly, Ingalls recalls being influenced by APL. The interactive environment was part of it, but significantly he also mentions the influence on him of the fact that it is expression oriented and not statement oriented like Fortran.

And oh, Ingalls also opines on the age old question: should programmer education begin with assembly. His answer: No. As you would expect, other interviewees probably feel differently.

The interview with Knuth is also very interesting, as you might expect. Here are a few of the things I picked up on in his interview. From his description, it would seem that Knuth was doing his own style of test driven development, though for some reason this angle is not elaborated on in the interview. While Ingalls ponders how to expose kids (and adults) to programming, and Norvig reflects on the failures of end-user programming, Knuth recites his observation that 2% of people are natural born programmers (my words) since they "really resonate with the machine." Perhaps surprisingly Knuth is here concerned with being attuned to the way the machine "really works," not to algorithmic thinking in a general sense. Perhaps, I wonder, what really unites programmers is a compulsion to program: Knuth admits to having the need to program even before having breakfast.

Knuth has a challenge to programming language designers. He claims that every time a new language comes out it cleans up what's already understood, and then adds something new and experimental. How about "setting our sights lower" and aiming for stability. "It might be a good idea," he says. I am pretty sure some here will argue that we have too much lowering of expectations already...

What really resonated with me, and with the LtU ethos, was Knuth lament about people not going back to the original papers and source materials. He puts it simply and powerfully: "I wish I could... instill in more people the love that I have for reading original sources... I was unable to pass that on to any of my students." LtU always had a history department, and going back to historical papers is something I personally love doing. Maybe Knuth should guest blog on LtU... Really! He talks about having collections of source code, compilers in particular - we want to know more!

Finally, let me note the nice contrasts you find among the interviewees. Naturally, these manifest themselves in differing opinions about C. While Knuth sees the C pointer as one of the great advances in computer science, Fran Allen argues that "C has destroyed our ability to advance the state of the art in automatic optimization, automatic parallelization, automatic mapping of a high-level language to the machine."

And if that's not a call to action to all you programming language fanatics, what is?

Disclosure: I was asked to provide a blurb for the cover of the book, and so read the interviews before the book was published. Other than that I had no involvement with the creation of the book, and I have no stake in its success.

Radoslaw Karwowski and Przemyslaw Prusinkiewicz. Design and implementation of the L+C modeling language. Electronic Notes in Theoretical Computer Science 86 (2), 19 pp.

L-systems are parallel grammars that provide a theoretical foundation for a class of programs used in the simulation of plant development and procedural image synthesis. In particular, the formalism of L-systems guides the construction of declarative languages for specifying input to these programs. We outline key factors that have motivated the development of L-system-based languages in the past, and introduce a new language, L+C, that addresses the shortcomings of its predecessors. We also describe a simulation program, lpfg, which makes it possible to execute models specified in L+C. To this end, L+C programs are translated into C++, compiled into a DLL, and linked with lpfg at runtime. The use of this strategy simplifies the implementation of the modeling system.

I somehow failed to notice L+C as a demarcated language before. I am not entirely sure what one needs to download in order to use L+C directly.

I am sure this is relevant to the great DSL debate, but I am not sure in favor of which side of the debate...

The page gives links to other papers about L+C. While you are there, don't miss The Algorithmic Beauty of Plants, which is great fun.

The site for DSL'09, which took place two months ago in Oxford, is a treasure trove for DSL fans. While the blog format may be a bit confusing for a conference website, you should be able to find your way around to links to slides and paper versions of the presentations. Even better, the posts include various comments people made about the papers (each talk was followed by a comment from a discussant). Apparently one can even join in and post comments!

So tell us: What item caught your attention? Which paper should everyone here rush to read? Which DSL is downloadable and worth downloading?

Parallel Performance Tuning for Haskell. Don Jones Jr., Simon Marlow, and Satnam Singh.

Parallel Haskell programming has entered the mainstream with support now included in GHC for multiple parallel programming models, along with multicore execution support in the runtime. However, tuning programs for parallelism is still something of a black art. Without much in the way of feedback provided by the runtime system, it is a matter of trial and error combined with experience to achieve good parallel speedups. This paper describes an early prototype of a parallel profiling system for multicore programming with GHC. The system comprises three parts: fast event tracing in the runtime, a Haskell library for reading the resulting trace files, and a number of tools built on this library for presenting the information to the programmer. We focus on one tool in particular, a graphical timeline browser called ThreadScope. The paper illustrates the use of ThreadScope through a number of case studies, and describes some useful methodologies for parallelizing Haskell programs.

Relations of Language and Thought: The View from Sign Language and Deaf Children provides an interesting angle on the Sapir-Whorf hypothesis that we periodically discuss on LtU. A small sample from Google Books is available.

...Hypothesis concerning language and thought...:

• Language equals thought. Perhaps the simplest view of language and thought is that they are essentially the same thing. This position is most frequently ascribed to American behaviorists, and especially to John Watson, who argued that thought is just subvocal speech.
• Language and thought are independent. This view, most often attributed to theorists like Noam Chomsky and Jerry Fodor, suggests that the development of language and the development of cognition are distinct, dependending on different underlying processes and experiences.
• Language determines thought. In the form usually identified with the linguistic determinism and linguistic relativity theories of Sapir and Whorf, this perspective directly entails a correlation between language skill and cognitive skill. One implication of this view is that individuals who have "inferior" (or superlative) language are expected to have "inferior" (or superlative) thought. Implicitly or explicitly, such a perspective has been used as a rationale for an emphasis on spoken language for deaf children by those who have seen sign language as little more than a set of pragmatic gestures.

...The more interesting question... is whether growing up with exposure to a signed language affects cognition in a way different from growing up with a spoken language. Indeed, that is one of the fundamental questions of this volume. While we fully agree... that any strong form of the Sapir-Whorf position appears untenable, it also seems clear that language can affect and guide cognition in a variety of ways. Much of what a child knows about the world, from religion to the habitats of penguins, is acquired through language.

Sign language is an obvious candidate for linguistic study, since the mode is visual as opposed to oral/aural. The summary of one of the authors is telling:

The conclusion that American Sign Language (ASL) is an independent, noncontrived, fully grammatical human language comparable to any spoken language has been supported by over 30 years of research. Recent research has shown that ASL displays principles of organization remarkably like those for spoken languages, at discourse, semantic, syntactic, morphological, and even phonological levels. Furthermore, it is acquired, processed, and even breaks down in ways analogous to those found for spoken languages. The similarities between signed and spoken languages are strong enough to make the differences worth investigating. In the third section of this chapter, I will argue that although there are differences in detail, the similarities are strong enough to conclude that essentially the same language mechanism underlies languages in either modality.

On a programming language level, I can't help but think that sign language offers valuable clues into the nature of visual PLs (though I haven't quite nailed down any specifics). ASL on Wikipedia informs us that signs can be broken down into three categories:

• Transparent: Non-signers can usually correctly guess the meaning
• Translucent: Meaning makes sense to non-signers once it is explained
• Opaque: Meaning cannot be guessed by non-signers

With the majority of signs being opaque. As much as those who design visual languages would like them to be intuitive - falling into the Transparent and Translucent category - I figure you still have to end up using many signs that are only meaningful internally to the language at hand.

On a personal level, I have recently been attempting to delve into ASL. I've almost got the alphabet and numbers down, and have a vocabulary of about 100 additional signs - which probably means that I'm at the proficiency level of somewhere between ankle biter and sesame street. I do find it to be a fascinating language. I noticed when I was looking at the course offerings for college (my son started university this year) that ASL is now offered for foreign language credit (wish it had been offered when I was a student all those years ago).

R. E. Moe, 2006. Expressive Modes and Species of Language. In Proc. 23rd World Academy of Science, Engineering and Technology.

This paper is very relevant to my attempts to characterise what I call the Scott-Strachey school of computer science; cf. Right On!.

I am grateful to Ehud for bringing the following paper to my attention: White, G., 2004; The Philosophy of Computer Languages; In L. Floridi (ed.): Philosophy of Computing and Information; Blackwell, 2004.

Function Interface Models for Hardware Compilation. Dan Ghica.

The problem of synthesis of gate-level descriptions of digital circuits from behavioural specifications written in higher-level programming languages (hardware compilation) has been studied for a long time yet a definitive solution has not been forthcoming. The argument of this essay is mainly methodological, bringing a perspective that is informed by recent developments in programming-language theory. We argue that one of the major obstacles in the way of hardware compilation becoming a useful and mature technology is the lack of a well defined function interface model, i.e. a canonical way in which functions communicate with arguments. We discuss the consequences of this problem and propose a solution based on new developments in programming language theory. We conclude by presenting a prototype implementation and some examples illustrating our principles.

Ghica's work has been mentioned before, but not this particular article, which is a follow-up to that work. The paper touches on a number of common LtU topics: language design for hardware description, game semantics, Reynolds's SCI... I don't know much about hardware design, so I'd be interested to hear what people think.

According to a draft statement, Scheme is to be split into a small and a large language, the small being designed for educators and "50-page purists", the large for "programmers, implementors".

The small language should remain true to the language design precepts found in the RnRS introduction ("Programming languages should be designed not by piling feature on top of feature, …").

But what about the large one? Will it drop continuations, become a Lisp-2, and challenge Common Lisp?

Pottier (2007). Wandering through linear types, capabilities, and regions. Survey talk given at INRIA, Rocquencourt, France, May 2007.

Following Ehud's prompt, I again recommend it as a tutorial on the relationship between such things as linear&affine logic, resource logics, effect-typing systems, and the idea of observably pure function definitions in stateful languages.

Registration is now open for the Workshop on Non-Traditional Programming Models for High-Performance Computing (part of the Los Alamos Computer Science Symposium). The symposium and workshop will be held in Santa Fe, New Mexico on October 13-14, 2009.

The goals of the workshop are two-fold:

1. To begin to identify, specify and capture in writing, the problematic issues and barriers inherent in today's scientific software construction process.
2. To expose attendees to non-traditional programming models with the express purpose of igniting thought and discussion on the future of large-scale scientific programming.

The one-day workshop will consist of three sequential tracks, each lead by a moderator/facilitator. The tracks will include a small number of speakers who will each present a short position paper outlining their thoughts on current problems and how specific non-traditional techniques may be applied to address these issues. Following the presentations, the moderator will lead a discussion with the audience on the ideas presented by the speakers. Both the position papers and the captured discussion will be published on the workshop web site. It is our hope that the output of this workshop, perhaps refined, can act as input to a future meeting or workshop on this topic.

(at the web site, click on the workshop title to display the preliminary agenda)