The `member?` bug #11

New issue

Closed

opened 2026-03-18 16:35:29 +00:00 by simon · 1 comment

simon commented

2026-03-18 16:35:29 +00:00

Owner

This is not a bug actually in member?, but member? exercises/demonstrates it.

If you run the following code:

(set! nil? (lambda (o) (= (type o) "NIL ")))

(set! CDR (lambda (o) 
  (print (list "in CDR; o is: " o) *log*) 
  (let ((r . (cdr o))) 
    (print (list "; returning: " r) *log*) 
    (println *log*) 
    (println *log*) 
    r)))

(set! member? 
  (lambda
    (item collection)
    (print (list "in member?: " 'item item 'collection collection) *log*)(println *log*)
    (cond
      ((nil? collection) nil)
      ((= item (car collection)) t)
      (t (member? item (CDR collection))))))

(member? 5 '(1 2 3 4))

You get a non-terminating recursion thus:

("in member?: " item 5 collection (1 2 3 4))
("in CDR; o is: " (1 2 3 4))("; returning: " (2 3 4))
("in member?: " item 5 collection (2 3 4))
("in CDR; o is: " (2 3 4))("; returning: " (3 4))
("in member?: " item 5 collection (3 4))
("in CDR; o is: " (3 4))("; returning: " (4))
("in member?: " item 5 collection (4))
("in CDR; o is: " (4))("; returning: " nil)
("in member?: " item 5 collection (4))
("in CDR; o is: " (4))("; returning: " nil)
("in member?: " item 5 collection (4))
("in CDR; o is: " (4))("; returning: " nil)
....

In other words, when member? recurses down to the last item in the collection, CDR correctly returns nil, but member? then recurses with its.... oh, jings, I think I've got it.

We're binding collection to nil in the dynamic environment. And then we're looking in the dynamic environment for the binding, and the first one we hit is nil, so we take the second one...?

Worth checking.

This is not a bug actually in `member?`, but `member?` exercises/demonstrates it. If you run the following code: ```lisp (set! nil? (lambda (o) (= (type o) "NIL "))) (set! CDR (lambda (o) (print (list "in CDR; o is: " o) *log*) (let ((r . (cdr o))) (print (list "; returning: " r) *log*) (println *log*) (println *log*) r))) (set! member? (lambda (item collection) (print (list "in member?: " 'item item 'collection collection) *log*)(println *log*) (cond ((nil? collection) nil) ((= item (car collection)) t) (t (member? item (CDR collection)))))) (member? 5 '(1 2 3 4)) ``` You get a non-terminating recursion thus: ```lisp ("in member?: " item 5 collection (1 2 3 4)) ("in CDR; o is: " (1 2 3 4))("; returning: " (2 3 4)) ("in member?: " item 5 collection (2 3 4)) ("in CDR; o is: " (2 3 4))("; returning: " (3 4)) ("in member?: " item 5 collection (3 4)) ("in CDR; o is: " (3 4))("; returning: " (4)) ("in member?: " item 5 collection (4)) ("in CDR; o is: " (4))("; returning: " nil) ("in member?: " item 5 collection (4)) ("in CDR; o is: " (4))("; returning: " nil) ("in member?: " item 5 collection (4)) ("in CDR; o is: " (4))("; returning: " nil) .... ``` In other words, when `member?` recurses down to the last item in the collection, `CDR` correctly returns `nil`, but `member?` then recurses with its.... oh, jings, I think I've got it. We're binding `collection` to `nil` in the dynamic environment. And then we're looking in the dynamic environment for the binding, and the first one we hit is `nil`, so we take the second one...? Worth checking.