More history of Algol

[Nelson H. F. Beebe]

The bibliographies on Algol development at

	https://www.math.utah.edu/pub/tex/bib/algol-bulletin.bib

	https://www.math.utah.edu/pub/tex/bib/algol68.bib

continue to receive updates, and there are new related bibliographies
in the BibNet Project at

	https://www.math.utah.edu/pub/bibnet/authors/b/backus-john-w.bib

	https://www.math.utah.edu/pub/bibnet/authors/n/naur-peter.bib

	https://www.math.utah.edu/pub/bibnet/authors/p/perlis-alan-j.bib

for three of the key Algol team members in the late 1950s and early
1960s.  

John Backus was the lead developer of FORTRAN, and also an important
member of the American half of Algol team.  Alan Perlis led that
American half.  

Peter Naur was the chief editor of the Algol specifications.

All three received the ACM Turing Award: Perlis (the first, in 1966),
Backus (1977), and Naur (2005)

There are older, but still often updated, bibliographies for other
Algol team members at

	https://www.math.utah.edu/pub/bibnet/authors/b/bauer-friedrich-ludwig.bib

	https://www.math.utah.edu/pub/bibnet/authors/d/dijkstra-edsger-w.bib

	https://www.math.utah.edu/pub/bibnet/authors/r/rutishauser-heinz.bib

	https://www.math.utah.edu/pub/bibnet/authors/w/wirth-niklaus.bib

Fritz Bauer, and his close friend and colleague, Klaus Samelson, along
with Heinz Rutishauser, were early leaders of the Algol work in
Europe.

Edsger Dijkstra co-wrote the first compiler for the full Algol 60
language, including thunks and recursion, and "own" variables; it was
announced in June 1960. Dijkstra was the 1972 ACM Turing awardee.

Niklaus Wirth later developed several other languages (Euclid, Euler,
Algol W, Pascal, Modula, Modula-2, and Oberon), co-developed the
Lilith and Lola hardware, workstations, and operating systems
(1981--2014), and was the 1984 ACM Turing awardee.

Several of those people left the Algol 68 team due to their
displeasure with the design complexity.

A key, and hotly contested, debate item in the late 1950s was whether
recursion should be added to Algol 60; it was NOT in Algol 58, nor was
it in COBOL or FORTRAN.  The Dijkstra--Zonneveld Algol 60 compiler
proved that recursion could be supported, even on a small machine ---
just 4096 27-bit words.

Seven months later, in January 1961, Naur's team in Denmark had an
Algol 60 compiler working on the small Danish DASK computer (1024
42-bit words, with 8096 words on magnetic drum as backing store),
including recursion, but with a few features omitted.

So, where did the idea of recursion come from?

Bauer and Samelson together invented the idea of a call stack (which
they called Operationskeller --- operation cellar) independently from
others in 1955--1956, and filed a patent application in Germany in
1957, and received patents in Germany (1960), the UK (1958), and the
USA (1962).

However, the algol68.bib file records work by Charles Hamblin in
Australia, who independently first publicized the use of Polish, and
reverse Polish (RPN), notation for expression evaluation in 1957,
using a stack for the operands and operators.  He based his ideas on
work in 1920 by the Polish mathematician, Jan {\L}uksiewicz.  Hamblin
implemented an RPN expression evaluator on the English Electric DEUCE
(the commercial extension of Alan Turing's Pilot ACE and ACE computer
in the UK).  Hamblin's use of RPN largely solved the stumbling block
of expression evaluation that had made compiler work in the 1950s
difficult.  Bauer credits Hamblin with the idea of hardware-supported
stacks, and by the 1960s, Burroughs and DEC had built commercial
machines with hardware stack instructions, and most machines built
from the 1970s onwards have had hardware stack support (CDC and Cray
supercomputers excepted).  The Forth, PostScript, and PDF languages
all use RPN for fast interpretation.

That isn't the end of the history, because it was discovered in 1977
by two New Zealanders, B. E. Carpenter and R. W. Doran, that Alan
Turing had actually proposed a stack and procedure recursion in 1945
for his Automatic Computing Engine (ACE); alas, the technology of the
time was not sufficient to implement it, and the ACE and DEUCE did not
have recursion.  Turing devoted only a few sentences to the procedure
call, and used peculiar terminology, so his idea seems to have gone
unnoticed for 32 years.

There are also statements that Konrad Zuse's Z4 in 1945 independently
used recursion, but I have yet to find details of that claim.

The arguments against recursion were that it was unnecessary, because
nobody then had yet found a good use for it in numeric computing.

Some historical examples, such as Euclid's greatest common denominator
algorithm, and factorials, can be compactly expressed with recursion,
but are easily rewritten with iteration, or tail recursion, without
needing stacks.  However, divide-and-conquer algorithms, like
quicksort and tree traversal, are far easier to implement, and to
parallelize, with recursion than with iteration.

The CDC 6x00 and 7x00 machines stored the return address in the memory
word immediately before the first procedure instruction, and returned
via an indirect jump to that word.  Cray machine procedure calls
avoided memory, but instead put the return address in a fixed
register, so nested calls required the compiler to manage a software
stack.

What is surprising today is that the Backus--Naur Form (BNF) notation
for language grammars that was developed for Algol 58 and 60 used
recursion naturally, as in the grammar rules
 
	<digit>  := 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
	<number> := <digit> | <digit> <number>

Forbidding a procedure from calling itself, as Fortran and COBOL did,
meant extra checking in the compiler, and complicated the language
grammar.  Alternatively, you could make a recursive call, but it could
never return to its top-level compiler, and would either crash, or
loop.

-------------------------------------------------------------------------------
- Nelson H. F. Beebe                    Tel: +1 801 581 5254                  -
- University of Utah                                                          -
- Department of Mathematics, 110 LCB    Internet e-mail: beebe@math.utah.edu  -
- 155 S 1400 E RM 233                       beebe@acm.org  beebe@computer.org -
- Salt Lake City, UT 84112-0090, USA    URL: https://www.math.utah.edu/~beebe -
-------------------------------------------------------------------------------