[Axiom-developer] RE: Tail recursion

[Page, Bill]

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.

---------

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.

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"?

Thanks for your comments.

Regards,
Bill Page.