Writing Immutable Objects with Elegance

Edit: This blog post has been turned into a draft paper.

Today, I got burned with design issues of Smalltalk’s dictionaries. They implement object comparison = using value equality, but are at the same time mutable. The internal state of a dictionary consists of an array of associations. In addition to problems of equality, the the internal state can be accessed and aliased with Dictionary>>associationsDo: and Dictionary>>add:

We should instead have an immutable dictionary using value comparison, and a mutable dictionary using identity comparision. Mixing styles is too dangerous. For the mutable dictionary, the internal state should never be accessible and data should be copied to ensure no dependencies on mutable state are established.

In an old post I rant on the conflict between the imperative object paradigm that promotes mutable state, and the functional paradigm that promotes immutable data structures. It is mostly a problem of readability, though.

Assignment Syntax

To make the use of immutable objects more readable, we could actually generalize operator assignment syntax like +=, -=, <<= to any message.  Postfixing a message with = would imply that the reference pointed to the receiver of the message is updated with the value of the message.

aReference message=: 5            
<-->      
aReference := aReference message: 5
aDictionray at: key put=: value   
<-->      
aDictionary := aDictionary at: key put=: value

When the selector has multiple arguments, the prefix comes at the very end. This is simple, efficient syntactic suggar.

What about self-sends? Accordind to the previous examples, self would be updated with the value of message. While it might sound counter-intuitive or plain absurd, this is what we need:

Point>>moveX: offsetX y: offsetY
self x=: self x + offsetX. 
self y=: self y + offsetY.
^ self

Assuming #x: and #y: return copies of the objects, wihth this semantics, the reference to self on the last line corresponds to the last copy created.

The only difference between self-sends and regular sends is the implicit contract that is assumed for the method. In the regular case, the message send can return any object. Any invocation of the returned object will happen with a regular send that will in the worst case raise a message not understood exception. For self-sends to work as in the example above, messages #x: and #y: must return instances of Point, so that the activation frame can be updated correctly. Updating the activation frame rebinds self to the new object, but preserves the temporary variables.

(I believe this would have an incidence on closures. More investigations are needed. The precise semantics could maybe be simulated with continuations)

Copy syntax

The previous proposal still leaves the burden of copying the objects to the developers. In the previous examples, #x: , #y: and #at:put: would need to first clone the receiver (self), then update it.

Point>>x: newX
^ ( self clone ) basicX: newX ; yourself.

Ugly, right? Following a similar syntactic approaches, message sends could be prefixed with % to indicate that the message must be delivered to a clone of the receiver:

aReference %message: 5 <--> aReference clone message: 5

We know that cloning is broken. However, it is not the subject of this post, so we will assume that we have a reasonable implementation of #clone. With % and = we have all ingredient to implement immutable structures easily.

Point>>x: newX
  self basicX: newX

Point>>moveX: offsetX y: offsetY
self %x=: self x + offsetX. 
self %y=: self y + offsetY.
^ self

(The accessor Point>>x is actually superfluous, since it is similar to basicX. It serves as example only.)

For an even more concise syntax, a third prefix/postfix could be introduced.

aReference ~message: 5 <--> aReference %message=: 5

Nested Objects

The proposed syntactic suggar has limited benefits for more complex mutation of objects with nested objects. Let’s consider an immutable circle with an immutable point as center.

Circle>>moveX: offsetX y: offsetY
   self ~center: (self center %moveX: offsetX y: offsetY )
  ^ self

But what we would really like to write is

Circle>>moveX: offsetX y: offsetY
   self center ~moveX: offsetX y: offsetY
  ^ self

Handling this situation so that the receiver “self center” is replaced with the new point, implies first the replacement of “self” with a new circle. The replacement of the receiver “self center” (that is not an L-value) could be achieved if by convention the corresponding setter is used. The above code would then execute implicitely “self ~center: xxx” to replace “self center”. This corresponds to the intended behavior. In other words,

self a ~m: args <--> self ~a: (self a %m: args)
self a b ~m: args <--> self ~a: (self a %b: (self a b %m: args))
etc.

The ~ can appear only before the last message send. The statement “self a ~b m: args” would be ill-defined.

More Links

Transformation for Class Immutability

Object-Oriented Equality

I discussed in my previous post the fact that we need a better support of immutability in object-oriented language. The problem is that it’s no so easy to add because the object paradigm is rooted in the concept of an object being an entity whose state is normally mutable. I discuss here about one of its cousin: object equality.

Some objects are more equal than others

First a quick recap. Object equality is an equivalence relation traditionally implemented through equals and hashCode. Here is the corresponding Javadoc:

The equals method implements an equivalence relation on non-null object references:
•    It is reflexive: for any non-null reference value x, x.equals(x) should return true.
•    It is symmetric: for any non-null reference values x and y, x.equals(y) should return true if and only if y.equals(x) returns true.
•    It is transitive: for any non-null reference values x, y, and z, if x.equals(y) returns true and y.equals(z) returns true, then x.equals(z) should return true.
•    It is consistent: for any non-null reference values x and y, multiple invocations of x.equals(y) consistently return true or consistently return false, provided no information used in equals comparisons on the objects is modified.
•    For any non-null reference value x, x.equals(null) should return false.

The definition implicitly allows mutable state to be used for equality. This is however dangerous, and equals should be defined only based on immutable state when possible.

This is notably a requirement for Collections, which require a stronger equality contract. If the object equality changes while it is in the collection, the behavior of the collection may not be consistent. See pitfall #3 in How to write equality in Java.

The simplest solution to this problem is to make object equality immutable, that is, the fields participating in the equivalence relation are final – the equality can never change post-construction.

This is however not always possible, especially if the object requires an initialization in a post-construction phase. If the object equality depends on related objects, a strictly immutable object might still see its hashCode change if one of the depending object is mutated. This leads to the concept of ownership, where object that are owned should also be immutable. Pure ownership is however an object-level/run-time concern which is not easy to ensure (class-based ownership is possible but more limited).

As presented in “Understanding the Impact of Collection Contracts on Design”, we should then consider (i) the construction of object (ii) the mutability of the object state and (iii) the “deepness” of the equivalence relationship to reason about object equality.

We have then actually three types of fields:

–    final. Never change post-construction and referenced object is immutable
–    eventually final. Can change post-construction but will be frozen in a point in time
–    mutable. Can be mutated anytime.

Object could be frozen post-creation as is proposed in “Flexible immutability with frozen objects”. The equivalence relation could use only final and eventually final fields. Owned object could be modified only through the parent object, as to ensure that the equality contract is never broken.

There is no one notion of equivalence

The problem remains that there is not “correct” implementation of object equality. It mostly depends on the usage. You may want to compare list based on reference identity, but also based on their content sometimes. Should we then have a notion of  “deepness” right into the equals operator, in a way similar to the variants of shallow and deep cloning?

aList.deepEquals( anotherList )

Well, that’s actually what already exists with OrderedCollection, where you specify the Comparator to be used. Is it the solution? Should we remove the object equality form the object and move it the client of the object?

Set s = new HashSet( new ReferenceEqualityContract() );

Or should we be able to instantiate an object and specify which equality contract (or more generally a comparison contract) it should fulfill?

In this case, an object is limited to have only one equivalence relation at a time.  (See this post for a Haskell sample of how to do it)

One could specify the behavior of the object at creation time and see that as an object-level behavioral variation. The types of two objects with different equivalence relation should however be different to ensure the relation is always symmetric (objects with different equivalence relation are always different). This means that the each specific variation would correspond to a type, which inherits from a common type.

– Is object equality as subset of the problem of object comparison? Or are they fundamentally different? State used for comparison shouldn’t change while object is in collection, but it’s no necessary part of the “primary key”…

– Should an object have only one equivalence or comparison definition at a time? Or could an object have several ones at the same time? Or one equivalence relation but several comparison definitions at a time? (We could easily imagine two lists with the same objects, but one list storing the object in ascending order and the other one in descending order)

The fact is that in a pure object world we should uniquely compare object by reference. There should be no two objects with the same “primary key”. In “Declarative object identity using relation type“, the authors introduced the notion of scope as to create and obtain the same reference for a given key. The risk then is to alter objects in an unexpected way and break other object invariants (dangling alias, etc.). It is simply impractical. The world is constantly evolving, and we are forces sometimes to have two objects for the same entity: one for the old and one for the new entity (See this other post on persistent data structure). Such objects somehow relates together and are not completely “different”, hence the notion of object equality.

But this little digression still doesn’t solve the issue that whatever the equality contract that the object must fulfill, we cannot ensure that it will be the case.

And it gets worse with inheritance

“There is no way to extend an instantiable class and add a value component while preserving the equals contract, unless you are willing to forgo the benefits of object-oriented abstraction.”  — Effective Java

Indeed if we have a Point class and a ColorPoint class, the equivalence relation may be broken if ColorPoint doesn’t redefine equals and hashCode. See pitfall #4 in How to write equality in Java. To enforce the equality contract, two objects may be equal only if they have the same type.

The problem is that it is too restrictive. A context that uses color points, such as a graphic editor, may want to share the points with a context that doesn’t have a notion of color, such as 2D algorithm.  The graphic editor would test the equivalence of two figures according to the color as well. And the 2D algorithm would test the equivalence of two points according to their position solely, in a way to prevent division by zero.

Also, once an object has overridden the default equals and hashCode which implements reference equality, it is also impossible for an object to fall back to this mode. As a consequence we may end up in a situation with subclasses whose equivalence relation can’t be expressed. In such case, it should be forbidden to compare objects.

Should we then re-think object equality with ternary logic, so as to be able to return true, false and N/A?

EDIT

Here I will gather other links related to the subjects

Object-Oriented Immutability

There seem to be a growing awareness about the benefit of immutability. Particular cases where immutable objects are much welcome are for instance in the case of value objects or for defensive copying. The problem is that immutable object don’t really go well with the object paradigm.

Let’s consider an application, which need to deal with the concept of revision. A revision is composed of a major and a minor revision number, e.g. “1.4”. This is typical candidate for a value object. The only sensible methods that deal with revision are inc which increases it, and promote which jumps to the next major version (“1.3” -> “2.0”). I will consider only inc in this post.

Here would be the (trivial) code in Java:

public class Revision
{
   private final int major;
   private final int minor;
   public Revision( int major, int minor ) { ... }

   public Revision inc() {
       return new Revision( major, minor+1 );
   }
}

This is however only a ad-hoc solution. This does not work well with polymorphism for instance: if a subclass of Revision is created, say NameRevision, calling inc on an instance would result in a Revision not NameRevision. This problem can be solved in other ways, and would for instance not appear in Smalltalk where instanciation would be done with super.basicNew on the class-side. But this just shows how mainstream OO language are not designed for immutability.

How would that be in a functional language such as Clojure? A map would probably be used to hold the major and minor number and the inc function would be as simple as setting a new value to the minor key in the map. Because any data modification results in a new structure, we don’t have the explicity make a difference between creating and modifying a structure. See my discussion on persitente data structure

(defn create-revision [] (hash-map :minor 1 :major 0))
(defn inc-revision [r] (assoc r :minor ( + (get r :minor) 1 ))

Note that the inc function is “polymorphic” in the sense that if I pass a map with :minor, :major and :name, I obtain a copy which has the three keys values.

The fundamental mismatch between OO and functional programming is that assignment has different semantics. In OO, assignment change the data in-place. In functional programming, assignments result in a copy.

And what if assignment would also result in a copy in OO? That sounds a bit contradictory to the OO spirit, but well, let’s give it a try…

If assignments result in a copy, this means that something like this.field = “newvalue” actually returns a new instance of the object, right? We could then imagine a class like this:

public class immutable Revision
{
   int major;
   int minor;

   public int getMajor {
      return this.major
   }

   public Revision setMajor( int value ) {
      // assignment result in a copy!
      return ( this.major = value );
   }

   // same for minor

   public Revision inc()  {
      return this.setMajor( this.getMinor() + 1 );
   }
}

We can somehow see that a generalized form of the builder pattern, and it fit well with fluent interface:

Revision r = new Revision( 1, 0 );
r.inc(); // return 1,1
r.inc(); // return 1,1

But

Revision r =
new Revision( 1, 0 )
.inc()
.inc(); // return 1,2

Note the keyword immutable that is necessary to specify the semantics of assignment for the class (there will indeed always be some mutable classes).

We now have two semantics for the assignment, one producing a copy and one changing the data in-place.

That sounds logical, that all classes in class hierarchy share the same mutability.  Assigning a field from a subclass or a superclass should indeed produce the same result. But at the same time, this also means that we have two Object types? One mutable and one immutable? Hmm…

Another sound restriction for such a language would be to have assignment restricted to this. Something like obj.field = "newvalue" would be forbidden. This is anyway a good practice.

Also assuming that the language supports closures, do they fit in the picture? I would say yes, but I’m not sure. Given the signature of the closure is determined (it’s a function after all), and it cannot access any field of the object directly, so the semantics should be consistent.  This would however require a bit more formalization to ensure there is no hole…

Like in some other post, I don’t know if the idea presented here hold for real. But I do like immutable object even in OO, and think that OO language lacks supports for such design. Current solution for immutable object is ad-hoc, but we could imagine blending functional programming and OO a bit more, resulting in some object having a hybrid behavior. Such object would essentially be immutable data structure embedding at the same time the function that corresponds to them, which still fit the equation Object = Data + Logic.

More About Immutability

  • To mutate or not to mutate?
  • Frozen object in ruby
  • Java.next : immutability “But the benefit of using immutable data increases when you compose objects together. If you wanted to compose the synchronized version with another object, you would have have to dig back into the internals of both objects, study their locks, and pick a new lock strategy to cover the two objects together. Composing operations with immutable objects is much easier.”

Persistent Data Structures

I read recently the post “Persistence is a subset of immutability” and was then surprised to discover that Clojure shared the exact same concept of “persistent data structure”, which turned out to be a concept common to all functional language.

Still, I don’t like this terminology of “persistent data structure”.

“A persistent data structure is a data structure which always preserves the previous version of itself when it is modified; such data structures are effectively immutable, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure.”

This definition is completely confusing to me. One the one hand it says that the structure is immutable and that invoking an operation on such a structure produces a new structure. This is ok to me.

One the other hand, it speaks about some form of versioning, as if both the old and the new version had some relationship. This implies then a notion of identity.

“An identity is indeed a logical entity which associate a series of different values over time.”

This is not ok. Both structures are maybe related implementation-wise (the newest structure being merely a diff over the previous one), but from point of view of the client, both structures are unrelated. From point of view of the client, data structure are immutable. Period.

Heraclitus, a greek philosopher, pioneered the concept of identity and state with his famous saying: “You can not step twice into the same river.” He recognizes the changing of objects with the flow of time.

This corresponds to the mutable references in Clojure. References are the only construction that can be mutated.

If the state of an entity changes over time, Einstein was the first one to recognize that the notion of simultaneity is not absolute but depend on the observer.

This corresponds to the transactional memory model in Clojure. At a given time, two different observers will observe two different states of the same entity.  We can indeed see transactional memory as a kind of special asynchronous replication: each observer (thread) has a complete snapshot of the world and synchronization between the snapshots happens at commit time. The sequence of state that can be observed is however always the same and the causality between events is preserved.

More links