tag:blogger.com,1999:blog-8288194986820249216.post3674366676385010228..comments2024-03-22T05:09:17.789-07:00Comments on Abstract Heresies: Joe Marshallhttp://www.blogger.com/profile/03233353484280456977noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-8288194986820249216.post-23071945417279987262008-02-26T12:38:00.000-08:002008-02-26T12:38:00.000-08:00I'm not entirely sure how to address the question....I'm not entirely sure how to address the question. I was contrasting a pair of equivalent hypothetical languages that differed only in that one guaranteed tail recursion and the other consumed stack on every call. You seem to be asking about the practical difficulties of retrofitting general tail recursion into a language that did not take it into account when it was originally designed.<BR/><BR/>This is a bit of a digression, but I can offer a couple of opinions.<BR/><BR/>Some languages, like C++, place such restrictions on the implementation to make tail recursion essentially impossible (control must return to a frame in order to run the destructors). If your language has some feature like that, then you are basically hosed. You simply cannot use mutually recursive procedures in an unbounded way or you'll overflow the stack.<BR/><BR/>Other languages, like Common Lisp (which I think you had in mind), have only a few impediments to offering fully general tail recursion. You mention special variables and conditions. There are two approaches: the easiest is to avoid using special variables in tail-recursive loops. That's practical enough, but not theoretically satisfying. The second approach is to solve the `dead binding' problem and collect the special variable stack. Darius Bacon wrote a <A HREF="http://www.accesscom.com/~darius/writings/dynatail.html" REL="nofollow">short page</A> on the problem and Henry Baker <A HREF="http://www.pipeline.com/~hbaker1/BuriedStale.html" REL="nofollow">discusses it as well.</A> Conditions can be handled in a manner analagous to dead bindings.<BR/><BR/>The other thing you mentioned is stack traces. There are a few points to make. The first is that debugging isn't usually considered part of the `language proper' as far as semantics are concerned. The second is that traditional iterative constructs like for and while do not push frames for debugging and no one seems to mind. But I think the best `argument' (athough what are we arguing?) is that you can preserve a fixed amount of backtrace information without making recursion use unbounded space. MIT Scheme has a `history' mechanism that records the most recent tail-recursive calls. You can dynamically adjust the history size to give you more or fewer frames of backtrace.Joe Marshallhttps://www.blogger.com/profile/03233353484280456977noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-17655919060119364942008-02-25T11:45:00.000-08:002008-02-25T11:45:00.000-08:00What about costs of introducing tail recursion int...What about costs of introducing tail recursion into a language? E.g., influences on debuggability (stack traces), interaction with conditions and special variables.michaelwhttps://www.blogger.com/profile/10926144101079011297noreply@blogger.com