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

[Sean Cribbs]

Woops, forgot reply-all.

---------- Forwarded message ----------
From: Sean Cribbs <sean@REDACTED>
Date: Mon, Oct 6, 2014 at 8:31 AM
Subject: Re: [erlang-questions] The history of recursion in languages.
Any stories from erlang?
To: Bhasker Kode <bosky101@REDACTED>


This video [1] explains it in better detail than I can, but it seems
to be that an early version was a term-rewriting interpreter.
Basically it would apply (reduce?) functions to their base terms and
then consume the terms. This means that as long as the recursive call
is the last thing in the function, tail-recursion is nearly free, it
just gets rewritten. The stack depth only increases when a caller uses
the return value directly, otherwise tail-recursive calls incur
constant space.

[1] http://www.erlang-factory.com/conference/SFBay2010/speakers/joearmstrong

On Mon, Oct 6, 2014 at 12:28 AM, Bhasker Kode <bosky101@REDACTED> wrote:
> We erlangers, have much to thank tail recursion for many of the
> benefits and constructs that it gives us.
>
> 1. Tail recursion after all is the foundation of processes. Without
> which the call stack would keep growing.
> 2. Processes are the foundation of implementing state machines
> 3. And it was Lesie Lamport "Turing Award" winner and considered the
> father of distributed computing, who said that distributed systems
> should be represented as state machines since they're so many unknowns
> and things are changing all the time.
>
> Which is why I thought I'd give a talk about tail recursion at FuConf,
> a functional programming conference next week.
> => http://functionalconf.com/ , ping me for a big discount or if
> you're travelling to Bangalore for the first time )
>
> But I was also fascinated investigating the history of recursion and
> tail recursion itself.
>
> Arguably the first programming language in which recursive procedures
> were included was J. McCarthy’s LISP. However, it was added only 2/3
> months before the first implementation of LISP was complete.
>
> During the 60's, stories and conspiracies around Algol-60 run like a
> bond-movie, from the accounts of Djikstra and P Naur many years later.
> Its committee members calling it the "Amsterdam Plot". Resignations,
> Secretly adding sentences to language drafts. Cross-country phone
> calls. Much of the controversy I believe stemmed from including
> recursion vs not.
>
> - C compilers are known to tail call optimize.Talking about relatively
> more modern languages:
> - Python still doesn't have tail recursion although map, reduce, and
> lambda's were introduced in 1994, through the work of an anonymous but
> prolific early contributor.
> - Java compiler doesn't tail call optimize.
> - But Scala does. In fact you can define functions to be tail
> recursive, and it won't compile until it "is" tail-recursive.
>
> 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?
>
> Thanks
>
> ~Bosky | @bhaskerkode
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions



--
Sean Cribbs <sean@REDACTED>
Software Engineer
Basho Technologies, Inc.
http://basho.com/


-- 
Sean Cribbs <sean@REDACTED>
Sr. Software Engineer
Basho Technologies, Inc.
http://basho.com/