A basic reactive system

I’m making a pause in the “semaphores” series to visit a problem from exercism.io, namely react in Go. As the description says, the idea is to implement a basic reactive system in Go.

Wikipedia defines “reactive programming” as “a programming paradigm oriented around data flows and the propagation of change. This means that it should be possible to express static or dynamic data flows with ease in the programming languages used, and that the underlying execution model will automatically propagate changes through the data flow.”

Basically, any modern spreadsheet program.

In the proposed exercise, the idea is to “implement a basic reactive system with cells with settable values (“input” cells) and cells with values computed in terms of other cells (“compute” cells). Implement updates so that when an input value is changed, values propagate to reach a new stable system state.”

This is exercise is the first one that (at least for me) requires a less-than-trivial amount of code to solve it. It’s also interesting because it forces you to deal with a Go feature that is often overlooked: interfaces. This is why I thought it would make for an interesting blog post.

As usual in exercism.io, a series of tests are provided, and in this case also some basic starting code.

Looking at the tests, the first one is very simple:

func TestSetInput(t *testing.T) {
	r := New()
	i := r.CreateInput(1)
	assertCellValue(t, i, 1, "i.Value() doesn't match initial value")
	i.SetValue(2)
	assertCellValue(t, i, 2, "i.Value() doesn't match changed value")
}

The function New returns an instance of “something” satisfying the interface Reactor, which looks like this:

// A Reactor manages linked cells.
type Reactor interface {
	// CreateInput creates an input cell linked into the reactor
	// with the given initial value.
	CreateInput(int) InputCell

	// CreateCompute1 creates a compute cell which computes its value
	// based on one other cell. The compute function will only be called
	// if the value of the passed cell changes.
	CreateCompute1(Cell, func(int) int) ComputeCell

	// CreateCompute2 is like CreateCompute1, but depending on two cells.
	// The compute function will only be called if the value of any of the
	// passed cells changes.
	CreateCompute2(Cell, Cell, func(int, int) int) ComputeCell
}

As you can see, a reactor basically creates several kinds of cells. The fact that the documentation says that it manages them is interesting, as it suggests a possible implementation that the person who developed the exercise had in mind.

If you examine the way New is used, the type returned by this function is never named explicitly in the tests. All that matters is that the interface is satisfied, in other words, that all the methods required by the interface are implemented.

My implementation of New looks like this:

func New() Reactor {
	return &reactor{}
}

where a pointer to reactor satisfies the Reactor interface. In order to pass the first test, CreateInput looks like this:

func (r *reactor) CreateInput(i int) InputCell {
	return &inputCell{cell: cell{v: i}}
}

why a pointer receiver if the receiver is not getting changed? Initially I though that reactor was going to manage the cells it created, as the documentation for the interface suggested, but since I followed a TDD approach to solving the exersice, eventually the implementation went in a different direction and this wasn’t necessary.

A pointer to inputCell satisfies the InputCell interface, and the type looks like this:

type inputCell struct {
	cell
}

It embeds another type cell because there some common parts shared with other two cell types. This mimics the InputCell interface:

// A Cell is conceptually a holder of a value.
type Cell interface {
	// Value returns the current value of the cell.
	Value() int
}

// An InputCell has a changeable value, changing the value triggers updates to
// other cells.
type InputCell interface {
	Cell

	// SetValue sets the value of the cell.
	SetValue(int)
}

InputCell embeds the Cell interface. My Initial inputCell implementation didn’t do this and instead satisfied the interface by implementing the methods directly. After some refactoring, cell stores the value of the cell and provides the Value() method. This will become important later. inputCell extends this by implementing the SetValue(int) method:

func (i *inputCell) SetValue(v int) {
	i.setValue(v)
}

where the setValue(int) method is actually provided by the cell type. With this it’s enough to pass the first test.

The other two methods of the Reactor interface (CreateCompute1 and CreateCompute2) follow a similar logic: create an instance of a type that implements the ComputeCell interface:

// A ComputeCell always computes its value based on other cells and can
// call callbacks upon changes.
type ComputeCell interface {
	Cell

	// AddCallback adds a callback which will be called when the value changes.
	// It returns a callback handle which can be used to remove the callback.
	AddCallback(func(int)) CallbackHandle

	// RemoveCallback removes a previously added callback, if it exists.
	RemoveCallback(CallbackHandle)
}

There are multiple underlying types, because they need to store different information. As the documentation says, the callback is called with the value changes. This means that the compute cell needs to known the its inputs change. I figured the simplest way to achieve that was to add the callback mechanism to the cell type, which is why it actually looks like this:

type cell struct {
	v         int
	callbacks map[int]func(int)
}

the cell stores callbacks to be called when the stored value changes. This is why cell has a setValue method:

func (c *cell) setValue(v int) int {
	if c.v != v {
		c.v = v
		for _, cb := range c.callbacks {
			cb(c.v)
		}
	}

	return c.v
}

This method checks that the new value is different from the current value, and if that’s the case, it stores the new value and calls the callbacks.

What this means is that when the value in the inputCell is changed, its callbacks are called. In this way, creating a computeCell1 looks like this:

func (r *reactor) CreateCompute1(c Cell, f func(int) int) ComputeCell {
	cc := &computeCell1{i: c, f: f}

	if a, ok := c.(addCallbacker); ok {
		a.addCallback(func(int) { cc.Value() })
	}

	// This forces one evaluation of the inputs
	cc.Value()

	return cc
}

here addCallbacker is an interface that requires the addCallback method to be implemented. All the actual types that satisfy the Cell interface also satisfy this other interface, so the type assertion is always going to work. It’s worth nothing that this is always possible to do: if you have a value passed using an interface, you can type-assert to a different interface to check that the actual type of the value satisfies the other interface.

The callback is written like that to adapt the signature of the existing method to that of the callbacks.

The other function (CreateCompute2) is very similar, with the only difference that is necessary to register two callbacks.

Why is the callback calling Value()? Because it made the implementation simple:

func (c *computeCell1) Value() int {
	return c.setValue(c.f(c.i.Value()))
}

func (c *computeCell2) Value() int {
	return c.setValue(c.f(c.i1.Value(), c.i2.Value()))
}

as you can see, the compute cells perform the computation when the Value() is queried and they store the newly computed value. If the value doesn’t change, setValue won’t change the stored value and the callbacks won’t be called. Since Value is called when the inputs change, this causes the compute cells to propage the changes as they happen.

If you look closely, this implementation is far from optimal, because the computations might be done multiple times for a single change. For example, if you have i -> c1 -> c2, changing the value in i will call Value in c1, which triggers the call to Value in c2, which in turn calls Value in c1, which doesn’t call the callbacks again because that second time the value doesn’t change (but you can pass a function to the compute cell that causes this process to enter a loop).

Nevertheless I found it interesting that the problem has a relatively simple solution that uses very straightforward constructions.

Next week is back to the semaphores series.