Re: CL Implementations and Tail-Call Elimination



Pillsy wrote:
Every once in a while, a newbie comes along working through a problem
where they use recursion to do iteration, and usually one of the first
things anyone suggests is that they switch over to using DOLIST or
LOOP or something. In and of itself, this is perfectly good advice,
but one of the reasons always cited (and I cite it too) is that you
can't rely on an ANS Common Lisp implementation to eliminate tail
calls, the way you can rely on a Scheme implementation to do that.

However, it looks to me like CL implementations really usually will do
that sort of elimination, at least with the right set of declarations.

It's a pity that ANSI Common Lisp doesn't define a more straightforward way to declare that you need tail call merging. It is true that most algorithms which are expressed recursively can as well be expressed with iteration constructs, and are probably easier to understand that way, or don't benefit from tail call merging because they are inherently recursive.

However, this misses a programming style where a state machine can be expressed in terms of sets of mutually recursive functions. For example, I am just exploring the implementation of 3-Lisp, and it relies on such an implementation approach. On top of that, the core is (equivalent to) a read-eval-print-loop, that is essentially a non-terminating loop. For that, it is essential that such a set of mutually recursive functions doesn't grow the stack. I can imagine that there are other kinds of programs which could benefit from such a programming style.

It's unfortunate that there is no straightforward way to support such a programming style in an otherwise excellent multi-paradigm language.

I guess, one wouldn't have to go as far as in Scheme, where "proper" tail recursion is a strict requirement. But a declaration, such as (declare (optimize tail-calls)) that is known across several CL implementations would already be very helpful. If implementations are still free to decide not to implement tail call merging, _but_ issue a warning or an error when they see such a declaration, it would be much easier to quickly determine whether some code is easy to port or not. One could have different levels, like (declare (optimize (tail-calls 3))) could be as strong as Scheme's proper tail recursion while anything below 3 just means that the compiler should optimize, but is free to try less hard. (declare (optimize (tail-calls 0))) would then supposedly mean that the compiler should not merge tail calls.

This is, of course, just a sketch, the devil is in the details. But maybe someone is willing to work on a proposal, for example for a CDR document? It's probably a good idea to investigate what the major CL implementations have in common in this regard, and then try to come up with a unified interface for that...


Pascal

--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
.



Relevant Pages

  • Re: CL Implementations and Tail-Call Elimination
    ... where they use recursion to do iteration, and usually one of the first ... at least with the right set of declarations. ... straightforward way to declare that you need tail call merging. ... this misses a programming style where a state machine can be ...
    (comp.lang.lisp)
  • Re: knowing when it is tail recursion or not?
    ... Because then you'd get warnings on any use of recursion. ... Local tail recursion is a special case that is easy to identify, but, ... functions could potentially be turned into a loop. ...
    (comp.lang.functional)
  • Re: knowing when it is tail recursion or not?
    ... Because then you'd get warnings on any use of recursion. ... Local tail recursion is a special case that is easy to identify, but, ... functions could potentially be turned into a loop. ... non-tail call, but you wouldn't know if it is part of a recursion. ...
    (comp.lang.functional)
  • Re: Recursive file listing function - which one is best?
    ... Proper recursion is one of the best things in Lisp/Scheme. ... Tail call elimination isn't mandated in Common Lisp. ... between CL and Scheme have been around the commercial/practical aspects ... the difference in "common practice" is encoded in the language. ...
    (comp.lang.lisp)
  • Re: CL Implementations and Tail-Call Elimination
    ... straightforward way to declare that you need tail call merging. ... tail recursion is a strict requirement. ... In Scheme, proper tail recursion is a strict requirement. ...
    (comp.lang.lisp)