Re: [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
Resolution:                  |   Keywords:
-----------------------------+--------------------
Description changed by sjamaan:

Old description:

> 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.

New description:

 This is really bad.  C_equal is defined to run inline, so it can't clear
 up stack space, but it consumes stack space! It will just bail out with an
 exception when it runs out of stack.  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#comment:1>
CHICKEN Scheme <http://www.call-cc.org/>
CHICKEN Scheme is a compiler for the Scheme programming language.