[erlang-questions] The history of recursion in languages. Any stories from erlang?

[Richard A. O'Keefe]

It is someone 'revisionist' to suggest that looping constructs
are the innovation.  For example, look at
http://bitsavers.informatik.uni-stuttgart.de/pdf/ibm/650/28-4028_FOR_TRANSIT.pdf
the reference manual for the FOR TRANSIT programming language
on the IBM 650, developed in 1958.
The control statements of FOR TRANSIT included
    GOTO label               ! simple goto
    GOTO (label,...), index  ! switch
    IF (expr) neg,zro,pos    ! 3-way conditional (on sign)
    DO label var = first,last[,step] ! loop

FOR TRANSIT could call functions written in SOAP, but you
could not write subroutines or functions in FOR TRANSIT itself.
To my astonishment, the same is true of IBM 650 FORTRAN.
http://bitsavers.informatik.uni-stuttgart.de/pdf/ibm/650/29-4047_FORTRAN.pdf

So, 1958 "high level language": subroutines no, loops yes.

It's worse than that.  On my reading of
http://bitsavers.informatik.uni-stuttgart.de/pdf/ibm/650/22-6060-2_650_OperMan.pdf
the IBM 650 doesn't strictly speaking *have* a procedure calling
instruction.  Remember, this is a machine from 1953.  (The link
above points to the 1955 revision of the manual.)  Instructions
had the form
<sign: ignored>
<opcode: 2 decimal digits>
<data address: 4 decimal digits>
<next instruction address: 4 decimal digits>
On later models of the machine, which had 3 index registers,
I imagine you could do one level of procedure calling thus:
   L1: load index register 3 with contents of M1
       goto L3
   L2:

   L3: here is the procedure
       goto 0+Index3

   M1: data word holding L2 (the return address)
On earlier models of the machine, which had no index registers,
I imagine doing procedure calls thus:
   L1: load accumulator with contents of M1
       store accumulator into next instruction address
       field of L3
       goto L3+1
   L2:

   L3: goto 0
       here is the procedure
       goto L3

   M1: data word holding L2 (the return address)

(If you have ever read Knuth's "The Art of Computer Programming",
the MIX machine is *extremely* like an IBM 650.)  Both of these
sketches could in concrete contexts be improved in small ways.
But heck, the machine only had 2,000 words of memory, so it was
not as if you could _have_ lots of subroutines or nest calls to       
them deeply.  The key thing is that you will notice that
recursion would have been seriously impractical on this machine.

The IBM 650 was arguably the Model T Ford of computers.
The first computer in this country (used by the Treasury
for several years) was an IBM 650.

Algol 60 introduced recursion to many programmers, but it
*also* had loop keywords.  This is where we get 'while' from,
though it was tangled up with other things, and it's also
where we get 'Boolean' from, and it's definitely where we get
the word "stack" from.

The idea of tail recursion optimisation was published in the 1970s.

> The controversial innovation (if anything here can be considered 
> "controversial") would be the loop construct. This is a new idea that does not 
> exist at the basic level of sequential processing.

This is a dubious claim.  Loop constructs were commonplace in
the late 1950s, and some computers designed in the 1960s had
special hardware support for loops (as for example z/Series
and POWER still do, not to mention that other weirdo, x86).