Dealing with Mutable State in KernelF

Boxes, State Machines and Transactional Memory

In the previous post I discussed various characteristics functional programming languages might have, concepts such as purity, caching, idempotency (I got comments that higher-order functions, laziness and currying were missing. I agree. They were missing). We finished that post with the idea of effect tracking, i.e., making it explicit, and thus, more easily analysable, where an effect happens. This way, the IDE can report errors if effects occur in places where it is not allowed (for example, in preconditions) and exploit purity in the execution, for example through caching.

We also discussed that one usually uses immutable data structures in functional languages because, in order to cache previous results of functions, those values cannot change once they have been “released to the wild” by a function (there are other reasons why immutable data is useful as well).

In this post I will discuss further the handling of state in functional programs.

Boxes

Immutable data means that you cannot change a value once it has been created. For primitive types, this is rather intuitive. For example in …

val a = 1 + 2
val b = 3 + a
val x = a + b

… it is rather intuitive that 1+2 creates a new value 3, and that adding a and b creates a new value c. It’s maybe not so obvious that you cannot reassign a variable later:

val x = a + b
x = x + 1 // invalid

The problem with this is that anybody who has a reference to x now sees the value of x changing. So you have to invent a new name for the new value (this can sometimes be a bit annoying).

Let us look at collections. Assume you have a list of three elements and you add a fourth one:

val l1 = list(1, 2, 3)
val l2 = l1.plus(4)
assert l1.size == 3
assert l2.size == 4

So here, too, the original list remains unchanged and you get a new list, one that now has a fourth element, as the result of l1.plus(4).

So, how then, do you store changing global state, for example, a database of measurements? Using a new variable for each update “state of the database” is not a solution because it is *the* database that is supposed to change. One solution would be to introduce variables (as opposed to the values used so far):

var db = list(1, 2, 3) // note the r instead of the lfun store(x: int) {
  db.add(x)
}

So, for this to work, you will have to mark the add method to have an effect, which will, transitively, also give store an effect. That’s fine, this is what effect tracking is for. And the whole purpose of this function is to have an effect, so all is good. But: you need a whole second set of APIs for mutable collections. The list in this example cannot be the same list as the one used earlier; it’s a different class, a mutable list, called mlist. You need mutable versions of all collections. This approach is a valid solution, and some languages, for example, Scala, use it.

There is another approach that does not require a second set of types: boxes. You explicitly package a value inside a box. The box itself is immutable (i.e., its own reference stays stable), but its contents can change:

val globalcounter: box<int> = box(0)fun incrCounter() {
  globalcounter.update(globalcounter.val + 1)
}

Apart from creation, boxes have two methods: a val that returns the contents of the box, as well as a update() method that sets a new value. The former has a read effect, the latter a modify effect. When you update the box’s content, you pass a new value, so you don’t need additional APIs for changing value — the boxes themselves are generic:

val db = box(list(1, 2, 3)) // we're back to a value here!fun store(x: int) {
  db.update(db.val.plus(4))
}

Now, while this approach is nice because you can stick with the original immutable APIs (plus the generic box functionality), it is also annoying because the usage syntax is kinda awkward. You can’t completely get rid of this, but you can make it less awkward by providing concise access to the current content of the box through the it expression:

val globaxlcounter = box(0)
val db             = box(list(1, 2, 3))fun incrCounter() { globalcounter.update(it + 1) }
fun store(x: int) { db.update(it.plus(4)) }

So that’s not quite as bad. In fact, I think it’s ok! There’s another nice example: in a concurrent setting, you can build it so that the it is initialized only once at the very beginning of the update, and the value stays stable even if the box contents change (and you reference it multiple times).

KernelF uses this approach. I think it is very similar (identical?) to what Clojure does; boxes are called refs there.

In terms of implementation, for example, in an interpreter, boxes are really just wrapper objects with a method to get and set a generic java.lang.Objectbox content. The val and update operations are interpreted by the interpreter to call those methods on the runtime Java object.

public class BoxValue {
  private Object value;
  public BoxValue(Object initial) { this.value = initial; }
  public void set(Object newValue) { this.value = newValue; }
  public Object get() { this.value; }
}

Native Mutable Data

The embodiment of changing state are state machines (surprise!). Here is a minimal one that represents a (slightly contrivted) counter:

It defines two events (i.e., ways to trigger the machine), one to initialize the machine’s counter, and the other one to increment it. It has two states, an initial state and operational state. The init event goes from the initial initstate to the count state, where it then accepts inc events. If the by value is less than 10, the counter gets incremented, otherwise a counter of invalidsincrementation attempts is increased (yeah, it’s a contrived example, but it’s simple).

The state machine (surprise again) is inherently stateful. So we don’t have to pretend anything’s immutable. This is why we allow an assignment operator := inside a state machine. Inside a state machine you can also read one of its variables by just mentioning its name (as in invalids + 1); you don’t need the val. This is kinda interesting from an interpreter perspective, because if a variable name is mentioned on the left of the assignment operator, it must evaluate to a box (so you can set the new value), and if it is used elsewhere, you want to evaluate to the contents of the box (in order for the existing implementation of, for example, the + to continue to work). Luckily, the AST structure makes it obvious whether a box or a value is required (relevant for type checking and for execution): you need the box if and only if it is used in the left slot of an assignment.

So how do you use a state machine? Here is how:

val ctr = start(CounterToMax).init(0) // start instantiates a SMfun doStuffWithCounter() {
  ctr.inc(5)      // now 5
  ctr.inc(3)      // now 8
  ctr.inc(20)     // invalid; still 8
  assert ctr.counter  == 8
  assert ctr.invalids == 1
}

Note that even though there is mutable state all over the place (and the various operations on state machines have effects!), there are no boxes to be seen. You don’t need an update, you don’t need val on anything. Why is this?

Well, internally the state machines still have box semantics (in the implementation, a bunch of interfaces for IBoxLike things are used to generalise box-like behavior). But state machines have been purpose-built to have state, there is no need to reuse existing immutable APIs, as was the case for primitive operators and collections.

Let’s look at the interpreter. To implement the variable references inside state machines, we use an interface ICanBeUsedAsLValue to mark that they can be used on the left side of an assignment (an “lvalue”). The interface has a method isUsedAsLValue that detects structurally, from the AST, if a particular variable reference is on the left side of an assignment. The interpreter uses this method to determine what it needs to evaluate to. Here is the generic interpreter for the assignment; note how it relies on the runtime representation of things that can be lvalues to implement the ILValueinterface to generically implement this functionality:

Object rvalue = #right; // recursively call interpreter on right
Object lvalue = #left;  // and left arguments
if (lvalue instanceof ILValue) {          // must be an ILValue
  ((ILValue) lvalue).updateValue(rvalue); // which has update method
} else {
  throw new InvalidValueException(node.left, "not an ILValue");
}
return rvalue;

In the case of state machines, the interpreter plays together with, the VarRefconcept that represents references to state machine variables. Look at its interpreter:

SmValue currentMachine = (SmValue) env[SmValue.THIS];
SMVarValue value = currentMachine.getVar(node.var);
if (node.isUsedAsLValue()) {
  return value;          // returns the box
} else {
  return value.value();  // returns box contents
}

It first retrieves the currently executing instance of the state machine from the environment (the triggers put that there), and then asks the current state machine for the variable that it references. Note that this returns the ILValue-implementing class that represents the variable. Then comes the crucial distinction: if the current variable reference is used in lvalue position, we return the ILValue (so that the assignment interpreter can call update). Otherwise we directly return the contents of the box (e.g., an int)

We are not going to discuss the implementation of the state machine’s behavior itself; it’s a bunch of if statements like any other state machine. What is important though, is that the current total state of the machine (the current state plus the values of all its variables) is also an immutable object. This will become important for state machines to work with transactions, as shown next.

Transactions

Take a look at the following code:

type intLE5: int where it <= 5

val c1: box<intLE5> = box(0)

val c2: box<intLE5> = box(0)fun incrementCounters(x1: int, x2: int) {
  c1.update(it + x1)
  c2.update(it + x2)
}

 

fun main() {
  incrementCounters(1, 1)
  incrementCounters(3, 5)
}

Boxes respect the constraints on their content type: if you set a value that violates the constraint, than the update fails. What actually happens then is configurable, at least in KernelF’s default interpreter: output a log message and continue, or throw an exception that terminates the interpreter. While, in the second case, the program stops anyway, and it doesn’t really matter which value is set, in the first case we run into the problem that, for the second invocation of incrementCountersc1 is updated correctly, but the update of c2 is faulty. In many cases, this is not what you want.

So what can you do? Enter transactions.

fun incrementCounters(x1: int, x2: int) tx{
  c1.update(it + x1)
  c2.update(it + x2)
}

A transaction block is like a regular block, but if something fails inside it (interpreter: an exception is thrown), it rolls back all the changes. This is really easy to implement: remember that values are immutable. So you can simply grab the value of each box (or more generally, ITransactionalValue) before you perform the update and remember them in the transaction. If you have to rollback, you just re-set the value you remembered. Real easy.

This also works with state machines, and with combinations of state machines and other boxes, as shown in the example below where the state machine modifies other global data.

Finally, the framework also supports nested transactions (which can be rolled back individually) as well as the distinction between starting a new transaction (with newtx) and a block requiring to be executed in an existing transaction (using intx).

Remember how above I said that the current total state of a state machine is also an immutable object; in other words, it also implements ITransactionalValue. The implementation of the transaction in the interpreter looks like this:

Transaction tx = new Transaction(node);
env[Transaction.KEY] = tx; // store in env for nested calls
try {
  Object res = #body;
  tx.commit();
  return res;
} catch (SomethingWentWrong ex) {
  tx.rollback();
} finally {
  env[Transaction.KEY] = null;  // no tx active anymore
}

Now, if you are in a concurrent setting and you need isolation you have to do a bit more work to implement transactions reasonably.

·       You want thread B not to see changes to global state performed in a transaction in thread A. So instead of updating the boxes and rolling back in case of a problem, you just record the updated value in the transaction itself and only upon commit (when nothing failed) you actually updatethe boxes.

·       Inside the transaction, however, you do want a call to .val to return the value you may have set earlier in the transaction. So .val has to check whether the current environment contains an active transaction, and if so, return that temporary value stored in that transaction, if any.

·       And finally, during commit, when you actually set the value, you want to check if it has been changed by another transaction in the meantime (easy to do, it’s just an identity check because values are immutable!). If so, you abort and don’t really commit.

This form of transactional memory is also used in Clojure, as far as I understand (please correct me if I am wrong).

Wrap Up

A few comments before we close. The boxes, assignment and transactions are a generic framework offered by the mutable extension of KernelF. Any stateful language construct can be integrated by implementing interfaces like ILValue or ITransactionalValue and adhering to a few idioms (such as checking whether an ICanBeUsedAsLValue is actually used on the left side of an assignment, an then returning the box).

Further, implementing this functionality in KernelF really helped me understand how the “magic” works in languages like Clojure. It also helped me appreciate the use of immutable data. I am getting more and more convinced that this is the way to go. One criticism about immutable data structures is their overhead. In particular, for collections, graphs and maps you have to copy things all the time. Not true! Modern implementations of persistent data structures, i.e., immutable data structures with sharing of unchanged parts, are really efficient. A recent workshop with Michael Steindorfer as well as some benchmarks we did in the context of a different project made that point very impressively.

Lastly: in some sense, functional languages and immutable data are more “primitive” than imperative or object-oriented languages, they just do less. However, combining this with language extensions that directly support relevant patterns, whether generic as discussed in this post, or domain-specific as in pattern number three here, can compensate for those “shortcomings” without compromising the appealing semantics of functional languages.