digitalmars.D - Tail call elimination
- bearophile (7/7) Nov 27 2008 If D wants to become more fit for functional programming, then D specs m...
- Walter Bright (6/14) Nov 27 2008 I know how to do tail call optimization (it's a very old optimization),
- bearophile (8/9) Nov 27 2008 - I think GCC is able to perform tail call optimization in some situatio...
- bearophile (4/5) Nov 27 2008 They are ways to "cheat", so they may be used where a proper tail call e...
- BCS (6/11) Nov 27 2008 I read that as, "the DMD backend *can't* do tail call elimination" becau...
- bearophile (4/9) Nov 27 2008 I have already answered this in a recent post, but the short answer is: ...
- Nick Sabalausky (10/29) Dec 03 2008 Maybe I'm just too new to functional programming and tail call eliminati...
- Bill Baxter (11/40) Dec 03 2008 Recursion is the functional way to do all iteration. So it's very
- Nick Sabalausky (15/59) Dec 03 2008 I see. From what bearophile said, it sounded like he was indicating it
- Christopher Wright (11/22) Dec 03 2008 You allocate memory whenever you overflow the currently allocated stack....
- Nick Sabalausky (6/28) Dec 04 2008 I see, so a relocatable stack would be required, and I can see how that
- Christopher Wright (5/35) Dec 04 2008 If you required a physically contiguous stack that could be logically
- =?ISO-8859-1?Q?=22J=E9r=F4me_M=2E_Berger=22?= (19/43) Dec 05 2008 -----BEGIN PGP SIGNED MESSAGE-----
- Christopher Wright (5/7) Dec 05 2008 That's exactly what I said. It didn't occur to me beforehand that you
- BCS (4/39) Dec 03 2008 Some not exactly function programs (Lisp programs that accept user input...
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
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/1331I 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
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
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
Reply to bearophile,Walter Bright: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 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.
Nov 27 2008
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
"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
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...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 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
"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: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.)"bearophile" <bearophileHUGS lycos.com> wrote in message news:ggmm4n$o6d$1 digitalmars.com...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 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
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
"Christopher Wright" <dhasenan gmail.com> wrote in message news:gh759s$2ucs$1 digitalmars.com...Nick Sabalausky wrote: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)?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 04 2008
Nick Sabalausky wrote:"Christopher Wright" <dhasenan gmail.com> wrote in message news:gh759s$2ucs$1 digitalmars.com...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.Nick Sabalausky wrote: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)?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 04 2008
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Christopher Wright wrote:Nick Sabalausky wrote: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-----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 05 2008
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
Reply to Nick,"bearophile" <bearophileHUGS lycos.com> wrote in message news:ggmm4n$o6d$1 digitalmars.com...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.- 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