What declarations do I need to make in Allegro CL to ensure that the
compiler optimizes the tail-calls in a tail-recursive function?
Some details:
I've defined the following:
(defun tr-fact (n &optional (acc 1))
(if (zerop n) (break "reached 0")
(tr-fact (1- n) (* n acc))))
The debugger seems to indicate that the recursive calls are not being
merged -- running (tr-fact 5) gives the following backtrace in the
debugger:
Backtrace:
0: (SWANK::DEBUG-IN-EMACS #<EXCL:SIMPLE-BREAK @ #x20f9c152>)
1: (SWANK:SWANK-DEBUGGER-HOOK #<EXCL:SIMPLE-BREAK @ #x20f9c152>
#<Function SWANK-DEBUGGER-HOOK>)
2: (BREAK "reached 0")
3: (TR-FACT 1 120)
4: (TR-FACT 2 60)
5: (TR-FACT 3 20)
6: (TR-FACT 4 5)
7: (TR-FACT 5 1)
8: (TR-FACT 5)
9: (EVAL (TR-FACT 5))
On Apr 6, 4:48 am, Adlai <·········@gmail.com> wrote:
> What declarations do I need to make in Allegro CL to ensure that the
> compiler optimizes the tail-calls in a tail-recursive function?
>
See
http://www.franz.com/support/documentation/8.1/doc/compiling.htm#tail-merge-disc-2
Karsten
On Apr 5, 4:48 pm, Adlai <·········@gmail.com> wrote:
> What declarations do I need to make in Allegro CL to ensure that the
> compiler optimizes the tail-calls in a tail-recursive function?
>
> Some details:
>
> I've defined the following:
> (defun tr-fact (n &optional (acc 1))
> (if (zerop n) (break "reached 0")
> (tr-fact (1- n) (* n acc))))
>
> The debugger seems to indicate that the recursive calls are not being
> merged -- running (tr-fact 5) gives the following backtrace in the
> debugger:
>
> Backtrace:
> 0: (SWANK::DEBUG-IN-EMACS #<EXCL:SIMPLE-BREAK @ #x20f9c152>)
> 1: (SWANK:SWANK-DEBUGGER-HOOK #<EXCL:SIMPLE-BREAK @ #x20f9c152>
> #<Function SWANK-DEBUGGER-HOOK>)
> 2: (BREAK "reached 0")
> 3: (TR-FACT 1 120)
> 4: (TR-FACT 2 60)
> 5: (TR-FACT 3 20)
> 6: (TR-FACT 4 5)
> 7: (TR-FACT 5 1)
> 8: (TR-FACT 5)
> 9: (EVAL (TR-FACT 5))
Paul Graham says in _On Lisp_ (pg. 23) that (proclaim '(optimize
speed)) should do the trick. It seems to be enabled by default with
SBCL and Clozure.
Aloha,
David Sletten
On Apr 6, 4:03 am, David Sletten <·····@bosatsu.net> wrote:
> On Apr 5, 4:48 pm, Adlai <·········@gmail.com> wrote:
>
>
>
>
>
> > What declarations do I need to make in Allegro CL to ensure that the
> > compiler optimizes the tail-calls in a tail-recursive function?
>
> > Some details:
>
> > I've defined the following:
> > (defun tr-fact (n &optional (acc 1))
> > (if (zerop n) (break "reached 0")
> > (tr-fact (1- n) (* n acc))))
>
> > The debugger seems to indicate that the recursive calls are not being
> > merged -- running (tr-fact 5) gives the following backtrace in the
> > debugger:
>
> > Backtrace:
> > 0: (SWANK::DEBUG-IN-EMACS #<EXCL:SIMPLE-BREAK @ #x20f9c152>)
> > 1: (SWANK:SWANK-DEBUGGER-HOOK #<EXCL:SIMPLE-BREAK @ #x20f9c152>
> > #<Function SWANK-DEBUGGER-HOOK>)
> > 2: (BREAK "reached 0")
> > 3: (TR-FACT 1 120)
> > 4: (TR-FACT 2 60)
> > 5: (TR-FACT 3 20)
> > 6: (TR-FACT 4 5)
> > 7: (TR-FACT 5 1)
> > 8: (TR-FACT 5)
> > 9: (EVAL (TR-FACT 5))
>
> Paul Graham says in _On Lisp_ (pg. 23) that (proclaim '(optimize
> speed)) should do the trick. It seems to be enabled by default with
> SBCL and Clozure.
>
> Aloha,
> David Sletten
There's already a link to Franz's docs which is of course definitive
for that implementation. In other implementations, be aware that TCO
may not be enabled if debug settings are high because it is the very
nature of TCO that it can eliminate stack frames (i.e., TCO can re-
uses stack frames rather than growing the stack). When one is
debugging, one often wants to be able to see stack backtraces, so when
one does (optimize ... (debug 3)... one may not get TCO.
Again, each implementation's docs are the last word on how to achieve
this. For example, Lispworks won't do TCO if (optimize (debug 3) is in
effect (among other things):
<http://www.lispworks.com/documentation/lw51/LWUG/html/lwuser-111.htm>