[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Chicken-users] Unbounded stack growth
From: |
Marc Feeley |
Subject: |
Re: [Chicken-users] Unbounded stack growth |
Date: |
Wed, 11 Jul 2012 21:52:53 -0400 |
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
- [Chicken-users] Unbounded stack growth, Marc Feeley, 2012/07/11
- 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 <=
- 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
- Re: [Chicken-users] Unbounded stack growth, Alex Shinn, 2012/07/12
- Re: [Chicken-users] Unbounded stack growth, Alex Queiroz, 2012/07/12
- Re: [Chicken-users] Unbounded stack growth, Alex Shinn, 2012/07/12
Re: [Chicken-users] Unbounded stack growth, Marc Feeley, 2012/07/11