Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!stanford.edu!lucid.com!karoshi!fy
From: fy@lucid.com (Frank Yellin)
Newsgroups: comp.lang.lisp
Subject: Re: EQUAL on circular lists
Message-ID: <FY.91Jun11102247@hardwick.lucid.com>
Date: 11 Jun 91 15:22:47 GMT
References: <2849@prles2.prl.philips.nl> <1991Jun8.002630.22596@elroy.jpl.nasa.gov>
Sender: usenet@lucid.com
Organization: Lucid, Inc., Menlo Park, CA
Lines: 37
In-Reply-To: gat@forsight.jpl.nasa.gov's message of 8 Jun 91 00:26:30 GMT

>> kostelij@apolloway.prl.philips.nl (T. Kostelijk 43897) writes:
>> Does anyone have an extended version of EQUAL which can determine in 
>> finite time whether two trees of conses have the same printed
>> (possibly infinite) representation?

> gat@forsight.jpl.nasa.gov (Erann Gat) replies:
> (defun printed-representations-equal-p (l1 l2)
>   (let ( (*print-circle* t) )
>    (string= (format nil "~S" l1) (format nil "~S" l2))))

I don't really think that the above code will work.  But the problem, as
originally stated, was rather vague.

For example, Kostelijk explicitly wanted the following two lists to be
equal:
    #1=(a a a . #1#)
    #1=(a . #1#)
since they both print out as (a a a a a a a a ...).  The function
#'printed-representations-equal-p will return nil, since with
*print-circle* bound to 't, one prints out as "#1=(a a a . #1#)" and the
other as "#1=(a . #1#)" 

Then again, my solution, posted a while ago, doesn't really solve what the
original poster asked for either.  

The two lists
    (#1=(a . #1) b)
    (#1=(a . #1) c)
both print out as ((a a a a a a .....)) since the printer never gets to the
second element of the list.  So reading Kostelijk's query literally, the
above two lists should be extended-equal.  Both my code and Gat's code will
return nil.  

Maybe I'm beginning to believe in program specification again.

-- Frank Yellin
   fy@lucid.com