On Thu, Jul 12, 2012 at 10:52 AM, Marc Feeley <fee...@iro.umontreal.ca> wrote: > > 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.
I disagree - I think a stack grown too large is likely indicative of a programming error, or at the very least an inefficient algorithm. In the general case I want my programs to be able to allocate as much heap as possible, but have a separate limitation on the stack. The default Chibi stack is only 1k. It can grow, but again to a limit of only 1M (by default). This coincidentally causes it to also return #t on the 200,000 input to even and raise an "out of stack" error on 300,000 (with a ridiculously long stack trace making me wonder if 1M is too large). -- Alex > > 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 mailing list > Chicken-users@nongnu.org > https://lists.nongnu.org/mailman/listinfo/chicken-users _______________________________________________ Chicken-users mailing list Chicken-users@nongnu.org https://lists.nongnu.org/mailman/listinfo/chicken-users