Re: Iteration in lisp

Pertti Kellomäki <pertti.kellomaki@xxxxxx> writes:

Kent M Pitman wrote:
wrf3@xxxxxxxxxxxxxxx (Bob Felts) writes:
Kent M Pitman <pitman@xxxxxxxxxxx> wrote:
A
recursive function can run out of stack since CL does not guarantee
tail call elimination.
Any pointers to the rationale for this decision?
Stack debugging.

While technically correct, I don't think this really holds
water. In the absence of guaranteed tail call elimination,
iterative processes have to be written using loops, which
destroy exactly the same information as tail calls.

IMO the only real argument against guaranteed tail call elimination
is that it may be too expensive for some implementations.

I think you're getting into the classic Scheme-vs-CL terminology
trap. These discussions have gone on periodically, and from my own
participation in them I shun the use of the phrases "tail call
elimination" or "tail-call optimization", because they are both
misnomers, and each have different meanings in the Scheme and CL
worlds, so talking about them inevitably leads to cross-purposes.
We're not "eliminating" anything here; we are just exchanging a call
for a jump. And though the second term has not shown up in this
thread, the kind of "optimization" being done is not necessarily
time-wise efficient, it is all about optimizing the use of stack
space.

So I personally prefer the terms that came out of some of those
past discussions to describe the two _different_ styles of tail call
handling: for Scheme requirements: "space-efficient tail recursion",
and for CL, "tail-call merging".

So now the question becomes "why don't you use space-efficient tail
recursion for iterative tasks in CL"? And the answer is "because CL
implementations do not implement space-efficient tail recursion - they
only implement tail-merging". And if you're wondering why this is, it
is because CL implements special variables and because it does not
implement CPS, both issues make space-eficient tail recursion very
hard.

There are some programming techniques that are only possible with
tail call elimination, yet have little to do with functional
programming. Implementing a state machine as a set of mutually
recursive functions comes to mind, and I'm sure there are others
as well.

"only possible with tail call elimination" is a strong statement.
Be sure of yourself before you tell people what they can't do; it
generally tends to make them more determined to prove you wrong, even
if indeed you are right to start with. Think Turing, and then if you
choose restate your point in terms that are correct.

--
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: CAS, Lambda Calculus, Continuation and Functional Programming
    ... >>Recursion that's equivalent to loops can always be optimized back into ... and that tail calls are equivalent to loops. ... If a loop is formulated in a recursive way then ... >> that makes tail call elimination less attractive for compiler writers. ...
    (sci.math.symbolic)
  • Re: Iteration in lisp
    ... recursive function can run out of stack since CL does not guarantee ... In the absence of guaranteed tail call elimination, ...
    (comp.lang.lisp)
  • Re: Recursive calls and stack
    ... tail recursion, mutual recursion, and any other tail call to ... support either. ... elimination) require some sort of external support: ...
    (comp.lang.python)
  • Re: CAS, Lambda Calculus, Continuation and Functional Programming
    ... >>that makes tail call elimination less attractive for compiler writers. ... > I don't know why exception handling should prevent tail-call ... so a local array would be best (in languages ...
    (sci.math.symbolic)
  • Re: Iteration in lisp
    ... Nearly all compilers seem to do tail call elimination ... My remarks were directed not any user making a properly informed ... Common Lisp, I generally mean "any Common Lisp"; when I want to talk about ...
    (comp.lang.lisp)