[Axiom-developer] Re: Tail recursion (was: Lexicographic order)

[Jens Axel Søgaard]

Page, Bill wrote:

> I think the example at:
>
> http://www.axiom-developer.org/zope/mathaction/SandBoxTailRecursion
>
> shows that something more subtle is happening here than just
> tail-recursion elimination (or not).
>
> For one thing, the call to summa(1000000) did not fail with a
> "Invocation history stack overflow" as Jens predicted above
> but summa2(1000000,0) did fail.
>
> The definition::
>
>   summa(n) ==
>     if n=0
>     then 0
>     else n + summa(n-1)
>
> is apparently treated specially by Axiom as a "recurrence
> relation" and so does not produce a stack overflow.

Ok - I choose a bad example.

> Now let's see what happens if we tell Axiom to compile the
> function (see web page above):
>
> \begin{axiom}
> )set functions compile on
> \end{axiom}
>
> \begin{axiom}
>   -- a stands for accumulator
>   summa3(n, a) ==
>     if n=0
>     then a
>     else summa3(n-1, n+a)
> \end{axiom}
>
> \begin{axiom}
> summa3(1000000,0)
> \end{axiom}
>
> Now this function returns a correct value without the stack
> overflow. And similarly
>
> \begin{axiom}
> loop : INT -> INT
> loop (n) == loop (n)
> \end{axiom}
>
> if called here with 'loop(1)' becomes an infinite loop.
>
> So it seems that perhaps the tail recursion elimination only
> works when the function is compiled unless it is recognized as
> special case of a recurrence relation.

It does seem to work in cases, where the tail recursive call is
to the function itself.

I tried another tail recursive loop in the Octorber 2004 version:

)set functions compile on
foo : INT -> INT
bar : INT -> INT
foo (n) == bar (n)
bar (n) == foo (n)
foo (1)

and got a

  >> System error:
  Value stack overflow.

However, I am not sure the above is the correct way to define
two mutually recursive functions.

> The message "Invocation history stack overflow" is actually generated
> by gcl (gcl 2.6.6 is the lisp compiler used to build Axiom on MathAction).
> Although the examples above seem to suggest that tail recursion
> elimination is working as expected in the case where the Axiom interpreter
> functions are compiled, a search of the web returned the following hits
> which suggest that some previous versions of gcl may have had some problems
> with tail recursion:
>
> - https://savannah.gnu.org/task/?func=detailitem&item_id=788
>
> - http://lists.gnu.org/archive/html/gcl-devel/2002-03/msg00032.html
>
> - http://www.mail-archive.com/address@hidden/msg00287.html
>
> So maybe there is still a problem lurking out there?

That depends on the Axiom interpreter/compiler. Since Common Lisp
doesn't guarantee proper tail recursion, it isn't an error that
tail recursive code can run out of stack space in GCL. Some
Common Lisp compilers make an effort to optimize som tail recursive
calls, but it is usually unsafe to rely on it.

The code from SICP (which uses Scheme) that Maguire is trying is
thus not supposed to work an all Common Lisp implementations.

--
Jens Axel Søgaard