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

> You think its cheap to scan methods for mutablity??  Remember you have to identify inst var writes not just mutating primitives like at:put:.

in our experimentation on doing a per reference flow of security property (pure research) we have to check all the iv store and this is not
something I would do on a real solution.

I have the impression that the immutability bit can give us an opportunity to slowly build a more secure system.
What I like is that it is simple to understand and we can build alternate and enhanced solution. Even if for us it uses a bit that we like to have to
create strange ideas.

>
> BTW, I implemented a per-class scheme ages ago in above BrouHaHa (in a Smalltalk-80 v2.3 derived image) to provide immutable literals.  It worked badly for literals since 'foo' class ~~ 'foo' copy class (one needs an ImmutableByteString class and a ByteString class for every class one wants to make immutable).

Eliot I did not get that why for every class

>  Lots of the system was affected by the change since the store string of a mutable string ends up being
>     'the immutable string literal' copy
> to get a mutable string.
>
> Our experience with VisualWorks was different.  Lots of methods had to be changed because they were attempting to update immutable literals.  There were lots of
>     stream := '' writeStream.
> throughout the system which had not been noticed.

Yes this would be nice to spot such places. I would really like to know other cases where immutability helped VW.
Do you have some anecdotes?
Since it required an effort to bring that in VW, what was the selling argument at that time for getting it into the system?

>  But unlike the BrouHaHa experience the changes only affected violations of immutability.  In BrouHaHa the changes were due to trying to accommodate the clumsy class-based scheme.
>
> cheers,
> Eliot
>
>
> > Cheers,
> >  - Andreas
> >
>
>
>
> --
> Best regards,
> Igor Stasenko AKA sig.
>

On 9 June 2010 23:24, Eliot Miranda <[hidden email]> wrote:
>
>
>
> On Wed, Jun 9, 2010 at 1:14 PM, Igor Stasenko <[hidden email]> wrote:
>>
>> On 9 June 2010 22:57, Eliot Miranda <[hidden email]> wrote:
>> >
>> >
>> >
>> > On Wed, Jun 9, 2010 at 12:34 PM, Igor Stasenko <[hidden email]> wrote:
>> >>
>> >> On 9 June 2010 21:51, Andreas Raab <[hidden email]> wrote:
>> >> >
>> >> > On 6/8/2010 7:41 AM, David T. Lewis wrote:
>> >> >>
>> >> >> What do the VM developers think with respect adopting the VM changes?
>> >> >> The immutability bit is a scarce resource. Is it OK to allocate it
>> >> >> for this purpose or are there likely to be other projects interested
>> >> >> in using it for other reasons?
>> >> >
>> >> > Oh, and one thing that I'm just realizing is that by far the biggest impact
>> >> > of immutability is in primitives and plugins. All primitives in all plugins
>> >> > must be rewritten to test for mutability of the objects they store into
>> >> > before this can work reliably. Ouch.
>> >> >
>> >>
>> >> Yeah. I told before, that i'm not a big fan of making VM more and more clever.
>> >> It is because 'clever' is synonym to 'complexity'.
>> >>
>> >> I'd rather focus on providing immutability at language side, instead
>> >> of implementing it
>> >> primitively.
>> >>
>> >> However, i am thinking, if there could be good alternatives to
>> >> immutability bit in object header.
>> >> One idea is to add this bit on a per-class basis, not on a per-instance basis.
>> >>
>> >> Then VM could check immutability during a method lookup and throw
>> >> exception before entering method(s) which can mutate
>> >> an instance of such class. But then we should also divide
>> >> primitives/methods on those which can and can't
>> >> mutate the object's state, which is also a lot of work.
>> >
>> > You think its cheap to scan methods for mutablity??  Remember you have to identify inst var writes not just mutating primitives like at:put:.
>> >
>> >>
>> >> Checking before entering method potentially will have much less impact
>> >> on performance, because it is not so fine granular as per each write.
>> >
>> > I don't think so.  Not without a JIT to cache the scanning of methods for mutators.
>>
>> It could be done at compilation stage. No need  to scan bytecode at run time. :)
>> I referred to checks as 'if this method perform writes to receiver'.
>> But not 'if this method performs writes anywhere'.
>>
>> >This scheme also only works for methods, not for code in plugins.
>>
>> Sure. Plugins is another story.
>>
>> > The above is speculation.  The immutability scheme I'm discussing is real and known to work in practice.
>> >
>> > BTW, I implemented a per-class scheme ages ago in above BrouHaHa (in a Smalltalk-80 v2.3 derived image) to provide immutable literals.  It worked badly for literals since 'foo' class ~~ 'foo' copy class (one needs an ImmutableByteString class and a ByteString class for every class one wants to make immutable).
>>
>> I don't see this as a disadvantage.
>> Mutable and immutable objects are clearly having different behavior.
>> And in smalltalk the only way to get two objects with different
>> behavior is to use different classes for them. No?
>>
>> > Lots of the system was affected by the change since the store string of a mutable string ends up being
>> >     'the immutable string literal' copy
>> > to get a mutable string.
>>
>> Err.. not sure i understood what 'store string of a mutable string' means.
>>
>> What is the point in having an immutable objects then, if you
>> automatically copying them at write attempt?
>> I don't see any gains comparing to:
>>
>> ' the mutable string' copy at: 1 put: $x
>>
>>
>> > Our experience with VisualWorks was different.  Lots of methods had to be changed because they were attempting to update immutable literals.  There were lots of
>> >     stream := '' writeStream.
>> > throughout the system which had not been noticed.  But unlike the BrouHaHa experience the changes only affected violations of immutability.  In BrouHaHa the changes were due to trying to accommodate the clumsy class-based scheme.
>>
>> I am really interested to hear more about BrouHaHa implementation,
>> because i like this approach. So, i'd like to hear,
>> why you considering it clumsy.
>
> Consider the file-out of a method category stamp:
> !FooClass methodsFor: 'category' stamp: 'initials date'!
> Since a literal string is immutable and has a different class to a normal mutable string then in the original Smalltalk-80 code without changing the file-out code to take account of immutability the above printed out as
> !FooClass methodsFor: 'category' copy stamp: 'initials date' copy!
> So many places which used storeString et al with literals that had mutable duals (string and array literals) had to be rewritten to produce the old format.  Clumsy.

I am confused by this example. Why one should file out !FooClass

methodsFor: 'category' copy stamp: 'initials date' copy!

instead of old one?
I am agree, that this will require a sizeable effort for introducing
the immutable subclasses.
But in this way, it is reflected in a language, instead of implicit
and hidden VM checks.

> But you don't need take my word for it.  Try it and see.  Implement e.g. LiteralByteString & LiteralByteArray, modify the compiler and see how things go.

:)

> cheers,
> Eliot
>>

>

--

Best regards,
Igor Stasenko AKA sig.

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

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

On 6/9/2010 5:15 PM, Eliot Miranda wrote:

   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.

Obviously. But what I was trying to point out is that the problem doesn't arise when it comes to constructing an immutable object graph (i.e., "implementing" deep immutability) but that the issues arise when you need to ensure that what you're passing along is in fact deep-frozen. Might have been bad terminology on my part.

   2) Traverse the object graph to prove deep immutability.

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.

All of this is exactly right, but now you're making my point ;-)
I'm *asking* for that level of support of immutability. Are we perhaps a little confused as to what "policy" means in this context? To me it means what I can build in the image with the semantics that are provided by the VMs implementation and primitives. And I can currently *not* reliably build what you describe above with the means provided (simply due to the fact that one can nilly-willy change the immutability bit on any object one likes). However, if you consider primitives part of the policy then indeed one could do that by ripping out the existing set of prims and replacing them with others.

BTW, for the records, I think I do see your point here. I think what you're saying is that regardless of how/when immutability is turned on for objects, the VM (plugin) support is useful to have since it provides a basic layer which makes utilizing immutability in various contexts possible. Thus, even though we might argue a couple of years about whether there should be a prim for turning immutability off or not, it shouldn't stop us from allowing the VM to trip over an object that has in fact been marked immutable. I do agree with that reasoning.

   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.

Well we're hypothesizing about some uses here. They haven't been implemented. What I've been wondering is how immutability in those systems has been *actually* used and in particular whether (m)any non-db apps or uses were amongst them.

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.

Thanks. Any other known uses for this outside persistence (which is the "database" category) and immutable literals?

Cheers,
 - Andreas