help links subscribe changes refresh edit

	SandBox
SandBox Statistics ←	↑	→ SandBox Text Files

SandBox Tail Recursion

Edit detail for SandBox Tail Recursion revision 1 of 2

	1 2
Editor: Time: 2007/11/18 18:43:03 GMT-8
Note:

changed:
-
On Tuesday, August 30, 2005 3:44 PM <b>Jens Axel Søgaard</b> 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.

**Martin Rubey** asked::

 > Although this is not a nice way for Axiom to fail, two questions:
 > 
 > * is this an instance of tail-recursion?
 > 

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.

::

 > * what result would you expect?

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
\begin{axiom}
  summa(n) ==
    if n=0
    then 0
    else n + summa(n-1)
\end{axiom}

\begin{axiom}
summa(10)
\end{axiom}

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:

\begin{axiom}
  -- a stands for accumulator
  summa2(n, a) ==
    if n=0
    then a
    else summa2(n-1, n+a)
\end{axiom}

\begin{axiom}
summa2(10,0)
\end{axiom}

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(1000000) would cause a stack overflow, just
as in Axiom,
\begin{axiom}
summa(1000000)
\end{axiom}

but a call summa2(1000000,0) would work without any problems.
\begin{axiom}
summa2(1000000,0)
\end{axiom}

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

<hr />
**Bill Page** wrote:

I think the evidence above suggests 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 occurs in this simpler case:
\begin{axiom}
loop : INT -> INT
loop (n) == loop (n)
\end{axiom}

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

Let's see what happens if we tell Axiom to compile the function:

\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/gcl-devel@gnu.org/msg00287.html":http://www.mail-archive.com/gcl-devel@gnu.org/msg00287.html

So maybe there is still a problem lurking out there?

<b>Jens Axel Søgaard</b> wrote:

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.

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.

**Bill Page** wrote:

I think that what you are writing is correct. With Axiom from the
most recent Patch-44 (as here on MathAction) which used gcl-2.6.6
I tried:

\begin{axiom}
)set functions compile on
foo : INT -> INT
bar : INT -> INT
foo (n) == bar (n)
bar (n) == foo (n)
\end{axiom}

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

---------

Expanding the compiler output above you can see that MathAction
gets the same result as you said.

But when I tried this in a separate console session in Axiom
using exactly the same version of Axiom on the same machine as
MathAction, Axiom returned just::

   Compiling function bar with type Integer -> Integer

with no other output.

That behaviour is odd. It should have returned either a result
or an error message. So I repeated the command.

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

and got::

   >> 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:
\begin{axiom}
foo (n) == if n>0 then bar (n-1)+1 else 0
bar (n) == if n>0 then foo (n-1)+1 else 0
\end{axiom}

\begin{axiom}
foo (1)
foo (100)
\end{axiom}

\begin{axiom}
foo (1000000)
\end{axiom}

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:
\begin{axiom}
bar2 (n,a) == if n>0 then foo2 (n-1,n+a) else a
foo2 (n,a) == if n>0 then bar2 (n-1,n+a) else a
\end{axiom}

\begin{axiom}
foo2(1,0)
foo2(100,0)
foo2(10000,0)
\end{axiom}

\begin{axiom}
foo2(1000000,0)
\end{axiom}

--------

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.

On Tuesday, August 30, 2005 3:44 PM Jens Axel Søgaard 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.

Martin Rubey asked:

 > Although this is not a nice way for Axiom to fail, two questions:
 > 
 > * is this an instance of tail-recursion?
 >

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.

 > * what result would you expect?

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.

fricas

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

Type: Void

fricas

summa(10)

fricas

Compiling function summa with type Integer -> Integer

fricas

Compiling function summa as a recurrence relation.

$\label{eq1}55$

(1)

Type: PositiveInteger?

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:

fricas

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

Type: Void

fricas

summa2(10,0)

fricas

Compiling function summa2 with type (Integer,Integer) -> Integer

$\label{eq2}55$

(2)

Type: PositiveInteger?

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(1000000) would cause a stack overflow, just as in Axiom,

fricas

summa(1000000)

$\label{eq3}500000500000$

(3)

Type: PositiveInteger?

but a call summa2(1000000,0) would work without any problems.

fricas

summa2(1000000,0)

$\label{eq4}500000500000$

(4)

Type: PositiveInteger?

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

Bill Page wrote:

I think the evidence above suggests 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 occurs in this simpler case:

fricas

loop : INT -> INT

Type: Void

fricas

loop (n) == loop (n)

Type: Void

Axiom output parse error!

Let's see what happens if we tell Axiom to compile the function:

Axiom output parse error!

Now this function returns a correct value without the stack overflow. And similarly

Axiom output parse error!

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:

So maybe there is still a problem lurking out there?

Jens Axel Søgaard wrote:

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.

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.

Bill Page wrote:

I think that what you are writing is correct. With Axiom from the most recent Patch-44 (as here on MathAction?) which used gcl-2.6.6 I tried:

Axiom output parse error!

---------

Expanding the compiler output above you can see that MathAction? gets the same result as you said.

But when I tried this in a separate console session in Axiom using exactly the same version of Axiom on the same machine as MathAction?, Axiom returned just:

   Compiling function bar with type Integer -> Integer

with no other output.

That behaviour is odd. It should have returned either a result or an error message. So I repeated the command.

Axiom output parse error!

and got:

   >> 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: Axiom output parse error!

Axiom output parse error!

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: Axiom output parse error!

Axiom output parse error!

--------

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.