Born to Evolve

So I gave a demo at SenSys last week based around Lorien’s core paradigm of building to evolve.

I thought I’d write down why I think this is a good way to build systems software – and therefore as a foundation of all software. Unlike many of its contemporaries Lorien’s fundamental system building model is not an abstraction model, or a processing model, or resource management model; rather it is a fundamental model of software itself. The Lorien operating system is founded on a general model of software structure, composition and evolution uniformly applied to all of software. We find that with this model we can build all of the others, but with none of the others can we build Lorien, suggesting that it represents a more general system building model with which we should arguably construct all systems software. What’s interesting is that Lorien can do this construction of arbitrary functionality completely online, able to seemlessly change every aspect of itself to become whatever kinds of software (and abstractions) you currently need. This is a brief introduction to the development of Lorien: an OS built to evolve.

First, a quick history lesson. The history of operating systems can be summarised as building to abstract. A system designer creates what they think is a nice abstraction layer (or API) atop which all other functionality can be developed - all of the functions that other software might need to call on are encoded in this API. This is a bit like the famous Win32 API, or the POSIX model; above this API sits the software of applications and services which will (more or less) work on many different kinds of computer that host this same API. The collection of software currently running above this API is anticipated to change over time so that when the user wants to do some word processing they can launch their favourite corresponding application and start typing. When they’ve finished with their word processing task they might close that application (and I’ll come back shortly to why they tend to close it).

Both of these actions - starting an application and closing it - are actually examples of software evolution. The currently running collection of software, from operating system to applications, is all hosted inside memory. In fact this is a special variety of memory called executable memory. The machine code of software in executable memory can be directly fetched and processed by the CPU as a sequentially arranged collection of instructions. Other kinds of memory exist like secondary storage which is not directly executable; hard disk drives are examples of this, and this memory can be used to store extra files or machine code that can be loaded into executable memory when needed. Changing what’s in executable memory therefore equates to an evolution of the sum of the currently running software on the computer.

So why does our running software need to evolve?

The problem is that the amount of executable memory available on a computer is quite small; this memory has to be very fast to access and so is both expensive and also tends to be physically large. By comparison secondary storage media like hard disks don’t need to be so fast to access; they tend to be much cheaper by comparison as well as being physically smaller.

The need for software to evolve is then simply a factor of this pathology: over time the user always wants to be able to choose between more kinds of software than can fit inside executable memory. This has almost always been the case, and will almost certainly continue to be the case. When the user opens the word processing application, the machine code of that application is therefore copied from secondary storage into an empty area of executable memory. If executable memory has no more empty areas you can’t start any new applications and so you have to close some existing ones which frees up some of that executable memory. This is why people tend to close applications they’re not currently using, even if they only realise why they do it on a subconscious level: they perceive that it keeps their computer running relatively quickly.

The need for software to evolve will thus almost always be with us; over time our needs tend to change and we’ll always want to switch between different activities. We support it by allowing machine code to be moved from secondary storage into executable memory, and for machine code in executable memory to be deleted to make room for different machine code since executable memory is finite. It’s worth noting that even if hard disk drives were directly executable, even their storage capacity is finite and our “secondary storage” then becomes some other medium like the Internet.

Despite this basic requirement to evolve software, unfortunately today we don’t actually build to evolve on a fundamental level, we instead build to abstract. As evidence of this take a look at a book on modern operating system design; you’ll see lots of information about hardware architecure, instruction sets, operating system organisation, scheduling, memory allocation, processes and memory protection, paging, networking, parallel computing, security, and of course abstraction layers. What you probably won’t find however is much about the constitution of software itself and the way in which that software evolves - chapter 1 will almost certainly not be “fundamental model of software". I strongly believe that this should be chapter 1, and that without such a fundamental, general model of system building providing “level 1″, software is simply a somewhat arbitrary mix of “stuff".

But this seems to work, right?

I wouldn’t begrudge contemporary operating systems too much for what they are - the history of operating systems systems has generally been a race to just make things work, without too much deep thought on the “how", and they seem to be pretty good by now at doing most of the things we want to do. But let’s take a step back here and think about those abstraction layers again. I talked about how software like applications and services runs above these APIs, allowing the same software to run on a wide variety of different computers - your laptop computer is really quite different from your desktop computer, for example, though you might not notice this because most of the same software seems to work fine on both. And I talked about how software above this API (like applications) is allowed to evolve quite freely to accomodate users’ changing needs over time, as well as our reasonably good understanding of how to do this by shifting machine code form secondary storage into executable memory or else wiping some of that machine code from executable memory to make room for different code.

But what about the other side of this nice API? The stuff below it? This is a different world. What’s underneath here does not tend to run the same on different computers, and instead needs to be changed for each different type of computer it will target. This includes things like hardware drivers, scheduling systems and memory managers. Most of the time the average user doesn’t need to know about or understand this stuff, and if they did have to understand it computers would certainly be more complex to use! But what happens when we want to evolve this software, the software below the APIs? The answer is, this happens:

Or this:

Or even this:

Most of the time the user doesn’t understand why this happens, but they do grudgingly accept it because they’re told that it’s necessary. What I’m interested in here is showing that actually it isn’t necessary - ever - but we do need to fundamentally change how we build software. We need to stop building to abstract, and start building to evolve. Of coure this doesn’t mean throwing away abstraction layers as a useful concept, but it does mean throwing them away as the core paradigm of system building. If we fundamentally build to evolve as our core paradigm, we can easily build abstraction layers within this framework whenever we want. But if we keep fundamentally building to abstract, we’ll always have this broken model of software evolution. Building to evolve also demonstrates some fascinating properties that software can have if we try to maximally generalise its central theoretical model.

Building to Evolve

A quick recap: Operating systems today are built as abstraction layers atop which common software executes. Researchers have actually often played around with the size and makeup of this abstraction layer (micro-kernels would be an example), but the size of it isn’t the problem; the problem is the nature of the abstraction itself. Because we build fundamentally with abstraction layers we have a broken model of software evolution; it works one way for applications and a fundamentally different way for so-called system-level concerns.

So I’m going to talk about a general, uniform model of software evolution: one that works exactly the same for all parts of software. With this, no computer would ever need to restart no matter how much its software needs to evolve. I believe this is a more fundamental purpose for operating systems – and therefore all systems – than any other purpose, because with a uniform model of software evolution we can build everything else we know today, but there is no other model that I know of with which can we build uniformly evolvable software.

This work in implementation is currently based around wireless sensor node hardware, which is a little simpler to work with than the hardware of modern PCs and so has facilitated some relatively rapid progress, but it’s interesting to also consider the concepts in their general form.

I am not a kernel: So what do we need to able to evolve software?

Something close to the minimum amount of functionality we need to support software evolution is the following:

1. A memory manager. This helps us to allocate areas of that all-important executable memory. How this works isn’t important, but an example collections of operations for this would be malloc() and free().

2. A file system for secondary storage, where our vast array of available software is stored in big, cheap memory (this could be a hard disk, cheap flash memory, or even the Internet). An example set of operations for this would be open(), close(), read() and write().

3. A dynamic loader to understand the process of loading machine code from secondary storage into executable memory with the help of the above two elements. An example set of operations for this would be load(), unload(), and getSymbol().

4. An entity which understands the current software in executable memory and how to change it. An example set of operations for this would be load(), instantiate(), destroy(), unload(), declareProvision(), declareRequirement(), connect() and disconnect().

It’s important to note that the individual example operation sets mentioned above are actually not important in themselves and can be substituted for others at will (though employing a minimal set has its uses); what’s important here is the much more difficult to define sum of their behaviour. No single one of these elements is in itself necessary - take a minute to think about this - but together they represent the ability to evolve all of software including themselves.

In more detail, the key to why the above functionality isn’t a ‘kernel API’ - an absraction layer - in the traditonal sense is that all of this functionality is actually meta-functionality. This is to say that none of this meta-functionality is needed in normal system operations, and that normal, functional software has no reason to ever interact with this meta-functionality. To put this another way, Lorien could technically unload from executable memory its dynamic loader. It could also unload the entity which understands the current software in executable memory and how to change it. In the face of such actions system functionality simply continues as if nothing had happened, so you can still keep typing that document in Word and browsing the Internet looking for inspiration.

That is of course until the next time you wish to evolve your software (like loading a new application) and then you have a bit of a problem. While this might seem like a strange capability, the point of being able to describe such a software modification with total uniformity is that we can for example seamlessly replace the current loader with another one if we decide we need something different; it’s all part of a maximally generalised model of software and its evolution. But the main point here is hopefully clear: this meta-functionality at the heart of Lorien is no kernel in the functional sense, not even a micro-kernel, since normal software has no interaction with this meta-functionality in normal system operations, and this meta-functionality applies with generality even to its own machine code.

Beyond these basic mechanics, Lorien’s core system building theory is composed of six key elements:

A. Build to encapsulate: Build standalone pieces of generalised software functionality that fully encapsulate useful processing functionality. Design interfaces made up of function prototypes that describe what these chunks of software can do, or in other words what functionality they are willing to publicly provide. We’re already quite used to doing this with object oriented models, but are quite not so used to strictly doing the second thing:

B. Don’t create what you need, declare what you need: At the fundamental level of system building, encapsulated pieces of software should not create the other encapsulated elements that they need to be able to function. Instead they should declare what those other elements are using required interfaces. Required interfaces can be connected (by some third entity) to the declared provided interfaces of other software elements to satisfy dependencies. This empowers the system composer instead of the software developers in deciding how to compose and recompose the running software as currently desired. We can still have the other model - the object-oriented one, where objects tend to create what they need - in the areas of the system where it makes sense, but it seems we can’t do this as our fundamental model.

C. The Universe is Inside Itself: If we’re going to be able to uniformly evolve software we need to maintain a model of what that software currently looks like. With a maximally general model, the thing that maintains this model - or in fact anything that plays any part in maintaining the model - must necessarily represent itself within that model with full generality. The representor of the universe should therefore just be another encapsulated piece of functionality like any other, with provided and required interfaces, able to be changed at will like any other piece of software.

D. The Universe needs Laws: A software system that can fundamentally evolve any part of its functionality at any moment, without ever going offline, is likely to exist on the edge of chaos. To bring order and safety to such a system - not to mention developer confidence - a small set of rules is defined to control the way in which software elements are allowed to interact; we find that most of these fundamental “integrity rules” need not be particularly complex.

E. The Start of the Universe is a Singularity: If we have close to a maximally general model of software evolution we tend to find that some small part of software cannot exist within that model; it has to exist within another model which “creates” the general model - without, as it happens, having to actually know what that general model is at the point of creation. Lorien tries to make this “singularity", outside the general model, as small as possible - it’s just 1.2KB on sensor hardware.

F. Rationalisation: Just like we need something to model the evolving universe, we also need something to rationalise it and its evolution into something that we can comprehend on a fairly abstract level, away from the fine details. Lorien has such a rationalisation which exhibits strong independence of evolution actions in different areas of a running system, enabling highly localised impact of change and providing a simpe way to descrbe this localised change.

By using the above simple mechanisms and theory we find that almost all of machine code in executable memory - except for that 1.2KB singularity - can be changed at will while all software unrelated to that evolution continues uninterrupted.

As noted above what’s particularly interesting is that we find that the elements that support this model of software evolution, like a dynamic loader, can themselves be subject to that evolution without loss of generality - so we really can unload the dynamic loader as if it were any other piece of software. This is actually quite profound, in part leading to the idea that such a universe of software, founded on a generalised uniform model of software evolution, is at its core a universe that is notionally inside itself. This really is an extraordinarily general model of software, uniformly applicable to almost all of machine code in a computer’s executable memory including that which directly supports the model.

And, as I showed at SenSys last week, the great thing about this is that it’s not just a theoretical model; we have a real working implementation of such a self-containing universe of software amenable to an extremely general model of software evolution - hardware drivers, file systems, schedulers, protocols, and all of the supporting elements of this model, all the way up to applications, can all evolve in exactly the same way with highly localised impact on the wider software system. The prototype implementation currently targets wireless sensor network hardware, which is itself a fascinating application of computer technology, and if you have some TelosB’s you can try Lorien out for yourself.

Back to the start

I’ll expand on the above theory with much more detail another time, but hopefully this gives some flavour of it. For now let’s go back to where this article started. I talked about how we currently build to abstract, how this lets us run the same software on lots of different computers thanks to things like the Win32 API, and how a form of software evolution is supported in these systems by allowing particular parts of machine code to cycle between executable memory and secondary storage as needs change. I’ve talked about how this focus on building to abstract has, however, ultimately led to a broken model of software evolution in which users are actually expected to restart their computers when mysterious parts of software evolve.

Other areas of science would tell us that such a specialised model, unable to describe all circumstances with generality, is not a good one. In respect of this I’ve talked about the possibility of a much more general model of software building, taking us away from building to abstract as our core model, and instead looking towards building to evolve. This is a core system building model able to uniformly describe the composition and evolution of almost all of machine code in executable memory. Such a uniform model of software evolution - essentially a kind of meta-functionality - can evidently therefore be used to build and later evolve all other functionality that we might want, including arbitrary abstraction layers, processing models and resource management frameworks, and including, critically, the functionality implementing the meta-functionality of the software evolution model itself.

To me this seems like a much better way to build all modern software, a chapter 1 of “operating systems", and if we start doing this then I hope we’ll start to see software catching up with the kinds of things it ought to be able to do by now. And I hope that made some kind of sense :-)