Atomic Install

A few months ago, I wrote a post about the become: operation in the Smalltalk family of languages. The post elicited a good discussion. One of the interesting points that came up, was that you could implement become: by changing the class of objects, provided all the changes were atomic - changing the class, modifying the object’s schema accordingly, and copying the data between the objects.

Setting the discussion of become: aside, I observe that in general, reflective change should be atomic. What I mean by this, is that one should be able to group an arbitrary number of distinct reflective changes to the program, and install them into the running program all at once, in one atomic operation. I will use the term atomic install to refer to this ability.

Oddly enough, this point is not well understood. Most languages that support reflective change do not provide a way for atomically performing a set of changes.

Smalltalk provides a reflective API centered around classes. You can ask a class to modify itself in a variety of ways - adding or removing variables, methods or changing its superclass. There is, however, no way to change several classes at once.

The CLOS APIs are similar in this respect.

Scripting languages don’t really have a reflective API as such. Instead, the reflective changes may come about as the result of executing some code (e.g., an assignment may add a variable). In other cases, the reflective capacity of the language comes about directly from exposing the data structures of the language implementation back to the language.

In all these cases, one cannot perform a set of program changes as an atomic unit.

Why do you need to atomically apply a set of changes instead of sequentially applying one change after another?

One reason is that you’d like to apply the changes as a transaction. If a change fails (say, because you created a cycle in the class graph, or duplicated an instance variable) you don’t want any further changes to take place. It’s easier if you don’t have to catch exceptions etc. after each step.

Another reason is that the changes are often dependent on each other. Applying one change without the other leaves your program in a broken state. The fact that intermediate states may be inconsistent even though the overall set of changes is correct means that it isn't sufficient to wrap a series of reflective changes in a transaction.

Of course, most people don’t rely on reflective modification to develop their programs. Rather, they suffer through the classic edit-compile-run-debug cycle. In the absence of anything better, you typically edit source code in files. You then compile these files and load the resulting program. This actually has one big advantage: the load is atomic - all the changes that resulted from your edits are loaded as a unit.

Evolving your program reflectively has the advantage that you can make corrections to the running program. Often, this is done during fix-and-continue debugging. Even then, in most cases, the “program” in question is an application that is stopped in the debugger, and you can apply fixes sequentially. But as noted above, it’s still easier if you can apply the changes as a transaction.

More interesting cases are when you are modifying a program, and need to run it between the individual modifications. Unlike most people, I run into this often, when modifying the IDE I am using. However, there are additional situations of this nature.

Long lived applications that must provide continuous service have this flavor. Erlang allows you to replace an entire module as a unit in these situations. In Java, you use class loaders to get the desired effect; it’s complicated, but it’s your only way out. A scenario I'm especially interested in is software services: the service updates applications on the fly without shutting them down - and in particular, I may want to update the update mechanism itself.

If you can’t make all the changes in one go, you find that you have to break the transition into a series of steps, each of which leaves the system in a consistent state while leading to the desired final program. This is tricky and error prone: you need to apply the right changes in just the right order.

Scripting languages like Ruby often go through a series of program changes during program start up. Different modules are loaded, modifying the program in the process. This process is also order dependent, and therefore brittle. In many cases, this sort of reflective change isn’t actually essential; rather it’s an artifact of the language semantics. However, I suspect there are situations where it is used to real advantage.

Overall, one can live for a long time without the ability to atomically apply a set of program changes. And yet it seems that there are some situations where atomic install seems to be very useful. It also has another advantage: batching the changes is more performant. Often one doesn’t care, but it doesn’t hurt to be faster, and on some occasions it actually can matter. One might as well see if one can come up with a reflective API that supports atomic install.

In Strongtalk, the VM supported atomic install as a primitive operation in the VM. More recently, in the latest Newspeak update release, I added an atomic install facility written entirely in Newspeak. Exactly 372 lines of code (whitespace and copious comments included). It is a tribute to the Squeak design that this is doable without any privileged access to the VM .

Tangent1: Thanks to Peter Ahe and Eliot Miranda for the discussions that led to this scheme; and to Lars Bak, for the discussions that led to the original notion of atomic install.


Tangent2: Squeak’s existing mechanism for changing classes, the ClassBuilder, is, on the other hand, rather unattractive. It’s three times as long, vastly more complicated, and provides only a subset of the functionality. It shows how tricky this kind of reflective change can get if you don’t conceptualize it the right way.

Naturally, the actual atomic step here is done using a variant of become:. Specifically, it’s a one-way become: on an array of objects. Given two object arrays a and b, both of size n, all references to a[i] are changed to refer to b[i], for i =1 .. n.

The atomic installation process nice and simple. The input is a list of mirrors describing mixins, and a namespace listing which of those mixins already exist in the system. The namespace parameter is crucial BTW, as there is no global namespace in Newspeak.

We then produce a fresh set of mixins based on the input list. For any existing mixins, we locate all classes that are invocations of those mixins, and all subclasses thereof. We make fresh versions of these as well, reflecting the changed mixins involved. For each such class, we locate all its instances (does your system have allInstances?) and produce new instances based on the new descriptions. Each new object is associated with the old object by keeping them in parallel arrays. Then we just do the become: and we’re done.

Unlike Smalltalk, in Newspeak we never have to recompile code that hasn’t been modified at the source level - because Newspeak code is representation independent.

It’s clearly harder to do atomic install in a system that does sophisticated JIT compilation and inlining - but as I said, Strongtalk supported it (albeit at the VM level, largely because of the extar complexity involved) in the mid-90s.

How do we get this kind of reflective power on mainstream platforms? It is harder, because the widely used platforms don’t support the needed abstractions as well as Smalltalk VMs do.

At least on the web browser, I expect to be able to get similar effects with Javascript, albeit with a very different implementation.

In Java, the absence of the necessary primitives tends to force one to build one’s own custom object representation, which is costly in both developer time and machine time.

Ironically (but not coincidentally), the bulk of the necessary machinery already exists in the Hotspot JVM, which is capable of changing at least method implementations on the fly (via JVMDI), including deoptimizing compiled code that may have inlined a method that has been modified. The problem is exposing it to user - and especially exposing it securely. Mirrors can help here - but that is for a future post.

On .Net, the DLR helps one construct one’s own custom representation. Conversely, there’s little support for deoptimization etc. in the CLR itself.

Of course, one goal of this post is to encourage implementors to add such support, and do it in the right way.