Four small SCP / tree-calculus lessons

Each lesson has its own equality/, patterns/, size/ or source/ directory, keeping its runner and SCP dependencies together. These are compiled SCP workers, not the reference IR interpreter. Start with each short .scp source; its .tri runner only reads and compiles source, supplies workers where needed, invokes it, and displays the result. From the repository root, after nix build .#:

result/bin/tricu arboricx import --store /tmp/scp-lessons \
  --file test/fixtures/support-library.arboricx --indexed
# Substitute equality, patterns or source for LESSON below.
result/bin/tricu arboricx run --store /tmp/scp-lessons --module support-library \
  --name demos_consumers_lessons_LESSON_LESSON.main --io \
  --allow-read demos/consumers/lessons --allow-read lib/consumer --format tree

size also has a stored entry with the same naming convention. Its logical self-size traversal can exceed short budgets; run it explicitly with a deadline, not as a required smoke test. The other three lesson runners have stored-execution coverage. This is native artifact loading, not Haskell source compilation.

The final t printed by --format tree is the IO program's return value, not part of a worker's output. These runners compile source at launch; they are not deployed-CAS startup measurements.

1. equality/structural-equality.scp — behavior is not representation

equal left right compares complete trees. The runner supplies two tricu identity functions: one returns its input; the other destructures and reconstructs every Leaf, Stem, and Fork. Their results agree on Leaf and Fork, but the functions' own trees differ:

same representation: same
two identities: different
result on Leaf: same
result on Fork: same

The shape-based definition is visibly identity for every reduced tree; merely checking two examples would not establish extensional equality in general. The older demos/equality.tri is another intensional comparison, but its particular two not definitions actually normalize to the same tree in the current compiler. Intensional equality is not a method for deciding arbitrary behavioral equivalence.

2. patterns/shape.scp — one tree, no declared datatype

Rule order distinguishes leaf, stem leaf, and a general Stem. A computed match child of (...) reuses the same structural patterns. Forks can be list cells, pairs, or executable code; the matcher sees shape, not a type label. Try t, t t, t (t t t), and t t t in patterns.tri. Unlike tricu-wide matchBool, SCP's choose matches only the two canonical Boolean trees; it is not used here to misclassify arbitrary non-Leaf trees.

3. size/tree-size.scp — size of code is still tree size

tree-size.scp structurally recurs over any tree. It calls two SCP workers, succ.scp and add.scp, on tricu's compact LSB natural-number trees; it does not use unary intermediate counts. The adder accepts two numbers as a pair, so there is no separate state adapter. call uses each worker's stored initial state, while recur preserves the pair of arithmetic descriptors. The runner prints 1, 2, and 3 for the smallest three tree shapes, then applies the compiled SCP size worker to its own worker descriptor. That last number depends on the compiler and descriptor representation (69382 on one checked build): it is not an intrinsic constant or the same term as the lambda implementation in demos/size.tri. showNumber merely renders the compact number already computed by SCP. This larger worker descriptor also exposes the cost of compiling nested SCP workers.

4. source/to-source.scp — inspect a value, not remembered source text

The renderer walks the tree and emits t, (t child), or (t left right); it works on executable functions too. source.tri renders a Leaf, Stem, Fork, the tricu identity function, and the tree behind a quoted string. The function's output reflects its eliminated tree, not the original x : x spelling; the quoted string is a list tree, not the characters "a" in source notation. This is the same intensional idea as demos/toSource.tri, written as an SCP program.

The renderer joins fragments through several calls to join.scp, which delegates to lib/consumer/append.scp with an explicit suffix. Each call uses the target's initial state.

Continue exploring

These lessons use input @ state, scoped captures, recursion, and calls to expose tree structure and worker relationships. Larger compositions and effects live one directory above.