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

Eliot Miranda eliot.miranda at gmail.com
Thu Jun 10 00:15:55 UTC 2010

On Wed, Jun 9, 2010 at 3:27 PM, Andreas Raab <andreas.raab at gmx.de> wrote:

> 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.

The issue is of course both.  How one implements deep immutability /is/ a
worthy topic of discussion (as this thread demonstrates) and not something
that can be condescended away by shifting levels.

> 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.

Option 2 can be written in Smalltalk without a data structure to record the
visited set by provisionally setting the immutability bit to terminate the
recursion, unsetting it if the attempt to freeze substructure failed.

Further, option 2 can be implemented at instance creation time so a root
object is only instantiated if all its parts are immutable and an attempt to
do otherwise fails.  If one has to prove that an object is immutable after
instantiation something is wrong.  The framework should support maintaining
immutability throughout an object's lifetime.

So trivially shallow immutability can implement deep immutability if a
system provides no way to turn-off shallow immutability once on and if an
object is created shallowly immutable but having only immutable
substructure.  The issue then becomes when to allow immutability to be
temporarily rescinded, e.g. for instance mutation on class redefinition.

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

Which has already been discussed.  One can take various approaches to
preventing immutability being reset.  It is possible to build a general
framework that allows some objects to toggle their immutability sate (e.g.
to implement write barriers) while others refuse to (e.g. to implement deep

>  Note that 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.

Right; a convenient default for a typical Smalltalk development system.

> And become is already allowed to modify "immutable" instances, no?

FWIW, in VW a symmetric become: fails it either object is immutable &
one-way become always succeeds, and I'm not sure the latter is correct.  It
depends on usage.  Some uses of one-way become are legit (mutating existing
instances when class definitions change), others are not.

 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)

You've already discussed a broad use category in introducing concurrency
above.  Another broad category is being able to pass by value in a
distributed system.  Another is providing immutable literals.  None of these
are to do with OODBs.

>     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?

In VW there's a Modification Management framework that supports attaching
modification behaviours to specific objects.  By default an attempt to
modify an object is an error (except by the class builder).  Managers
attached to specific objects can handle modification errors in various ways
depending on the application.  Above that you implement what you want,
including GemStone's persistence framework.

    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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20100609/f6c823f6/attachment-0001.htm

More information about the Vm-dev mailing list