[gambit-list] Big number Bug?

Christian Jaeger christian at pflanze.mine.nu
Thu Apr 26 07:44:17 EDT 2007


dillo gimp wrote:
> Ok, I isolated the code that crashes both gsi and gsc compiled code:
> it's doing reduced-row-echelon-form.
> It's a bit long, but this is the best I can do:
>   
Bugs happen.

(This is a somewhat lengthy demonstration of debugging; the relevant
finding is at the end of this mail.)

For debugging, it's often best to switch off tail call optimization, so
that really the error is reported in the scope where the triggering code
is situated is reported and not the place of the next outer non-tail
continuation after elimination of all 'empty' continuations.

It helps using the provided gambit elisp file with Emacs, this way you
can have keys bound to the debugger commands, and Emacs automatically
jumps to the place in the sources where the debugger is hinting at.

(generate-proper-tail-calls #f)
(load "bignumbug.scm")

*** ERROR IN ##ratnum.* -- Divide by zero
(quotient 0 0)

Now you can make use of the fine Gambit debugger:

1> ,b
0 ##ratnum.*
1 *
2 #<procedure #4> "bignumbug.scm"@21:31 (* z r)
3 map
4 rref "bignumbug.scm"@21:14 (map (lambda (z) (* z r...
5 rref "bignumbug.scm"@19:35 (rref (map cdr a))
6 rref "bignumbug.scm"@19:35 (rref (map cdr a))
7 rref "bignumbug.scm"@19:35 (rref (map cdr a))
8 rref "bignumbug.scm"@28:9 (rref (map cdr (cdr b)))
9 rref "bignumbug.scm"@28:9 (rref (map cdr (cdr b)))
...
20 rref "bignumbug.scm"@28:9 (rref (map cdr (cdr b)))
21 test "bignumbug.scm"@223:12 (rref M)
22 (interaction) (stdin)@22:1 (test)
23 ##main

The first two are part of the system (and hence, because the Gambit
system has not been compiled with debuggig enabled, doesn't report
file/line information). The fist continuation in your code is
continuation 2.

1> ,2
2 #<procedure #4> "bignumbug.scm"@21.31 (* z r)
1\2> z
0/2
1\2> r
2/0

This looks 'interesting', both 0/2 and 2/0.

1\2> (* z 3)
0/2
1\2> (* 3 r)
2/0
1\2> (* z r)
*** ERROR IN ##ratnum.* -- Divide by zero
(quotient 0 0)
2>

Hit Ctl-d once to get back to the previous debugging level.

The call is in the lambda in this code:

(let* ((b (let* ((r (/ (caar a)))
(top (map (lambda (z) (* z r)) (car a))))

How did r happen to be 2/0? From (/ (caar a)). We can see the rest of
the environment:

1\2> ,e
z = 0/2
r = 2/0
a = '((0/2 0/8 0/32 0/128 0/512 0/2048 0/8192 0/32768 0/131072 0/524288
0/20...
x = '((0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3) (0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4) (0...
(current-exception-handler) = primordial-exception-handler
(current-input-port) = '#<input-port #2 (stdin)>
(current-output-port) = '#<output-port #3 (stdout)>
(current-directory) = "/home/chris/schemedevelopment/gambit/work/"

So a is a list with those strange numbers.

1\2> (caar a)
0/2

1\2> a
((0/2
0/8
0/32
0/128
0/512
0/2048
0/8192
0/32768
0/131072
0/524288
0/2097152
0/8388608
0/33554432
0/134217728
0/134217728
-805306368/134217728)
(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3)
...

Next step is to find out how those values in a are being produced. I'll
use the stepper. I'm instrumenting the code with a (step) like so:

(let ((a (call-with-current-continuation
(lambda (cc)
(step) ;; <---switch on stepping
(let df ((y x))
(if (null? y)
(cc x)
(if (zero? (caar y))
(let ((z (df (cdr y))))
(if (null? z)
y
(cons (car z) (cons (car y)(cdr z)))))
y)))))))

Stepping through I see that the last branch is taken, y is returned, the
unchanged x. Not interesting yet. The problem must happen in a later
recursive call of rref.
So I'm entering
1> ,c

Next rref run is not interesting either, I'm hitting ,c about 10 times
now x is:

1> x
((0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3)
(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4)
(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -4)
(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1)
(0
0
...

Still no interesting effect though.

What we want is see how a is being built right before the error happens.

Using call/cc we can save previous state of a computation:

(define lastcc #f)
...
(let ((a (begin
(call/cc (lambda (cc) (set! lastcc cc)))
(call-with-current-continuation
(lambda (cc)
;;(step)
(let df ((y x))

I'm running the code again,
*** ERROR IN ##ratnum.* -- Divide by zero
(quotient 0 0)
1>
hit ctl-d, then
> (begin (step) (lastcc))
and step through the code

1> x
((0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3)
(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4)
(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -4)
(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1)
(0/2
0/8
0/32

hm, it already contains such numbers. The problematic operations have
happened earlier already. Well, let's change the debugging hooks again, to

(define lastcc '())
...
(call/cc (lambda (cc) (set! lastcc (cons cc lastcc))))


Run the code again, will get you all those continuations in reverse order.

> lastcc
(#<procedure #23>
#<procedure #24>
#<procedure #25>
#<procedure #26>
#<procedure #27>
#<procedure #28>
#<procedure #29>
#<procedure #30>
#<procedure #31>
#<procedure #32>
#<procedure #33>
#<procedure #34>
#<procedure #35>
#<procedure #36>
#<procedure #37>
#<procedure #38>
#<procedure #39>)

I check the one before the last:

> (begin (step) (#24))
,s ,s ,s..

then I check the others
#30 -> x already contains buggy rationals,
#38 -> x does not yet contain buggy rationals,
#35 -> x already contains buggy rationals:
..
(0
0
0
0
0
0
0
0
0
0
0
0
0/2
0/8
0/32
0/128
0/512
0/2048
0/8192
0/32768
0/131072
0/524288
0/2097152
0/8388608
0/33554432
0/134217728
0/134217728
-805306368/134217728)
..

#36 -> contains same as #35
#37 -> x does not yet contain those values.

Ok, so we can just continue to step on beginning from #37, that should
lead us to the buggy op.

Instead of entering the ,s command many times manually, I'm switching to
the *scratch* buffer, enter

(dotimes (i 1000) (gambit-step-continuation)) ; or use 2000 to make sure
you get to it

and hit ctl-j. Then I switch back to the *scheme* buffer and search for
0/ in the buffer from the start of the stepping. This gives me this
relevant cutout:

1> | | | > re
| | | -2147450880/2
*** STOPPED IN #<procedure #79>, "bignumbug.scm"@30.17
1> | | | > *
| | | #<procedure #66 *>
*** STOPPED IN #<procedure #79>, "bignumbug.scm"@30.19
1> | | | > t
| | | 65535/8192
*** STOPPED IN #<procedure #79>, "bignumbug.scm"@30.22
1> | | | > car
| | | #<procedure #62 car>
*** STOPPED IN #<procedure #79>, "bignumbug.scm"@30.26
1> | | | > row
| | | (-134217728 -234881024 -293601280 -325058560 -341311488 -349569024
-353...
*** STOPPED IN #<procedure #79>, "bignumbug.scm"@30.21
1> | | | > (car row)
| | | -134217728
*** STOPPED IN #<procedure #79>, "bignumbug.scm"@30.16
1> | | | > (* t (car row))
| | | -1073725440
*** STOPPED IN #<procedure #79>, "bignumbug.scm"@30.10
1> | | | > (- re (* t (car row)))
| | | 0/2

Using those values:
> (- -2147450880/2 -1073725440)
0
where the above has given 0/2. Well, I'm out of idea now, I hope Marc or
Brad can help further.

BTW, another idea to help track down the above numbers would have been
to wrap the gambit ops with ones that check the result for not
containing a zero numerator or denominator and throw an error right away
if it does. This would have been easier than the above, but my
description may help you anyway.

(BTW I'm using 4.0 beta 21)

Christian.

PS. I've already suggested once to add a mode to the debugger to save
all continuations onto a stack. So instead of recording everything into
the Emacs buffer as shown above, the continuations would be on a
stack/list which could be examined, that could maybe be more efficient
computation-wise and maybe offer better handling.

PS.2: Gambit shouldn't exit if ,s is entered on the toplevel. (This
makes using repeated ,s dangerous since one too many and the collected
data of the running interpreter is lost.)




More information about the Gambit-list mailing list