Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!think.com!snorkelwacker.mit.edu!stanford.edu!lucid.com!karoshi!fy
From: fy@lucid.com (Frank Yellin)
Newsgroups: comp.lang.lisp
Subject: Re: EQUAL on circular lists, yet again.
Message-ID: <FY.91Jun17160712@hardwick.lucid.com>
Date: 17 Jun 91 21:07:12 GMT
References: <2867@prles2.prl.philips.nl>
Sender: usenet@lucid.com
Organization: Lucid, Inc., Menlo Park, CA
Lines: 59
In-Reply-To: kostelij@apolloway.prl.philips.nl's message of 13 Jun 91 14:54:55 GMT


Ton Kostelijk posts the following algorithm from Bernhard Pfahringer.
> (defun equal-circle (cons1 cons2)
>   (or (eql cons1 cons2)
>       (and (consp cons1)
>            (consp cons2)
>            (let ((f2 (first cons2))
>                  (r2 (rest cons2)))
>              (unwind-protect
>                  (progn (setf (first cons2) (first cons1)
>                              (rest cons2) (rest cons1))
>                         (and (equal-circle (first cons1) f2)
>                              (and (equal-circle (first cons1) f2)
>                                  (equal-circle (rest cons1) r2))))
>               (setf (first cons2) f2 (rest cons2) r2))))))

I received mail from Jim Boyce (the originator of the idea for my original
algorithm) this morning.  He sent me an example for which the above
algorithm goes into an infinite loop, even though it should return 't.

Imagine four cons cells, which we'll call a, b, c, and d, in which the car
and cdr of each of the four cells are themselves one of the four cons cells.

Trivially, any two should be equal-circle to each other, since c {a|d}* r
applied to any of the four cells gives you another of the cells.

Here's what a, b, c, and d look like:

           a       b       c       d
        (c . b) (a . c) (a . c) (d . d)


Now try (equal-circle a d)
                                a          b          c          d

(equal-circle a d)           (c . b)    (a . c)    (a . c)    (d . d)
  BASH d=d.d                 (c . b)    (a . c)    (a . c)    (c . b)
  (equal-circle c d)         (c . b)    (a . c)    (a . c)    (c . b)
    BASH d=c.b               (c . b)    (a . c)    (a . c)    (a . c)
    (equal-circle a c)       (c . b)    (a . c)    (a . c)    (a . c)  **
      BASH c=a.c             (c . b)    (a . c)    (c . b)    (a . c)
      (equal-circle c a) => t
      (equal-circle b c)     (c . b)    (a . c)    (c . b)    (a . c)
        BASH c=c.b           (c . b)    (a . c)    (a . c)    (a . c)
        (equal-circle a c)   (c . b)    (a . c)    (a . c)    (a . c)  **

The two lines marked ** are identical, but one is a subproblem of the
other.  So the result is infinite recursion.

Here's the example in "standard" lisp notation:
   (equal-circle '#1=(#3=(#1# . #3#) . #2=(#1# . #3#))   '#4=(#4# . #4#))
Try it and watch your stack overflow.

The moral:  rplaca and rplacd are dangerous toys, even when they go by
other names.  


-- Frank Yellin
   fy@lucid.com