Immutable or not immutable?

Question

Ok, as I understand it, immutable types are inherently thread safe or so I've read in various places and I think I understand why it is so. If the inner state of an instance can not be modified once the object is created there seems to be no problems with concurrent access to the instance itself.

Therefore, I could create the following List:

class ImmutableList<T>: IEnumerable<T>
{
    readonly List<T> innerList;

    public ImmutableList(IEnumerable<T> collection)
    {
         this.innerList = new List<T>(collection);
    }

    public ImmutableList()
    {
         this.innerList = new List<T>();
    }

    public ImmutableList<T> Add(T item)
    {
         var list = new ImmutableList<T>(this.innerList);
         list.innerList.Add(item);
         return list;
    }

    public ImmutableList<T> Remove(T item)
    {
         var list = new ImmutableList<T>(this.innerList);
         list.innerList.Remove(item);
         return list;
    } //and so on with relevant List methods...

    public T this[int index]
    {
        get
        {
            return this.innerList[index];
        }
    }

    public IEnumerator<T> GetEnumerator()
    {
        return innerList.GetEnumerator();
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return ((System.Collections.IEnumerable)this.innerList).GetEnumerator();
    }
}

So the question is: Is this really an immutable type? Is it really thread safe?

Obviously the type itself is immutable but there is absolutely no garantee that T is and therefore you could have concurrent access and threading issues related directly with the generic type. Would that mean that ImmutableList should be considered mutable?.

Should class ImmutableList<T>: IEnumerable<T> where T: struct be the only type truly considered immutable?

Thanks for any input on this issue.

UPDATE: A lot of answers/comments are concentrating on the particular implementation of ImmutableList I've posted which is probably not a very good example. But the issue of the question is not the implementation. The question I'm asking is if ImmutableList<MutableT> is really an immutable type considering everything that an immutable type entails.

Answer 1

If the inner state of an instance can not be modified once the object is created there seems to be no problems with concurrent access to the instance itself.

That is generally the case, yes.

Is this really an immutable type?

To briefly sum up: you have a copy-on-write wrapper around a mutable list. Adding a new member to an immutable list does not mutate the list; instead it makes a copy of the underlying mutable list, adds to the copy, and returns a wrapper around the copy.

Provided that the underlying list object you are wrapping does not mutate its internal state when it is read from, you have met your original definition of "immutable", so, yes.

I note that this is not a very efficient way to implement an immutable list. You'd likely do better with an immutable balanced binary tree, for example. Your sketch is O(n) in both time and memory every time you make a new list; you can improve that to O(log n) without too much difficulty.

Is it really thread safe?

Provided that the underlying mutable list is threadsafe for multiple readers, yes.

This might be of interest to you:

http://blogs.msdn.com/b/ericlippert/archive/2011/05/23/read-only-and-threadsafe-are-different.aspx

Obviously the type itself is immutable but there is absolutely no garantee that T is and therefore you could have concurrent access and threading issues related directly with the generic type. Would that mean that ImmutableList<T> should be considered mutable?.

That's a philosophical question, not a technical one. If you have an immutable list of people's names, and the list never changes, but one of the people dies, was the list of names "mutable"? I would think not.

A list is immutable if any question about the list always has the same answer. In our list of people's names, "how many names are on the list?" is a question about the list. "How many of those people are alive?" is not a question about the list, it is a question about the people referred to by the list. The answer to that question changes over time; the answer to the first question does not.

Should class ImmutableList<T>: IEnumerable<T> where T: struct be the only type truely considered immutable?

I'm not following you. How does restricting T to be a struct change anything? OK, T is restricted to struct. I make an immutable struct:

struct S
{
    public int[] MutableArray { get; private set; }
    ...
}

And now I make an ImmutableList<S>. What stops me from modifying the mutable array stored in instances of S? Just because the list is immutable and the struct is immutable doesn't make the array immutable.

Answer 2

Immutability is sometimes defined in different ways. So is thread-safety.

In creating a immutable list whose purpose is to be immutable, you should document just what guarantees you are making. E.g. in this case you guarantee that the list itself is immutable and does not have any hidden mutability (some apparently immutable objects are actually mutable behind the scenes, with e.g. memoisation or internal re-sorting as an optimisation) which removes the thread-safety that comes from immutability (though one can also have such internal mutations performed in a manner that guarantees thread-safety in a different way). You are not guaranteeing that the objects stored can be used in a thread-safe manner.

The thread-safety that you should document relates to this. You can not guarantee that another object won't have the same object (you could if you were creating new objects on each call). You can guarantee that operations will not corrupt the list itself.

Insisting upon T : struct could help, as it would mean that you could ensure that each time you return an item, it's a new copy of the struct (T : struct alone wouldn't do that, as you could have operations that didn't mutate the list, but did mutate its members, so obviously you have to also do this).

This though limits you in both not supporting immutable reference types (e.g. string which tends to be a member of collections in lots of real-world cases) and doesn't allow a user to make use of it and provide their own means of ensuring that the mutability of the contained items doesn't cause problems. Since no thread-safe object can guarantee that all the code it is used in is thread-safe, there's little point tryint to ensure that (help as much as you can by all means, but don't try to ensure what you can't ensure).

It also doesn't protect mutable members of immutable structs in your immutable list!

Answer 3

Using your code, let's say i do this:

ImmutableList<int> mylist = new ImmutableList<int>();

mylist.Add(1); 

... your code, posted on StackOverflow, causes a StackOverflow-Exception. There are quite a few sensible ways to create thread save collection, copying collections (at least trying to) and calling them immutable, a lot, doesn't quite do the trick.

Eric Lippert posted a link that might be very worth reading.

Answer 4

A prime example of a data type that behaves as an immutable list of mutable objects: MulticastDelegate. A MulticastDelegate may be modeled pretty accurately as an immutable list of (object, method) pairs. The set of methods, and the identities of the objects upon which they act are immutable, but in the vast majority of cases the objects themselves will be mutable. Indeed, in many if not most cases, the very purpose of the delegate will be to mutate the objects to which it holds references.

It is not the responsibility of a delegate to know whether the methods it's going to invoke upon its target objects might mutate them in thread-unsafe fashion. The delegate is responsible merely for ensuring that its lists of functions and object identities are immutable, and I don't think anyone would expect it to likewise.

An ImmutableList<T> should likewise always hold the same set of instances of type T. The properties of those instances might change, but not their identity. If a List<Car> was created holding two Fords, serial #1234 and #4422, both of which happened to be red, and one of the Fords was painted blue, what started out as a list of two red cars would have changed to a list holding a blue car and a red car, but it would still hold #1234 and #4422.

Answer 5

I believe that one thing adding to the rather lengthy discussion on this topic is that immutability/mutability should be considered along with scope.

As an example:

Say that I am working with a C# project and I define a static class with static data structures, and I define no way to modify those structures in my project. It is in effect a read-only cache of data that I can use, and for the purposes of my program, it is immutable from one run of my program to the next. I have total control over the data, and I/the user am/is unable to modify it at run time.

Now I modify my data in my source code and re-run the program. The data has changed, so in the highest sense of the word, the data is no longer immutable. From the highest level perspective, the data is actually mutable.

I would therefore posit that what we need to be discussing is not the black and white question blanketing something as immutable or not, but rather we should consider the degree of mutability of a particular implementation (as there are few things that actually never change, and are therefore truly immutable).

Answer 6

I would say that generic list is not immutable if the element is mutable, because it does not represent the full snapshot of the data state.

To achieve immutability in your example you would have to create deep copies of list elements, which is not efficient to do every time.

You can see my solution to this problem at IOG library