Recursion

[A.M. Kuchling]

On Mon, 1 Jan 2001 16:31:42 -0500, Tim Peters <tim.one at home.com> wrote:
>> In Ruby, you can input a value as high as 763 before you get a
>> SystemStackError (stack level too deep) error.
>
>The recursion limit in Python varies across platforms; I assume that's true
>in Ruby too; in Python you can use sys.setrecursionlimit() to fiddle it (but
>if you set it "too high", you risk having the interpreter blow up due to C
>stack corruption).

The value of 763 is interesting; since it's not a magic constant that
a human would have chosen, that means Ruby must be detecting when the
stack is near overflow.  This might be worth borrowing for Python, so
I decided to take a look.

Digging into ruby-1.6.1, the code that trips the error is this:

    if ((++tick & 0xff) == 0) {
        CHECK_INTS;             /* better than nothing */
        if (stack_length() > STACK_LEVEL_MAX) {
            rb_raise(rb_eSysStackError, "stack level too deep");
        }
    }

Very similar to the corresponding bit of ceval.c.  STACK_LEVEL_MAX is
either a constant or a value obtained from getrlimit().  

stack_length(), then, is the last piece:

extern VALUE *rb_gc_stack_start;
static int
stack_length()
{
    VALUE pos;

#ifdef sparc
    return rb_gc_stack_start - &pos + 0x80;
#else
    return (&pos < rb_gc_stack_start) ? rb_gc_stack_start - &pos
	                              : &pos - rb_gc_stack_start;
#endif
}

Ignore the "#ifdef sparc" branch, and it's quite
simple. rb_gc_stack_start is determined by doing {VALUE start;
rb_gc_stack_start = &start;} during program initialization. 

Is this approach worth pursuing for Python?  This probably depends on
nonportable behaviour not guaranteed by ANSI C (the stack pointer is
continuously incremented/decremented, and not segmented or something
weird), but for most practical platforms these assumptions probably
hold.

--amk