Tail call elimination

[Nick Sabalausky]

"Bill Baxter" <wbaxter at gmail.com> wrote in message 
news:mailman.86.1228306347.22690.digitalmars-d at puremagic.com...
> 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

I see. From what bearophile said, it sounded like he was indicating it 
enabled something more idiomatic/high-level then preventing stack overflow.

On a side note, stack overflows are still possible anyway (whether 
functional or imperative). Is there a reason (other than inertia) that stack 
frames aren't set up like a dynamic array to grow as needed? (Of course, I 
can understand not doing that during a debug build to help detect 
unintentional infinite recursion) I realize the overhead of checking the 
stack size on every function call might be undesirable, but (not that I've 
given this much thought) is there no trick to set something up to 
automatically trigger when the stack fills up? Or, isn't it already 
detecting stack overflow anyway (I know some languages do that)? (Of course, 
I'm not saying any of this would be a substitute for TCE, just a good 
compliment to it.)