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

[zxq9]

On Tuesday 07 October 2014 10:40:27 Richard A. O'Keefe wrote:
> On 6/10/2014, at 6:28 PM, Bhasker Kode wrote:
> > Which brings me to erlang. To the esteemed members of this list:
> > 
> > When was recursion or tail recursion introduced in erlang?
> > Was it a controversial decision? Was it an easy one?
> > Any anecdotes you'd like to share, even about inspirations for
> > recursion in erlang?
> 
> Erlang has always supported recursion.
> I don't know about the first interpreter,
> but at least since the first compiler (to JAM),
> Erlang has exploited tail recursion.
> 
> What could possibly be controversial about it?
> If you have a strict functional language you are
> pretty much crippled without recursion and tail
> recursion.

A discussion of "tail call optimization" VS looping VS adding stack frames, 
etc. in the context of asking "what is the history of recursion" is perhaps a 
bit misplaced.

The first processing systems were programmed the way developmental systems are 
today: by writing out raw instructions. A tiny step above that is translating 
the basic instruction codes to easier to remember symbols and formalizing a 
syntax for their notation, which results in a basic assembly language. At this 
level there are no loop constructs, just jump instructions.

A GOTO is a thin wrapper around an addressed jump instruction. No optimization 
other than not messing with the stack is necessary to make this as efficient a 
cyclic processing instruction as possible. A function call (in fact, the whole 
concept of function+arg definition) is a wrapper around indexed calling that 
adds a handy way to assign symbols to arguments up front. A function calling 
itself is a way to make a GOTO that returns to the head of the same segment 
easier to write. These are the basics of dealing with sequential processing 
machines and came before the loop construct was invented.

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. It wraps the idea of a GOTO 
together with the idea of condition checking to break the processing cycle. 
Hence it is possible to write a function loop() or assembler macro that 
behaves like a language primitive loop{};, but not the other way around.

This permitted the "C calling convention" to be known to always push to the 
stack, and this rule greatly simplifies the number of cases you have to analyze 
when writing a compiler (and since goto exists in C you can still write a 
compiler in C that implements TCO). C-style function calls are always going to 
grow the stack, so loop primitives are ways to guarantee that one can perform 
iterative processing without growing the stack *and* without forcing the 
compiler to be smart enough to recognize recursive tail calls.

With this in mind, it may be more interesting to give a history of "loop 
words" rather than a history of recursion, as C-derived looping constructs are 
the new, controversial thing here, not recursion.

>From this perspective it may be easier to understand why your question about 
the "inclusion of recursion as a feature" isn't generating a lot of buzz. To 
an FP language designer recursive calls are the default, normal way of 
thinking of things and loop primitives are a complication to the language. An 
attempt to introduce a loop/while/for primitive would be controversial, not 
the other way around.

-Craig