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

zxq9 zxq9@REDACTED
Fri Oct 10 03:13:09 CEST 2014


On Thursday 09 October 2014 19:29:56 you wrote:
> another erlang specific question.
> 
> foo()->
>   foo().
> 
> bar()->
>   receive
>       X ->
>          bar()
>   end.
> 
> both the above functions are tail-call optimized and happen to be recursive.
> 
> if i run foo(), would its callstack remain unchanged? will beam bring it
> down? how does it compare with the procedural while (1) { //do something }

foo() -> foo(). behaves the same as while(1) {};. Testing just now, the stack 
indeed remains constant (at ~2.5k), and checking with Observer on the system 
I'm sitting at now shows around 4 billion reds per update. Beam will not bring 
down a simple infinite loop like this unless you tell it to (its performing as 
intended, why kill it if the user wanted it?).

Its sort of interesting, with regard to scheduling not recursion, to spawn a 
few more of these than  you have cores, and then run something else and watch 
the EVM schedule around all the blank load.

With regard to the original line of this thread...

Richard O'Keefe, in a line of private emails, has convinced me that while 
recursion is at the root of computing theory, the concept was almost 
completely unknown in commercial languages until sometime in the (probably 
very late) 60's, and still not very well accepted outside AI research until a 
bit later.

He demonstrated to me that the world of computing theory and AI research, 
being full of recursive definitions from the beginning (Lovelace -- with a 
unique notation for "cycles of cycles", Church, Gödel, etc.), had shockingly 
little impact on the tradition of language design that brought us to where we 
are today. In particular, it played no role in informing commercial hardware 
development and that led to an almost deliberate aversion to the subject by 
language designers working for those companies.

Richard O'Keefe wrote:
> APL (designed through 1960-1965)
> could do recursion, but it was interpreted, and was and
> remained, like Lisp, a niche language irrelevant to
> nearly all programmers.  PL/I supported recursion, which
> like much else it copied from Algol 60, but it was
> regarded as strange, scary, and rare, and you had to
> explicitly write, e.g.,
> 
>    factorial:
>       procedure (n) options (recursive);
>       
>          if n < 2 then return 1;
>          else return n * factorial (n-1);
>       
>       end;
> 
> Programming textbooks warned people not to use this feature
> because it was too inefficient

This makes me feel that we are still only rediscovering ideal ways to 
communicate with our computers and haven't yet come up with anything really 
new (some of the ideal notational concepts go as far back as Ada Lovelace's 
notes!). I'd always thought that developments in theory/research were 
influential in industry, but this  was clearly not the case.

I'd like to thank Richard for taking the time to so thoroughly prove my 
assumptions wrong. It was really interesting!

-Craig



More information about the erlang-questions mailing list