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

[Camm Maguire]

Greetings!

Jens Axel Søgaard <address@hidden> writes:

> 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.

Just wanted to confirm the basic gist of this thread -- GCL will
implement tail recursion when:

1) the call is to the function itself
2) the function is compiled
3) the argument list and return types are known and not variable
   (i.e. proclaimed)
4) one is not running in degugging mode (si::use-fast-links nil)

One thing I'd like to do is to extend this to optional arguments, and
perhaps multiple value returns.  

As far as mutual recursion goes, this cannot be done in C without
special non-standard support from the C compiler.  Thankfully, GCL
prvides this.  I have a patch, not yet committed, which gets mutual
tail recursion elimination when

1) the above is satisfied
2) the two calls are in the same file
3) the two functions have exactly the same argument and return types.

As for the old example from SICP, it is true that lisp is not required
to eliminate this, but that's not really relevenat for GCL as we do
want to do tail recursion where possible.  On looking at it again, I
don't see why it is tail recursive at all, even if one grants mutual
tail recursion.  I'm probably just overlooking something. 

> 
> > 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
> 
> 
> 
> 
> _______________________________________________
> Axiom-developer mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/axiom-developer
> 
> 
> 

-- 
Camm Maguire                                            address@hidden
==========================================================================
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah