Can an immutable type change its internal state?

Question

The question is simple. Can a type that can change its internal state without it being observable from the outside be considered immutable?

Simplified example:

public struct Matrix
{
    bool determinantEvaluated;
    double determinant;

    public double Determinant 
    {
         get //asume thread-safe correctness in implementation of the getter
         {
             if (!determinantEvaluated)
             {
                  determinant = getDeterminant(this);
                  determinantEvaluated = true;
             }

             return determinant;    
         }
    }
}

UPDATE: Clarified the thread-safeness issue, as it was causing distraction.

Answer 1

The purpose of specifying a type to be immutable is to establish the following invariant:

• If two instances of an immutable type are ever observed to be equal, any publicly-observable reference to one may be replaced with a reference to the other without affecting the behavior of either.

Because .NET provides the ability to compare any two references for equality, it's not possible to achieve perfect equivalence among immutable instances. Nonetheless, the above invariant is still very useful if one regards reference-equality checks as being outside the realm of things for which a class object is responsible.

Note that under this rule, a subclass may define fields beyond those included in an immutable base class, but must not expose them in such a fashion as to violate the above invariant. Further, a class may include mutable fields provided that they never change in any way that affects a class's visible state. Consider something like the hash field in Java's string class. If it's non-zero, the hashCode value of the string is equal to the value stored in the field. If it's zero, the hashCode value of the string is the result of performing certain calculations on the immutable character sequence encapsulated by the string. Storing the result of the aforementioned calculations into the hash field won't affect the hash code of the string; it will merely speed up repeated requests for the value.

Answer 2

It depends.

If you are documenting for authors of client code or reasoning as an author of client code, then you are concerned with the interface of the component (that is, its externally observable state and behavior) and not with its implementation details (like the internal representation).

In this sense, a type is immutable even if it caches state, even if it initializes lazily, etc - as long as these mutations aren't observable externally. In other words, a type is immutable if it behaves as immutable when used through its public interface (or its other intended use cases, if any).

Of course, this can be tricky to get right (with mutable internal state, you may need to concern yourself with thread safety, serialization/marshaling behavior, etc). But assuming you do get it right (to the extent you need, at least) there's no reason not to consider such a type immutable.

Obviously, from the point of view of a compiler or an optimizer, such a type is typically not considered immutable (unless the compiler is sufficiently intelligent or has some "help" like hints or prior knowledge of some types) and any optimizations that were intended for immutable types may not be applicable, if this is the case.

Answer 3

Yes, immutable can change its state, providing that the changes are unseen for other components of the software (usually caches). Quite like quantum physics: an event should have an observer to be an event.

In your case a possible implementation is something like that:

  public class Matrix {
    ...
    private Lazy<Double> m_Determinant = new Lazy<Double>(() => {
      return ... //TODO: Put actual implementation here
    });

    public Double Determinant {
      get {
        return m_Determinant.Value;
      }
    }
  }

Note, that Lazy<Double> m_Determinant has a changing state

m_Determinant.IsValueCreated 

which is, however, unobservable.

Answer 4

I'm going to quote Clojure author Rich Hickey here:

If a tree falls in the woods, does it make a sound?

If a pure function mutates some local data in order to produce an immutable return value, is that ok?

It is perfectly reasonable to mutate objects that are expose APIs which are immutable to the outside for performance reasons. The important thing about immutable object is their immutability to the outside. Everything that is encapsulated within them is fair game.

In a way in garbage collected languages like C# all objects have some state because of the GC. As a consumer that should not usually concern you.

Answer 5

I'll stick my neck out...

No, an immutable object cannot change its internal state in C# because observing its memory is an option and thus you can observe the uninitialised state. Proof:

public struct Matrix
{
    private bool determinantEvaluated;
    private double determinant;

    public double Determinant
    {
        get
        {
            if (!determinantEvaluated)
            {
                determinant = 1.0;
                determinantEvaluated = true;
            }

            return determinant;
        }
    }
}

then...

public class Example
{
    public static void Main()
    {
        var unobserved = new Matrix();
        var observed = new Matrix();

        Console.WriteLine(observed.Determinant);

        IntPtr unobservedPtr = Marshal.AllocHGlobal(Marshal.SizeOf(typeof (Matrix)));
        IntPtr observedPtr = Marshal.AllocHGlobal(Marshal.SizeOf(typeof(Matrix)));

        byte[] unobservedMemory = new byte[Marshal.SizeOf(typeof (Matrix))];
        byte[] observedMemory = new byte[Marshal.SizeOf(typeof (Matrix))];

        Marshal.StructureToPtr(unobserved, unobservedPtr, false);
        Marshal.StructureToPtr(observed, observedPtr, false);



        Marshal.Copy(unobservedPtr, unobservedMemory, 0, Marshal.SizeOf(typeof (Matrix)));
        Marshal.Copy(observedPtr, observedMemory, 0, Marshal.SizeOf(typeof (Matrix)));

        Marshal.FreeHGlobal(unobservedPtr);
        Marshal.FreeHGlobal(observedPtr);

        for (int i = 0; i < unobservedMemory.Length; i++)
        {
            if (unobservedMemory[i] != observedMemory[i])
            {
                Console.WriteLine("Not the same");
                return;
            }
        }

        Console.WriteLine("The same");
    }
}