Tail call elimination

[Bill Baxter]

On Wed, Dec 3, 2008 at 8:21 PM, Nick Sabalausky <a at a.a> wrote:
> "bearophile" <bearophileHUGS at lycos.com> wrote in message
> news:ggmm4n$o6d$1 at digitalmars.com...
>> - I know it's not necessary, just as closures aren't necessary in an OO
>> language,
>> because you can create a class every time you may want a closure. But
>> functional
>> programmers are used to use certain idioms, such idioms they are part of
>> the
>> functional style of mind (and they are useful because you can build over
>> them.
>> Functional programming is all about building functions using other
>> functions). If
>> you want to push some functional-style in D (and I think it's a good
>> thing) then
>> several things are necessary (quite useful) to allow such style of mind
>> (even if
>> some of them may look redundant to nonfunctional programmer, like
>> closures).
>> This is why I think things tail call elimination and a little may be
>> useful if D wants
>> to become more functional.
>
> Maybe I'm just too new to functional programming and tail call elimination,
> but I don't see how TCE could be needed for a functional frame of mind. It's
> just an optimization, right? And as I understand it, it just decreases
> performance hits from function call overhead and prevents the call stack
> from growing proportionally to the depth of recursion (or more simply, it
> just keeps the size of the call stack down). Can you provide an example
> situation where a lack of TCE would be a problem for a functional
> programmer?

Recursion is the functional way to do all iteration.  So it's very
easy to exhaust your stack iterating over a large list, for instance,
if you don't have tail call elimination.

A functional-style list processing function in D might look something like this:

   void process_list(T[] list) {
       if (list.length==0) return;
       process_elem(list[0]);
       process_list(list[1..$]);
   }

--bb