Tic-tac-toe, II: lines, aliases and the board
Part I built the atom: a stored cell that holds a mark, and a platonic
cell that answers - where nothing has been played. Everything else in the game is a
gathering of cells, or a question about one, and this part builds the gatherings: a line
of cells, the eight lines a board has, and the board. It follows the fourth part of the
series Part I credits, which is where the original makes the same move.
Only one of the three new things is an endpoint worth reading. The eight lines are not code at all, and the board is a dozen lines that read three names. The lesson is what that arrangement does when a mark is played.
A line of cells has a name
A line of cells is named by its members, in order:
urn:iki:tutorial:ttt:cells:0.0,1.0,2.0 is the cells at (0,0), (1,0) and (2,0), read in
that order. Each member is x.y, and members are joined by commas.
/// A line of cells: the members, in order, each spelled `x.y`, joined by `,`.
pub const CELLS: &str = "urn:iki:tutorial:ttt:cells:{list}";
/// The board: every row, top to bottom.
pub const BOARD: &str = "urn:iki:tutorial:ttt:board";It is a sequence rather than a set, because a row reads left to right: the same three cells named the other way round are another line, and answer the other way round. And the model stays as loose as the cell’s. Any coordinates, any length, the same cell twice if you like — nothing in the name knows a board is three by three.
/// The members of a line, read out of its name: `0.0,1.0,2.0` is `(0,0) (1,0) (2,0)`.
///
/// The same strictness as a single cell's coordinates, for the same reason. Every member
/// is two integers in their plain form, joined by one `.`; members are joined by one `,`;
/// nothing else — no spaces, no empty member, no trailing comma. A list has exactly one
/// spelling, so a line has exactly one name, and one name is one cache entry and one
/// golden thread. The model stays loose about *which* cells: any coordinates, any
/// length, repeats allowed.
fn members(inv: &Invocation<'_>) -> Result<Vec<(i64, i64)>> {
let list = inv
.bindings
.get("list")
.ok_or_else(|| Error::MissingArgument("list".to_string()))?;
let refuse = |detail: String| Error::InvalidArgument {
name: "list".to_string(),
detail,
};
list.split(',')
.map(|member| match member.split_once('.') {
_ if member.is_empty() => Err(refuse(
"an empty member — cells are x.y, joined by single commas".to_string(),
)),
Some((x, y)) => Ok((plain_integer("list", x)?, plain_integer("list", y)?)),
None => Err(refuse(format!(
"`{member}` is not a cell spelled x.y (e.g. 0.2)"
))),
})
.collect()
}The one-spelling rule from Part I carries over, and for the same reason. Two spellings of
one line would be two names over one answer, so two cache entries, and a move would have to
find both. So a member is two integers in their plain form joined by one ., members are
joined by one ,, and there is nothing else: no spaces, no empty member, no trailing
comma. Both separators are safe everywhere the name travels. RFC 8141 allows , and .
in a URN. The engine’s grammar treats only whitespace, quotes, |, (, ), ; and a
.. standing alone as syntax. And a template’s last variable captures the rest of the
name, commas included.
/// `ttt-cells`: a line of cells — the marks of its members, side by side, in order.
///
/// A composite over the platonic cell, and nothing more: it sources each member through
/// the kernel and concatenates the answers, so an empty cell reads `-` and a row reads
/// like `X-O`. It is `.cacheable()` and names no thread; its dependencies are its
/// sub-requests, so a move that changes one member cuts this line's cached answer and
/// leaves every line that does not pass through that cell alone.
pub fn line_of_cells() -> AsyncFnEndpoint {
AsyncFnEndpoint::new("ttt-cells", |inv: &Invocation<'_>| -> InvokeFuture<'_> {
Box::pin(async move {
let mut marks = Vec::new();
for (x, y) in members(inv)? {
let cell = Iri::parse(cell_name(x, y))
.map_err(|e| Error::Endpoint(format!("a cell's name: {e}")))?;
marks.extend(inv.source(&cell).await?.bytes);
}
Ok(Representation::new(text_plain_utf8(), marks).cacheable())
})
})
.with_description(
Description::new("ttt-cells")
.title("Line of cells")
.summary("The marks of the named cells, in order, side by side: X-O.")
.verb(Verb::Source)
.verb(Verb::Meta)
.input(
ArgSpec::new("list")
.summary("the cells, in order: x.y joined by commas, e.g. 0.0,1.0,2.0")
.class(XSD_STRING)
.binding(),
)
.output(TEXT_PLAIN_UTF8),
)
}The endpoint is a composite over the platonic cell and nothing more. It sources each member
through the kernel, as any caller would, and puts the marks side by side. It is
.cacheable() and names no golden thread. Its dependencies are its sub-requests, and
Part I showed what the kernel does with those.
As in Part I, one kernel serves every cell on this page and keeps its cache between runs, so run them in order. A page starts on a fresh board. Here is a row of three empty cells, and a stranger line of two, one of them far off any board:
--- [computed] -- [computed]
And the second spellings, refused. A trailing comma is an empty member, and 01 is 1
spelled another way:
error: invalid argument `list`: an empty member — cells are x.y, joined by single commas
`list`: the cells, in order: x.y joined by commas, e.g. 0.0,1.0,2.0
error: invalid argument `list`: `01` is not an integer in its plain form (e.g. 0, 2, -1)
`list`: the cells, in order: x.y joined by commas, e.g. 0.0,1.0,2.0
The first line of each is the endpoint’s refusal, word for word. The indented line under it is
the shell’s, not the game’s: since ikigai-cli 0.1.63, a refusal of one named argument is
followed by what that argument’s own description says it takes, read from the endpoint’s
contract, so the fix sits next to the complaint. The game declared that description once, in
its ArgSpec, and never wrote it into an error message.
Rows, columns and diagonals: eight names, no code
A row is a line of cells with a shorter name. So it is written as exactly that: a name for a name. Eight exact rules, as text:
/// The rows, columns and diagonals of a 3×3 board, as names for lines of cells.
///
/// This table is where "three by three" lives — not in the cell, which takes any
/// coordinates, and not in the line, which takes any cells. `y` runs down the board, so
/// row 0 is the top row; a line reads left to right, or top to bottom, and diagonal 1
/// runs from the top-right corner to the bottom-left.
pub const LINES: &str = "\
exact urn:iki:tutorial:ttt:row:0 urn:iki:tutorial:ttt:cells:0.0,1.0,2.0
exact urn:iki:tutorial:ttt:row:1 urn:iki:tutorial:ttt:cells:0.1,1.1,2.1
exact urn:iki:tutorial:ttt:row:2 urn:iki:tutorial:ttt:cells:0.2,1.2,2.2
exact urn:iki:tutorial:ttt:column:0 urn:iki:tutorial:ttt:cells:0.0,0.1,0.2
exact urn:iki:tutorial:ttt:column:1 urn:iki:tutorial:ttt:cells:1.0,1.1,1.2
exact urn:iki:tutorial:ttt:column:2 urn:iki:tutorial:ttt:cells:2.0,2.1,2.2
exact urn:iki:tutorial:ttt:diagonal:0 urn:iki:tutorial:ttt:cells:0.0,1.1,2.2
exact urn:iki:tutorial:ttt:diagonal:1 urn:iki:tutorial:ttt:cells:2.0,1.1,0.2
";/// The game's space: the endpoints, wrapped in the table that names the lines.
pub fn space() -> Alias {
space_over(Arc::default())
}
/// [`space`], with the stored cells in a [`CellStore`] the caller keeps — so a test can
/// read the counter.
pub fn space_over(store: Arc<CellStore>) -> Alias {
space_with_store(Arc::new(stored_space(store)))
}
/// The game over ANY store: every composite, then `store` for the stored cells, all
/// wrapped in the table that names the lines.
///
/// Nothing here holds state. `store` is whatever binds [`STORED`] — the in-memory
/// [`stored_space`], or a peer in another process or language — and the composites reach
/// it by name, through the kernel, so they cannot tell which one answered.
pub fn space_with_store(store: Arc<dyn Space>) -> Alias {
// One table, shared: the aliases rewrite through it, and the rules read it.
let table = Arc::new(lines());
let composites = EndpointSpace::new()
.bind(template(CELL), platonic_cell())
.bind(template(CELLS), line_of_cells())
.bind(template(BOARD), board())
.bind(template(CHECKSET), checkset(Arc::clone(&table)))
.bind(template(WINNER), winner(Arc::clone(&table)))
.bind(template(TURN), turn())
.bind(template(MOVE), play_move())
.bind(template(RESET), reset(Arc::clone(&table)))
.bind(template(TEMPLATE), templates())
.bind(template(VIEW_BOARD), view("board"))
.bind(template(VIEW_SQUARE), view("square"))
.bind(template(VIEW_STATUS), view("status"))
.bind(template(VIEW_REPLY), view("reply"))
.bind(template(VIEW_GAME), view("game"))
.bind(template(VIEW_PLAY), view_play())
.bind(template(VIEW_RESET), view_reset());
Alias::new(
table,
Arc::new(Fallback::new(vec![Arc::new(composites), store])),
)
}
/// A store: the stored cell over one [`CellStore`], and nothing else.
pub fn stored_space(store: Arc<CellStore>) -> EndpointSpace {
EndpointSpace::new().bind(template(STORED), stored_cell(store))
}The game’s space is its bound endpoints wrapped in an
Alias that rewrites through that table. The first
three are this part’s and the one before it; the next four are the rules, which
Part III builds, reading the same table; the rest (a reset, the templates and
the views) arrive in Part V. The stored cell sits in a space
of its own after them, because Part IV swaps it per game. No
endpoint implements a row. urn:iki:tutorial:ttt:row:0 resolves because the table
rewrites it to urn:iki:tutorial:ttt:cells:0.0,1.0,2.0, and the line endpoint answers
that. The table parses from text, so it could as easily have been read from a file.
Nothing about it is compiled logic.
This table is also where “three by three” lives, and nowhere else does. The cell takes any coordinates and the line takes any cells, so the size of the board is the one thing the game has to say for itself, and it says it here, as data. Connect Four is a board of seven columns and six rows, won by four in a line, and it has sixty-nine such lines. It would be another table over the same two endpoints, not another crate. That is what keeping Part I’s model loose was for: the atoms do not change when the game does, only the names laid over them.
y runs down the board, so row 0 is the top row. A line reads left to right, or top to
bottom, and diagonal 1 runs from the top-right corner to the bottom-left.
One name for the row, one cache entry
An alias is a second name, not a second resource. The Alias reports the name it rewrote
to, and the kernel files the answer under that name before it computes the cache key. So
row:1 and the line it names are one cache entry, and a read through either name serves
the other:
/// An alias is a second NAME, not a second resource: the row and the line it names are
/// one cache entry. The second read runs nothing at all.
#[test]
fn a_row_and_its_line_are_one_cache_entry() -> Result<()> {
let store = Arc::new(CellStore::default());
let kernel = kernel_over(store.clone());
assert_eq!(source(&kernel, &row_name(1))?, "---");
let reads = store.reads.load(Ordering::SeqCst);
assert!(cached(&kernel, ROW_1), "cached under the line's own name");
assert_eq!(source(&kernel, ROW_1)?, "---");
assert_eq!(
store.reads.load(Ordering::SeqCst),
reads,
"served, not recomputed"
);
Ok(())
}Read the row by its short name, then ask about the line by its own:
--- [computed] cached --- [cached]
The line was never read under its own name, and it is cached. That is what a zero-code alias over a set buys in ikigai: the eight short names add nothing to the cache and nothing to invalidate. Whatever reaches the line reaches the row, because they are one thing.
Two consequences, both of them core’s decisions rather than this game’s. Ask the row what
it is (describe urn:iki:tutorial:ttt:row:0 text/turtle) and it describes ttt-cells,
because a description reports the backing resource. And probe the line’s cache by the
line’s name, as the cell above does. cache asks without resolving, and a rewrite made
inside a space is known only by resolving through it, so cache urn:iki:tutorial:ttt:row:1
answers not cached even while the entry is there. The probe under-reports a hit; it never
invents one. (A table installed on the kernel itself with Kernel::with_aliases is known
to the probe. This one travels with the game’s space instead, so that the page and every
other host get the rows with no wiring of their own.)
Nor does the catalog list the aliases. It lists what is bound — cells:{list} once, and
board — and the table is data of its own: in urn:kernel:topology, the game’s space is an
ik:Alias node carrying eight ik:RewriteRules, each with its logical and canonical name,
above the spaces that bind the templates. Type source urn:kernel:topology
into any cell on this page to see the whole arrangement as a graph.
The board
/// `ttt-board`: the three rows, top to bottom, one per line of text.
///
/// It reads the rows by their alias names, through the kernel, like any other caller —
/// it does not know that a row is a line of cells, or that a line is cells. Cacheable,
/// with no thread named: the move that changes one cell reaches the board through the
/// one row that holds the cell, and through nothing else.
pub fn board() -> AsyncFnEndpoint {
AsyncFnEndpoint::new("ttt-board", |inv: &Invocation<'_>| -> InvokeFuture<'_> {
Box::pin(async move {
let mut rows = Vec::new();
for y in 0..3 {
let row = Iri::parse(row_name(y))
.map_err(|e| Error::Endpoint(format!("a row's name: {e}")))?;
rows.push(String::from_utf8_lossy(&inv.source(&row).await?.bytes).into_owned());
}
Ok(Representation::new(text_plain_utf8(), rows.join("\n").into_bytes()).cacheable())
})
})
.with_description(
Description::new("ttt-board")
.title("Board")
.summary("The board: row 0 (the top row) to row 2, one row per line.")
.verb(Verb::Source)
.verb(Verb::Meta)
.output(TEXT_PLAIN_UTF8),
)
}The board reads the three rows by their short names, through the kernel, like any other caller. It does not know that a row is a line, or that a line is cells, and it does not need to. It answers them top to bottom, one row per line of text:
--- --- --- [computed]
The board was computed, but not all of it was. Row 1 was already cached from the cell above, so the board’s read of it ran nothing.
One move, and what it recomputes
Here is what the arrangement is for. The board depends on three rows, each row on three cells, each cell on its stored mark, and the kernel recorded every one of those dependencies as it resolved them. So a move reaches exactly what was derived from the cell it changed:
/// One move recomputes the cell, the lines through it and the board — and nothing else.
#[test]
fn one_move_recomputes_only_what_passes_through_it() -> Result<()> {
let store = Arc::new(CellStore::default());
let kernel = kernel_over(store.clone());
// Read the board and every line once: all of it computed, all of it cached.
source(&kernel, BOARD)?;
for line in [COLUMN_0, COLUMN_1, COLUMN_2, DIAGONAL_0, DIAGONAL_1] {
source(&kernel, line)?;
}
// Play the top-left corner. It is on one row, one column and one diagonal.
play(&kernel, 0, 0, "X")?;
for through in [ROW_0, COLUMN_0, DIAGONAL_0, BOARD] {
assert!(!cached(&kernel, through), "{through} passes through (0,0)");
}
for past in [ROW_1, ROW_2, COLUMN_1, COLUMN_2, DIAGONAL_1] {
assert!(cached(&kernel, past), "{past} does not");
}
// Read the board again. Of the nine stored cells, exactly one is read again: the
// corner. Row 0's other two cells, and rows 1 and 2 whole, are served from cache.
let reads = store.reads.load(Ordering::SeqCst);
assert_eq!(source(&kernel, BOARD)?, "X--\n---\n---");
assert_eq!(store.reads.load(Ordering::SeqCst), reads + 1);
Ok(())
}Run it here. First read some lines the board does not: the column and the diagonal through the top-left corner, and one of each that miss it:
--- [computed] --- [computed] --- [computed] --- [computed]
Now play the corner. The four probes are row 0, column 0, diagonal 0 and the board, the four things that pass through (0,0). None of them is cached any more:
ok [uncacheable] not cached not cached not cached not cached
And the ones that miss it are row 1, row 2, column 1 and diagonal 1. All four are still cached:
cached cached cached cached
The Sink named one stored cell. Nothing in any endpoint named a row, a column or the
board, and nothing walked the board looking for what to throw away. The dependencies were
recorded when the answers were computed, and the cut followed them.
Now read the board again, traced, to see what it recomputes:
trace urn:iki:tutorial:ttt:board client ikigai repl · capability: root (full authority) transport embedded · in-process urn:iki:tutorial:ttt:board ttt-board · computed · ThreadId(1) · — → 11b X--… ├─ urn:iki:tutorial:ttt:cells:0.0,1.0,2.0 ttt-cells · computed · ThreadId(1) · — · alias=urn:iki:tutorial:ttt:row:0 -> urn:iki:tutorial:ttt:cells:0.0,1.0,2.0 │ ├─ urn:iki:tutorial:ttt:cell:0:0 ttt-cell · computed · ThreadId(1) · — │ │ └─ urn:iki:tutorial:ttt:stored:0:0 ttt-stored · computed · ThreadId(1) · — │ ├─ urn:iki:tutorial:ttt:cell:1:0 ttt-cell · cached · ThreadId(1) · — │ └─ urn:iki:tutorial:ttt:cell:2:0 ttt-cell · cached · ThreadId(1) · — ├─ urn:iki:tutorial:ttt:cells:0.1,1.1,2.1 ttt-cells · cached · ThreadId(1) · — · alias=urn:iki:tutorial:ttt:row:1 -> urn:iki:tutorial:ttt:cells:0.1,1.1,2.1 └─ urn:iki:tutorial:ttt:cells:0.2,1.2,2.2 ttt-cells · cached · ThreadId(1) · — · alias=urn:iki:tutorial:ttt:row:2 -> urn:iki:tutorial:ttt:cells:0.2,1.2,2.2
Read it from the top. The board was computed. Row 0 was computed, and inside it only the
corner went back to the store: its two neighbors were served from cache. Rows 1 and 2 were
served whole, and their six cells were never asked, so they are not in the tree at all.
Each row carries a note, alias=… -> …, which is the name the board asked for beside the
name the kernel filed it under. Of nine stored cells, one was read.
That is the normalized-recompute property, and it comes from the shape of the design rather than from any cleverness in the code. Each resource depends only on the resources it is made of, so a change travels up exactly the paths that lead to it. (The corner shows its stored cell as a child because it has been played. An unplayed cell that recomputed would show as one line: its failed read of the store is recorded as a dependency, but a trace in this release does not draw it.)
One more move, in the center, and the board again: computed once, then served.
ok [uncacheable] X-- -O- --- [computed] X-- -O- --- [cached]
The center is on four lines (row 1, column 1 and both diagonals), a corner on three, and an edge on two. That count is about to matter.
Next
Part III asks questions of the board. Which lines a cell is on becomes a resource of its own: a representation that is a list of the names of other resources. Whose turn it is and who has won are questions about those lines, and the rules of tic-tac-toe arrive there, at the edge of the application, with the model underneath still loose.