Michael Weber: Random Bits and Pieces

...Please don't assume Lisp is only useful for Animation and Graphics, AI, Bioinformatics, B2B and E-Commerce, Data Mining, EDA/Semiconductor applications, Expert Systems, Finance, Intelligent Agents, Knowledge Management, Mechanical CAD, Modeling and Simulation, Natural Language, Optimization, Research, Risk Analysis, Scheduling, Telecom, and Web Authoring just because these are the only things they happened to list.

Kent M. Pitman

Lisp Logo (by Conrad Barsky)

Except—how to decide when two objects are alike? And what, exactly, is the meaning of alike?

Common Lisp provides a whole bunch of ways to compare two objects (EQ, EQL, EQUAL, EQUALP, not to mention the versions specialized on more specific types), each of which is suited for a particular purpose.

When I define application-specific types, odds are good that at some point I want to compare their instances, and possibly with a coarser equality than pointer equality (which is what any of the functions mentioned above will give me for such objects). I can still define my own specialized equality predicate to compare two of my object directly, but what if I want to compare, e.g., graphs of lists of my objects? The predicate needs to be able to deal not only with my objects, but also with any other type of CL object which I might reference.

One such equivalence (and there are many other possible ways to define one) is MW-EQUIV:OBJECT=. It distinguishes between mutable and frozen objects, and is extensible. The rules are simple:

  • Mutable objects are compared by pointer equality. Henry Baker has a lot to say about why that makes sense in his paper Equal Rights for Functional Objects.
  • If I promise in some way or other that two object are frozen, i.e., they will not be mutated (even though they might be mutable in principle), then they are compared by looking at their respective constituents.

As an example, I define a class FOO with two slots and check equivalence of two instances.


CL-USER> (defclass foo ()
           ((fred   :initarg :fred   :reader fred)
            (barney :initarg :barney :reader barney)))
#<STANDARD-CLASS FOO>
CL-USER> (equal (make-instance 'foo :fred 'fred :barney 'barney)
                (make-instance 'foo :fred 'fred :barney 'barney))
NIL
CL-USER> (equiv:object= (make-instance 'foo :fred 'fred :barney 'barney)
                        (make-instance 'foo :fred 'fred :barney 'barney))
NIL

Fair enough, by default objects are considered mutable, hence two different instances are not equivalent wrt. OBJECT=.

Now, I promise that I will not modify instances of FOO. Also, both of its slots are relevant to determine equivalence between two instances.


(defmethod equiv:object-frozenp ((foo foo))
  t)

(defmethod equiv:object-constituents ((type (eql 'foo)))
  (declare (ignore type))
  (load-time-value (list #'fred #'barney)))

Here is what I get:


CL-USER> (equiv:object= (make-instance 'foo :fred 'fred :barney 'barney)
                        (make-instance 'foo :fred 'fred :barney 'barney))
T
CL-USER> (let ((fred (list 'fred))
               (barney (list 'barney)))
           (equiv:object= (make-instance 'foo :fred fred :barney barney)
                          (make-instance 'foo :fred fred :barney barney)))
T

Cool, instances of FOO are now compared by their slots. However, this might not be enough:


CL-USER> (equiv:object= (make-instance 'foo :fred (list 'fred)
                                            :barney (list 'barney))
                        (make-instance 'foo :fred (list 'fred)
                                            :barney (list 'barney)))
NIL

Lists are build from cons cells and those are mutable, and so are our instances then, by proxy. I have to promise that at least I will not mutate the conses pointed to in the slots of our FOO instances:


CL-USER> (equiv:object= (make-instance 'foo :fred (list 'fred)
                                            :barney (list 'barney))
                        (make-instance 'foo :fred (list 'fred)
                                            :barney (list 'barney))
                        t)
T

Of course, usual caveats apply. If I do something stupid like breaking my promises, or subclassing a class with mutable instances, and declaring subclass instances as frozen, I will lose.

(It's MW-EQUIV, in case anybody missed link above.)

p.s.: For a brief moment I thought that AND/APPEND method combinations together with NO-APPLICABLE-METHOD would make a nice implementation, but I'll leave that for another time.