I’m still working towards Wikilon, a wiki-based development environment and initial software platform for the Awelon project. The design is still fluid, and has taken me in some interesting and unconventional directions on the ‘development environment’ side.
On the ‘software platform’ side, I was contemplating a filesystem model, for long-lived data and applications. But I was concerned: how do developers disentangle their app from the filesystem? So I shifted to Wikilon hosting abstract virtual machines (AVMs) that host applications. AVMs provide boundaries for entanglement, forcing developers to address latency, concurrency, and disruption. This week, I decided I don’t want the heavy weight of a filesystem in every AVM. AVM state is now just a value, and a trie value is a decent model of a filesystem if developers want to use one. The development of VCache makes it entirely feasible to model filesystem-sized values containing gigabytes of data.
I selected message passing as a basis for communication between AVMs. I’m not fond of message passing, but ease of implementation and integration with existing systems sold it to me anyway.
Some interesting differences between AVMs and other message passing systems:
- AVMs cleanly separate state from behavior. The behavior of an AVM is a pure function of the form `(InMessage, State) → (OutMessages, State)`. All messages travel through this function. This separation makes live programming easy: bind behavior to a Wikilon dictionary, such that edits affect behaviors in real-time. Similarly, we can apply a structure editor to browse and directly manipulate state.
- Every message carries a capability-secure context: every InMessage is a (Context, Content) pair while every OutMessage is a (Capability, Content) pair, where the capability is an ADT that keeps context opaque to the sender. An AVM is (usually) given a pure function `self :: Context → Capability` so that it can construct capabilities needed for query-response and other feedback patterns. An AVM constructs ad-hoc, fine-grained capabilities on the fly.
- AVMs cannot create/spawn/fork/etc. new AVMs as a primitive. However, AVMs may host other AVMs hierarchically, using context to route messages. AVMs tend to centralize a lot of state under just a few objects, which has many advantages for debugging. That said, spawning can be modeled in terms of a capability to ask another machine to host an AVM.
- A friendly scheduler is specified. Messages between AVMs are implicitly grouped into batches. Output messages resulting from a batch are sorted into a new batch for each target AVM. Batches are processed atomically, and messages within each batch preserve order. Batches between machines also preserve order, using timestamps. Thus, developers don’t need to think about worst cases for non-determinism.
- A ‘common capabilities’ concept is also supported. For example, if access to UTC time is provided by a capability, and we send this capability to a remote host, said host may recognize this capability as a common one and provide a local implementation. This is discretionary; the host may instead send the message across the network to get UTC time at the origin. This mechanism is highly extensible: time, random numbers, high performance matrix multiplication, HTTP access, multi-homing, etc. can be modeled this way.
- I’ll make a reasonable effort at timely, reliable delivery of messages, but I won’t guarantee delivery. If a message cannot be delivered easily, I’ll drop it. If a message has a much larger latency than physically expected, I’ll drop it. Dropping messages allows a simple and scalable implementation in the face of varying connectivity, congestion, migration, administration that might take a machine offline, etc.. AVMs can react intelligently to network conditions via special capabilities that can report delivery status or provide alternate behaviors. Developers are encouraged to explicitly model mailboxes and tuple spaces and other robust offline delivery mechanisms where needed.
- In addition to state and behavior, every AVM has a ‘signal :: Context’ value. This value is used by the hosting environment to get an AVM running (an ‘init’ signal) or support graceful shutdown (a ‘stop’ signal) or indicate other concerns (e.g. low power) or to inject information about the environment or the Self function. Basically, it’s an initial capability. It provides an extensible set of generic AVM methods.
- At the toplevel, AVMs will be given global names – a secure hash of a public key – with routing based on a distributed hashtable. This makes it easy to create tons of fine-grained AVMs, to move them across physical systems, and to secure them against man-in-the-middle attacks without relying on a central naming service. If developers want common names, e.g. similar to domain names, these might be supported via NameCoin and similar protocols. (I’d rather avoid depending on ICANN or CAs.)
As with other message-passing systems, effects are modeled in terms of sending messages to resources masquerading as machines. Access to Redis, S3, AMQP, XMLHttpRequest, sockets, user interfaces, etc. could be modeled this way. Though I’ll initially focusing on just whatever I need for web services and web sockets.
Addendum: to emphasize a few points
I really love the simple, pure, non-monadic nature of the step function.
This sort of straight-line code is easy to express in a first-order manner. It is abundantly clear to developers that nothing happens – no output, no new input, no progress – unless the function terminates. It is clear that developers cannot wait on a message in response to a send unless they model waiting in a higher layer abstraction. The loop itself is clearly separated from state, which simplifies both live programming and visualization or direct manipulation of machine state.
I believe AVMs will prove highly scalable, and this is greatly aided by their purely functional nature and clear simplicity. Read-only messages are easy to parallelize. If we notice (by comparing before and after states) that many messages are read-only, we can heuristically switch to parallel modes and use compare-and-swap or other rework models to resolve read-write conflicts. Developers can leverage this by dividing AVMs for read-mostly loads or arranging for a single writer to avoid read-write conflicts. This sort of parallelism is highly scalable, e.g. can be implemented through replicating the entire abstract machine. Read-write messages are more difficult to parallelize. But if we have expensive computations distributed across small partitions of state, we can use pure parallelism to be processing many updates at one time. Normal sharding techniques also apply.
The real challenge will be to make these AVMs competitively efficient, i.e. by developing an effective compilers or JIT for Awelon Bytecode, leveraging annotations for memoization, etc..