Subject: Re: Tail recursion & CL From: Erik Naggum <erik@naggum.net> Date: Mon, 22 Oct 2001 02:33:51 GMT Newsgroups: comp.lang.lisp Message-ID: <3212706829871008@naggum.net> * Bruce Hoult | This is hardly surprising. But it obviously is, to _so_ many people. | At heart, the idea of tail-call merging comes from the observation that | if the compiler generates code like... | | jsr foo | ret | | ... then it can be replaced with: | | jmp foo I think this is a very good summary of the _actual_ issue. However, if the language mandates that it be "properly tail-recursive", there will be a lot more cases like that than if it does not mandate it, and lots of things that would make it impossible to do it, will be taken out of the language. Given that we find cases like this in our compiled code and can exploit the existing stack framework, wanting tail-call merging is harmless to the language. Given that requesting more tail-call merging on an abstract level has far-reaching consequences for the rest of the language, this means that the request is not just a desire to change these two instructions into one where they occur, but an implicit desire for all the other changes that come with it. | I guess that's not pleasing to purists, but it's good enough for me. Me too. I am perfectly happy with Allegro CL's way of separating the mergeability of tail-calls to self and to non-self. Since a tail-call to self can easily be made into a jump to a _different_ location than one would normally jump to enter a function, not the least because you know the exact argument list and can do everything you may need to do arrange for optional and keyword arguments and what-not before you jump to the real code, effectively only setting the lambda variables to new values, the complexity of unwinding the stack and all that evaporates, the stack frame can be reused, and (almost) all the complexity of a non-self tail- call is simply not there. Nonetheless, Allegro CL does an impressive job of merging non-self calls, too. It turns out to be quite useful in CLOS. /// -- Norway is now run by a priest from the fundamentalist Christian People's Party, the fifth largest party representing one eighth of the electorate. -- The purpose of computing is insight, not numbers. -- Richard Hamming