chicken-users
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Chicken-users] Unbounded stack growth


From: Marc Feeley
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.

Here's a simple example where this matters :

;; File: even.scm

(define (even n)
  (if (= n 0)
      #t
      (if (even (- n 1)) #f #t)))

(print (even (string->number (car (command-line-arguments)))))

and a shell transcript of the behavior on a Mac OS X machine :

% csc even.scm
% ./even 111111
#f
% ./even 200000
#t
% ./even 300000
Segmentation fault: 11

The segmentation fault is due to a C stack overflow.

In this example, there will be an arbitrarily long sequence of C calls (in the 
unwinding of the recursion to even) with no Scheme call, so stack size checks 
will not be performed during the unwinding, yet the C stack grows during the 
unwinding.  There is no stack overflow during the winding phase of the 
recursion because the stack size checks are performed at regular intervals (at 
each entry to even).

I believe the fix should be simple (i.e. a stack size check should be added to 
return points).

Marc




reply via email to

[Prev in Thread] Current Thread [Next in Thread]