[Chicken-janitors] #1236: equal? can break at random moments

[Chicken Trac]

#1236: equal? can break at random moments
----------------------------+--------------------
 Reporter:  sjamaan         |      Owner:
     Type:  defect          |     Status:  new
 Priority:  critical        |  Milestone:  4.11.0
Component:  core libraries  |    Version:  4.10.x
 Keywords:                  |
----------------------------+--------------------
 This is really bad.  C_equal is defined to run inline, so it can't clear
 up stack space.  This is really really bad, because it basically means
 that you're playing russian roulette every time you call {{{equal?}}}; it
 can break or not, which depends on the state of the stack, over which you
 have very little control. It is also very hard to predict when exactly it
 will fail.

 I found this out [[http://salmonella-linux-x86-64.call-cc.org/master-
 debugbuild/gcc/linux/x86-64/2015/12/22/salmonella-
 report/test/numbers.html|the hard way]].

 Here's a standalone version that boils down to the code in the numbers
 tests:

 {{{
 #!scm

 ;; Creates lists like (((1))) and ((((1)))) for 3 and 4, respectively.
 (define-syntax recompose
   (er-macro-transformer
    (lambda (e r c)
      (let ((n (cadr e))
            (op (caddr e))
            (arg (cadddr e)))
        (define (recompose-1 n)
          (if (= n 1)
              `(,op ,arg)
              `(,op ,(recompose-1 (- n 1)))))
        (recompose-1 n)))))

 (let lp ((i 0))
   (print i " " (equal? (recompose 1000 list '(1))
                        (recompose 1000 list (list 1))))
   (lp (add1 i)))
 }}}

 You'll see this blows up after only 16 or so iterations.  I had to up the
 list nesting to 1000 because 100 only seems to crash once every blue moon.

 A fix could involve dynamically allocating (with {{{malloc}}} or so) a
 "working list" stack and use that to convert the recursion to a loop.
 Alternatively, we could "de-inline" it so it can reclaim memory.  On the
 plus side, this allows us to convert it to Scheme and taking the CPS hit.

 Originally I thought it might be possible to use the scratch space in
 CHICKEN 5, but I'm not sure that's suitable in this case because there's
 nothing in the heap or nursery that points directly to it.  We could
 create one and make an actual Scheme list of "todo" objects, but it would
 be such a long chain that it would become pretty slow I think.

--
Ticket URL: <http://bugs.call-cc.org/ticket/1236>
CHICKEN Scheme <http://www.call-cc.org/>
CHICKEN Scheme is a compiler for the Scheme programming language.