Dr. Felleisen, Thanks for the informative response. Is Racket the only language with unbounded recursion depth as far as you know? And with respect to implementation, can you explain the role of the one extra bit that you mention?
A number of functional languages targeting platforms like the JVM and browsers are compromised by the lack of proper tail calls. I often wonder how much of a performance penalty you would have to pay if those languages were implemented by CPS-transforming the whole program and running on a trampoline, except where the compiler could prove constant-bounded call depth. On Tuesday, April 25, 2017 at 9:09:10 PM UTC-4, Matthias Felleisen wrote: > Brendan, > > you’re correct in attributing the idea that the proper implementation of tail > calls is far less important to the Scheme and Racket community. Dybvig > expressed this idea first in a talk titled a Bag of Hacks in the early 90s. > Matthew then at some point said that the true goal is to never run out of > stack space (other than run out of memory period); once we have that proper > tail-call implementation might just be of secondary value. > > As for terminology, I think I would say that a language ought to support > ‘unbounded recursion depth’. Unwieldy name. > > How is it implemented? When a call is about to exhaust the available stack > space, grab the stack, move it into the heap, start a new one with a frame > that links to the moved stack. If you now also want to implement > continuation-grabing control operators (call/cc, C, F, prompt, etc) you can > do so with one extra bit per stack frame and lazy copying of heap-moved > stacks to the stack proper. > > While I am at it, let me advocate PITCH as the slogan for Proper > Implementation of Tail Calls. (Where does the H come from? I added it to make > a complete word.) What many people fail to see is that every language with > function calls has tail positions. The syntax may obscure those with various > superfluous keywords but that does not invalidate the idea. A tail-call > position is a ‘return’ place in a function body. Period. So when people say > “we implement tail calls”, it’s basically nonsense because every language > with function calls must implement tail calls. The question is whether the > evaluation of arguments or the evaluation of function calls consumes space. > And if you love OO design patterns — which is where Scheme comes from — you > must opt into the former not the latter, which means you must implement tail > calls properly. > > — Matthias > > > > > > > > > On Apr 25, 2017, at 7:32 PM, brendan <bren...@cannells.com> wrote: > > > > Good points: It wasn't strictly true to say that you can make non-tail > > calls "without fear." Rather, your memory for continuation frames is shared > > with, and just as large as, any other kind of data. > > > > -- > > You received this message because you are subscribed to the Google Groups > > "Racket Users" group. > > To unsubscribe from this group and stop receiving emails from it, send an > > email to racket-users+unsubscr...@googlegroups.com. > > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
