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

[Page, Bill]

On Tuesday, August 30, 2005 3:44 PM Jens Axel Søgaard wrote: 

> >  >
> >  > loop : INT -> INT
> >  >
> >  > loop (n) == loop (n)
> >  >
> >  > loop (1)
> >  >
> >  >    >> System error:
> >  >    Invocation history stack overflow.
> >

> Martin Rubey wrote:
> > Although this is not a nice way for Axiom to fail, two questions:
> >
> > * is this an instance of tail-recursion?
> >
> > * what result would you expect?
> 
> Yes - if tail recursion were supported, then the above would be
> an infinite loop. I haven't got any complaints over the wording
> of the error message.
> 

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.

Similarly a stack overflow does occur in this simpler case:
\begin{axiom}
loop : INT -> INT
loop (n) == loop (n)
\end{axiom}

\begin{axiom}
loop (1)
\end{axiom}

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.

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?

Regards,
Bill Page.