An overview of Cell

The purpose of this section is to provide a bird's eye view of the Cell programming language, by emphasizing its unique features and explaining how it differs from every other programming language I know, in order to give you a sense of what it can be useful for.

Be warned though that this overview is not for the faint of heart: it's long, abstract and contains no code. If you are just curious to find out what the language looks like and what it can be used for, start with the introductory example instead. Another useful resource is the FAQ.

The functional sublanguage

The innermost layer of Cell is its semi-functional sublanguage, which provides the foundation for its stateful features. It's functional in the sense that functions don't have any side effects, and are referentially transparent. It also provides a number of features typically associated with functional programming like union types, pattern matching, list comprehension and closures. It differs from fully functional languages in that the role of closures is a lot more limited, mainly because, by design, normal data and closures are kept completely separate. It also gives you the option of using a fully procedural syntax, complete with loops and the ability to update local variables. All side effects are local, so as not to compromise referential transparency, but the overall programming experience is very different from that of languages like ML and Haskell.

The most distinctive feature of the functional subset of the language is its data model and type system. Both are entirely structural, and that gives the language the ability to (among other things) manipulate data whose structure is unknown, or just partially known. That sort of flexibility is indispensable to support orthogonal persistence, that is, the ability to transparently save and restore the state of a program (or at least part of it). This is, incidentally, the main reason Cell was designed from scratch and not built on top of an existing functional language like, for example, Haskell.

Relational automata

The core construct of Cell is relational automata. To a first approximation, think of them as fully programmable miniature databases. Their ability to use relations to encode their own state is by far the most consequential feature provided by the language: we will not be saying much about it here, as this topic is so important that it deserves to be discussed extensively, and with plenty of examples, once we have a full picture of the language. We'll do so in the Why relations are better than objects page. Suffice it to say for now that relations, with some help from reactive programming and memoization, can simplify (drastically, in some cases) both the data structures used to encode the state of an application and the code that updates them.

Relations in Cell are very different from those of SQL databases: for one thing, their fields can contain any type of values, unlike in SQL where they are limited to a few predefined data types; for another, they are designed to be used in a fully reduced form, whereby the majority of relations will be either unary, binary or ternary, with higher-arity relations used less often. In practice, these differences lead to a very different sort of data modeling, and allow, I believe, for a better integration with general-purpose programming capabilities. In a way, Cell's flavor of the relational model looks a bit like a sort of high-level version of the Entity/Component architecture commonly used in videogames. There are many similarities in the physical implementation as well, and there will be even more in the future.

The only way to mutate the state of an automaton is by sending it a message, which is just an ordinary value, that can be copied and passed around, serialized and so on. For every type of message an automaton can accept there's a corresponding handler that is invoked in order to update the automaton's state. Unlike what happens with pure functional languages (and with the functional subset of Cell itself) where the normal, and often the only, way to "mutate" a value is to make a mutated copy of it, the state of an automaton is updated imperatively, and its relation variables in particular can be updated in place by inserting new tuples and deleting existing ones, just like in relational databases. It's important to note here that while the state of an automaton can be accessed in read-only mode without restrictions, there's no sharing of state between automata, and all side effects are limited in scope to the automaton that receives the message, with no effects on the state of other automata. The scope of these side effects is further reduced by other restrictions that are placed on updates, which will be described in another chapter.

Every update takes place inside a transaction: that is, if the update fails (for whatever reason) the message is discarded and the state of the automaton is left untouched. This currently works only when the failure is caused by a programming error (an "exception"), but a more sophisticated implementation could also, for example, provide the ability to terminate updates that are taking too long, using too much memory or that are pre-empted by higher-priority ones.

One important property of updates is that they are deterministic: that is, the state after the update depends only on the state before it and the message that triggered it. So if two instances of the same automaton are sent the same sequence of messages, they will end up in the same state, even if the processes they belong to are run at different times on different machines. So you'll be able to trivially reproduce any bug (even the almost-impossible-to-reproduce ones) if you just store all those messages in a log file, which can be done, with the help of a tiny library, with just one line of code, thanks to the structural nature of Cell's data model. Those same message logs will also make it a lot easier to retest your application after a refactoring, or (to a lesser extent) the development of new features.

There are also other, fancier ways to to take advantage of this deterministic behavior: it could be used, for examples, to provide redundancy (and some load-sharing) for stateful server applications, by running two (or more) identical automata (or set of automata) on different computers, and sending every update to all of them (so that their states are kept in sync), while rerouting read-only queries to any of them (so as to split up the workload).

Another unusual feature of relational automata is orthogonal persistence. At any point in time a client can take a snapshot of the state of an automaton, which can then be saved to persistent storage. Such snapshot can later be used to recreate an identical copy of the original automaton, which will just pick up where the original instance left off. The whole process is transparent to the interested automata, which are completely unaware of it, and it is only marginally more complex (in terms of number of lines of code) than saving and restoring the state of, say, an integer variable in other languages.

Orthogonal persistence is made possible, and practical, by a combination of some of the language features we've already examined, like Cell's value-based data model; the fact that automata are self-contained; the deterministic nature of the language; and its structural data model, which not only makes serialization and deserialization trivial, but also makes it (a lot) easier to deal with the equivalent of schema changes in databases.

The current implementation forces you to explicitly save and restore the whole state of the automata you want to persist, which of course is not feasible in the presence of large amounts of data. But note that if an application keeps a message log, it's not necessary to save its state after every single update, because in the event of a crash the most recent state can always be reconstructed by starting from the last saved one and replaying all the messages that were received after that. A better persistence implementation, one that can automatically store just the part of the data that has changed during an update is of course possible, but since the implementation is non-trivial, it's only part of the long term plans for the language.

Future versions of Cell will also gradually integrate into the language Datalog-style inference rules of increased complexity, although the focus will be on the simple queries typical of OLTP systems, rather than the arbitrarily complex, long-running queries used in data analysis.

Reactive automata

Cell also includes a second type of automata: reactive automata. A reactive automaton can be regarded as a sort of "reactive object". It has inputs, outputs and a state. It reacts to changes in the values of the inputs by adjusting its state. The values of the outputs are, at any given time, a function of the current values of the inputs and the state. Unlike relational automata, whose state is entirely visible from the outside, reactive automata hide their inner workings from the rest of the world, similarly to (but more effectively than) objects in OOP. The only part of a reactive automaton that is visible from the outside is its inputs and outputs, which we will collectively refer to with the term "signals", and the same word will be also used to describe other similar non-public variables that are part of an automaton definition. All signals have values that vary over time, and they can be either continuous or discrete. Continuous signals are characterized by having a value at any given point in time. As an example, think of the position of the mouse in a GUI application, or the coordinates provided by a GPS sensor in a mobile app. Discrete signals, on the other hand, are normally idle, and take on a value only at specific points in time as they are used to model any sort of events (they are not the same thing as messages in relational automata, though). An example, again in the case of a GUI application, is mouse clicks or key presses.

A reactive automaton responds either to changes in values of continuous inputs or the activation of discrete ones, and updates its outputs accordingly. Outputs are typically defined in terms of a number of intermediate values, which may in turn be defined in terms of other intermediate values and so on, but ultimately everything depends on the inputs. So updates usually happen in stages: the first signals that are updated are those that depend directly on the inputs that have changed, then come those that depend on this first layer of recalculated signals, and so on all the way from the inputs to the outputs. The developer only needs to define the value of each signal (inputs excluded, of course) in terms of other signals, and the compiler (or, rather, the code it generates) takes care of performing all the recalculations, in the proper order and only when necessary (for efficiency).

When automata strictly follow the stateless model described above the values of their outputs are, at any point in time, entirely determined by the values of inputs at the same point in time, and any such stateless automaton is conceptually nothing more than a fancy function, with the only difference being that it may be able to avoid unnecessary recalculations when the values of the inputs change. While this stateless form of reactive programming is useful in its own right (we'll see exactly why in the following chapters), it becomes more so when automata are allowed to retain some information about the history of their inputs in the form of internal state. In stateful automata the value of the outputs is a function of both the inputs and the internal state, which is also updated when the values of the inputs change.

Changes in the internal state of an automaton can also be triggered, even in the absence of changes in the values of the inputs, by the simple passing of time. It's very easy to express in Cell things like "update the value of state variable V if condition C has been true for 30 seconds" or "change the value of output O if none of signals S1..Sn has changed in the last 200 milliseconds". Time-dependent rules like these are both specified declaratively (no need to deal with low-level constructs like timers and callbacks) and implemented efficiently (no polling required).

The behaviour of reactive automata is also entirely deterministic, so everything that was said before about their relational counterparts applies here too. As for orthogonal persistence, the whole situation is more complex than it is for relational automata. There's currently support for full orthogonal persistence only for reactive automata that don't have time-dependent rules. In that case saving the values of all continuous inputs and state variables is enough to reconstruct the exact state of the automaton at a later time. The same operation can be done done with automata that are aware of the passing of time, but in that case that's not enough to reconstruct their state, because they also contain some "hidden state", in the form of timers, that is not persisted (not yet, at least). In general reactive automata are not great candidates for orthogonal persistence, for reasons we'll examine later, so the language also provides the ability to explicitly declare what part of their state has to be persisted.

Reactive automata also follow a different error handling model. Relational automata react to an error during an update by simply discarding the message that triggered it, thereby implicitly assuming that messages can be discarded without compromising the application logic, and when that assumption applies transactions are an almost ideal error-handling mechanism. Unfortunately that cannot be applied to reactive automata, as it's not really feasible to undo changes to its inputs (it can be implemented of course, but it typically doesn't make any sense in the context of the application's logic). So when a calculation inside a reactive automaton fails, the signal whose value was being calculated, or the state variable that was being updated, enters a special "undefined" state, and that state is also propagated to all signals (and state variables) that depend on it, either implicitly or explicitly, although there are some limited recovery mechanisms. The purpose of such an error model is twofold: firstly, no incorrect result must be produced as a consequence of an exception being thrown: errors mustn't go unnoticed. Secondly, an error in one subsystem must not be allowed to compromise (or bring down) the entire application, and other, independent subsystems must be able to carry on as usual. This error model has also some (rather limited) self-healing capabilities: if an undefined signal is, at some later time, successfully recalculated it can then resume its normal functioning. This is unfortunately not always true for state variables, which will never recover if the expressions used to calculate their new value depend on the previous, undefined one.

Like classes in OOP reactive automata can be defined incrementally, by deriving new automata from existing ones. The derived automata can add state variables and add and also remove inputs and outputs and redefine the relationship between them. Unlike inheritance in OOP, this is only an implementation feature, and from the outside derived automata appear completely unrelated to their parent. Any notion of subtyping between automata would be pointless anyway, as their type is always statically know at compile time (so there's no polymorphism), and would only add unnecessary restrictions to the derivation process. (Just to be clear, functions can be polymorphic, and actually support multiple dynamic dispatch: but polymorphism is a notion that only applies to values, and not to automata of either type).

Compared to relational automata, which are the workhorse of the language, reactive automata are more of a niche feature, but they are nonetheless useful in a number of situations. We'll see in the following chapters a couple of examples taken from the field of embedded software development, but their applicability is not restricted to that. Large reactive subsystems are present, for example, in many games. A typical game has quests to complete, skills to learn or, in general, any sort of in game events that are unlocked only once you've performed certain actions, completed some tasks or even, in the case of online or mobile games, after some assets, like images or level data, have been downloaded from the servers. A new quest can be unlocked once, say, you've completed previous ones, or reached certain areas in the game, owned specific artifacts or talked to some NPCs, or any complex combinations of those conditions. Even in simple mobile games these subsystems can become pretty large, with hundreds of inputs, outputs and state variables, and they can be modeled quite naturally using reactive programming.

A domain-specific language, not a general-purpose one

Although Cell is, in and of itself, a general-purpose language, that can be used to write complete programs (the Cell compiler, for example, is entirely written in Cell), that's not what it is designed for. It is, instead, meant to be used as a domain-specific language, that complements your primary language, instead of replacing it. The Cell compiler is actually a code generator: it outputs a source file in any of the supported target languages, which you can then include in an existing application. For each automaton in your Cell code, the compiler produces a corresponding native class that allows you to instantiate and interact with those automata, by doing things like sending messages to, invoking methods on and reading, saving and restoring the state of a relational automaton, or setting the inputs and being notified of changes in the values of the outputs of a reactive one.

The most complicated part of interfacing Cell with the host language is of course converting the data that is passed back and forth between them from one representation to the other. The compiler/code generator here first tries to map the Cell data types to build-in data types of the host language, or types that are defined in its standard libraries, like integers, floating point numbers, strings or arrays. Failing that, it tries to generate classes in the host language that can be mapped to the native Cell types. This approach is mostly used to deal with records and union types, and, in the case of Java, with tuples. When everything else fails (which doesn't happen very often) the language resorts to a generic format that is less convenient to use but that has the advantage of being universal.

The interface is still a work in progress, and feedback and suggestions on how to improve it are of course always very welcome. The eventual goal is to make the generated classes almost as easy to use as hand-coded ones, even though it may not be possible to completely eliminate every source of friction between Cell and the host language.

The output languages that are currently supported are C++, Java and C#. In the longer term, other interesting targets are C, JavaScript and maybe Swift, if there's demand for them. All those implementations will march along at different speeds, so don't expect them to ever be perfectly aligned in terms of functionalities or performance.

The reason Cell was designed to be a domain-specific language, and its compiler to be a code generator, should be obvious. Choosing the main language for your application has usually more to do with the tools, libraries and support that are available for it than it has with the language itself, and one generally has to be, by necessity, very conservative there. But a domain-specific language that integrates with your primary language, instead of replacing it, stands a much better chance of actually being useful, as it can be adopted gradually, and only when, and to the extent that, it provides a clear advantage. It's just another tool in your toolbox. You can start by identifying a small part of your application that could benefit from being written in Cell: it could be a viable alternative, for example, to an in-memory embedded SQL database, providing a better data model, full programmability, a better interface with the host language and the performance of a compiled, statically typed language. Or it could be used to implement a reactive subsystem of your application, as an alternative to a reactive library, or to the tedious (and error-prone) hand-coded propagation of changes. These are just examples. Cell is nothing if not different: its strengths and weaknesses don't have a lot of overlap with those of more conventional languages, and object-oriented ones in particular, and there's no shortage of areas where it can complement them effectively.