Re: [Chicken-users] Unbounded stack growth

[Marc Feeley]

On 2012-07-11, at 5:59 PM, Felix wrote:

>> 
>> Performance should not trump safety and correctness.
> 
> Absolutely right, yet everybody has a different perception of what
> performance, safety and correctness means. Segfaulting on
> _stack-overflow_ is not something that I'd call "incorrect" or "unsafe"
> - I'd call it "inconvenient" and it may be the case that handling the
> overflow gracefully isn't such a big deal at all. On the other hand,
> an extremely deep recursion could in such a case (stack checks
> everywhere) bring the machine to a halt due to excessive thrashing.  I
> don't know whether I'd perhaps prefer the segfault in such a situation...

The point is that, in a high-level language, a segfault represents a loss of 
control of the language implementation.  On unix systems, it is usually caused 
by a protected virtual memory page that has been touched, and a segfault signal 
is generated.  Not very informative, but not a big safety issue.  On other 
operating systems (e.g. in a Nintendo DS, a FPGA, or a toaster), some unrelated 
zone of memory (say the heap containing Scheme objects) has been corrupted 
silently and the program has started executing random stuff, possibly burning 
your toast and setting fire to the house.

The programmer already has control (with the csc -heap-limit N option) over how 
much memory is available to the program to avoid thrashing caused by an 
infinite recursion, or an allocation loop gone wild.  There should be no 
difference in heap and stack allocation.  These are implementation terms.  It 
is all just memory.  After all, the Cheney on the MTA approach was designed to 
migrate the stack frames to the heap transparently, so the user should be 
isolated from the concern of where the continuation is stored.

What is unfortunate with this bug is that it goes against the programmer's 
intuition.  If you slightly modify the code to this :

;; File: even.scm

(define (even i n)
  (if (= 0 (modulo i 100000)) (print i))
  (if (= i n)
      #t
      (not (even (+ i 1) n))))

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

So that it is easy to see how deep in the recursion the program has gone, then 
you get this output :

% ./even 900000
0
100000
200000
300000
400000
500000
600000
700000
800000
900000
Segmentation fault: 11
% ./even 300000
0
100000
200000
300000
Segmentation fault: 11

This shows that the stack overflow is occuring during the unwinding phase of 
the recursion.  This is quite unintuitive for me.  Try explaining to a beginner 
that the unwinding of the recursion is causing memory allocation!  Moreover, if 
you slightly modify the code so that there is a call to the my-not function 
instead of the builtin not, then there are no problems (because the call to 
my-not at each step of the unwinding is going to gracefully handle the growing 
C stack and garbage collect it):

;; File: even.scm (slightly modified)

(define (my-not x) (not x))

(define (even i n)
  (if (= 0 (modulo i 100000)) (print i))
  (if (= i n)
      #t
      (my-not (even (+ i 1) n))))

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

% ./even 900000
0
100000
200000
300000
400000
500000
600000
700000
800000
900000
#t

The decision for not testing the stack limit on returns is based on a 
performance concern.  Adding this test at return points would allow the above 
code to work correctly, for very large values of n.

By the way, I'm surprised that the very similar looking code for rev-iota :

(define (rev-iota n)
  (if (= n 0)
      '()
      (cons n (rev-iota (- n 1)))))

does not trigger the bug.  Is "cons" treated differently from "not"?

Marc