Skip to content

React

Build a small reactive system: input cells hold values that can be set, compute cells hold functions of other cells that stay up to date, and callbacks report when a compute cell’s value changes.

Adapted from Exercism’s problem specification (MIT). Listed under Collections & Algorithms.

// FILE: react.nomi
//# A reactive system: input cells and compute cells that follow them, with
//# callbacks on change.

/// A spreadsheet of named cells: input cells hold a value that is set, and
/// compute cells hold a function of other cells that is kept up to date. It
/// is a value: setting an input answers a new reactor.
pub opaque struct Reactor
    values:    Map<String, Int>
    inputs:    Set<String>
    computed:  List<Computed>
    callbacks: Map<String, String>
end

/// A compute cell: its name, the cells it reads, in order, and how it
/// computes its value from theirs.
struct Computed
    name:    String
    inputs:  List<String>
    compute: (Vector<Int>) -> Int
end

/// Why a cell cannot be made, set or watched.
pub enum Error
    /// A cell of this name already exists.
    Duplicate String
    /// No cell has this name.
    UnknownCell String
    /// The cell computes its value, so it cannot be set.
    NotAnInput String
end

impl Reactor
    /// A reactor with no cells.
    pub fn new() -> Reactor
        {values: {}, inputs: [], computed: [], callbacks: {}}
    end

    /// `reactor` with an input cell `name` holding `value`.
    pub fn input(reactor: Reactor, name: String, value: Int) -> Result<Reactor, Error>
        if name in reactor.values then return Err(.Duplicate(name))

        Ok({
            ..reactor,
            values: Map.put(.., name, value),
            inputs: Set.insert(.., name),
        })
    end

    /// `reactor` with a compute cell `name` whose value is `compute` of the
    /// values of `inputs`, in their order.
    pub fn compute(
        reactor: Reactor,
        name:    String,
        inputs:  List<String>,
        compute: (Vector<Int>) -> Int,
    ) -> Result<Reactor, Error>
        if name in reactor.values then return Err(.Duplicate(name))

        if Some(unknown) = Iter.find(inputs, &(not &1 in reactor.values)) then
            return Err(.UnknownCell(unknown))
        end

        cell = Computed{name:, inputs:, compute:}

        Ok({
            ..reactor,
            values:   Map.put(.., name, value_of(cell, ..)),
            computed: [.., cell],
        })
    end

    /// The value of the cell `name`, or `None` when there is none.
    pub fn value(reactor: Reactor, name: String) -> Maybe<Int>
        Map.get(reactor.values, name)
    end

    /// `reactor` with the input cell `name` set to `value` and every compute
    /// cell brought up to date, and the callbacks that fire: each callback
    /// watching a cell whose value changed, with the cell's new value.
    pub fn set_value(
        reactor: Reactor,
        name:    String,
        value:   Int,
    ) -> Result<(Reactor, Map<String, Int>), Error>
        if not name in reactor.values then return Err(.UnknownCell(name))

        if not name in reactor.inputs then return Err(.NotAnInput(name))

        set = Map.put(reactor.values, name, value)

        values = Iter.reduce(reactor.computed, set, fn values, cell ->
            Map.put(values, cell.name, value_of(cell, values))
        end)

        fired =
            reactor.callbacks
            |> Iter.filter(fn (_, cell) ->
                Map.get(values, cell)! != Map.get(reactor.values, cell)!
            end)
            |> Iter.map(fn (callback, cell) -> (callback, Map.get(values, cell)!))
            |> Iter.to_map()

        Ok(({..reactor, values:}, fired))
    end

    /// `reactor` with the callback `callback` watching the cell `cell`.
    pub fn add_callback(reactor: Reactor, cell: String, callback: String) -> Result<Reactor, Error>
        if not cell in reactor.values then return Err(.UnknownCell(cell))

        Ok({..reactor, callbacks: Map.put(.., callback, cell)})
    end

    /// `reactor` without the callback `callback` on `cell`; the same
    /// reactor when it is not there.
    pub fn remove_callback(reactor: Reactor, cell: String, callback: String) -> Reactor
        if Map.get(reactor.callbacks, callback) == Some(cell) then
            {..reactor, callbacks: Map.remove(.., callback)}
        else
            reactor
        end
    end
end

/// The value `cell` computes from `values`, which hold every cell it reads.
fn value_of(cell: Computed, values: Map<String, Int>) -> Int
    inputs =
        cell.inputs
        |> Iter.map(&Map.get(values, &1)!)
        |> Iter.to_vector()

    cell.compute(inputs)
end

// FILE: react_test.nomi
import react.{Error, Reactor}

/// One cell a case starts with: an input with its first value, or a compute
/// cell with the cells it reads and its function of their values.
enum Cell
    Input (String, Int)
    Compute (String, List<String>, (Vector<Int>) -> Int)
end

/// One canonical operation and what it should answer: a cell's value, an
/// input set and the callbacks that fire with their values, a callback added
/// or removed.
enum Step
    Value (String, Int)
    Set (String, Int, Map<String, Int>)
    AddCallback (String, String)
    RemoveCallback (String, String)
end

/// The reactor that holds `cells`, made in order.
fn build(cells: List<Cell>) -> Result<Reactor, Error>
    Iter.try_reduce(cells, Reactor.new(), fn reactor, cell ->
        case cell
            .Input((name, value))             -> Reactor.input(reactor, name, value)
            .Compute((name, inputs, compute)) -> Reactor.compute(reactor, name, inputs, compute)
        end
    end)
end

/// Runs each step's operation on `reactor`, in turn, and answers the steps
/// as they happened. A reactor that does what every step says answers the
/// steps it was given.
fn replay(reactor: Reactor, steps: List<Step>) -> Result<List<Step>, Error>
    (_reactor, happened) =
        steps
        |> Iter.map_reduce(reactor, fn reactor, step ->
            case step
                .Value((cell, _)) ->
                    case Reactor.value(reactor, cell)
                        Some(value) -> (reactor, Ok(Step.Value(cell, value)))
                        None        -> (reactor, Err(Error.UnknownCell(cell)))
                    end

                .Set((cell, value, _)) ->
                    case Reactor.set_value(reactor, cell, value)
                        Ok((next, fired)) -> (next, Ok(.Set(cell, value, fired)))
                        Err(error)        -> (reactor, Err(error))
                    end

                .AddCallback((cell, callback)) ->
                    case Reactor.add_callback(reactor, cell, callback)
                        Ok(next)   -> (next, Ok(.AddCallback(cell, callback)))
                        Err(error) -> (reactor, Err(error))
                    end

                .RemoveCallback((cell, callback)) ->
                    (
                        Reactor.remove_callback(reactor, cell, callback),
                        Ok(.RemoveCallback(cell, callback)),
                    )
            end
        end)

    Result.collect(happened)
end

test "react"
    [
        (
            "input cells have a value",
            [Cell.Input("input", 10)],
            [Step.Value("input", 10)],
        ),
        (
            "an input cell's value can be set",
            [.Input("input", 4)],
            [.Set("input", 20, {}), .Value("input", 20)],
        ),
        (
            "compute cells calculate initial value",
            [
                .Input("input", 1),
                .Compute("output", ["input"], fn v -> Vector.get(v, 0)! + 1),
            ],
            [.Value("output", 2)],
        ),
        (
            "compute cells take inputs in the right order",
            [
                .Input("one", 1),
                .Input("two", 2),
                .Compute("output", ["one", "two"], fn v ->
                    Vector.get(v, 0)! + Vector.get(v, 1)! * 10
                end),
            ],
            [.Value("output", 21)],
        ),
        (
            "compute cells update value when dependencies are changed",
            [
                .Input("input", 1),
                .Compute("output", ["input"], fn v -> Vector.get(v, 0)! + 1),
            ],
            [.Set("input", 3, {}), .Value("output", 4)],
        ),
        (
            "compute cells can depend on other compute cells",
            [
                .Input("input", 1),
                .Compute("times_two", ["input"], fn v -> Vector.get(v, 0)! * 2),
                .Compute("times_thirty", ["input"], fn v -> Vector.get(v, 0)! * 30),
                .Compute("output", ["times_two", "times_thirty"], fn v ->
                    Vector.get(v, 0)! + Vector.get(v, 1)!
                end),
            ],
            [.Value("output", 32), .Set("input", 3, {}), .Value("output", 96)],
        ),
        (
            "compute cells fire callbacks",
            [
                .Input("input", 1),
                .Compute("output", ["input"], fn v -> Vector.get(v, 0)! + 1),
            ],
            [.AddCallback("output", "callback1"), .Set("input", 3, {"callback1" => 4})],
        ),
        (
            "callback cells only fire on change",
            [
                .Input("input", 1),
                .Compute("output", ["input"], fn v ->
                    if Vector.get(v, 0)! < 3 then 111 else 222
                end),
            ],
            [
                .AddCallback("output", "callback1"),
                .Set("input", 2, {}),
                .Set("input", 4, {"callback1" => 222}),
            ],
        ),
        (
            "callbacks do not report already reported values",
            [
                .Input("input", 1),
                .Compute("output", ["input"], fn v -> Vector.get(v, 0)! + 1),
            ],
            [
                .AddCallback("output", "callback1"),
                .Set("input", 2, {"callback1" => 3}),
                .Set("input", 3, {"callback1" => 4}),
            ],
        ),
        (
            "callbacks can fire from multiple cells",
            [
                .Input("input", 1),
                .Compute("plus_one", ["input"], fn v -> Vector.get(v, 0)! + 1),
                .Compute("minus_one", ["input"], fn v -> Vector.get(v, 0)! - 1),
            ],
            [
                .AddCallback("plus_one", "callback1"),
                .AddCallback("minus_one", "callback2"),
                .Set("input", 10, {"callback1" => 11, "callback2" => 9}),
            ],
        ),
        (
            "callbacks can be added and removed",
            [
                .Input("input", 11),
                .Compute("output", ["input"], fn v -> Vector.get(v, 0)! + 1),
            ],
            [
                .AddCallback("output", "callback1"),
                .AddCallback("output", "callback2"),
                .Set("input", 31, {"callback1" => 32, "callback2" => 32}),
                .RemoveCallback("output", "callback1"),
                .AddCallback("output", "callback3"),
                .Set("input", 41, {"callback2" => 42, "callback3" => 42}),
            ],
        ),
        (
            "removing a callback multiple times doesn't interfere with other callbacks",
            [
                .Input("input", 1),
                .Compute("output", ["input"], fn v -> Vector.get(v, 0)! + 1),
            ],
            [
                .AddCallback("output", "callback1"),
                .AddCallback("output", "callback2"),
                .RemoveCallback("output", "callback1"),
                .RemoveCallback("output", "callback1"),
                .RemoveCallback("output", "callback1"),
                .Set("input", 2, {"callback2" => 3}),
            ],
        ),
        (
            "callbacks should only be called once even if multiple dependencies change",
            [
                .Input("input", 1),
                .Compute("plus_one", ["input"], fn v -> Vector.get(v, 0)! + 1),
                .Compute("minus_one1", ["input"], fn v -> Vector.get(v, 0)! - 1),
                .Compute("minus_one2", ["minus_one1"], fn v -> Vector.get(v, 0)! - 1),
                .Compute("output", ["plus_one", "minus_one2"], fn v ->
                    Vector.get(v, 0)! * Vector.get(v, 1)!
                end),
            ],
            [.AddCallback("output", "callback1"), .Set("input", 4, {"callback1" => 10})],
        ),
        (
            "callbacks should not be called if dependencies change but output value doesn't change",
            [
                .Input("input", 1),
                .Compute("plus_one", ["input"], fn v -> Vector.get(v, 0)! + 1),
                .Compute("minus_one", ["input"], fn v -> Vector.get(v, 0)! - 1),
                .Compute("always_two", ["plus_one", "minus_one"], fn v ->
                    Vector.get(v, 0)! - Vector.get(v, 1)!
                end),
            ],
            [
                .AddCallback("always_two", "callback1"),
                .Set("input", 2, {}),
                .Set("input", 3, {}),
                .Set("input", 4, {}),
                .Set("input", 5, {}),
            ],
        ),
    ]
    |> subtests (description, cells, steps), description
        assert Ok(reactor) = build(cells)

        assert replay(reactor, steps) == Ok(steps)
    end
end

// Not canonical: the canonical cells are all well made and every operation
// names a cell that exists.
test "a cell's name is used once"
    reactor = Reactor.new() |> Reactor.input("input", 1)?

    assert Err(.Duplicate("input")) = Reactor.input(reactor, "input", 2)
end

test "a compute cell reads only cells that exist"
    result = Reactor.new() |> Reactor.compute("output", ["input"], fn v -> Vector.get(v, 0)!)

    assert Err(.UnknownCell("input")) = result
end

test "only an input cell can be set"
    reactor = build([.Input("input", 1), .Compute("output", ["input"], fn v -> Vector.get(v, 0)!)])?

    assert Err(.NotAnInput("output")) = Reactor.set_value(reactor, "output", 2)
    assert Err(.UnknownCell("missing")) = Reactor.set_value(reactor, "missing", 2)
end
  • Adapted: the exercise asks for cells that are objects updated in place and callbacks that are functions run for their effect when a value changes. Nomi values cannot change and a function cannot record that it ran, so the reactor is a value, set_value answers the reactor after the change, and a callback is a name: set_value also answers the callbacks that fire, each with its cell’s new value, as a Map<String, Int>. The canonical “expect callbacks” and “expect callbacks not to be called” become that one map, compared whole.
  • Reactor is an opaque struct of every cell’s value by name, the set of input names, the compute cells in the order they were made, and each callback’s cell. A compute cell may read only cells made before it, so the cells in order are already sorted by dependency: set_value recomputes them in one Iter.reduce, each exactly once, which is why a cell with two changed inputs fires its callbacks once. A callback fires when its cell’s value before and after differ, so a recomputed cell whose value stays the same fires nothing.
  • Every name a cell reads or a callback watches was checked when it was made, so the reactor reads values with Map.get(...)!, which traps on a missing key, rather than Map.get.
  • A compute cell’s function takes its inputs’ values as a Vector<Int> in the order the cell names them, so the canonical inputs[0] + inputs[1] * 10 is fn v -> Vector.get(v, 0)! + Vector.get(v, 1)! * 10.
  • Making or setting a cell answers a Result: a name used twice, an unknown cell, and setting a compute cell are Error variants. The canonical data never makes these mistakes; the test file adds three tests, marked not canonical, for them. They assert with a pattern, assert Err(Error.NotAnInput("output")) = ..., since a reactor holds functions and so has no ==.
  • The canonical cases are cells and lists of operations, so the test file follows circular-buffer: each case lists its Cells, which build makes in order, and its Steps (Value, Set with the callbacks it fires, AddCallback, RemoveCallback), which replay runs with one Iter.map_reduce; each row asserts replay(reactor, steps) == Ok(steps). The 14 cases are one subtests table named by the description column.