Re: [Axiom-developer] Re: [Axiom-mail] [Axiom-mail] Lexicographic order

[Jens Axel Søgaard]

Martin Rubey wrote:
>  > I tried the following and ran out of stack space:
>  > 
>  > loop : INT -> INT
>  > 
>  > loop (n) == loop (n)
>  > 
>  > loop (1)
>  > 
>  >    >> System error:
>  >    Invocation history stack overflow.
>
> 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?

Hi Martin,

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.


If tail recursion is supported, the above will result in an infinite
loop.

A loose definition of a tail call is: If in the body of f, a call
to g is made in a position, where the result of the call, is to
be returned by f, then the call to g is a /tail call/.

In

 summa(n) ==
   if n=0
   then 0
   else n + summa(n-1)

> summa(10)
55

the call to summa is not a tail cail, since the result of calling
summa(n-1) needs to be added to n before a value can be returned.

On the other hand in:

 -- a stands for accumulator
 summa2(n, a) ==
   if n=0
   then a
   else summa2(n-1, n+a)

> summa(10,0)
55

the result of calling summa2(n-1,n+a) is returned immediately
as the result of summa2(n,a) and is thus a tail call.


A call is /active/ if the function called hasn't returned yet.

Proper[1] tail recursion is supported, if an unbounded number
of active tail calls only use a bounded amount of stack space.

In Scheme a call summa(10000) would cause a stack overflow, just
as in Axiom, but a call summa2(10000,0) would work withput any
problems. However, in some Scheme implementations one can
turn the stack history on and off - so perhaps there is
magic switch somewhere?

See 
<http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-6.html#%_sec_3.5>
for a more formal definition.



[1] Here "Proper Tail Recursion" is a technical term, and doesn't
    mean "tail recursion done right".

--
Jens Axel Søgaard