tag:blogger.com,1999:blog-8288194986820249216.post8774790492990732480..comments2024-03-22T05:09:17.789-07:00Comments on Abstract Heresies: Afraid of Tail RecursionJoe Marshallhttp://www.blogger.com/profile/03233353484280456977noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-8288194986820249216.post-3659987398350010922020-11-15T19:04:44.138-08:002020-11-15T19:04:44.138-08:00IIRC "trampolining" was invented as a wa...IIRC "trampolining" was invented as a way to implement a tail-recursive language (Scheme, I think) inside of a total C environment without resorting to any assembly language tricks or knowledge of the generated C code from any particular compiler. Trampolining is unsuitable for any implementation that actually can generate code.<br /><br />I don't understand why the JavaScript compiler and JIT developers are hung up on trampolining (or even Cheny-on-the-MTA), using its poor performance as an excuse to not implement PTC as required by ES6. They definitely fall into the camp of "do not get TC". Because:<br /><br />You point to Steele's "lambda" papers. Yes. Those papers plus his Rabbit compiler prove that this problem was solved in the late 70's. As good as this blog post is - and it <i>is</i> good, thank you! - those papers are a model of clarity. How you could read them and not get understand the use of and need for PTC is beyond me.<br /><br />[possibly posted twice, if so, excuse me!]David Bakinhttps://www.blogger.com/profile/08596808011584860686noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-57134827969742094592020-11-15T18:58:29.148-08:002020-11-15T18:58:29.148-08:00IIRC trampolining was invented so that a tail recu...IIRC trampolining was invented so that a tail recursive language interpreter could be implemented entirely in C. The goal was to remain trapped in C, no recourse to low-level assembly or knowledge of the C compiler's generated code, yet still have a proper Scheme implementation.<br /><br />I just don't understand why JavaScript <i>compiler</i> (equivalently, <i>JIT</i>) developers don't get this and still talk about trampolining as if it was necessary to them - and thus, to complain about the "overhead" of having a code generation/runtime model that supports PTC.<br /><br />You point to Steele's "Lambda" papers. Yes, those papers and his Rabbit compiler showed that this issue was essentially solved in the late 70's. And, as good as this particular blog post is, and it is very good (thank you!), those papers are models of clarity. How you could read them and not get what's going on is beyond me.David Bakinhttps://www.blogger.com/profile/08596808011584860686noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-24052537352885913702020-02-06T14:30:30.445-08:002020-02-06T14:30:30.445-08:00In my view, the biggest problem with TCO is that i...In my view, the biggest problem with TCO is that it overloads the function call syntax with something that is similar yet completely different. That makes programs less readable. If you insist on having TCO, provide specific and explicit syntax for it. This would also avoid bugs where intended TCOs aren't.Frode Fjeldhttps://www.blogger.com/profile/15999123169380161501noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-73125057119030815972020-01-22T05:06:52.536-08:002020-01-22T05:06:52.536-08:00Manually handling recursive computation with an ex...Manually handling recursive computation with an explicit stack is basically orthogonal to whether the language you express it in offers tail recursion. In fact it is slightly easier if <i>do</i> have tail recursion. As an example, I point to MIT/GNU Scheme. It is written in C, and manually handles recursive computation with an explicit stack for the purpose of achieving tail recursion in the interpreted Scheme. But since C itself isn't tail recursive, the core of the interpreter has to be written in one big C function that doesn't itself make any function calls. The core of the Racket interpreter is one big C function as is the core of SIOD. If C were tail recursive, then the core of the interpreter could be broken into several more abstract units.Joe Marshallhttps://www.blogger.com/profile/03233353484280456977noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-6079038366255286952020-01-21T20:00:33.235-08:002020-01-21T20:00:33.235-08:00Another aspect of not having TCE is that by manual...Another aspect of not having TCE is that by manually handling recursive computation using an explicit stack make is easy to searialise the "continuation", which allows checkpointing in a distributed system.<br />I work for a $BIGCORP and all our data pipelines are done in a dataflow style, under the assumption that there are maybe thousands of compute nodes but they are very low priority and can be evicted at any moment.<br />In practice, even though I've tried Scheme & continuations I can't think of any case where I found those new control flow techniques superior to what we have from the point of view of my ability to reason about the code and debug it.<br />I hope one day somebody will come up with a runtime that will offer debugging and profiling tools adequate to these new control flow techniques.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-78953634126674701932020-01-21T12:23:09.424-08:002020-01-21T12:23:09.424-08:00
If you need stack traces for debugging, in most C...<br />If you need stack traces for debugging, in most Common Lisp impls I’ve tried it on, you can get the compiler to not do TCE by loading, rather than compile-and-loading, the code in question.Dave Cooperhttps://www.blogger.com/profile/01594397904246761818noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-74701764236156348712020-01-21T12:22:32.281-08:002020-01-21T12:22:32.281-08:00This comment has been removed by the author.Dave Cooperhttps://www.blogger.com/profile/01594397904246761818noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-85210585319633722232020-01-21T05:23:42.527-08:002020-01-21T05:23:42.527-08:00Baily and Weston have had the opposite experience....Baily and Weston have had the opposite experience. They report up to 7x improvement in performance in <a href="https://pdfs.semanticscholar.org/bd68/df8bcae9f1d8cb185b6be0fbcc6fd58c941f.pdf" rel="nofollow"><i>Performance Benefits of Tail Recursion Removal in Procedural Languages</i></a>. Perhaps they used a different approach.<br /><br />By most accounts, trampolining is about the slowest way to get proper tail recursion, and it usually causes only about a factor of 2 slowdown.Joe Marshallhttps://www.blogger.com/profile/03233353484280456977noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-88810272377934672682020-01-21T04:52:51.376-08:002020-01-21T04:52:51.376-08:00I think TCE is cool in principle, but I am simply ...I think TCE is cool in principle, but I am simply not willing to give up proper stack traces. I can immediately see through 80% of runtime errors by looking at a stack trace, so stack traces are of utmost value to me.<br /><br />The argument that loops don't give you a stack trace either is unconvincing. In practice, not having a trace for loops has never been an issue for me.<br /><br />I am aware that there are implementation techniques that give you both TCE and proper stack traces (at least for a subset of the stack). I would need to see more discussion and experience reports of those techniques to be convinced.<br /><br />A smaller, but nevertheless real, issue is the performance hit from TCE on really existing architectures. I have implemented a couple of Lisp interpreters, and the ones with TCE are about 10x slower in various approaches I have tried.Manuel Simonihttps://www.blogger.com/profile/07840673741485280526noreply@blogger.com