CL implementations and tail-call optimization
Dave Benjamin
optimization across various Common Lisp implementations? I'd like to know
which implementation(s) I should be focusing on if I need support for TCO,
as well as what specific directives or debugging/optimization settings are
necessary to enable it.
Thanks,
Dave
Duane Rettig
I don't know any general discussions, but for Allegro CL, for
starters, look at:
http://www.franz.com/support/documentation/8.0/doc/compiling.htm#tail-merge-disc-2
and be sure to also follow the links. Also, for debugging why a tail
call is not merged in any particular circumstance, check out:
http://www.franz.com/support/documentation/8.0/doc/compiler-explanations.htm#tailmerging-explain-2
and follow the links from there, as well.
--
Duane Rettig du...@franz.com 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
Pascal Costanza
All major implementations support this. You have to check their
documentation. It's sometimes hard to find in the respective
documentation, but it's typically enabled by declaiming the correct
optimization settings, i.e., the possible values for (declaim (optimize
(speed ...) (debug ...))), and so on. As a final resort, ask in the
respective mailing lists.
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/
Raffael Cavallaro
> I'd like to know which implementation(s) I should be focusing on if I
> need support for TCO, as well as what specific directives or
> debugging/optimization settings are necessary to enable it.
LispWorks for Macintosh, Windows, FreeBSD, Linux:
<http://www.lispworks.com/documentation/lw50/LWUG/html/lwuser-98.htm#pgfId-889221>
david.tol...@gmail.com
Dave,
if you need support for TCO in the sense that your algorithms rely on
tail call elimination than Common Lisp is not the best choice. All
major implementations support tail call optimization, but none
guarantees that it will work when you need it, and commercial ones are
not necessarilly better in this respect. I routinely face the need to
unroll tail-calls manually because either Lispworks or Allegro Common
Lisp fail to eliminate them, either due to bugs or due to limitations
of the implementation.
Common Lisp, unlike many languages with functional bias, does not
require tail call elimination; and implementations sacrificies this
optimization in favour of others, limiting cases when it is applied. In
many cases, the limitations are stronger in compilers that generate
faster code in general.
David
Dave Benjamin
> if you need support for TCO in the sense that your algorithms rely on
> tail call elimination than Common Lisp is not the best choice. All major
> implementations support tail call optimization, but none guarantees that
> it will work when you need it, and commercial ones are not necessarilly
> better in this respect. I routinely face the need to unroll tail-calls
> manually because either Lispworks or Allegro Common Lisp fail to
> eliminate them, either due to bugs or due to limitations of the
> implementation.
Thanks for your honest feedback. I'm willing to rewrite algorithms so that
they do not require tail call optimization, though I'd like to minimize
the need to do so if possible. That is what motivated my question; I
haven't committed to a particular CL implementation yet, and it'd be nice
to see a comparison so that I could pick one that supports TCO the most
(or at least, in most of the cases that I'd need it for). Unfortunately,
it seems like this information is spread out in various manuals and, as
you indicate, some of it must be uncovered through trial and error.
What were the most common issues with Lispworks or ACL that caused you to
modify your code? Did the introduction of an accumulator help in any of
these cases?
> Common Lisp, unlike many languages with functional bias, does not
> require tail call elimination; and implementations sacrificies this
> optimization in favour of others, limiting cases when it is applied. In
> many cases, the limitations are stronger in compilers that generate
> faster code in general.
So, I guess I should focus on the slower implementations, then. =)
I notice that the clisp FAQ says "You will always get a stack overflow on
infinite recursion.". Am I right in interpreting this to mean that clisp
doesn't do TCO at all?
Thanks, everyone, for your helpful responses.
Dave
david.tol...@gmail.com
> What were the most common issues with Lispworks or ACL that caused you to
> modify your code? Did the introduction of an accumulator help in any of
> these cases?
Hi,
Lispworks has a limitation on the number of function arguments for
tail-call eliminations. No more than four or five, if I remember
correctly. Besides, if there is a nested (labels ) around the tail
call, the tail call is not optimized into a loop. Allegro Common Lisp
has bugs in their implementation of TCE, they've got a ticket with a
test in their bug tracker -- I had to rewrite the function as a loop as
they didn't seem to be able to find a way to fix it. Or desire.
At the same time, both CMU CL and OpenMCL optimized all of my
tail-recursive (I used to overuse tail calls in Common Lisp) code
properly (that is, in a way I'd expect a Scheme or Haskell compiler
to). Unfortunately, OpenMCL is significantly slower than the two
commercial ones, and CMUCL lacks weak references (that is, working
ones).
David
Rob Thorpe
I've looked at all of the implementations on my machine. All of Sbcl,
Ecl , Clisp and Gcl have TCO in their compilers. The normal
interpreters of Ecl, Gcl and Clisp don't have it (and Sbcl doesn't have
an interpreter). By looking in the manual it seems Cmucl has it too.
So, fairly much all free lisps have it to some degree so long as you
stick to compiled code. There are probably some functions where it
will break, you'll have to do tests.
Camm Maguire
Just a note, the cvs experimental version of GCL has support for some
mutual recursion tail call elimination. Right now we restrict to
functions defined in the same original file and interned in the same
package.
Take care,
"Rob Thorpe" <robert...@antenova.com> writes:
--
Camm Maguire ca...@enhanced.com
==========================================================================
"The earth is but one country, and mankind its citizens." -- Baha'u'llah
Stephen Compall
> I notice that the clisp FAQ says "You will always get a stack overflow
> on infinite recursion.". Am I right in interpreting this to mean that
> clisp doesn't do TCO at all?
CLISP does TCO for self-recursion of at least functions created by
DEFUN and LABELS. No optimization declarations are necessary; CLISP
ignores all of them but SAFETY anyway. Unfortunately, it doesn't
currently optimize tail calls among separate functions defined in a
LABELS.
In general, you may wish to seek situations in which it is relatively
easy for the compiler to optimize tail calls. LABELS is very easy to
optimize without speed penalty, because inside the body of a function
bound by LABELS, any lexical reference to a function of that name
cannot possibly refer to a different function, unless of course there
is yet another lexical function binding of the name *within* said body.
For this reason I usually use a macro `rlet' that döppels Scheme's
named let syntax when I miss that syntax.
--
Stephen Compall
http://scompall.nocandysw.com/blog
Brian Downing
Rob Thorpe <robert...@antenova.com> wrote:
> I've looked at all of the implementations on my machine. All of Sbcl,
> Ecl , Clisp and Gcl have TCO in their compilers. The normal
> interpreters of Ecl, Gcl and Clisp don't have it (and Sbcl doesn't have
> an interpreter).
[Apologies for pulling this thread out of the deep.]
Just as a note, since 0.9.17 SBCL has had a full interpreter. It is not
enabled by default; to use it:
(setf sb-ext:*evaluator-mode* :interpret) ; :compile for default behavior
It is primarily intended for performance of run-once code and eventual
support of compilerless images. There is currently no debugger support
(you see the frames of the evaluator guts in the debugger), and in
general compiled code is a lot more developer-friendly.
Unlike CMUCL's interpreter SBCL's directly interprets the source code.
(CMUCL interprets the IR1 flow graph the compiler generates, IIRC.)
-bcd
--
*** Brian Downing <bdowning at lavos dot net>
sanky...@gmail.com
Is it possible, even in theory, to convert a NON-tail recursive
procedure to an iterative process?
sanket.
Marcin 'Qrczak' Kowalczyk
> Is it possible, even in theory, to convert a NON-tail recursive
> procedure to an iterative process?
What do you mean by iterative process? The call stack can be simulated
as an explicit data structure. But it doesn't let it use any less memory,
nor doesn't make it faster.
--
__("< Marcin Kowalczyk
\__/ qrc...@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Bill Atkins
> sanky...@gmail.com writes:
>
>> Is it possible, even in theory, to convert a NON-tail recursive
>> procedure to an iterative process?
>
> What do you mean by iterative process? The call stack can be simulated
> as an explicit data structure. But it doesn't let it use any less memory,
> nor doesn't make it faster.
The term is used in SICP; he might be referring to the definition used there.
Pascal Bourguignon
Using an explicit stack, yes.
(defstruct (tree (:copier nil)) label left right)
(defun walk-tree (tree prefix infix suffix leaf)
(if (tree-p tree)
(progn
(funcall prefix tree)
(walk-tree (tree-left tree) prefix infix suffix leaf)
(funcall infix tree)
(walk-tree (tree-right tree) prefix infix suffix leaf)
(funcall suffix tree))
(funcall leaf tree))
(values))
(walk-tree (make-tree :label '*
:left (make-tree :label '+ :left 3 :right 4)
:right 5)
(lambda (x) (princ "(") x)
(lambda (x) (princ (tree-label x)) x)
(lambda (x) (princ ")") x)
(lambda (x) (princ x) x))
prints: ((3+4)*5)
Here, we have two recursive calls that aren't tail calls. One could
be easily transformed into a tail call, but obviously, without
continuations you cannot have TWO tail calls. (And with
continuations, tail calls are not really tail calls either).
However:
(defun walk-tree (tree prefix infix suffix leaf)
(loop
:with towalk = (list (list :tree tree))
:while towalk
:do (let ((item (pop towalk)))
(case (first item)
((:tree) (if (tree-p (second item))
(progn
(push (list :proc suffix (second item)) towalk)
(push (list :tree (tree-right (second item))) towalk)
(push (list :proc infix (second item)) towalk)
(push (list :tree (tree-left (second item))) towalk)
(push (list :proc prefix (second item)) towalk))
(funcall leaf (second item))))
((:proc) (funcall (second item) (third item))))))
(values))
(walk-tree (make-tree :label '*
:left (make-tree :label '+ :left 3 :right 4)
:right 5)
(lambda (x) (princ "(") x)
(lambda (x) (princ (tree-label x)) x)
(lambda (x) (princ ")") x)
(lambda (x) (princ x) x))
prints: ((3+4)*5)
--
__Pascal Bourguignon__ http://www.informatimago.com/
Until real software engineering is developed, the next best practice
is to develop with a dynamic system that has extreme late binding in
all aspects. The first system to really do this in an important way
is Lisp. -- Alan Kay
Pascal Bourguignon
> sanky...@gmail.com writes:
>
>> Is it possible, even in theory, to convert a NON-tail recursive
>> procedure to an iterative process?
>
> What do you mean by iterative process? The call stack can be simulated
> as an explicit data structure. But it doesn't let it use any less memory,
> nor doesn't make it faster.
Perhaps, but the heap memory size might be much less constrained than
the system stack memory size (eg. in threads). So it might be useful
to convert a recursive function into an iteration+explicit stack,
sometimes.
--
__Pascal Bourguignon__ http://www.informatimago.com/
READ THIS BEFORE OPENING PACKAGE: According to certain suggested
versions of the Grand Unified Theory, the primary particles
constituting this product may decay to nothingness within the next
four hundred million years.
Rob Thorpe
> Marcin 'Qrczak' Kowalczyk <qrc...@knm.org.pl> writes:
>
> > sanky...@gmail.com writes:
> >
> >> Is it possible, even in theory, to convert a NON-tail recursive
> >> procedure to an iterative process?
> >
> > What do you mean by iterative process? The call stack can be simulated
> > as an explicit data structure. But it doesn't let it use any less memory,
> > nor doesn't make it faster.
>
> Perhaps, but the heap memory size might be much less constrained than
> the system stack memory size (eg. in threads). So it might be useful
> to convert a recursive function into an iteration+explicit stack,
> sometimes.
Yes. Once upon a time some compilers used to do this. The problem was
that on many platforms of the past the stack was often much smaller
than available memory. The heap though was less limited, so putting
stacks on the heap was sometimes useful.
Ways of doing recursive descent parsers with explicit stacks are
explained in older compiler textbooks.
Marcin 'Qrczak' Kowalczyk
> Perhaps, but the heap memory size might be much less constrained than
> the system stack memory size (eg. in threads). So it might be useful
> to convert a recursive function into an iteration+explicit stack,
> sometimes.
Ok, this depends on the language implementation. My compiler of my
language doesn't use the system stack, and the stack of each thread
is resized as needed.
Thomas A. Russ
Well, it depends.
Certainly for some functions, it is possible to convert them. I think,
but am not 100% sure, that you would have to be able to convert them
into tail recursive procedures in order to get a true iteration, but
there may be some exceptions. One simple example is the naive recursive
factorial function, which is not tail-recursive, but could be made so.
There are, however, certain functions that are fundamentally recursive
in nature (such as tree walks) which you can't convert into iterative
processes, simply because they are beyond the computational power of
non-recursive functions.
--
Thomas A. Russ, USC/Information Sciences Institute
Rob Warnock
+---------------
| sanky...@gmail.com writes:
| > Is it possible, even in theory, to convert a NON-tail recursive
| > procedure to an iterative process?
| There are, however, certain functions that are fundamentally recursive
| in nature (such as tree walks) which you can't convert into iterative
| processes, simply because they are beyond the computational power of
| non-recursive functions.
Not true. As Pascal showed in a parallel reply, tree-walks
can easily be converted to iteration using an explicit stack.
Such iteration+stack *is* the general solution: how else would
you write "recursive" functions on a CPU that didn't *have* a
recursive function call instruction?!? ;-} E.g., the DEC PDP-8
subroutine call was about as NON-recursive as you can get -- it
*stored* the return address *into* the first location of the
called routine! Yet people wrote Algol compilers [and other
languages with recursion] that ran just fine on a PDP-8.
-Rob
-----
Rob Warnock <rp...@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Thomas A. Russ
> Thomas A. Russ <t...@sevak.isi.edu> wrote:
> +---------------
> | sanky...@gmail.com writes:
> | > Is it possible, even in theory, to convert a NON-tail recursive
> | > procedure to an iterative process?
> ...
> | There are, however, certain functions that are fundamentally recursive
> | in nature (such as tree walks) which you can't convert into iterative
> | processes, simply because they are beyond the computational power of
> | non-recursive functions.
> +---------------
>
> Not true. As Pascal showed in a parallel reply, tree-walks
> can easily be converted to iteration using an explicit stack.
I don't consider functions that "hide" their recursion by managing their
own stack to be iterative functions. They are just a way of
implementing recursive functions.
Pascal Bourguignon
Of course, all functions are recursive. That's why we have lambda calculus.
--
__Pascal Bourguignon__ http://www.informatimago.com/