The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

Trade-offs of different Immutability designs

Hi,

I'm wondering what the trade-offs are for the following immutability designs. All examples come from the Java API but please feel free to discuss examples of other platforms as well.

1) Object composition: a mutable class wraps an immutable class without any sort of inheritance. Example: String vs StringBuilder.
2) Single interface with optional operations. Example: List throws UnsupportedOperationException when someone tries modifying an immutable list.
3) Object inheritance: a mutable class extends an immutable class. Example: MutableString extends String by adding mutation methods to it. I could not find an example of this in the JDK.
4) Are there other possible designs you're familiar with?
Gili Send private email
Wednesday, March 05, 2008
 
 
How about mutable objects which provide factory methods which return an immutable version of themselves?

For example, .Net's List.AsReadOnly() which returns a ReadOnlyCollection object.
Tim Hastings Send private email
Wednesday, March 05, 2008
 
 
5) Mutable interface that extends an immutable interface.

This would be my preference, objects would implement both interfaces if they are mutable or just the immutable one if they are not. This way the contract of the object is clearly discernable and does not require invoking a method to determine if it is mutable.
Gerald
Wednesday, March 05, 2008
 
 
2) is OK with me although I'd like to see the interface annotated or named in such a manner as to make its semantics obvious.  This can break down when you are writing to a generic interface that can give no clue.  e.g. List.  I'd prefer to see a more basic list interface that exposes implicitly read-only operations that you would use to implement your immutable. 

3) sounds like a reason why some people are allergic to inheritance. Changing the semantics of a base object via the derived object.  That would be a code smell to me.  Your derived class should behave identically to "String" in all cases where it is provided to objects expecting "String" -- and this would include immutability if that is part of "String"'s contract.

Wrapping it (as StringBuffer does, for example) would make more sense than extending it.
Dan Fleet Send private email
Wednesday, March 05, 2008
 
 
Single interface with the ability to query whether the actual implementation class is mutable or not. Of course, you can also do it using exceptions, and trapping the exceptions, so I suppose I am voting for (2). This is based on my experience with a C++ string interface with various implementations.
Graham Asher Send private email
Wednesday, March 05, 2008
 
 
Gerald, isn't your #5 is identical to my #3?

Dan, I think you misunderstood what I was saying in #3. I agree with you that subclasses may not change the contract of the superclass (this is required by Design by Contract). As such, MutableString must behave identical to a String for the methods inherited from it. All I meant is that MutableString might add extra methods to append data to the string.... Ah! I think I understand your point now! A problem would occur if one thread takes in a String, expecting it to be immutable, but another thread modifies the underlying object which is of type MutableString so the first thread sees the underlying data getting altered which should be impossible. Good point!

Now for a bigger question: Given the fact that the Collections API was designed by Joshua Bloch which is a competent senior designer, why do you suppose he decided to go for #2 instead of #3 or #1? I somehow get the feeling we're missing something here.

My own opinion is that #3 is deceivingly attractive. It seems natural at first, but as you decide to extend it further you run into problems (i.e. composition is more flexible). There is also the problem that Dan pointed out. A MutableString violates the class invariants of a String, which is to say that the underlying data will not change.

The only reason I can see for choosing #2 is when you have multiple optional methods that operate independently of one another. That is, in the case of a List you usually have two kinds of interfaces: MutableList and ImmutableList. So either all your optional methods are implemented or not. But imagine a case where some methods may be implemented but others may not and there is no sort of grouping. In such a case #2 makes more sense to me because you don't want to end up with 10 different classes, one for every possible combination of methods.
Gili Send private email
Wednesday, March 05, 2008
 
 
"A MutableString violates the class invariants of a String, which is to say that the underlying data will not change."

Keep in mind that a truly immutable object won't let you easily change (or possibly even access, even in a derived class) the underlying data, such as by making it final, in Java.  (e.g. String in Java is actually a final class, and can't be extended)

But in a philosophical situation, such as if your derived object played some sort of reflective game on the data, or the base class neglected to enforce its immutability, for example, it's a valid concern.

Another thing to consider is that immutable objects have advantages in multi-threaded applications, and if you were to somehow make it mutable, you break apps that share the object between threads.


As for why the Java Collections are done the way they are, good question.  Perhaps to avoid a lot of little interface specializations, and lacking multiple inheritance, it was deemed cleaner to just let methods throw an UnsupportedOperation or other exception.  It's a bit of a cop-out to me to claim to implement an interface that you actually don't, but it may be a necessary evil.
Dan Fleet Send private email
Wednesday, March 05, 2008
 
 
> Gerald, isn't your #5 is identical to my #3?

No your #3 is using objects whereas I am suggesting using interfaces which is a significant difference IMHO. So for example in Java:

public interface List {
 
  public Object get(int index);

  public int size();

}

public interface MutableList extends List {

  public void add(Object object);

  ...etc

}

public class LinkedList extends List {
 ...
}

public class MutableLinkedList extends LinkedList implements MutableList {

}

You get the idea, the benefit is the usual one with interfaces which is decoupling the implementation from the contract. The benefit of this approach is when you start coding you can have methods like:

//Instantly obvious that it requires a mutable list
//No danger of passing immutable version that would
//raise an exception
public void sort(MutableList list, Comparator c) {

}

Similarly:

//Instantly obvious the list is not going to be changed
//by the method
public Object[] toArray(List list) {

}
Gerald
Wednesday, March 05, 2008
 
 
I just realized something... Doesn't Collections.unmodifiableList(List) violate the immutability class invariant I mentioned?

1) Foo contains a mutable List called "names"
2) Foo.getNames() returns Collections.unmodifiableList(names)
3) The receiver expects getNames() to return an immutable list, but that list might in fact change if the underlying list is modified.

So Java's approach is #2 but it isn't necessarily any better than #3. Crap :(

I guess that's why they called the method unmodifiableList instead of immutableList. The only thing they guarantee is that the *receiver* won't be able to modify the list, not that it would actually be immutable.

So in conclusion, is it fair to say that one should use approach #1 (object composition) unless there are many different interface variants in which case one should use approach #2 (single interface with optional methods)?
Gili Send private email
Wednesday, March 05, 2008
 
 
I still don't see the problem with#3/#5 when based on interfaces instead of classes as that eliminates the composition problem you mention. And yes, I do realize my little example isn't the greatest in terms of MutableLinkedList extending LinkedList, I was just hacking out an example.
Gerald
Wednesday, March 05, 2008
 
 
I suspect the Java collections classes are the way they are to permit increasingly generic reference to them without knowing the underlying implementation.

Iterable -> Collection -> {Set,List,Queue} -> specific implementations


This would be hard to accomplish without multiple inheritance:

interface IReadableCollection
interface IWritableCollection extends IReadableCollection

interface IReadableList extends IReadableCollection
interface IWriteableList extends IWritableCollection and IReadableList oops!



You could keep them all separate and have something like:

abstract class ImmutableList implements IReadableCollection, IReadableList;

abstract class MutableList implements IReadableCollection, IWritableCollection, IReadableList, IWritableList;

But then you don't have your basic "List" or other collection types as interfaces, you have them as classes, and everything would have to derive from one of them.
Dan Fleet Send private email
Wednesday, March 05, 2008
 
 
Dan,

I think you hit the nail on the head. Class inheritance is so disappointing that way. It's so intuitive at the beginning but transforms into a total mess soon thereafter. I actually remember running into a similar hierarchy problem in my own product years back <shudder>

So if I understand you correctly, you just explained the problem with approach #3. Still, it doesn't explain why they didn't go with approach #1. I think that for Collections all optional methods are grouped (immutable or not) so the resulting design shouldn't be too complex. Here is what I was thinking:

Immutable hierarchy: Iterable -> Collection -> {Set,List,Queue} -> specific implementations

Mutable hierarchy: MutableCollection -> Mutable{Set,List,Queue} -> specific implementations

The mutable classes do not inherit from the immutable ones, but return them by composition. So, just like you have StringBuilder.toString() you would have MutableCollection.unmodifiableView() which would returns a Collection, Set, List, Queue depending on your specific implementation (thanks to covariant return types).

Granted you now have twice as many classes as before, but the new API provides extra compile-time checking.
Gili Send private email
Wednesday, March 05, 2008
 
 
Dan,

I'm still not seeing the issue, Java allows an interface to extend multiple interfaces. So your example:

>interface IWriteableList extends IWritableCollection and
> IReadableList oops!

Is perfectly valid in Java

interface IWriteableList extends IWritableCollection, IReadableList {

}
Gerald
Thursday, March 06, 2008
 
 
Gerald, I was commenting on Dan's example of using separate interfaces (i.e. it was becoming a huge mess). You are right that the multiple inheritance approach is much cleaner but I remember running into some serious problems with it before (especially when using Generics). Unfortunately, I don't remember the exact details so I can't comment conclusively one way or another. Does anyone else have a concrete example of why multiple inheritance of interface is problematic?

Also as a sidenote, I think we have all been confusing immutability with unmodifiable, which are not the same thing. The Collection API actually exposes an unmodifiable interface while String exposes a truly immutable interface.

I believe the only way to implement Immutability (in Java) is option 1. The other two options simply won't work. Unmodifiable interfaces, on the other hand, can be implemented using all three approaches.

I am actually curious about both immutable and unmodifiable interfaces.
Gili Send private email
Thursday, March 06, 2008
 
 
Whether something is unmodifiable or immutable is a facet of implementation, so an interface based approach really as no bearing on which is implemented. For example, if you went with my initial hack example of extending classes which derived from interfaces you would probably have an unmodifiable design rather then an immutable design since the classes would likely share fields and inter-operate. However you could certainly code a truly immutable design that implemented the same interfaces as well.

Any time you have multiple inheritance be it classes (in C++) or interfaces you do have to be careful in your design. Having said that in the very few cases where it made sense to do it I have not had any issues with it in Java. I do think this is one of the cases where it makes sense, however I think you would have to take things further and do a more full featured mockup to really understand all the pros and cons.
Gerald
Thursday, March 06, 2008
 
 
In Java, a String is actually an immutable implementor of the CharSequence interface (which, IMO, is not used *nearly* as often as it should be), and StringBuffer and StringBuilder are mutable implementors of that interface.

I like that pattenrn.

The interfaces define the functionality but not the mutability. The classes (which don't use composition in this example, but provide completely different implementations) define the mutability.

Subclassing to change the mutability seems like a really bad idea to me.

I have mixed feelings about the implementation of unmodifiable collections. When an API consumer receives a List as a return value from a method call, it doesn't know whether the List is mutable or not until it tries to mutate the List and an exception is thrown.

The immutability is actually provided by a concrete class (for ArrayList, that class is java.util.Collections$UnmodifiableRandomAccessList) but  it's an undocumented private inner class, so you can't actually use it anywhere in your code. Whenever you want to return an immutable list, you're stuck. You have to just use List as your return type, and consumers of your class will have no idea that the resultant object is immutable.

Lame.

In my opinion, the Collections.unmodifiableList() method should have UnmodfiableList as its return type, and UnmodfiableList should be a public class implementing the List interface.
BenjiSmith Send private email
Thursday, March 06, 2008
 
 
">interface IWriteableList extends IWritableCollection and
> IReadableList oops!

Is perfectly valid in Java"


You are absolutely correct, and I am a bonehead for not remembering this and getting it conflated with multiple (class) inheritance in Java in general.  Shows you how much (zero) I've used this feature.  Guess it's time to refresh my Java basics.

Given this, it reopens the question.  Apart from the larger number of interfaces, it actually breaks down the features of each component fairly solidly.  As long as you laid out your hierarchy carefully you could maintain the usefulness of base interfaces like Iterable. 

Given this the reason they probably didn't is simply because there may not have been a great need for immutable collections (although I could see a need for readonly interfaces that co-incidentally could be implemented by immutable classes if need be).
Dan Fleet Send private email
Thursday, March 06, 2008
 
 
I'll disagree with Benji and state that the interface should define the mutability because it should be part of the contract. He's right in that it's lame that returning a List interface based object doesn't tell you anything about the mutability.

But IMHO he's wrong that the solution is to return a concrete class. Returning a concrete class ties your class to a specific implementation of a List, for example ArrayList versus LinkedList. If you need to change the implementation that is returned by your code for performance or other reasons you are screwed because of all the dependencies on the expected return value being a concrete class.

Having an interface called ImmutableList (or UnmodiableList) means you are not coupled to returning a specific implementation while still correctly indicating that the class is immutable.
Gerald
Thursday, March 06, 2008
 
 
"The interfaces define the functionality but not the mutability. "

This is true.  Immutability is an implementation detail, and unless you have syntax to mark up a definition as being explicitly immutable, the only way to know would be to trust the documentation or inspect the source code.

A readonly interface is subtle, because readonly doesn't mean immutable, and if you really do need an immutable object you'd need to expressly check the implementing type to be certain of it.
Dan Fleet Send private email
Thursday, March 06, 2008
 
 
Heh. 

http://groups.csail.mit.edu/pag/jsr308/dist/jsr308-checkers.html

@Immutable annotation marker (among others)
Dan Fleet Send private email
Thursday, March 06, 2008
 
 
Gerald, you make an excellent point. I'm convinced.

I'm also warming to the idea of WritableList and ReadableList as ways to further subdivide the functionality.

It's not hard to conceive of a class that allows API consumers to add items to a collection, without permitting them the ability to read those items.

Something else I've been thinking about lately is the ability to grant and revoke mutability privileges on objects. An object (like a mutex) could be passed around as a mutability authorization token. Anyone possessing that token could call the mutation methods, but for everyone else, the object would be immutable.

Not a fully baked idea yet... just somthing I've been tossing around.
BenjiSmith Send private email
Thursday, March 06, 2008
 
 
Good spot on the annotations Dan. I agree that true immutability versus readonly is an implementation detail. A base implementation of a List interface, which at a base interface level is read only, could use that immutable annotation to indicate immutability versus readonly.  Another option other then an annotation is to simply have an empty marker intarface called Immutable that could be added to collection implementations.
Gerald
Thursday, March 06, 2008
 
 
"Anyone possessing that token could call the mutation methods, but for everyone else, the object would be immutable"

Be somewhat careful of this.  This is where you can blur the lines of the meaning of "immutable" (or whatever other word you want to use).

A truly immutable object has certain benefits that are violated if it's only "sometimes immutable".  (Thread safety, easy copy by reference, unchanging hash values, etc)
Dan Fleet Send private email
Thursday, March 06, 2008
 
 
Here's an associated question.

For Java, at least, it's been identified as a best practice to use immutable objects where possible.  Yet for whatever reason, the JavaBean model seems prelevant (complete with empty constructors and settors).

Does this mean in practice, immutability isn't all that necessary?
Dan Fleet Send private email
Thursday, March 06, 2008
 
 
I think the need and benefits of immutability is not well understood by the average developer. One of my interview questions is what does it mean to make a class immutable and why would you do it. Not many developers even know the word immutable which is pretty sad and the number of architects who can't answer it is pathetic. Even when you explain the concept they can't explain why you would do it.
Gerald
Thursday, March 06, 2008
 
 
It does occur to me that making something immutable is actually effort.  Not to mention the general number of libraries that expect the JavaBean model, as well as the fact that almost all examples follow this method.

IDEs tend towards spitting out "Getters and Setters" as well.

I will admit that in general, I don't make things immutable unless I have an actual need to, but I've been thinking about the concept more (having known that in general it's a good idea), particularly since I've been evaluating web4j, which is based on immutable model objects.

I see it as a combination of: takes effort (classes are not immutable by default, and it takes some work to train yourself to make them so), being mutable doesn't actually hurt you in most cases, so the benefits of it aren't in-your-face obvious, and a lot of libraries are based around things being mutable.  e.g.: an ORM that loads a model object, you make changes and they're automatically reflected in the database.


Starting to give me flashbacks of getting const correctness  in C++.
Dan Fleet Send private email
Thursday, March 06, 2008
 
 
Guys,

Why do you need to be able to find out whether a List is modifiable or not at runtime? If someone passes you the wrong type of list, don't you want to throw a RuntimeException and move on? Isn't this simply an example of an unrecoverable programming error?

Dan, it is my belief that JavaBeans are evil :) Martin Fowler has written pages on end about how they violate basic OOP principals. JavaBeans exist for the same reason that XML exists: we needed to introduce some convention to enable computers to parse data. This machine-readable language was never meant for human consumption. One day someone came along and decided it would be neat to use them for other tasks. We've been suffering ever since :) I'd say you should only use the JavaBeans convention when you absolutely have to. Otherwise, all your methods should be use-case driven.

For example, you should prefer:

firstAccount.transfer(secondAccount, $100)

to:

firstAccount.setBalance(firstAccount.getBalance() - $100);
secondAccount.setBalance(secondAccount.getBalance() + $100)

1) Exposing object properties defeats Object Encapsulation.
2) Use-case driven APIs are easier to read and use. This is a consequence of the first point because you end up developing better abstractions.
Gili Send private email
Thursday, March 06, 2008
 
 
I think the JavaBean model is so prevalent because Hibernate and Spring depend on it, and everyone uses Hibernate and Spring out of convenience and/or laziness.

But my soul dies a little bit every time I see something like this:

Person p = new Person();
p.setName("Benji");
p.setAge(30);
p.setCoolness(Double.MAX_VALUE);

Can you really construct a valid Person object with no arguments?

Yikes.

A few of the design principles that I always use in my code:

1) I try to make all of my classes immutable and only add mutator methods when it seems unavoidable.

2) If the object will ever serve as the key in a Map, I absolutely will not make it mutable.

3) If the class has a no-arg constructor and/or setter methods, then those methods must return semantically valid objects. Calling a method should never result in an object that violates its contract invariants.

4) Some classes that need the advantages of both mutability and immutability can be implemented so that all mutator methods return new instances of the object, with the changed state.

This is cool because those objects can still be used as Map keys, but it doesn't prevent them from being arbitrarily mutated. As a bonus, it also enables method-call chaining, which can be very handy:

Sandwich hamAndCheese = new Sandwhich(RYE_BREAD)
  .add(HONEY_HAM).add(SWISS).add(TOMATO);

At any point in the method call chain, you get a valid sandwich. And yet, a sandwich is still immutable, so I can use it as a map key:

Map<Sandwich, Price> menu = getMenuFromSomewhere();
menu.add(hamAndCheese, new Price(5.99));

Fun fun fun.
BenjiSmith Send private email
Thursday, March 06, 2008
 
 
Gili:
"Why do you need to be able to find out whether a List is modifiable or not at runtime? If someone passes you the wrong type of list, don't you want to throw a RuntimeException and move on? Isn't this simply an example of an unrecoverable programming error?"

Not at runtime. At compile time.

If the Collections.unmodifiableList() method returned an instance of a ReadOnlyList interface, then you could write your code against that interface, and the compiler would check it for you.

That way, you'd avoid those unrecoverable programming errors to begin with.
BenjiSmith Send private email
Thursday, March 06, 2008
 
 
Benji,

Agreed. I must have misread one of your earlier comments.
Gili Send private email
Thursday, March 06, 2008
 
 
Guys, I want to thank you for this conversation, it's given me some interesting perspectives to consider.  I appreciate it.
Dan Fleet Send private email
Friday, March 07, 2008
 
 
Dido :)
Gili Send private email
Sunday, March 09, 2008
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz