Re: [Chicken-users] Unbounded stack growth

[Felix]

From: Marc Feeley <address@hidden>
Subject: [Chicken-users] Unbounded stack growth
Date: Wed, 11 Jul 2012 13:23:30 -0400

> I have been experimenting with the Spock Scheme to JavaScript compiler.  I 
> encountered a bug in its implementation of the Cheney on the MTA approach to 
> tail-calls and continuations.  The bug also exists for Chicken.
> 
> In the Cheney on the MTA approach there needs to be a check, at regular 
> intervals, of the stack size, so that the stack can be GC'd using a 
> throw/catch or longjmp/setjmp.  Chicken (and Spock) perform this check at the 
> entry of Scheme functions.  For correctness, it must also be performed at the 
> *return point* of every non-tail call.  This is because the code has been CPS 
> converted, so a Scheme return is actually a C (or JS) *call* to the 
> continuation function, which grows the stack.

Yes, this is a known bug (see also
https://bugs.call-cc.org/ticket/876). For performance reasons, the
stack check is not done in continuation procedures.  As John has
pointed out, this usually only matters for code that would blow the
stack anyway on "normal" stack-based implementations that don't evict
stack-frames to the heap, or doing other trickery. Nevertheless it
would be nice to have a "heap-bounded" virtual stack and handle every
recursion without crashing. I think the best approach is to add a
compiler option for this (not that we haven't got enough already), to
(a) give the user the chance to switch to the "safe" behaviour and (b)
measure the performance impact.


cheers,
felix