equal? can break at random moments

[sjamaan]

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 ​the hard way.

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

;; 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. On the downside, we'd be taking a 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.

[sjamaan]

According to Felix, tagged pointer tag comparisons could just be implemented with eq?/eqv?. This would be strictly backwards incompatible, so maybe only do that in CHICKEN 5?

Alternatively, deprecate the whole inline mess, but keep using it for tagged pointers. At the same time, we could also deprecate the fact that it uses equal? and switch to eqv? in a later version.

[sjamaan]

It seems that with some of the fixes we've made to prevent runaway stack us, it's not as pressing an issue anymore. The example program no longer crashes, unless the nesting is very extreme (lists of 10000 deep).

[sjamaan]

Less urgent than I initially thought; never ran into this again after.