If D wants to become more fit for functional programming, then D specs may talk about this, and the DMD may learn to perform part of such optimization, and GCC does.

One of the several possible alternative solutions: http://www.score.is.tsukuba.ac.jp/~minamide/papers/sas03.pdf

A bit of related discussion: http://lambda-the-ultimate.org/node/1331

Bye,
bearophile

bearophile wrote:
> If D wants to become more fit for functional programming, then D
> specs may talk about this, and the DMD may learn to perform part of
> such optimization, and GCC does.
> 
> One of the several possible alternative solutions: http://www.score.is.tsukuba.ac.jp/~minamide/papers/sas03.pdf
> 
> A bit of related discussion: http://lambda-the-ultimate.org/node/1331



I know how to do tail call optimization (it's a very old optimization),
but there are some technical problems with it in the back end.

In any case, tail call optimization is not necessary to do D-style
functional programming, because loops with mutable indices are practical
with pure functions.

Walter Bright:

>I know how to do tail call optimization (it's a very old optimization), but there are some technical problems with it in the back end. In any case, tail call optimization is not necessary to do D-style functional programming, because loops with mutable indices are practical with pure functions.<

- I think GCC is able to perform tail call optimization in some situations, but not in all of them, I think it has some limits. So I presume that even if you know how to perform such optimization, you may not know how to make the compiler perform it in every situation.
- 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.
- I was mostly talking about D as a language, about its specs, not about DMD. So even if DMD isn't able to perform a tail call optimization, it may become part of its specs anyway. Putting it into the specs (for example like this: "every conformant D implementation must optimize tail calls in this and that situation") seems the only way to make people write code that uses such optimization: GCC has it, but very few C programs I see around rely on it because it's not part of the official C specs.
- I don't know if the LDC compiler is able to perform such optimization, or if can learn such trick. I think LDC can become an important part of the future of the D language.
- I have shown two documents (an HTML page and a pdf) that talk about two possible ways to implement forms of tail call elimination. One of similar ways can be used by DMD to perform some forms of tail call optimization so it can respect the D specs :-)

Bye,
bearophile

bearophile:
>- I have shown two documents (an HTML page and a pdf) that talk about two possible ways to implement forms of tail call elimination. One of similar ways can be used by DMD to perform some forms of tail call optimization so it can respect the D specs :-)<

They are ways to "cheat", so they may be used where a proper tail call elimination (TCE) isn't doable, for example in the current Java Virtual Machine. If you look at Closure, it's a very Lisp-like language written for the JVM, and it's quite functional. It has to do loops and twists to allow some forms of tail-call elimination that Scheme programmers naturally expect Closure able to do. Today there are several people that push to see TCE into the JVM, because later it can be used by Closure, Scala, etc.

Bye,
bearophile

Reply to bearophile,

> Walter Bright:
> 
>> I know how to do tail call optimization (it's a very old
>> optimization), but there are some technical problems with it in the
>> back end.

I read that as, "the DMD backend *can't* do tail call elimination" because, given how long Walter has been writing compilers, if it could, I'd be surprised if Walter wouldn't have added it yet. It may be a cases of "ya can't get that from here" or some such that would requiter a major rewrite for a relatively minor gain. 

BCS:
> I read that as, "the DMD backend *can't* do tail call elimination" because, given how long Walter has been writing compilers, if it could, I'd be surprised if Walter wouldn't have added it yet. It may be a cases of "ya can't get that from here" or some such that would requiter a major rewrite for a relatively minor gain.

I have already answered this in a recent post, but the short answer is: there are many ways to "cheat" at this; that is to perform a limited form of this optimization even if a backend isn't able to perform it. So what you say doesn't hold.

Bye,
bearophile

"bearophile" <bearophileHUGS@lycos.com> wrote in message news:ggmm4n$o6d$1@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?

On Wed, Dec 3, 2008 at 8:21 PM, Nick Sabalausky <a@a.a> wrote:
> "bearophile" <bearophileHUGS@lycos.com> wrote in message news:ggmm4n$o6d$1@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

Reply to Nick,

> "bearophile" <bearophileHUGS@lycos.com> wrote in message
> news:ggmm4n$o6d$1@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?
> 

Some not exactly function programs (Lisp programs that accept user input) have infinite recursion. Without TCE they will always crash sooner or later, with it they run just fine.

"Bill Baxter" <wbaxter@gmail.com> wrote in message news:mailman.86.1228306347.22690.digitalmars-d@puremagic.com...
> On Wed, Dec 3, 2008 at 8:21 PM, Nick Sabalausky <a@a.a> wrote:
>> "bearophile" <bearophileHUGS@lycos.com> wrote in message news:ggmm4n$o6d$1@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.)