Edit detail for SandBox Tail Recursion revision 2 of 2

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.

Actually, when using sbcl this is an infinite loop.

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

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

summa(10)

Compiling function summa with type Integer -> Integer

Compiling function summa as a recurrence relation.

(1)

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)

summa2(10,0)

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

(2)

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, however FriCAS recognizes that summa has special form and compile it to iteration

summa(1000000)

(3)

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

summa2(1000000,0)

(4)

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

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.

The definition:

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

is apparently treated specially by FriCAS as a "recurrence relation" and so does not produce a stack overflow.

Similarly a stack overflow may occur in this simpler case:

loop : INT -> INT loop (n) == loop (n) loop (1)

but result depends on underlying Lisp. When using sbcl default is to optimize tail call, but different setting or using different Lisp can lead to stack overflow.

Let's see what happens if we tell FriCAS to interpret the function:

)set functions compile off

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

summa3(1000000,0)

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

   >> System error:
   Control stack exhausted (no more space for function call frames).
This is probably due to heavily nested or infinitely recursive function
calls, or a tail call that SBCL cannot or has not optimized away.

PROCEED WITH CAUTION.

Now this function leads to stack overflow. And similarly

loop : INT -> INT

loop (n) == loop (n)

would give stack overflow.

So tail recursion elimination only works when the function is compiled unless it is recognized as special case of a recurrence relation.

The message about stack overflow is actually generated by Lisp implementation. gcl (used on MathAction in the past) printed "Invocation history stack overflow", sbcl (currently used) prints "Control stack exhausted". Although the examples above seem to suggest that tail recursion elimination is working as expected in the case where the FriCAS 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
• 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?

Jens Axel Søgaard wrote:

That depends on the FriCAS 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.

Let's try a slightly more complicated mutual recursion:

)set functions compile on

foo (n) == if n>0 then bar (n-1)+1 else 0

bar (n) == if n>0 then foo (n-1)+1 else 0

foo (1)

Compiling function foo with type Integer -> NonNegativeInteger

Compiling function bar with type Integer -> NonNegativeInteger

Compiling function foo with type PositiveInteger -> 
      NonNegativeInteger

(5)

foo (100)

(6)

foo (1000000)

   >> System error:
   Control stack exhausted (no more space for function call frames).
This is probably due to heavily nested or infinitely recursive function
calls, or a tail call that SBCL cannot or has not optimized away.

PROCEED WITH CAUTION.

Here is the error message which as you suggest implies that FriCAS/sbcl did not recognize this as a case where tail recursion can be eliminated.

But sbcl recognized "proper" case:

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

foo2(1,0)

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

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

(7)

foo2(100,0)

(8)

foo2(10000,0)

(9)

foo2(1000000,0)

(10)