www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Tail call elimination

reply bearophile <bearophileHUGS lycos.com> writes:
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
Nov 27 2008
parent reply Walter Bright <newshound1 digitalmars.com> writes:
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.
Nov 27 2008
parent reply bearophile <bearophileHUGS lycos.com> writes:
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
Nov 27 2008
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
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
Nov 27 2008
prev sibling next sibling parent reply BCS <ao pathlink.com> writes:
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.
Nov 27 2008
parent bearophile <bearophileHUGS lycos.com> writes:
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
Nov 27 2008
prev sibling parent reply "Nick Sabalausky" <a a.a> writes:
"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?
Dec 03 2008
next sibling parent reply "Bill Baxter" <wbaxter gmail.com> writes:
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
Dec 03 2008
parent reply "Nick Sabalausky" <a a.a> writes:
"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.)
Dec 03 2008
parent reply Christopher Wright <dhasenan gmail.com> writes:
Nick Sabalausky wrote:

 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.) 


You allocate memory whenever you overflow the currently allocated stack. 
The caveat is that it has to be contiguous to the existing stack 
(virtually contiguous, not physically contiguous). In the best case, as 
soon as you allocate something outside the stack, you've set a limit on 
the stack size.

On Linux, if your stack exceeds its allowed size, you get SIGSEGV. You 
can trap this, but you need to specify an alternate stack to do so. On 
my machine, the default stack limit is 8MB, though you can change that. 
I assume that setting the limit will alter the ranges that heap memory 
allocation can deal with, as well.
Dec 03 2008
next sibling parent reply "Nick Sabalausky" <a a.a> writes:
"Christopher Wright" <dhasenan gmail.com> wrote in message 
news:gh759s$2ucs$1 digitalmars.com...

 Nick Sabalausky wrote:

 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.)


 You allocate memory whenever you overflow the currently allocated stack. 
 The caveat is that it has to be contiguous to the existing stack 
 (virtually contiguous, not physically contiguous). In the best case, as 
 soon as you allocate something outside the stack, you've set a limit on 
 the stack size.

 On Linux, if your stack exceeds its allowed size, you get SIGSEGV. You can 
 trap this, but you need to specify an alternate stack to do so. On my 
 machine, the default stack limit is 8MB, though you can change that. I 
 assume that setting the limit will alter the ranges that heap memory 
 allocation can deal with, as well.


I see, so a relocatable stack would be required, and I can see how that 
would be a problem. Is it (at least in theory) possible to use paging tricks 
to transparently move the stack to a location with more available space 
(perhaps with the cooperation of both the OS and the GC)?
Dec 04 2008
parent Christopher Wright <dhasenan gmail.com> writes:
Nick Sabalausky wrote:

 "Christopher Wright" <dhasenan gmail.com> wrote in message 
 news:gh759s$2ucs$1 digitalmars.com...

 Nick Sabalausky wrote:

 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.)


 You allocate memory whenever you overflow the currently allocated stack. 
 The caveat is that it has to be contiguous to the existing stack 
 (virtually contiguous, not physically contiguous). In the best case, as 
 soon as you allocate something outside the stack, you've set a limit on 
 the stack size.

 On Linux, if your stack exceeds its allowed size, you get SIGSEGV. You can 
 trap this, but you need to specify an alternate stack to do so. On my 
 machine, the default stack limit is 8MB, though you can change that. I 
 assume that setting the limit will alter the ranges that heap memory 
 allocation can deal with, as well.


 
 I see, so a relocatable stack would be required, and I can see how that 
 would be a problem. Is it (at least in theory) possible to use paging tricks 
 to transparently move the stack to a location with more available space 
 (perhaps with the cooperation of both the OS and the GC)? 


If you required a physically contiguous stack that could be logically 
noncontiguous, yes. You need a logically contiguous stack that does not 
need to be physically contiguous, though, so that fails. You'd have to 
change pointers.
Dec 04 2008
prev sibling parent reply =?ISO-8859-1?Q?=22J=E9r=F4me_M=2E_Berger=22?= <jeberger free.fr> writes:
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Christopher Wright wrote:

 Nick Sabalausky wrote:

 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.) 


 
 You allocate memory whenever you overflow the currently allocated stack.
 The caveat is that it has to be contiguous to the existing stack
 (virtually contiguous, not physically contiguous). In the best case, as
 soon as you allocate something outside the stack, you've set a limit on
 the stack size.
 
 On Linux, if your stack exceeds its allowed size, you get SIGSEGV. You
 can trap this, but you need to specify an alternate stack to do so. On
 my machine, the default stack limit is 8MB, though you can change that.
 I assume that setting the limit will alter the ranges that heap memory
 allocation can deal with, as well.


	Actually, on Linux, the stack for the main thread grows dynamically
until it reaches the allowed size. It is *not* allocated with the
full size at the start. For other threads OTOH, the stack is
allocated once and for all at thread creation.

		Jerome
- --
+------------------------- Jerome M. BERGER ---------------------+
|    mailto:jeberger free.fr      | ICQ:    238062172            |
|    http://jeberger.free.fr/     | Jabber: jeberger jabber.fr   |
+---------------------------------+------------------------------+
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEARECAAYFAkk5eWgACgkQd0kWM4JG3k+9wQCfVLBCeV38yS/CQVUiuEvSxpoK
V5EAnRPauWLZ0oRbAUWXaGgDd9TIHcs8
=NnEi
-----END PGP SIGNATURE-----
Dec 05 2008
parent Christopher Wright <dhasenan gmail.com> writes:
Jérôme M. Berger wrote:

 	Actually, on Linux, the stack for the main thread grows dynamically
 until it reaches the allowed size.


That's exactly what I said. It didn't occur to me beforehand that you 
could preallocate the stack, but now that I think about it, nobody would 
be happy if Linux preallocated 8MB for every process.

Thanks for the information on threads, though.
Dec 05 2008
prev sibling parent BCS <ao pathlink.com> writes:
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.
Dec 03 2008