A spreadsheet, I: cells are atoms

Tic-tac-toe built an application out of names, and every answer in it changed for one reason: somebody played a move. This arc builds something a little bigger, a spreadsheet, and it brings two things tic-tac-toe did not have. A cell can hold code: a formula, which has to be compiled before it can run. And one edit ripples: change one number and every total that reads it, and every total that reads those, is wrong until it is computed again. Spreadsheet engines are built around that second problem. This arc’s claim is that the kernel already solves it, and that an application built as resources never writes a recalculation engine at all.

It comes in parts, as tic-tac-toe did. This one draws the model on paper and builds the atoms: the cells as a person types into them, the values of those that hold no formula, and the grid that shows them. Part II makes a formula a resource, compiled and cached like any other answer. Part III edits one cell and watches exactly the cells that depend on it compute again.

The model, on paper

As before, the names come first. A cell is named by its column and row, A1 to D6: a small sheet, four columns by six rows, which is enough to show everything and small enough to see all of it at once.

Only the input holds state. Everything below it in the table is a question about inputs: what does this one compile to, which cells does it read, what is its value. That is the same bet tic-tac-toe made, with one difference that matters later. There, the questions were about marks, and a mark is data. Here, some inputs are programs.

/// What was typed into a cell: the atom.
pub const INPUT: &str = "urn:iki:tutorial:sheet:input:{ref}";

/// The compiler: formula text in, an s-expression out.
pub const COMPILE: &str = "urn:iki:tutorial:sheet:compile";

/// A cell's formula, compiled.
pub const FORMULA: &str = "urn:iki:tutorial:sheet:formula:{ref}";

/// The cells a cell's formula reads.
pub const REFS: &str = "urn:iki:tutorial:sheet:refs:{ref}";

/// Every cell a cell's value depends on, however far back.
pub const PRECEDENTS: &str = "urn:iki:tutorial:sheet:precedents:{ref}";

/// The cells in a rectangle.
pub const RANGE: &str = "urn:iki:tutorial:sheet:range:{from}:{to}";

/// A cell's value.
pub const CELL: &str = "urn:iki:tutorial:sheet:cell:{ref}";

/// A piece of the sheet's HTML.
pub const TEMPLATE: &str = "urn:iki:tutorial:sheet:template:{name}";

/// A cell's value, as HTML.
pub const VIEW_CELL: &str = "urn:iki:tutorial:sheet:view:cell:{ref}";

/// The grid, as HTML.
pub const VIEW_GRID: &str = "urn:iki:tutorial:sheet:view:grid";

/// The formula bar's write: set or clear one cell's input.
pub const VIEW_EDIT: &str = "urn:iki:tutorial:sheet:view:edit";

There is no name for “the dependents of a cell”, the list a spreadsheet engine keeps so it knows what to recompute after an edit. That is not an oversight. It is the subject of Part III.

A cell has one name

A cell is written A1: a capital letter for the column, then the row, with no leading zero. Only that spelling names a cell, and only the cells on the sheet have names:

/// The cell a name's `{ref}` (or other binding) names, on the sheet, in its one spelling.
fn cell_binding(inv: &Invocation<'_>, binding: &str) -> Result<CellRef> {
    let text = inv
        .bindings
        .get(binding)
        .ok_or_else(|| Error::MissingArgument(binding.to_string()))?;
    on_sheet(binding, text)
}

/// `text` as a cell of the sheet, or a refusal naming `argument` and saying what to fix.
fn on_sheet(argument: &str, text: &str) -> Result<CellRef> {
    let refuse = |detail: String| Error::InvalidArgument {
        name: argument.to_string(),
        detail,
    };
    let cell = CellRef::parse(text).ok_or_else(|| {
        refuse(format!(
            "`{text}` is not a cell: a capital letter for the column, then the row (e.g. B3)"
        ))
    })?;
    if !cell.on_sheet() {
        return Err(refuse(format!(
            "{cell} is off the sheet, which is columns {}–{} and rows 1–{}",
            &formula::COLUMNS[..1],
            &formula::COLUMNS[formula::COLUMNS.len() - 1..],
            formula::ROWS
        )));
    }
    Ok(cell)
}

The strictness is the one tic-tac-toe had, for the same reason. The kernel caches an answer under the name it was asked by, and cuts a golden thread by name. If a1 and A1 both named the top-left cell, a write to one would leave a cached answer under the other, still wrong, with nothing to cut it. So there is one spelling, and the rest are refused with a word on what to fix:

error: invalid argument `ref`: `a1` is not a cell: a capital letter for the column, then the row (e.g. B3)
       `ref`: the cell, A1 to D6
error: invalid argument `ref`: E1 is off the sheet, which is columns A–D and rows 1–6
       `ref`: the cell, A1 to D6

The page’s formula bar, further down, is more forgiving: it is the edge where a person types, so it takes a1 and writes to A1. The names themselves are not.

The input: the atom

What was typed into each cell is kept in memory, in a map the host holds. (It keeps every write, each stamped with the time; until Part VI only the latest one matters.)

/// What has been typed into each cell, and when: every write, oldest first. The sheet's one
/// piece of state. A write is stamped with the kernel's clock (0 on a kernel with none), and a
/// clear is a write of nothing.
#[derive(Debug, Default)]
pub struct InputStore {
    inputs: Mutex<BTreeMap<CellRef, Vec<Write>>>,
}

/// One write to a cell: when, in milliseconds since 1970, and what was typed (`None` clears).
#[derive(Clone, Debug)]
struct Write {
    at: u64,
    typed: Option<String>,
}

The endpoint over it takes three verbs. Sink stores what was typed, trimmed, and answers what it stored; Source reads it back; Delete clears it. A cell nobody has typed into is NotFound, the way an unplayed square is:

/// `sheet-input`: what was typed into the cell `ref`, held in memory.
///
/// `Source` answers the text as typed, `.cacheable()` with no thread named: the kernel
/// hangs it from its own name, and cuts that after every `Sink` or `Delete` here. The media
/// type says what the text is. A formula, which starts with `=`, is `text/x-formula`;
/// anything else is `text/plain`. A cell nobody has typed into is `NotFound`.
///
/// `Sink` stores `content`, trimmed, and answers what it stored; an empty input is refused,
/// since "nothing" is what `Delete` says. Every write is kept, stamped with the kernel's
/// clock, so the sheet can be read as it stood at any instant (part VI).
pub fn input(store: Arc<InputStore>) -> FnEndpoint {
    FnEndpoint::new("sheet-input", move |inv: &Invocation<'_>| {
        let at = cell_binding(inv, "ref")?;
        match inv.request.verb {
            Verb::Sink => {
                let typed = typed_content(inv)?;
                store.write(at, stamp(inv), Some(typed.to_string()))?;
                Ok(Representation::new(
                    text_plain_utf8(),
                    typed.as_bytes().to_vec(),
                ))
            }
            Verb::Delete => {
                store.write(at, stamp(inv), None)?;
                Ok(Representation::new(text_plain_utf8(), b"ok".to_vec()))
            }
            _ => match store.latest(at) {
                Some(typed) => Ok(typed_repr(typed).cacheable()),
                None => Err(Error::NotFound(format!("nothing has been typed into {at}"))),
            },
        }
    })
    .with_description(
        Description::new("sheet-input")
            .title("Input")
            .summary("What was typed into a cell: read it, type into it, or clear it.")
            .verb(Verb::Meta)
            .action(
                ActionSpec::new(Verb::Source)
                    .summary("the input as typed; text/x-formula for a formula, NotFound if empty")
                    .input(ref_input("the cell, A1 to D6"))
                    .output(TEXT_PLAIN_UTF8)
                    .output(FORMULA_TYPE),
            )
            .action(
                ActionSpec::new(Verb::Sink)
                    .summary("type into the cell, and answer what was stored")
                    .input(ref_input("the cell, A1 to D6"))
                    .input(
                        ArgSpec::new("content")
                            .summary("a number, some text, or a formula starting with =")
                            .class(XSD_STRING),
                    )
                    .output(TEXT_PLAIN_UTF8),
            )
            .action(
                ActionSpec::new(Verb::Delete)
                    .summary("clear the cell")
                    .input(ref_input("the cell, A1 to D6"))
                    .output(TEXT_PLAIN_UTF8),
            ),
    )
}

One detail is new. The answer’s media type says what kind of input it is: a formula, anything starting with =, is served as text/x-formula, and everything else as text/plain. Nothing in this part reads that, but Part II’s compiler is found by it.

Type into a cell, and read it back:

42
[uncacheable]
42
[computed]
42
[cached]
error: not found: nothing has been typed into B1

The value, and the empty cell

The input is what a person typed. The value is what the cell shows, and it is the name everything else reads, just as tic-tac-toe’s platonic cell was. For a cell holding a number or some text, the value is the input, passed through. For a cell nobody has typed into, the value is empty: every cell of the sheet has a value before anything is typed, so nothing has to create a sheet before reading one.

The value endpoint is one function, and most of it belongs to Part II, which gives the formula branch its meaning. The first two arms are this part’s:

/// `sheet-cell`: the cell's value.
///
/// A cell nobody has typed into is empty. A literal (a number, some text) passes through as
/// typed. A formula is evaluated: first the cell's precedents are read, and a cell among its
/// own is `#CYCLE`; otherwise the compiled form is read back and evaluated over the values
/// of the cells it names.
///
/// Every answer is `.cacheable()` and names no thread. It hangs from what it read: the
/// input, the compiled formula, the precedents, and the values of the cells the formula
/// named. So typing into a cell cuts that cell's value, and the values that read it, and the
/// values that read those, and nothing else.
pub fn cell() -> AsyncFnEndpoint {
    AsyncFnEndpoint::new("sheet-cell", |inv: &Invocation<'_>| -> InvokeFuture<'_> {
        Box::pin(async move {
            let at = cell_binding(inv, "ref")?;
            let typed = typed_into(inv, at).await?;
            let value = match &typed {
                None => String::new(),
                Some(literal) if literal.repr_type.media_type != FORMULA_TYPE => {
                    String::from_utf8_lossy(&literal.bytes).into_owned()
                }
                Some(_) => {
                    let precedents = text_of(inv, &precedents_name(at)).await?;
                    if lines_of(&precedents).any(|name| cell_of(name) == Some(at)) {
                        CYCLE_ERROR.to_string()
                    } else {
                        let expr = compiled(inv, at, typed.as_ref()).await?.ok_or_else(|| {
                            Error::Endpoint(format!("{at} held a formula and then did not"))
                        })?;
                        eval(inv, &expr).await?.text()
                    }
                }
            };
            Ok(Representation::new(text_plain_utf8(), value.into_bytes()).cacheable())
        })
    })
    .with_description(
        Description::new("sheet-cell")
            .title("Cell")
            .summary(
                "A cell's value: a literal as typed, or its formula evaluated. Errors are \
                 values: #REF, #DIV/0, #CYCLE, #VALUE, #SYNTAX, #N/A.",
            )
            .verb(Verb::Source)
            .verb(Verb::Meta)
            .input(ref_input("the cell, A1 to D6"))
            .output(TEXT_PLAIN_UTF8),
    )
}

Type text into a cell, and ask for its value twice:

Rent
[uncacheable]
Rent
[computed]
Rent
[cached]

Now ask for a cell nobody has touched:

[cached]

No text, since the value is empty, and [cached] the first time you asked. Nothing on this page had asked for C5, as far as the cells go. The grid at the bottom of the page had: it shows every value on the sheet, and it asked for all twenty-four when the page loaded. The grid and the cells are one kernel with one cache, so the grid’s answer is the cell’s.

A write cuts what was built on it

The value of C5 is cached, and it is empty. What happens when somebody types into C5? Nothing in the value endpoint names a golden thread, and nothing in the input endpoint cuts one. Ask:

cached
hello
[uncacheable]
not cached
hello
[computed]

The kernel did both halves. When the value was computed, it read the input through the kernel, and the kernel recorded that read as a dependency, a failed one: the input was NotFound. A failed read counts, because an answer built on a resource’s absence is as wrong as one built on its content once it appears. So the empty value hung from the thread named after the input, and the Sink to the input cut that thread.

That is the same thing tic-tac-toe’s empty square did, and it is the rule the whole arc rests on: a value depends on exactly what it read, and the kernel keeps the list.

Delete is a write too, so clearing a cell brings the empty value back, computed again:

ok
[uncacheable]
[computed]

The grid

The grid is HTML, and it is resources in the way tic-tac-toe’s board was: templates, and views that fill them. The grid’s template is a table with a marker in each cell:

<table class="sheet-grid">
<caption>The sheet: the value of each cell</caption>
<thead><tr><td></td><th scope="col">A</th><th scope="col">B</th><th scope="col">C</th><th scope="col">D</th></tr></thead>
<tbody>
<tr><th scope="row">1</th><td>$r{urn:iki:tutorial:sheet:view:cell:A1}</td><td>$r{urn:iki:tutorial:sheet:view:cell:B1}</td><td>$r{urn:iki:tutorial:sheet:view:cell:C1}</td><td>$r{urn:iki:tutorial:sheet:view:cell:D1}</td></tr>
<tr><th scope="row">2</th><td>$r{urn:iki:tutorial:sheet:view:cell:A2}</td><td>$r{urn:iki:tutorial:sheet:view:cell:B2}</td><td>$r{urn:iki:tutorial:sheet:view:cell:C2}</td><td>$r{urn:iki:tutorial:sheet:view:cell:D2}</td></tr>
…

Each marker names one cell’s view, view:cell:{ref}, and that view is a template too, of one marker:

$h{urn:iki:tutorial:sheet:cell:{ref}}

The markers are the language of urn:iki:fn:compose, the generic composer from ikigai-fn. A marker names a resource; compose resolves it and splices the answer in, and there are three ways to splice. $h{…} splices the answer as text, escaped for HTML. $r{…} splices it as it is, as trusted markup: here, a view the kernel has already composed. $a{…} splices it as it is and then expands any markers in it, which is how one template includes another. The time chapter’s clock is one marker of the first kind, and Tic-tac-toe, V teaches the whole language.

A view is a template bound at a name. compose_over makes the binding, and the variables the name captures are the template’s arguments, so view:cell:B2 is the cell template with {ref} = B2:

/// A view: the template `name`, filled by `urn:iki:fn:compose`'s rules and bound at a name
/// of its own. The variables the name captures (`{ref}`) are the template's arguments.
/// There is no code here that reads a cell: the template names what it shows.
pub fn view(name: &str) -> ComposeOver {
    ikigai_fn::compose_over(iri(&template_name(name)).expect("a template's name is a name"))
}

        .bind(template(VIEW_CELL), view("cell"))
        .bind(template(VIEW_GRID), view("grid"))
        .bind(template(VIEW_CACHED), view("cached"))
        .bind(template(VIEW_COST_CELL), view("cost-cell"))
        .bind(template(VIEW_COST), view("cost"))

That is all the code the grid has. (The last three bindings are the cost table Part III adds.) The template says which cells there are and where they go, and each cell’s view says how a value is shown, so there is no four and no six in any code, and no code that reads a cell.

How a value is shown is the part that matters, because a value is text a person typed. $h escapes what it splices, so a cell holding <b> shows <b> rather than turning the rest of the row bold. And $h never expands what it splices, so a cell holding a marker shows the marker as typed. If it did, anybody who could type into a cell could make the page resolve any name they liked, and show the answer: $a{urn:kernel:cache} in a cell would print the kernel’s cache into the grid. Only $a expands what it splices, and the sheet never uses it: every marker in its templates is $h or $r.

<b>not bold</b> $a{urn:kernel:cache}
[uncacheable]
&lt;b&gt;not bold&lt;/b&gt; $a{urn:kernel:cache}
[computed]

A view reads a value and nothing else, so it is cached with the value and cut with it, like any other composite.

A sheet you can type into

Here is the sheet. The grid is the view above; the formula bar under it names a cell and what to type into it, and Enter writes it. Empty input clears the cell.

The formula bar is a form, and the form’s write is one more resource, view:edit. It takes the cell and the input as named arguments, the way a server would read a form body, and it writes the input with a Sink through the kernel, or clears it with a Delete:

/// `sheet-view-edit`: the formula bar's write. `Sink` only.
///
/// `ref` is the cell as a person typed it (`b3` will do: this is the human edge, so it is
/// forgiving here and nowhere else); `content` is what to type into it. Empty content
/// clears the cell. The write is a `Sink` (or a `Delete`) to the cell's input, through the
/// kernel, and the answer is one line of HTML text saying what happened, a refusal included,
/// in the kernel's own words.
pub fn view_edit() -> AsyncFnEndpoint {
    AsyncFnEndpoint::new(
        "sheet-view-edit",
        |inv: &Invocation<'_>| -> InvokeFuture<'_> {
            Box::pin(async move {
                if inv.request.verb != Verb::Sink {
                    return Err(Error::Endpoint(
                        "an edit is made, not read: `sink` it (read the grid view)".to_string(),
                    ));
                }
                let typed_ref = inv.inline_str("ref")?.trim().to_ascii_uppercase();
                let content = inv
                    .inline_str("content")
                    .unwrap_or_default()
                    .trim()
                    .to_string();
                let said = match on_sheet("ref", &typed_ref) {
                    Err(refused) => refused.to_string(),
                    Ok(at) => {
                        let target = iri(&input_name(at))?;
                        let outcome = if content.is_empty() {
                            inv.issue(Request::new(Verb::Delete, target)).await
                        } else {
                            let request = Request::new(Verb::Sink, target)
                                .with_arg("content", ArgRef::Inline(content.clone().into_bytes()));
                            inv.issue(request).await
                        };
                        match outcome {
                            Ok(_) if content.is_empty() => format!("{at} is clear."),
                            Ok(_) => format!("{at} is now {content}."),
                            Err(refused) => refused.to_string(),
                        }
                    }
                };
                Ok(Representation::new(
                    text_html_utf8(),
                    escape(&said).into_bytes(),
                ))
            })
        },
    )
    .with_description(
        Description::new("sheet-view-edit")
            .title("Edit, as a view")
            .summary(
                "Type into a cell (or clear it) and answer, as HTML text, what happened — a \
                 refusal included.",
            )
            .verb(Verb::Sink)
            .verb(Verb::Meta)
            .input(
                ArgSpec::new("ref")
                    .summary("the cell, e.g. B3 (any case)")
                    .class(XSD_STRING),
            )
            .input(
                ArgSpec::new("content")
                    .summary("what to type into it; empty clears it")
                    .class(XSD_STRING)
                    .optional(),
            )
            .output(TEXT_HTML_UTF8),
    )
}

The page’s markup is one more template, template:page. It asks for the grid when it loads, and posts the form to iki/tutorial/sheet/view/edit, by the same rule as tic-tac-toe’s board: a relative path’s segments, joined by :, after urn:. After an edit, and after any cell on this page runs, the page draws the grid again, because a grid on the screen is HTML the kernel handed out earlier and nothing cuts that. Drawing it again is cheap: every value the edit did not touch is served from the cache.

Type a number into A3, and then a formula into A4: =A3*2. It works, and why it works is the next part.

What was built

No part of it caches anything or invalidates anything, and the empty cell went stale and came back without being told. The input is the only thing that holds state. The next part puts code in it.