Re: [Axiom-developer] RE: Tail recursion

[Camm Maguire]

Greetings!

"Page, Bill" <address@hidden> writes:

> On Tuesday, August 30, 2005 7:59 PM Jens Axel Søgaard wrote:
> 
> > ... 
> > 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.
> > 
> 
> I think that what you are writing is correct. With Axiom from the
> most recent Patch-44 which used gcl-2.6.6 I tried:
> 
> (3) -> )set functions compile on
> (3) -> foo : INT -> INT
>                                Type: Void
> (4) -> bar : INT -> INT
>                                Type: Void
> (5) -> foo (n) == bar (n)
>                                Type: Void
> (6) -> bar (n) == foo (n)
>                                Type: Void
> (7) -> foo (1)
>    Compiling function bar with type Integer -> Integer
> 
> ---------
> 
> This behaviour is odd. It should have returned either a result
> or an error message. So I repeat the command.
> 
> (7) -> foo (1)
> 
>    >> System error:
>    The function |*1;foo;1;initial| is undefined.
> 
> ---------
> 

Don't know what to say about this offhand.

But I do recommend that the )set functions compile on feature
automatically proclaim the function signature before compiling, i.e.
running the following in this case:

(proclaim '(ftype (function (t) t) foo))
(proclaim '(ftype (function (t) t) bar))
 
or even 

(proclaim '(ftype (function (integer) integer) foo))
(proclaim '(ftype (function (integer) integer) bar))


> This time I get an error message but not the one I expected.
> I don't know what this message means. (Axiom is busted ... )
> 
> Let's try a slightly more complicated mutual recursion:
> 
> (7) -> foo (n) == if n>0 then bar (n-1)+1 else 0
>    Compiled code for foo has been cleared.
>    Compiled code for bar has been cleared.
>    1 old definition(s) deleted for function or rule foo
>                                     Type: Void
> (8) -> bar (n) == if n>0 then foo (n-1)+1 else 0
>    1 old definition(s) deleted for function or rule bar
>                                     Type: Void
> (9) -> foo (1)
>    Compiling function bar with type Integer -> Integer
>    Compiling function foo with type Integer -> Integer
> 
>    (9)  1
>                                     Type: PositiveInteger
> (10) -> foo (100)
> 
>    (10)  100
>                                     Type: PositiveInteger
> (11) -> foo (1000000)
> 
>    >> System error:
>    Value stack overflow.
> 
> Here is the error message which as you suggest implies that
> Axiom/GCL did not recognize this as a case where tail recursion
> can be eliminated.

Yes, currently we do not eliminate mutual tail recursive calls -- we
can only do this with special support from the C compiler such as
gcc.  When we do implement eventually, somehow axiom would have to
group these two functions into the same C file or otherwise instruct
GCL to do so, as this is a requirement of the GCC mutual tail
recursion elimination support.


> 
> Even this "proper" case is apparently not recognized:
> 
> (12) -> bar2 (n,a) == if n>0 then foo2 (n-1,n+a) else a
>                                     Type: Void
> (13) -> foo2 (n,a) == if n>0 then bar2 (n-1,n+a) else a
>                                     Type: Void
>  (14) -> foo2(1,0)
>    Compiling function bar2 with type (Integer,Integer) -> Integer
>    Compiling function foo2 with type (Integer,Integer) -> Integer
> 
>    (14)  1
>                               Type: PositiveInteger
> (15) -> foo2(100,0)
> 
>    (15)  5050
>                               Type: PositiveInteger
> (16) -> foo2(10000,0)
> 
>    (16)  50005000
>                               Type: PositiveInteger
> (17) -> foo2(1000000,0)
> 
>    >> System error:
>    Value stack overflow.
> 
> --------
> 
> So I think your caution about tail recursion elimination not being
> guaranteed is well taken.
> 
> I wonder when should expect a "Value stack overflow" instead of
> an "Invocation history stack overflow"?

If the calls pass arguments and return types via the list stack, such
as is the case when the functions are not proclaimed, or when running
in debugging mode, or (at present) when the function returns mutiple
values for example, one fills up the value stack as well as the
invocation history stack and it is undetermined which will fill first.
If all argument passing is done via the C stack, such as is the case
for proclaimed functions of simple argument and return types which are
compiled and debugging is off, then one will  either overrun the C
stack with a segfault or proceed forevever depending on whether GCL
has eliminated the recursion.  One can see explicitly what is going on
by examining the compiler notes.  I think Tim may be patching the GCL
source to eliminate these completely, but in 2.6.7 and later, there is
a simple switch:

compiler::*suppress-compiler-notes*

which can be set to achieve the same thing and give the user the
option to see them if needed.  Defaults to nil on 2.6.7 and t in 2.7.0
and higher.

Take care,


> 
> Thanks for your comments.
> 
> Regards,
> Bill Page.
> 
> 
> 
> _______________________________________________
> 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