Kent Pitman on Equal Rights -- and Wrongs -- in Lisp (1993)
nhplace.com
nhplace.com
Using higher-level data structures, each with a clear semantics, clarifies the meaning of both equality and copying. For example, my FSet functional collections library for CL has separate types for sets, sequences, maps, bags, and tuples, along with a generic function EQUAL? that has methods for all these different types. Thus one can construct nested types -- sets of sequences, maps whose domains are sets, etc. etc. -- and compare them by just calling EQUAL?. In bare CL one would pretty much have to write a separate equality function for each such type.
A critical distinction, in order to make this work, is that between object types and value types. Objects have identity and state; value types do not. When used with user-defined types, FSet requires this distinction to be made explicit: you have to say whether your type is an object or a value, and you have to be consistent about it. This way, it's always clear when equality should be "shallow" or "deep": equality comparison of object types is always by identity ("shallow"), while comparison of value types is always by content ("deep").
tl;dr: meaningful equality predicates can only be defined on immutable values.