std/tree: A Node Is a Registry Kind

A benchmark question drove a language feature this week, and the shape it settled into is worth writing down — partly because the reasoning is the kind this blog exists to keep honest, partly because a design you can’t explain in a post is a design you haven’t finished.

The question started as LangArena’s binarytrees_obj: build a depth-20 binary tree 36 times, fold a checksum over every node, free it all. Koru’s existing port did this on [tree]-flavored std/store rows — a cell array pretending to be an object graph — and it worked, but at 2M rows per iteration the checksum was a row-scan of a structure that wanted to be a tree.

What wanted to exist: a heap node — a record with owned references to its children — spelled in .k, with no malloc, no pointer syntax, and no .kz-only escape hatch.

The rejected vocabulary

The temptation list was long, and each entry taught the design what it wasn’t:

std/host:struct — materialize a proto as a host record. Mechanically fine, conceptually backwards: it exposes the representation (struct layout, malloc) instead of the concept (an owned tree). The declaration would have been about how the host stores a thing, not what the thing is.

std/mem — allocate, read, write, free. Correct and useless as a vocabulary: it’s mechanism lane, one level below the idea. A malloc you can spell is a malloc you can misuse — the surface would have leaked the very thing we wanted to hide.

std/store with [heap] — a store row flavored to point at heap cells instead of array slots. This was the closest wrong answer: stores already do capacity, borrow, discharge. But it makes one lane span two axes — a store that is also a heap allocator is a store that can’t say no to either — so the ruling was that std/store should refuse [heap] rather than grow it.

The settled surface

What survived is a node as a registered kind, declared in the same registry std/proto already owns:

std/tree:node(Node) { item: i64, left: ?Node, right: ?Node }

pub tor build { item: i64, depth: i64 } -> *Node<owned!>
build = if(depth > 0)
    | then |> build(item: item - 1, depth: depth - 1): l
           |> build(item: item + 1, depth: depth - 1): r
           |> std/tree:mint(Node) { item, left: l, right: r }: h -> h
    | else |> std/tree:mint(Node) { item, left: null, right: null }: h -> h

build(item: 0, depth: 20): t
|> sum(t): c
|> std/tree:dispose(t): _

Three verbs carry the whole lane. node declares the kind and leaves a marker in the registry. mint takes a field block and returns an owned node. dispose consumes it and recurses. There is no pointer syntax in user code — the edges are fields whose types happen to be node-registered.

What decides what a field is

The part I’m happiest about is the classifier. A field’s type asks the shared registry one question — what kind is this name — and the answer is the rule:

• Scalar or proto terminal → payload (embedded; the acyclic compound rule still applies)
• Node-registered → edge (a pointer; recursion is legal because a pointer isn’t containment)
• Anything else → a refusal that teaches

That single split is why std/proto(Node) and std/tree:node(Node) in the same home collide — a name is one kind — and why a proto field that names a node refuses with a message about edges, not “unknown terminal”. The registry gained a kind column; the collisions and refusals fell out of it for free.

Where ownership lives

Edges are <!owned>-consuming params on the synthesized mint-Node — the single-owner law is not a lint, it’s the obligation checker. Reparent a bound child and you get use-after-discharge. Dispose twice, same wall. A ?Node edge accepts a fresh mint or null; a required edge refuses null because optionality is what ? spells.

And the interaction that made the whole thing click: std/tree:dispose inside for ! each has to be recognized by the invariant-prefix hoist before the transform expands — otherwise build |> sum |> dispose leaves the consume inside the repeating scope and the obligation checker says no (KORU032). Once the hoist sees the lane verb as a discharge, the whole prefix lifts onto | done: the tree builds once, folds once, frees once; the loop only accumulates.

The number

binarytrees_obj, scored scale — depth 20, 36 iterations, checksum 75497436:

Same checksum, 9.6× at the scoring tier — not because the allocator got faster, but because the program finally is the shape it was simulating, and the compiler can hoist the invariant work out of the timed loop entirely.

What’s deliberately not in it

walk/fold aren’t lanes yet — a recursive tor is the honest spelling for a fold over an owned tree, and the verbs can land when there’s a caller that needs them. Compound-proto payload embeds refuse loudly rather than half-materialize. JS and C# materialization don’t exist. Shared edges — a DAG, a real graph — would need refcounting and belong to a std/graph kind, not this one.

The post stays a draft until the design reads right. If the argument holds, the checksum is the receipt — 75497436, in pure .k, on a tree that is actually a tree.