As some have pointed out downstream from here, SML is definitely a language that does it (but see Appel’s articles on why stacks are superfluous from years ago and weep).
I suspect that all faithful Scheme implementations get close or satisfy this property. But as others have mentioned, many languages fail this property. Their implementors will argue that deep recursions don’t exist or shouldn’t be supported. Sadly, this is even true for languages that support call/cc or similar control operators, with which you could easily achieve this (through internal uses). And when I read their arguments, I recall the tales of my first programming course which told us of IBM’s objections to Algol because it dynamically allocated memory (on the stack) and how inefficient this would be, and that Algol 60 had to be stopped etc. It reminds me of C++’s limits on template expansions. It was 7 or 8, it might be 20 now. It reminds me of Scala’s prelude which defines the function class for up to 5, 8, 22 arguments. When will we learn and implement the elegant solution so that we can strive for good performance for it? > On Apr 27, 2017, at 7:01 PM, brendan <bren...@cannells.com> wrote: > > 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.
