Common Lisp comes with quite some functions to compare objects for equality, yet none is applicable in every situation and in general this is hard, as equality of objects depends on the semantics of operations on them. As consequence, users find themselves regularly in a situation where they have to roll their own specialized equality test.
This module provides one of many possible equivalence relations between standard Common Lisp objects. However, it can be extended for new objects through a simple CLOS protocol. The rules when two objects are considered equivalent distinguish between mutating and frozen objects. A frozen object is promised not to be mutated in the future in a way that operations on it can notice the difference.
We have chosen to compare mutating objects only for identity (pointer equality), to avoid various problems. Equivalence for frozen objects on the other hand is established by recursing on the objects' constituent parts and checking their equivalence. Hence, two objects are equivalent under the
OBJECT=relation, if they are either identical, or if they are frozen and structurally equivalent, i.e, their constituents are point-wise equivalent.
Since many objects are potentially mutable, but are not necessarily mutated from a certain point in their life time on, it is possible to promise to the equivalence relation that they remain frozen for the rest of their life time, thus enabling coarser equivalence than the often too fine-grained pointer equality.
The code comes with a BSD-style license so you can basically do with it whatever you want.
The canonical location for MW-EQUIV is http://www.foldr.org/~michaelw/projects/mw-equiv/.
Download shortcut: http://www.foldr.org/~michaelw/projects/mw-equiv/mw-equiv.tar.gz.
MW-EQUIV together with this documentation can be downloaded from http://www.foldr.org/~michaelw/projects/mw-equiv/mw-equiv.tar.gz. Alternatively, it can be installed via ASDF-Install:
The current released version is 0.1.3.
A Subversion repository is available at http://svn.foldr.org/~michaelw/mw-equiv/.
Please direct bug reports, patches, questions, and any other feedback to Michael Weber.
To extend the equivalence
OBJECT= for a new type,
the following steps are necessary:
OBJECT-FROZENPfor instances of the new type to reflect whether they are frozen or not.
OBJECT-CONSTITUENTSfor the new type.
object-constituents type => list
Returns list of accessors used to determine equivalence of objects of type TYPE.
object-constituents (type (eql cons)) => list
Frozen conses are compared by their CAR and CDR entries. Note that by default (as per
OBJECT-FROZENP), conses are potentially mutable. Thus, two conses are only regarded equivalent when they are pointer-equal, i.e, the same.
object-constituents (type (eql pathname)) => list
Pathnames are compared according to their directory, name, type, version, host and device.
object-frozenp object => generalized-boolean
Indicates whether OBJECT is frozen. That is, this function must return true only if OBJECT will not be mutated in an observable way from the point of the call until the end of its life time, otherwise false.
object-frozenp object => generalized-boolean
Unknown objects are conservatively assumed to be mutating, hence this method returns false.
object-frozenp (object cons) => generalized-boolean
object-frozenp (object string) => generalized-boolean
object-frozenp (object vector) => generalized-boolean
object-frozenp (object pathname) => generalized-boolean
object-frozenp (object number) => generalized-boolean
object-frozenp (object character) => generalized-boolean
object-sequence= xs ys => generalized-boolean
Checks whether sequences XS and YS are element-wise equivalent, by means of
OBJECT=, and of the same length.
object-vector= xs ys => generalized-boolean
Checks whether vectors XS and YS are element-wise equivalent, by means of
OBJECT=, and of the same length. Use
object= x y &optional frozenp => generalized-boolean
Returns true if X and Y are (observationally) equivalent. Hence,
OBJECT=is an equivalence relation:
- (object= x x)
- (equal (object= x y frozenp) (object= y x frozenp))
- (implies (and (object= x y frozenp) (object= y z frozenp)) (object= x z frozenp))
Frozen objects (i.e., objects which are promised not to mutate) are compared by recursing into their constituents, as specified by
OBJECT-CONSTITUENTS. Mutating (i.e., not frozen) objects are compared with the pointer equality EQ.
FROZENP can be used to override the defaults for X and Y given by
OBJECT-FROZENP. It is a promise that none of the objects X and Y are referring to with their constituents, or any of the constituents' constituents, are mutated from the time of the call to
If one lies with FROZENP,
OBJECT-CONSTITUENTS, all bets are off and the result of
OBJECT=diverges if both X and Y are circular data structures.
See also: http://home.pipeline.com/~hbaker1/ObjectIdentity.html
This documentation was prepared with DOCUMENTATION-TEMPLATE.
BACK TO MY HOMEPAGE