I am currently reading SICP
(http://mitpress.mit.edu/sicp/full-text/book/book.html, up to now a
very nice read for a newbie like me) and I have just reached chapter
1.2.1 - Linear Recursion and Iteration. This passage was particulary
interesting (sorry for the large quote):
"One reason that the distinction between process and procedure may be
confusing is that most implementations of common languages (including
Ada, Pascal, and C) are designed in such a way that the interpretation
of any recursive procedure consumes an amount of memory that grows with
the number of procedure calls, even when the process described is, in
principle, iterative. As a consequence, these languages can describe
iterative processes only by resorting to special-purpose ``looping
constructs'' such as do, repeat, until, for, and while. The
implementation of Scheme we shall consider in chapter 5 does not share
this defect. It will execute an iterative process in constant space,
even if the iterative process is described by a recursive procedure. An
implementation with this property is called tail-recursive. With a
tail-recursive implementation, iteration can be expressed using the
ordinary procedure call mechanism, so that special iteration constructs
are useful only as syntactic sugar."
Above Scheme is mentioned, but how is it with Common Lisp? Does it also
do this optimization?
/Mathias
In article <························@s34g2000cwa.googlegroups.com>,
"Mathias Dahl" <············@gmail.com> wrote:
> I am currently reading SICP
> (http://mitpress.mit.edu/sicp/full-text/book/book.html, up to now a
> very nice read for a newbie like me) and I have just reached chapter
> 1.2.1 - Linear Recursion and Iteration. This passage was particulary
> interesting (sorry for the large quote):
>
> "One reason that the distinction between process and procedure may be
> confusing is that most implementations of common languages (including
> Ada, Pascal, and C) are designed in such a way that the interpretation
> of any recursive procedure consumes an amount of memory that grows with
> the number of procedure calls, even when the process described is, in
> principle, iterative. As a consequence, these languages can describe
> iterative processes only by resorting to special-purpose ``looping
> constructs'' such as do, repeat, until, for, and while. The
> implementation of Scheme we shall consider in chapter 5 does not share
> this defect. It will execute an iterative process in constant space,
> even if the iterative process is described by a recursive procedure. An
> implementation with this property is called tail-recursive. With a
> tail-recursive implementation, iteration can be expressed using the
> ordinary procedure call mechanism, so that special iteration constructs
> are useful only as syntactic sugar."
>
> Above Scheme is mentioned, but how is it with Common Lisp? Does it also
> do this optimization?
>
> /Mathias
In the ANSI Common Lisp standard tail-call-elimination is not mentioned
and not required. It is non-standard.
Several Common Lisp implementations are providing such optimizations.
Somehow. Often with limitations. Often only at certain optimization
levels.
See:
LispWorks:
http://www.lispworks.com/documentation/lw50/LWUG/html/lwuser-98.htm#pgfId
-889221
Franz:
http://www.franz.com/support/documentation/8.0/doc/compiling.htm#tail-mer
ge-disc-2
SBCL:
http://www.sbcl.org/manual/Debug-Tail-Recursion.html
"Mathias Dahl" <············@gmail.com> writes:
> I am currently reading SICP
> (http://mitpress.mit.edu/sicp/full-text/book/book.html, up to now a
> very nice read for a newbie like me) and I have just reached chapter
> 1.2.1 - Linear Recursion and Iteration.
> It will execute an iterative process in constant space,
> even if the iterative process is described by a recursive procedure. An
> implementation with this property is called tail-recursive. With a
> tail-recursive implementation, iteration can be expressed using the
> ordinary procedure call mechanism, so that special iteration constructs
> are useful only as syntactic sugar."
I think it is worth pondering the role of history. See
http://lambda-the-ultimate.org/node/1331#comment-15125
The language we use captures our historical path to our
current understanding. Given the accidental nature of that
path one needs to be wary of the assumptions implicit in our
language.
Alan Crowe
Edinburgh
Scotland
In <························@s34g2000cwa.googlegroups.com> Mathias >
Above Scheme is mentioned, but how is it with Common Lisp? Does it
> also do this optimization?
>
Fear not. The mature Common Lisps do.