Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!apple!snorkelwacker!bloom-beacon!bu.edu!bu-cs!lectroid!jjmhome!m2c!umvlsi!dime!dime.cs.umass.edu!moss From: moss@takahe.cs.umass.edu (Eliot &) Newsgroups: comp.object Subject: Re: Atomic Objects and Identity (was Re: Evaluating "Object-Oriented" Progra) Message-ID: Date: 1 Feb 90 14:59:03 GMT References: <2740@tukki.jyu.fi> <1990Jan31.052750.22507@Neon.Stanford.EDU> Sender: root@dime.cs.umass.edu Reply-To: Moss@cs.umass.edu Distribution: comp Organization: Dept of Comp and Info Sci, Univ of Mass (Amherst) Lines: 59 In-reply-to: pallas@Neon.Stanford.EDU's message of 31 Jan 90 05:27:50 GMT I want to make a brief follow up comment regarding mutability and identity. Identity has to do with equality -- that is, two objects are considered the same (identical) if they are "equal". Under this view one must distinguish equality of *objects* (identities) from equality of *states of objects* (roughly, values of the "variables" contained in the objects). This is true only for mutable objects, though -- the states can be equal for two distinct objects. *Immutable* objects should act like pure mathematical values (even if they don't fit into a small number of bits), and distinct copies of them *should not* be distinguished. (Almost) every mutable type (class, abstract data type) also has an immutable version, where each mutating operation of the mutable type instead produces a new immutable value without changing any of its inputs. Further, both can be useful to have around. In sum, the identity of an *immutable* object *is* its (abstract) value. Testing identity may not be entirely trivial, though -- consider the case of immutable sets using an array of unordered, possibly duplicated, elements as the representation. To test if immutable set X is the same as immutable set Y, we must check that each element of X occurs in Y and vice versa (this is expedited by removing duplicates and sorting, though sorting is not always possible since not all element classes have reasonable total orders defined on them). Manipulating the identity of the *mutable object representing* an immutable object will generally be a violation of clean semantics. (However, it would seem perhaps reasonable when comparing two immutable sets X and Y to first check whether their representing objects are identical, in which case the sets are clearly identical as well.) Likewise, it would be semantically improper to mutate the representing object in such a way as to change which abstract value is represented. (That is, it is fair to re-order and remove duplicates from the array representing an unordered immutable set, since that does not change what set is represented, but removing all occurrences of an element would be improper.) Another point to keep in mind is that an object/class can be immutable and yet *refer to* mutable objects. For example, consider an immutable set of airline reservation records. The individual records might still be mutable, but the *set* is immutable -- its state is the *identities* of the records in the set, not their *states*. (Of course, one might want sets of record states (snapshots), too, but that is a different abstraction.) One must be especially careful with collections (not meaning the Smalltalk class, but every abstract data types that is essentially a collection (more or less structured) of other, independent objects) not to get tangles up about mutability. Regarding identity, it is only the strongest (most distinguishing) equivalence relation defined over objects of a class. In general there are weaker equivalence relations of interest (e.g., mutable objects that currently have the same state, but may not be identical; arrays that contain the same elements at the moment, but possibly in different orders, etc.). A final note -- none of this stuff is directly related to inheritance. We thought through many of the issues in designing CLU, a language supporting abstract data types but not inheritance, in the early 70s. Cheers! Eliot -- J. Eliot B. Moss, Assistant Professor Department of Computer and Information Science Lederle Graduate Research Center University of Massachusetts Amherst, MA 01003 (413) 545-4206; Moss@cs.umass.edu