[Vm-dev] Re: Immutability, newspeak (was: Vm-dev post from jbaptiste.arnaud@gmail.com requires approval)

[Andreas Raab]

On 6/9/2010 11:40 AM, Eliot Miranda wrote:
>     Secondly, for concurrency uses (which is the aspect that interests
>     me most) the "kind" of immutability proposed here is wrong. What's
>     proposed here is a one-level immutability which is really more a
>     kind of write barrier, i.e., it gets turned on, then it gets caught,
>     then it gets turned off, and is written to anyway. For concurrency,
>     you need immutability that is a) transitive (i.e., freezes an entire
>     object graph) and b) irreversible (i.e., sealing the object graph).
>
>
> That's fine and one can build deep immutability above the shallow
> immutability that the immutable bit provides.  All one needs to do is
> traverse the object graph, setting the immutability bit.  You might want
> to carefully control unsetting the immutability bit so that its hard to
> inadvertently turn off immutability in substructure to get b).  But in
> any case turning off immutability on something that is immutable is
> never  something that's done lightly.
>
> I have at least discussed using shallow immutability to implement deep
> immutability with Gilad for Newspeak and he hasn't yet said it can't be
> done this way.

The issue isn't "implementing" deep immutability, the issue is "proving" 
that something is deeply immutable. Here is the use case: For 
concurrency as in E, Erlang and others, the goal is to share immutable 
objects between different concurrent units. To do this effectively, you 
must *prove* that a structure you're passing on is deeply immutable. 
There are two effective ways of doing this:

1) Have a flag that says that the object is deeply immutable and that 
only ever gets updated by freezing objects that are itself deeply immutable.
2) Traverse the object graph to prove deep immutability.

Option #2 wouldn't be so bad if not for the following problem: In order 
to prove non-trivial (circular) immutability you'll have to run a GC-ish 
algorithm which (unless you've got yet another header bit ;-) becomes 
inefficient since you'll have to throw out your current allocation state 
(the way image segments do it) which causes major inefficiencies.

And of course, allowing objects to become mutable again just throws 
everything out of the window...

> Note tat deep immutability is a tricky issue.  Is the class of a deeply
> immutable object immutable or can one still add methods to it?

The object and its contents are immutable, not its class. The class 
could separately be immutable (there is a longer argument here why 
that's The Right Thing to do even for deeply frozen structures).

> What
> happens (with both shallow and deep immutability) if one tries to add an
> instance variable to a class that has immutable instances?

The same as with one-level immutability; there is no difference. An 
instance can be updated and inherits the flags of the old instance. And 
become is already allowed to modify "immutable" instances, no?

> What if one
> wants a mostly deeply immutable data structure that contains e.g. a
> mutable query cache that memos the most recent N results of some
> expensive query?  Exactly what parts of a data structure should be
> immutable when is typically application and data structure dependent and
> some blanket deep immutability scheme in the VM is likely to be too
> inflexible.  A simple per-object bit which has simple semantics and can
> serve in many different uses is flexible enough, at least if 15 years of
> experience with VisualAge and 10 years of experience with VW is meaningful.

But in what applications? I suspect that the answer is "object 
databases, object databases, and ... err ... object databases" ;-)

(not that I'm saying that object databases aren't useful or important 
but I suspect this particular use of immutability is not remotely as 
general in practice as people seem to imply - and if I'm wrong, I'm 
looking forward to learning something new here)

>     So should we add two header bits for immutability instead of one?
>     What concerns me here is that any use of immutability appears to be
>     requiring yet another header bit - a sign that we thoroughly do not
>     understand what immutability is and how it should be implemented.
>     Thus my feeling that throwing header bits at the problem is the
>     wrong direction.
>
>
> Agreed.  I'm not proposing throwing bits at the problem.  One bit's
> enough.  Its up to the image level to design a good framework around the
> basic VM facility, and that's been done already.

Same thing. It would help to provide a few concrete examples.
What has been done, where, and what's it used for?

>     I'm not strongly opposed to it but header bits *are* a scarce
>     resource so their allocation should be done carefully as well as the
>     choice of semantics. I can say for sure that I would feel *much*
>     better if there was a customer who'd say "yes, this is exactly what
>     I need, the semantics is precisely right for what I need it for"
>     instead of just "Oooooohhhh, immutability, cooooool" (which is all
>     I'm hearing).
>
>
> While some people might be saying "it's cool" I hear the GemStone folks
> saying "we much prefer using the immutability bit than rewriting code.
>   the immutability bit has worked much better in practice", and GemStone
> has plenty of customers who don't have to worry about the issue because
> GemStone has done all the work for them. I don't hear anyone from
> VisualAge and VisualWorks saying "It's a bad idea, it's had a
> deleterious effect on performance".

Actually, I think the opposite is true. If you could use immutability 
for (lock-free) concurrency, I suspect that this is going to save a 
*lot* more cycles than it costs. Both in the CPU and your brain ;-)

Cheers,
   - Andreas