Recursion bug in Mosh Scheme
2011-09-08 by
Oh, great. In my first day of working with Mosh Scheme, on pretty elementary stuff, I find a bug.
Here's the simplified example that I sent in as part of the bug report. I want to write a procedure that tests whether a given binary tree of integers contains only even integers. I'm using the empty list to model the empty binary tree, and three-elements lists (root, left subtree, right subtree) to model non-empty ones. So here's the definition:
(define (buggy tree)
(letrec ((recurrer
(lambda (subtree)
(or (null? subtree)
(and (even? (car subtree))
(recurrer (cadr subtree))
(recurrer (caddr subtree)))))))
(recurrer tree)))
And here's a simple test case, giving the wrong answer.
> (buggy '(92 () (103 () ()))) #t
I was particularly puzzled to discover that the error disappears if you use any of the following three variations instead:
(define (ok0 tree)
(or (null? tree)
(and (even? (car tree))
(ok0 (cadr tree))
(ok0 (caddr tree)))))
(define ok1
(letrec ((recurrer (lambda (tree)
(or (null? tree)
(and (even? (car tree))
(recurrer (cadr tree))
(recurrer (caddr tree)))))))
recurrer))
(define (ok2 tree)
(letrec ((recurrer
(lambda (subtree)
(let ((result (or (null? subtree)
(and (even? (car subtree))
(recurrer (cadr subtree))
(recurrer (caddr subtree))))))
result))))
(recurrer tree)))
The explanation should be interesting.