MW-EQUIV — An Extensible Object Equivalence for Common Lisp


 

Abstract

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.


 

Contents

  1. Download
  2. Support
  3. Quick Start
  4. The MW-EQUIV dictionary
    1. object-constituents
    2. object-frozenp
    3. object-sequence=
    4. object-vector=
    5. object=
  5. References
  6. Acknowledgements

 

Download

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: 

  (asdf-install:install "http://www.foldr.org/~michaelw/projects/mw-equiv/mw-equiv.tar.gz")

The current released version is 0.1.3.

A Subversion repository is available at http://svn.foldr.org/~michaelw/mw-equiv/.


 

Support

Please direct bug reports, patches, questions, and any other feedback to Michael Weber.


 

Quick Start

To extend the equivalence relation OBJECT= for a new type, the following steps are necessary:


 

The MW-EQUIV dictionary


[Generic function]
object-constituents type => list


Returns list of accessors used to determine equivalence of objects of type TYPE.


[Method]
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.


[Method]
object-constituents (type (eql pathname)) => list


Pathnames are compared according to their directory, name, type, version, host and device.


[Generic function]
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.


[Method]
object-frozenp object => generalized-boolean


Unknown objects are conservatively assumed to be mutating, hence this method returns false.


[Method]
object-frozenp (object cons) => generalized-boolean
object-frozenp (object string) => generalized-boolean
object-frozenp (object vector) => generalized-boolean


Returns false.


[Method]
object-frozenp (object pathname) => generalized-boolean
object-frozenp (object number) => generalized-boolean
object-frozenp (object character) => generalized-boolean


Returns true.


[Function]
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.


[Function]
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-SEQUENCE= instead.


[Function]
object= x y &optional frozenp => generalized-boolean


Returns true if X and Y are (observationally) equivalent. Hence, OBJECT= is an equivalence relation:
  1. (object= x x)
  2. (equal (object= x y frozenp) (object= y x frozenp))
  3. (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 OBJECT= onwards.

If one lies with FROZENP, OBJECT-FROZENP, or OBJECT-CONSTITUENTS, all bets are off and the result of OBJECT= is meaningless.

OBJECT= diverges if both X and Y are circular data structures.

See also: http://home.pipeline.com/~hbaker1/ObjectIdentity.html


 

References

  1. Kent M. Pitman, EQUAL Rights—and Wrongs— in Lisp, 1997
  2. Henry G. Baker, Equal Rights for Functional Objects, 1992

 

Acknowledgements

This documentation was prepared with DOCUMENTATION-TEMPLATE.

BACK TO MY HOMEPAGE