[Top][All Lists]
[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
- [Chicken-users] Unbounded stack growth,
Marc Feeley <=
- Re: [Chicken-users] Unbounded stack growth, John Cowan, 2012/07/11
- Re: [Chicken-users] Unbounded stack growth, Marc Feeley, 2012/07/11
- Re: [Chicken-users] Unbounded stack growth, Felix, 2012/07/11
- Re: [Chicken-users] Unbounded stack growth, Marc Feeley, 2012/07/11
- Re: [Chicken-users] Unbounded stack growth, Alex Shinn, 2012/07/11
- Re: [Chicken-users] Unbounded stack growth, Matthew Flatt, 2012/07/11
- Re: [Chicken-users] Unbounded stack growth, John Cowan, 2012/07/11
- Re: [Chicken-users] Unbounded stack growth, Alex Shinn, 2012/07/11
- Re: [Chicken-users] Unbounded stack growth, cjtenny, 2012/07/12
- Re: [Chicken-users] Unbounded stack growth, Alex Queiroz, 2012/07/12