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

zxq9 zxq9@REDACTED
Tue Oct 7 09:12:08 CEST 2014

Bah... forgot to send to list...

On Tuesday 07 October 2014 18:14:32 Richard A. O'Keefe wrote:
> 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

This (and your other) examples illustrate the exact point I am trying to make. 
The original demonstrations of what a computable thing is were recursive as 
per Church's work in 1936 -- before the machines even existed (but "computer" 
meant an office girl armed with a calculation machine who knew how to execute 
prose or formal algorithms). McCarthy published his LISP specification in 1958 
(the same year as FOR TRANSIT which contains that DO instruction). Plankalkül 
had procedure definitions in 1945.

To say that Algol 60 "introduced recursion to many programmers" I think is a 
bit of a stretch. Recursion was very well established, even at the root of, 
computing theory.

It seems, though, that while recursion is simply the way things were noted 
from very early on, with machines that lacked languages entirely one was 
forced to plot jumps manually, which I can easily see would lead directly to 
development of a GOTO as an early language construct before loop or procedure 
definitions came along. From there the common pattern of "GOTO label_a ... IF 
NOT b GOTO label_a" would quickly emerge -- not from the theoretical folks, 
but from the technical folks who are trying to abstract their most common 
patterns in complex control words within their early languages.

>From there it probably *did* take some time before folks who worked with 
machines worked out a formal, reliable method for optimizing recursive calls 
outside of the lisp machines of the early 1970's.

So I suppose its really a question of whether one approaches the OP's theme 
from a theoretical or technical perspective. Recursion has been around for a 
long time in the formal languages that prompted the development of the 
electric computer, but both loop constructs and recursive procedure definitions 
took a rather long time to finally be implemented on machines, with TCO outside 
of Lisp machines being the last to the party.

I have been spoiled, being fortunate enough to start messing with computers in 
the 1980's, long after most of this was sorted.


More information about the erlang-questions mailing list