Don Knuth Book Tour!
I attended a talk by
Don Knuth last night, at the
Computer History Museum
in Mountain View (California).
He has a new book released this year, so there's an obligatory
"book tour" to promote it. Last night's lecture was the first stop
in that book tour. Unfortunately, he also said that it was the last
stop on the tour.
The new book is Selected Papers on Computer Languages by Donald E. Knuth (Stanford, California: Center for the Study of Language and Information, 2003, xvi+594pp. CSLI Lecture Notes, no. 139. ISBN 1575863812 cloth, 1575863820 paperback)
See http://www-cs-faculty.stanford.edu/~knuth/cl.html for Knuth's page about it.
Note the similarity to his 1996 book "Selected Papers on Computer Science" (see http://www-cs-faculty.stanford.edu/~knuth/cs.html ). The titles are similar enough that it might be easy for some to confuse them.
Last night's talk was billed as "A Dozen Precursors to FORTRAN".
Knuth essentially went through the new book's first chapter,
which is a paper called "The early development of programming languages",
co-written by Knuth and Luis Trabb Pardo. Last night, Knuth was
using a set of slides that Luis had written for a previous
version of this talk — given in 1977 at the nearby
Mountain Winery. These were the the actual real 26-year-old,
slightly dusty transparencies, none of this fancy online PowerPoint stuff.
The paper shows the "TPK algorithm" in a number of very early
(1940's and early 1950's) programming languages. That silly algorithm
was previously noted on Lambda the Ultimate Programming Languages Weblog, at http://lambda.weblogs.com/discuss/msgReader$7186 .
Points that stood out for me:
- This was probably one of the very few audiences
where Knuth could say "... if you've ever written a compiler ..." and be sure that many in the audience had.
- Knuth pointed out how long it took to come up with some of the
concepts we take for granted (e.g., assignment; variables with
names more than 1 or 2 characters long; "variables" at all, for that matter).
- Well-known computer makers of the time: Bendix, GE, Philco
Here are some impressions I got of some of the languages:
- Zuse, Plankalkül A paper design, Zuse had no hardware to
run it on. Formulae written in a sort of grouped array notation
(grouped by vertical lines like large
square brackets), with up to four rows per column,
and each column being one or two characters.
No notion of "assignment".
- Goldstine and von Neumann, Flow Diagrams Not like your
sixties-era "flow charts". Worked around the lack of assignment
by saying from here on, the notation changes: where we
write "i", we will now mean what we used to mean by "i-1".
- Haskell Curry had some very interesting compositional
notation, but Knuth didn't spend much time on it.
- Mauchly's Short Code was somewhat like a weird bytecode,
and has the first appearance of assignment as such.
- H. Burks, Intermediate PL looked somewhat BASIC-like,
and had something that looked a lot like Fortran's arithmetic IF.
- H. Rutishauser, Automatische Rechenplanfertigung wrote
a thesis which contained the first written description for converting
his language to machine language. Was influenced by Plankalkül.
- C. Böhm, Codification Automatique was essentially
all assignments. Assign to the program counter to do a goto,
assign to an I/O register to read or write, etc. Had no negative
numbers, and used a "saturated subtract".
This was the first language in which the compiler was actually
written in its own language.
- A.F. Glennie, Autocode in Manchester, did the first
working compiler with a real machine. (1952)
He continued with Grace Hopper, Whirlwind,
John Backus' "FORTRAN 0" (Knuth's name for it),
Ershov's work in Russia, some of the earliest declarative languages,
and Perlis' "IT" ("Internal Translator"), which may have been one
of the first popular high level languages. By then (1956), there
were over a thousand computers in the world.
And FORTRAN I, where "C-in-the-first-column" Comments first showed up.
One of the questions was about List Processing; Knuth's answer was
that IPL-V was probably the first real list processing language,
though Zuse' Plankalkül had some elements of that in its variable-length arrays, and Zuse used list processing in his code.
Another led to Knuth mentioning that he'd written about software
patents in Vol. III of TAoCP.
Other related Lambda threads:
Luke G.'s messages in this thread:
Knuth and the IBM-650 http://lambda.weblogs.com/discuss/msgReader$8107
Knuth's 1974 Turing Award Lecture
Also, a posting that I missed,
mentions that Knuth has an online preview of some segments of
Volume 4 of The Art of Computer Programming.