Lambda the Ultimate

EWD611, Edsger Dijkstra, 1976

My subject should be very simple, for it is only the difference between the orientations of computing science at two sides of the Atlantic Ocean.

I chased this up while looking for Alan Kay's rebuttal "On the fact that most software is written on one side of the Atlantic Ocean" which I couldn't find. I was struck by these passages:

My first visit to the USA, in 1963, was the result of an amazing invitation from the ACM. Without the obligation to present a paper I was asked to attend —as "invited participant", so to speak— a three-day conference in Princeton: for the opportunity of having me sitting in the audience and participating in the discussions, my hosts were willing to pay my expenses, travel included! As you can imagine, I felt quite elated, but shortly after the conference had started, I was totally miserable: the first speaker gave a most impressive talk with wall-to-wall formulae and displayed a mastery of elaborate syntax theory, of which I had not even suspected the existence! I could only understand the first five minutes of his talk, and realized that I was only a poor amateur, sitting in the audience on false pretences.

I skipped lunch, walking around all by myself, trying to make out what the first speaker had told us. I got vaguely funny feelings, but it was only during the cocktail party that evening, when I had recovered enough to dare to consider that it had all been humbug. Tentatively I transmitted my doubts to one of the other participants. He was amused by my innocence. Didn't I know that the first performer was a complete bogus speaker? Of course it was all humbug, everybody in the audience knew that! Puzzled I asked him why the man had been invited and why, at the end, some of the participants had even faked a discussion. "Oh, on occasions like that, we just go through the motions. IBM is one of the sponsors of this conference, so we had to accept an IBM speaker. He was given the first slot, because the sooner that is over, the better." I was flabbergasted.

This vividly reminds me of the first time I attended an ACM conference on programming languages! Though it's amazing to think that back in the golden age there would be just one bogus talk :-)

When writing CTM I was struck with how many of the good ideas in programming languages were discovered early on. The decade 1964-1974 seems to have been a "Golden Age": most of the good ideas of programming languages appeared then. For example:

• Functional programming: Landin's SECD machine (1964)
• Object-oriented programming: Dahl and Nygaard's Simula (1966)
• Axiomatic semantics: Hoare (1969)
• Logic programming: Elcock's Absys (1965), Colmerauer's Prolog (1972)
• Backtracking: Floyd (1967)
• Capability security: Dennis and Van Horn (1965)
• Declarative concurrency: Kahn (1974)
• Message-passing concurrency: Hewitt's Actor model (1973)
• Shared-state concurrency: Hoare's monitors (1974)
• Software engineering: Brooks's mythical man-month (1974)

It is a sobering thought that not much new stuff has come since then. Hindley-Milner type inferencing in 1978, constraint programming in 1980, CCS (precursor of pi-calculus) in 1980. What revolutionary new ideas came since 1980? Most of the work since then seems to have been in consolidation and integration (combining the power of the different ideas). Right?

It seems that Chomsky’s Syntactic Structures was published fifty years ago this month. Unquestionably a historic event as far as linguistics and cognitive science is concerned.

Just the other day I had a conversation with a (non CS) colleague about Chomsky. My friend argued that Chomsky is regarded as very important for CS. Not going into a full historical analysis I argued that most CS people are unaware of Chomsky, or at least don't see him as all that crucial to the discipline of CS. A CS undergrad probably encounters Chomsky when learning about the Chomsky Hierarchy in a formal languages course - which deals mostly with regular and context free languages, the lower rungs of the hierarchy.

A more cautious historical analysis will show how Chomsky influenced CS, as well as much else, but I think my assessment of the way most computer scientists view Chomsky's impact on the field is fairly accurate. Still, many of us are interested in languages in general, as well as programming languages, and in the interaction between PLT and linguistics. So I think LtU is a good place to mention the fiftieth anniversary of Syntactic Structures, surely a landmark affair in 20th century science.

Another entry for HOPL-III that is an interesting account of The Evolution of Lua by Roberto Ierusalimschy, Luiz Henrique de Figueiredo and Waldemar Celes.

We report on the birth and evolution of Lua, and discuss how Lua moved from a simple configuration language to a versatile, widely used language that supports extensible semantics, anonymous functions, full lexical scoping, proper tail calls, and coroutines.

The paper is timely for me, since I recently acquired the book "Programming in Lua V2" and am slowly trying to learn the language. It's hard not to like the model of language evolution taken by the Lua community. Lua has actively staked the ground of an embeddable scripting language, having simplicity and size as a major focus, and a very active two way street between embedded scripting language and host language C. The paper provides a good accounting of many of the design decisions made through the history of versions, though I would have liked a bit more mention of the decision to go with a register based VMs.

Overall, I'd rate it as a very good read for those that are interested in PL design. Other papers from HOPL-III mentioned on LtU: Haskell and AppleScript.

(via LogBlog)

This site offers written curricular materials, based on primary historical sources, for beginning and advanced undergraduate courses in discrete mathematics and computer science. Such courses, which often cover combinatorics, deductive reasoning (logic) and algorithmic thought, draw a variety of majors, ranging from computer science, mathematics, the physical sciences and engineering to secondary education. Traditional methods of instruction follow ``The Modern American Discrete Mathematics Text,'' which although thorough and mathematically precise, present the material as a fast-paced news reel of facts and formulae, often memorized by the students, with the text itself offering only passing mention of the motivating problems and original work which eventually found resolution in modern concepts such as induction, recursion, or algorithm.

This sort of apporach is very close to my heart, as LtU readers probably know. I wish them well.

T: A Dialect of Lisp, or, LAMBDA: The Ultimate Software Tool

The T project is an experiment in language design and implementation.
Its purpose is to test the thesis developed by Steele and Sussman in
their series of papers about the Scheme language: that Scheme may be
used as the basis for a practical programming language of exceptional
expressive power; and, that implementations of scheme could perform
better than other Lisp systems, and competitively with implementations of programming languages, such as C and Bliss, which are usually
considered to be inherently more efficient than Lisp on conventional
machine architectures. We are developing a portable implementation of
T, currently targetted fo rthe VAX under the Unix and VMS operating
systems and for the Apollo, a MC68000-based workstations.

Niklaus Wirth. Good Ideas, Through the Looking Glass, IEEE Computer, Jan. 2006, pp. 56-68.

An entire potpourri of ideas is listed from the past decades of Computer Science and Computer Technology. Widely acclaimed at their time, many have lost in splendor and brilliance under today’s critical scrutiny. We try to find reasons. Some of the ideas are almost forgotten. But we believe that they are worth recalling, not the least because one must try to learn from the past, be it for the sake of progress, intellectual stimulation, or fun.

A personal look at some ideas, mostly from the field of programming languages. Some of Wirth's objections are amusing, some infuriating - and some I agree with...

LtU readers will obviously go directly to sections 4 (Programming Language Features) and 6 (Programming Paradigms). Here are a few choice quotes:

It has become fashionable to regard notation as a secondary issue depending purely on personal taste. This may partly be true; yet the choice of notation should not be considered an arbitrary matter. It has consequences, and it reveals the character of a language. [Wirth goes on to discuss = vs. == in C...]

Enough has been said and written about this non-feature [goto] to convince almost everyone that it is a primary example of a bad idea. The designer of Pascal retained the goto statement (as well as the if statement without closing end symbol). Apparently he lacked the courage to break with convention and made wrong concessions to traditionalists. But that was in 1968. By now, almost everybody has understood the problem, but apparently not the designers of the latest commercial programming languages, such as C#.

The concept that languages serve to communicate between humans had been completely blended out, as apparently everyone could now define his own language on the fly. The high hopes, however, were soon damped by the difficulties encountered when trying to specify, what these private constructions should mean. As a consequence, the intreaguing idea of extensible languages faded away rather quickly.

LtU readers are also going to "enjoy" what Wirth has to say about functional programming...

(Thanks Tristram)

This is the inaugural edition of Code Reads, a weekly discussion of some of the central essays, documents and texts in the history of software. This week we're talking about Frederick Brooks's The Mythical Man-Month. (OK, let's be honest: I'm talking about it. I'm hoping you, or you, or you, may want to, as well!

This is an ongoing series with Dijkstra's "Go To Statement Considered Harmful" coming up. This essay was mentioned here a few times, of course, so you might want to check the archives.

This item is not directly language related, but since you can win prizes, I thought I'd better let you guys know..

Andreeesen discusses the problems with programming languages prior to 1995 and how things changed with the development of Java, followed by JavaScript and PHP. These languages were easier to learn and allowed for easier cross platform use and quick deployment. In addition, with the meteoric drop in hardware and network costs, more powerful applications will be much easier to develop and worldwide collaboration is possible.

A personal view on programming language history, biased in favor of dynamic languages and specifically PHP (audio show).

Feel free to comment on the historical accuracy and/or Andreeesen's central argument.

This is a prerelease version of the hypertext edition of the 6th edition of the Lisp Machine Manual. To read this manual, you need to use a browser that is capable of performing XSL transformations (Firefox, Internet Explorer and others).

A 1984 document by Richard Stallman, Daniel Weinreb and David Moon.

The preface contains a "personal note" from Stallman announcing GNU.

Some sections of interest are: cdr coding, closure manipulation functions, stack groups, and areas.