Mutability

In my last post about constructors I mentioned that objects have three states: under construction, mutable and immutable. The under construction state is not likely to be one you’ll see often — it will be more of an implementation detail — but the mutable and immutable states you’ll see.

Neutrino is strict about mutability. You are free to have mutable state but you are limited in how you are allowed to use it. State can only be shared between threads if it is immutable. State passed from one execution stage to another (think of it as from compile time to runtime), including global constants, must be immutable. In general, immutable data is required in a lot of places and neutrino has to make it as easy as possible to work with it.

The tricky issue with immutable data is: how do you construct it. Simple data like pairs and singly-linked lists compose nicely and lend themselves to being constructed immutably or compositionally, from only immutable parts. Most practical data structures, including hash maps and random-access arrays, do not lend themselves to immutable construction but are more conveniently constructed by successive operations on mutable data. To make immutable instances of these you need more complex machinery.

One popular pattern for more complex object construction is to use a mutable builder to define the structure of the object, and then have it produce an immutable copy. This is useful in a lot of cases but also has its limitations. First of all, it adds a lot of code. It also means that you get at least two copies of your object: the builder and the resulting object. Finally, it only helps if the resulting object is non-circular — you can’t use a builder to construct a circular list, for instance. Builders are neat but limited.

Another non-solution to this issue is to wrap your mutable data structure in an immutable wrapper. This doesn’t actually prevent the object from being mutated — the underlying data is still mutable — but it allows you to pass the object around in a way that prevents users of the data from modifying it. That is also useful but gives none of the guarantees we need.

The thing to note about these two examples is that they’re patterns for building nontrivial immutable data in languages that have no proper concept of mutable vs. immutable data. I would claim is that, as with threads, immutable data cannot be implemented as a library. This is why, even though the whole point of neutrino is simplicity, the distinction between mutable and immutable is basic and understood by the language.

As described in the post about constructors a neutrino object is in one of three states: under construction, mutable and immutable. An object can move from fewer restrictions to more, from under construction to mutable and from under construction and mutable to immutable, but never the other way. These states are used in a few different situations.

One way they’re used is when passing objects outside the current thread. Only objects that are transitively immutable, which the runtime can check, can be passed between threads, both within the same process or via RPCs. The state of an object is also taken into account when looking up methods. Basically, you can have mutator methods on an object which are only present when the object is not in the immutable state. For instance:

protocol HashMap;

def (this is HashMap)[key] {
def entry := this.find_entry(key, this.hash(key),
false);
if entry = null
then null;
else entry.value;
}

def (@mutable this is HashMap)[key]:=(value) {
def entry := this.find_entry(key, this.hash(key),
true);
entry.value := value;
}

// Rest of hash map implementation...

The effect of the @mutable annotation is that the setter here can only be called when the object is mutable. You might think of this in terms of reclassification: part of an object’s type is whether or not it is mutable, and changes to mutability status of an object changes the object’s type. This also works for the under construction state so initialization methods can be marked so that they’re only available when the object is under construction and you can be sure that it will be impossible for anyone to call those methods once the object is no longer under construction. The pattern for creating immutable data is simple: create a mutable version, populate it and then freeze it. The mutator methods will fall away and you’ll be left with an object with the appropriate immutable interface which the language will guarantee cannot be modified further, since it will prevent any attempt to write to a field of an immutable object.

Or, immutable objects can actually still be modified to some extent. That may sound conterintuitive but it is completely safe and follows from the mechanism above and how it interacts with field keys.

To reiterate what I described in more detail in the post about constructors, fields in neutrino are set using field keys. Rather than set and get a field through a string name like in python or javascript you use an object, the field’s key. If you have the field key then you can get and set the field. If you don’t have the key there is no way you can access the field, and no way for you to get access to the key except by having someone with the key pass it to you. Basically, it is a capability that allows you to access an object field. For a “public” field, one that others are allowed to access, there will be public getter and/or setter methods which have access to the key, so anyone can access it by calling those methods. For “private” state there would be no direct accessors, instead the methods that need to access the field will be given access to the key directly, and noone else.

This model means that there are two objects involved in getting and setting fields: the object itself and the field key. This gives four different combinations of mutability: the object can be mutable or not, the key can be mutable or not. Only if both are immutable will setting the field fail. Immutable field keys are said to be global, mutable ones are local.

Global fields are “normal” fields. They can be set only when the object is not in the immutable state, and when transferring an object out of its context. (A quick timeout: when I say “context” a good approximation is to think “thread”. In reality it is a bit broader and includes transferring from compile time to runtime, between threads and between processes over RPC, but the common and familiar case is between threads). Technically, the reason the values of global fields are accessible out of context is that the field key is immutable so it can be transferred along with the object and used to access the field in the destination context. You can also have global fields that are not accessible outside the context: if you don’t transfer the key along with the object.

Local fields on the other hand can be set even on immutable object. This is safe because, being mutable, the field key cannot leave the current context and hence is guaranteed to only be accessible locally. You might think of a local field as an associative map where setting the value doesn’t actually change the object, it just creates an association for the object in the key. Whether that’s how the implementation treats it up to it, it may decide to store the value on the object itself for efficiency, but it shouldn’t matter from the programmer’s viewpoint: you get to store some data with an object regardless of whether that object is mutable, under the restriction that the data will not be accessible outside your context. This is convenient for storing hashes, coloring objects when traversing object graphs, etc.

That is the general idea of how mutability works in neutrino. It is a slightly more complex model than in most languages but the complexity pays off in increased flexibility and security in a way that is practical and useful. In particular the simplicity of the rules that makes this secure, that mutable data cannot leave its context and that all fields are accessed through unforgeable keys, are a key part of the design of neutrino.

Leave a Reply

Your email address will not be published.


*