Part 1

What exactly do I mean by "immutable"? 

Something that is immutable doesn't change. Literal numbers, like 1, are immutable in almost all programming languages. Strings, like "hello world", are immutable in some languages, like C#, and not in others, like C.

Most of the time we just "get it". Take this example:
 
 
int i = 0;
int j = i;
j += 1;
print i;
print j;

If this outputted "0 1" it would be doing exactly what we expected. That's because we naturally assume integers are value types and immutable. That same logic allows us to write:
 
 
int i = 88;
int j = 90;
j -= 2;
print i == j;

and expect the answer to be "true". That because it doesn't matter how i and j become the same value, it's the value that is compared.

Now take: 
 
 
HashTable i;
HashTable j = i;
j.Insert("a", 1);
print i;
print j;
 
Now we'd expect output something like '{"a" 1} {"a" 1}' even though the code follows this code follows the same pattern as the code above. That's because we've been trained to think of complex objects like hash tables as being mutable, and the treat their assignment as being by reference; which is to say we don't expect "j = i" to create a completely new copy of the hash table "i" and place it in "j" because that would be inefficient. (or would it?)

And if we wrote:
 
 
HashTable i;
i.Insert("a",1);
HashTable j;
j.Insert("a",1);
print i == j;

We're expect the answer to be "false"; i and j are not the same hash tables even though they contain the same data.

Now consider this:
 
HashTable i;
HashTable j = i;
async { j.Insert("a", 1); }
async { i.Insert("b", 1); }
print i;
print j;

If you've done any multithreaded programming you're probably cringing right now. We'd have to add locks to make this work reliably, and locks are not efficient.

But if we replace hash table with 'int' something interesting happens:
 
 
int i;
int j = i;
async { j += 1; }
async { i += 1; }
print i;
print j;

Like magic the need for a lock goes away. The two asynchronous blocks no long modify a shared resource.

Okay, so how about:
 
 
F<T>()
{
  T i;
  T j = i;
  async { j(1); }
  async { i(1); }
}

 
That is to say for all types T can we do this safely? We've already shown we can't. So we need to add a constraint on T:
 
 
F<T>() : T is a ValueType
{
  T i;
  T j = i;
  async { j(1); }
  async { i(1); }
}

But that means we can't use F on complex types like our hash table.

What if we could make a complicated structure that did something like what a hash table does, but was a value type? Well we can.