Is there an article somewhere that compares the support for tail-call
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
Dave Benjamin <·····@lackingtalent.com> writes:
> Is there an article somewhere that compares the support for tail-call
> 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.
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 ·····@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
On 2006-08-25 15:05:27 -0400, Dave Benjamin <·····@lackingtalent.com> said:
> 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>
Dave Benjamin wrote:
> Is there an article somewhere that compares the support for tail-call
> 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.
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/
Dave Benjamin wrote:
> Is there an article somewhere that compares the support for tail-call
> 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.
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
On Sun, 27 Aug 2006, ···················@gmail.com wrote:
> 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
In article <·······················@h48g2000cwc.googlegroups.com>,
Rob Thorpe <·············@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>
On a related note, I had a question that I always wonder about:
Is it possible, even in theory, to convert a NON-tail recursive
procedure to an iterative process?
sanket.
From: Thomas A. Russ
Subject: Re: CL implementations and tail-call optimization
Date:
Message-ID: <ymiiri0ayxu.fsf@sevak.isi.edu>
··········@gmail.com writes:
> On a related note, I had a question that I always wonder about:
>
> Is it possible, even in theory, to convert a NON-tail recursive
> procedure to an iterative process?
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
Thomas A. Russ <···@sevak.isi.edu> wrote:
+---------------
| ··········@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 <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Thomas A. Russ
Subject: Re: CL implementations and tail-call optimization
Date:
Message-ID: <ymiwt68a5r7.fsf@sevak.isi.edu>
····@rpw3.org (Rob Warnock) writes:
> Thomas A. Russ <···@sevak.isi.edu> wrote:
> +---------------
> | ··········@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.
--
Thomas A. Russ, USC/Information Sciences Institute
···@sevak.isi.edu (Thomas A. Russ) writes:
> ····@rpw3.org (Rob Warnock) writes:
>
>> Thomas A. Russ <···@sevak.isi.edu> wrote:
>> +---------------
>> | ··········@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.
Of course, all functions are recursive. That's why we have lambda calculus.
--
__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
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: CL implementations and tail-call optimization
Date:
Message-ID: <87slh4eei2.fsf@qrnik.zagroda>
··········@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.
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
From: Bill Atkins
Subject: Re: CL implementations and tail-call optimization
Date:
Message-ID: <m2ac3c4kc3.fsf@bertrand.local>
Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:
> ··········@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.
Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:
> ··········@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.
Pascal Bourguignon wrote:
> Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:
>
> > ··········@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.
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: CL implementations and tail-call optimization
Date:
Message-ID: <87odrsqotw.fsf@qrnik.zagroda>
Pascal Bourguignon <···@informatimago.com> writes:
> 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.
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
··········@gmail.com writes:
> On a related note, I had a question that I always wonder about:
>
> Is it possible, even in theory, to convert a NON-tail recursive
> procedure to an iterative process?
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