Re: Iteration in lisp

Pertti Kellomäki wrote:
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.

No, they don't have to be written using loops.

You could, for example, decide to use a recursive version _in order_ to have more debug information at runtime.

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.

It would be good if the decision whether you want more debug information or not were orthogonal to whether you use recursion or iteration. The latter should ideally depend on whatever makes the code easier to understand. More often than not, iteration constructs reveal the intent of the programmer more clearly, though, because they are typically more specialized.


Pascal

--
1st European Lisp Symposium (ELS'08)
http://prog.vub.ac.be/~pcostanza/els08/

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: 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: Iteration in lisp
    ... recursive function can run out of stack since CL does not guarantee ... In the absence of guaranteed tail call elimination, ... recursion for iterative tasks in CL"? ...
    (comp.lang.lisp)
  • 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)
  • Re: Was not making tail recursion elmination a mistake?
    ... >> I have recently been annoyeed by the fact that tail recursion ... >> elimination and must use loops or some simular structue. ... > have been an optional feature. ...
    (comp.lang.lisp)
Loading