Subject: Re: Tail recursion & CL From: Erik Naggum <erik@naggum.net> Date: Tue, 02 Oct 2001 08:38:30 GMT Newsgroups: comp.lang.lisp Message-ID: <3211000707208480@naggum.net> * Erik Naggum | I think you might mean the form that evaluates to the value of the | function. It might, for instance, be possible to unwind special | bindings and unwind-protect forms in such a way that you could jump | to a function with it returning to the cleanup forms, so the notion | of "last" might be very confusing and counterproductive. * Bruce Hoult | I covered this in that previous message as well. | | Anything subject to unwind protect or the like is prima facie NOT in | tail position. It is possible that a smart compiler may be able to | optimize things so that it can be moved into tail position, but that's | not something you could depend on. If you had covered it, you would have known that this is not simply an "optimization", but a design decision that would have to be taken if you wanted true support for tail calls. Both special bindings and unwind- protect are so common in Common Lisp programs that separating them from the call stack would have been a _necessary_ design decision, in order that tail calls actually produce useful results. Since you said you had covered this, contrary to my usually flawless short-term memory (I study SQL intensely right now, so there may be some irregular lossage :), I looked for where you had, but I cannot find it. | It seems especially dangerous to move something out from the body of an | unwind-protect -- you'd have to prove first that it was impossible for it | to throw. This is utter nonsense. Please try to understand how a system that does unwind forms _must_ set up these things. The body forms in practice _do_ return, throws or not, through a chain of unwind form, including special bindings, and whether you do this by setting up in-band catcher code or through a separate stack of unwind-forms-to-be-executed, is immaterial. If you do the latter on a separate stack, there is no difference between a normal return from the code that sets it upand a return from somewhere else: the setup has already been done and the execution is performed as part of the return procedure. If you decide to mandate tail-call optimization into jumps, this design would have to be "required" of an implementation because refusing to do tail calls simply in the face of special bindings would just be stupid -- having an elegant solution as it does. If you do not mandate it, you can get away with only "simple" tail-call optimization, and you can get an even more inexpensive tail-call technique when you get it, if you get it. In essence, I believe "properly tail-recursive" is a design decision that affects how the call stack must be designed (and continuations fall right out of a heap-allocated call frame and chain design) and how you can deal with special bindings and unwind-protect (it is no accident that Scheme does not), while tail-call _optimization_ is possible even in languages such as ANSI C. I therefore also believe that it is a _disservice_ to the community to require "properly tail-recursive" because it requires too many negative and unwanted properties of the implementation, but that it is perfectly legitimate to ask the implementations for such a feature. Amazingly, this is the actual situtation: E.g., Allegro CL does a very good job of optimizing tail calls to both self and non-self if you ask for it in their proprietary way, but optimization _is_ a "proprietary" process, anyway. I think some language designers fail to understand this and believe in _mandated_ optimization, which only limit and restrict how their languages may be implemented to the techniques known at the time their favorite optimization theory was in vogue, or techniques developed along that evolutionary branch. The less you prescribe in terms of how to optimize, the more you can take advantage of free-ranging research in optimization, both software and hardware. This is why C is _still_ best optimized for PDP-11-style processors. ///