Re: CL Implementations and Tail-Call Elimination

Pascal Costanza <pc@xxxxxxxxx> writes:

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.

That's because tail merging is not straightforward. There are
tradeoffs involved, and they are usually associated with the
programming styles under which different programmers like to operate.
In fact, given any random group of Common Lispers, you'll find that
tail-merging can generate a lot of heated debate - on one hand, there
is the stack-space-efficiency issue, where the implementation wants to
use the system's stack space(s) but they are limited resources. On
another hand there are those who would rather see debugability, and
when frames are taken off of the stack due to tail-merging, it is a
lot harder to see the path from one function to its apparent (but
indirect) progeny. On a third hand, there is the conversation that is
usually dominated when Schemers are involved about "proper" tail
recursion (which I think is more properly called "space efficient tail
calling") - this issue (of whether this style is right or wrong, or
needed or unnecessary) tends to dominate conversations sometimes, but
that tends to leave the more subtle "stack-space vs debuggable frames"
conversation on the back burner. And at Franz, where we had most of
these conversations amongst ourselves (not agreeing, by the way, but
agreeing to disagree and to try to support as much of the range of
stances as possible), we noted that the conversation even changes when
discussing "self" calls vs calls to other functions - people's
priorities tend to change even with those distinctions, and we provide
different default behavior for each of those cases.

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.

Such a programming style would have to allow for the multi-paradigms
in all directions in order to be effective, including the ones I've
mentioned above - are CLers also willing to discuss the possibility of
defining CPS (which is usually implied when the "space-efficient tail
call" is discussed)?

I guess, one wouldn't have to go as far as in Scheme, where "proper"
tail recursion is a strict requirement.

Why not? If we are going to have such a multi-paradigm feature,
shouldn't it truly be multi-paradigm?

But a declaration, such as
(declare (optimize tail-calls)) that is known across several CL
implementations would already be very helpful.

I think this is too simplistic. For one thing, I have a problem with
the "optimize" aspect of it. Let me explain: When you say
(declare (optimize speed)) it is saying (declare (optimize (speed 3)))
which really means "I care about speed". It is also obvious that you
want faster, not slower (though even that could depend on your point
of view [1]). The same goes with the other standard optimize
settings: safety, space, and compilation-speed - it is pretty obvious
which way you want to go with these which would make the resultant
code "optimal" in that direction. But an "optimal" tail-call? No, a
tail call is a tail-call, whether it is implemented as a jump or a
jump-and-link. It is part of its nature, and what defines it. So
how do we "optimize" it? We don't - we optimize aspects of its
implementation instead. I would be more open to (though still not
enthusiastic about) optimization qualities named "tail-jump" or
"tail-merge", because at least those imply a direction.


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.

This is not consistent with the philosophy of Common Lisp, which, with
very few exceptions, allows declarations to be ignored. Obviously, an
implementation that ignores all declarations is not very valuable, but
neither is an implementation that spits out so much warning
information that important information is lost.

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...

To start with Allegro CL, as I stated elsewhere in this thread, a good
starting point is here:

http://www.franz.com/support/documentation/8.1/doc/compiling.htm#tail-merge-disc-2


[1] In my area we have a cable company which is advertising high-speed
internet over cable, and their commercials show a turtle and his wife
singing the praises of their nice, _slow_, unhurried DSL line; they
even try to get as far away physically from their hub as possible, so
the male turtle is out in the back yard trying to see if he can get
just a little bit more slowness out of his DSL...

--
Duane Rettig duane@xxxxxxxxx Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
.

Relevant Pages

  • Re: CL Implementations and Tail-Call Elimination
    ... It's a pity that ANSI Common Lisp doesn't define a more straightforward way to declare that you need tail call merging. ... this misses a programming style where a state machine can be expressed in terms of sets of mutually recursive functions. ... I guess, one wouldn't have to go as far as in Scheme, where "proper" tail recursion is a strict requirement. ... such as (declare (optimize tail-calls)) that is known across several CL implementations would already be very helpful. ...
    (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)