(A tribute to the work of Aphyr in the classic "Typing the Technical Interview" series.)
Your mother's mother's mother kept the cords. Not the ledgers, which came later; ledgers for men who believed nothing to be true until it was written in a line, left to right, in ink that bit into the wood pulp and dissolved, or else faded in the light of centuries. Your line kept cords: a spine with pendants, those pendants with distributaries and consequences, each knotted in places where the count lived. A cord that branches is a tree. A tree is a memory. A memory, tied tightly enough, is a law.
The undyed cotton lies bundled in your bag. It triggers no metal detectors. It has never needed a firmware update.
The office is a converted cannery warehouse on a pier that reeks of diesel and brine. A sigil has been painted on the door with a word of supposed power beneath: young, inchoate, aching like a sapling to shoulder off its burden of dirt and become a Name. The startup inside sells zero-knowledge proofs of things no one has yet asked to be proven. Their runway, you estimate from the bouquet of the cold brew, is fourteen months.
The interviewer is named Kellan. He wears a black hoodie stamped // TODO in neon green paint, which you respect. He has a late-model laptop, a Muji notebook, and the faintly startled look of a man who has recently read the Hoon style guide.
"So," he says. "We like to start with something classic. Can you invert a binary tree?"
"Is there any other kind?" you ask, and set the skein on the table.
"In Nock," you recount, "everything is a noun. A noun is an atom, which is a natural number, or a cell, which is a pair of nouns. It all grounds all things honestly. No strings, no floats, no nulls. No mirages."
You measure a length of cord and cut it with your scissors Atropos. You tie a knot at its center, then let the two ends fall. "A cell." You tie a knot in the left end, splitting it again. "A cell of a cell and an atom. [[1 2] 3]. Every datum ever stored in this system has some configuration of this."
"Sure," says Kellan. "But the tree's the input. What's the program?"
"Also a noun."
He opens his mouth, closes it, and nods for you to continue.
"We need an address scheme." You hold up the knotted cord by its root. "The whole weave is axis 1. Its head is 2, its tail is 3. The head of any axis n is 2n; the tail is 2n+1. You can walk any tree with nothing but arithmetic on a single integer. Your grandmother's filesystem wishes it were this forthright."
"My grandmother didn't have a filesystem."
"Then she had nothing to be ashamed of."
You uncap a marker. The volatile organic compounds echo juniper and you pause in a revery. Shaking loose of the moment, you proceed. The trick, you explain, is that a recursive function in Nock has to carry itself around. There are no names. There is only the subject, a single noun that holds everything the formula can see. So you will arrange the subject as a cell: the formula itself at axis 2, the tree at axis 3. The tree's head is then at axis 6, and its tail at 7.
You write at the whiteboard:
[6 [3 0 3]
[[2 [[0 2] 0 7] 0 2]
2 [[0 2] 0 6] 0 2]
0 3]
Kellan leans in. "Walk me through it."
"Opcode 6 states the conditional. Its test is [3 0 3]: fetch axis 3, the tree, and ask opcode 3 whether it's a cell."
"And it returns true."
"It returns zero."
"Zero is false."
"Zero is yes." You underline it twice. "Nock uses loobeans. Zero is yes, one is no. The C programmers get to be confused. Just this once, as a treat. It builds character. Of course, int main() always returned 0 but they rarely noticed."
He writes 0 = yes on a sticky note and presses it to his laptop with the grim precision of a man labeling a fuse box.
"If the tree is a cell, we take the middle branch. That's two expressions side by side, and when Nock sees a formula whose head is itself a cell, it evaluates both halves against the same subject and pairs the results. Autocons. The left half builds a new subject, [formula tail], from axes 2 and 7, then runs axis 2 against it. That's the recursive call on the tail. The right half does the same with axis 6, the head."
"So the tail comes out first."
"The tail comes out first. That's the inversion. It isn't an algorithm so much as a posture."
"And if it's an atom?"
"Then [0 3]. Return the tree unchanged. You cannot invert a leaf. You can only hold it."
Kellan does not wait for permission. He copies the formula into a prompt and feeds it the tree.
> .*([[1 2] 3] [6 [3 0 3] [[2 [[0 2] 0 7] 0 2] 2 [[0 2] 0 6] 0 2] 0 3])
3
"It dropped half my tree." He tries another.
> .*([3 2 1] [6 [3 0 3] [[2 [[0 2] 0 7] 0 2] 2 [[0 2] 0 6] 0 2] 0 3])
dojo: hoon expression failed
"Good," you say.
"Good?"
"That isn't the answer. That's the loop body. Look at what it assumes." You tap axis 2 in the recursive branch. "To call itself, it has to find its own code somewhere. Nock has no names and no heap. The subject is the only memory there is. So the body reaches for axis 2 and expects to find itself. Your tree doesn't contain it."
"So on [[1 2] 3]—"
"Axis 3 is 3. A leaf. It hands the leaf back and considers the job done. On [3 2 1], axis 3 is a cell, so it recurses, reaches for axis 2, finds the number 3, and tries to execute a number. Nock crashes. The crash is the honest one. The 3 would have shipped."
He writes the 3 would have shipped on a sticky note, then looks at it for a long moment and puts it in his pocket.
"The body can't bring itself," you go on, "because a finite noun can't contain an exact copy of itself. But a wrapper can carry the body as a literal and set the table before the first call." You write the answer, the whole answer, beneath it:
[8 [1 F] 2 [0 1] 0 2]
"Opcode 8 pushes a value onto the front of the subject. [1 F] is a literal, our formula. So the subject becomes [F tree], which is exactly the shape the formula expects. Then opcode 2 evaluates: the new subject is axis 1, all of it; the formula to run is axis 2, which is F. The function picks itself up by its own collar. Of course, we could also address it with opcode 0 if we preferred to build a core."
He pastes it into a REPL. He types [[1 2] 3] as the subject. He hits enter.
[3 2 1]
"Huh," he says. "[3 [2 1]]." He tries a deeper one, [[[1 2] [3 4]] [5 6]], and gets [[6 5] [4 3] 2 1]. He tries 42 and gets 42, and looks at the atom for a while as though it had personally declined participation.
"You can check it by hand," you say. "Twelve rules. They fit on a T-shirt. I've seen the T-shirt."
Kellan exhales. "Nobody on the team writes raw Nock, though. Can you do it in something higher level?"
"Of course." You inscribe the runes thus:
|= n=*
?@ n n
[$(n +.n) $(n -.n)]
He stares. "That's it?"
"|= makes a gate: a function taking any noun n. ?@ branches on whether n is an atom; if it is, return it. Otherwise build a cell. $ is the gate calling itself with n replaced by the tail, +.n, then the head, -.n."
"It's three lines."
"It compiles to roughly what I wrote on the board. Hoon is a very polite way of asking Nock to do what it was going to do anyway, altho it beats around the bush a little bit. Raw Nock does tend to make humans a little nervous."
"The runes, though," he says, with the tone of a man who has been asked to pronounce ?@ at a standup. "People complain about the runes."
"People complained about parentheses. Then about braces. Then about whitespace. The complaint is structural; only the glyph changes. At least these ones are honest about being glyphs."
He scrolls through his interview rubric, finds the next heading, and brightens. "Performance. What's the complexity?"
"Linear in the number of nodes. Every cell is visited once, rebuilt once."
"Great. And if the tree has, say, big atoms in it? Counters? We'd want to decrement them."
You pause. You had hoped to get through the afternoon without telling him about decrement.
"Nock has no subtraction," you say.
"What?"
"It has increment. Opcode 4. Plus one. That's the only arithmetic in the machine." You write the standard decrement, the one every Nock student meets in their first week and never fully forgives:
[8 [1 0]
8 [1 6 [5 [0 7] 4 0 6] [0 6] 9 2 [0 2] [4 0 6] 0 7]
9 2 0 1]
"To compute n minus one, we start a counter at zero, and ask, over and over, whether the counter plus one equals n. When it does, we return the counter."
Kellan does the arithmetic. You watch it happen on his face, the way you watch clouds cross a hillside.
"That's $O(n)$."
"In the value, not the bits. Decrementing a 256-bit hash would outlast the heat death of the sun, then several of its successors."
"So the whole thing is unusable."
"The whole thing is a specification." You tap the board. "The interpreter is allowed to cheat, provided it cheats correctly. When it recognizes a formula it has seen before, a known core, identified by a hint, it skips the Nock and runs native code instead. We call that an aeolipile, after Hero of Alexandria's steam engine."
"Ah. I'd heard something about jets."
"Or jets, if you prefer: more Old French." More androcentric, but you bite it down and write the hint in Hoon:
~/ %flip
|= n=*
?@ n n
[$(n +.n) $(n -.n)]
And the jet, in the runtime's C, beneath it:
u3_noun
u3qe_flip(u3_noun n)
{
if ( c3y == u3ud(n) ) {
return u3k(n);
}
return u3nc(u3qe_flip(u3t(n)),
u3qe_flip(u3h(n)));
}
"u3ud asks whether it's an atom. It returns c3y, which is yes, which is zero. u3k takes a reference. u3nc builds a cell and consumes the references it's handed. Same shape as the Nock. Same shape as the cord." You hold up the cord by its root. "When you've tied it once, you tie it the same way in every language. The knot doesn't care what the rope is made of."
Kellan has stopped typing. He is looking at the C with a new and specific unease.
"What happens," he says slowly, "if the jet is wrong?"
This is the first good question anyone has asked you in a technical interview in eleven years. You put the marker down.
"Then the machine disagrees with itself. On a single ship, you get a bug that appears only on nodes with the jet, and vanishes the instant you try to reproduce it in the pure interpreter. On a chain, it's worse. Two validators run the same formula; one uses a jet, one doesn't; they compute different nouns; the network forks on a question of arithmetic. Nobody is malicious. Everybody is wrong in a different direction."
"So how do you trust it?"
"You don't. The Nock is the law. The jet is a rumor that it agrees with the law." You write on the board, in a corner, very small:
for each random noun n:
assert nock(n, FLIP) == u3qe_flip(n)
"Generate nouns. Run both. Compare. Run it in CI, run it for a week, run it on every tree shape you can think of and a few thousand you can't. Test the atoms that cross the direct-atom boundary. Test the deep trees that blow the C stack, because that recursion will, somewhere past a few hundred thousand levels, and the Nock won't care. Fix that before you ship it. A slow correct answer is an inconvenience. A fast wrong answer on a consensus network is an incident with a postmortem and a lawyer. But there's talk of a Lean proof someday."
"The C stack thing," Kellan says. "That's real?"
"Lines seven and eight. Unbounded recursion on attacker-supplied input. I would not merge it." You shrug. "I wrote it for the whiteboard. A whiteboard has a very large stack."
He writes line 7 on the sticky note, directly under 0 = yes.
Kellan's rubric has one heading left. It says Culture Fit. Kellan looks at it, then at you, then at the cord, and seems to reach a decision about which of the three to trust.
"Why Urbit?" he asks. "Honestly. You clearly know how to write real systems."
You consider the question. Outside, a container ship is being unloaded by a crane that runs on software nobody at the port could audit, updated by a vendor that could stop answering the phone tomorrow.
"Every system I've worked on," you say, "had a spec that lived in someone's head, and an implementation that lived on a server, and the two drifted apart at something faster than the rate of tectonic plates, and I was paid to stand on the fault line. This one puts the spec in the machine. Twelve frozen rules. Everything above it is a noun you can inspect, and everything fast is a promise you can check. Your data is a tree you own, addressed by integers, running on a computer that is small enough to hold in your head." You pick up the cord and the skein. "My family kept records like this for a very long time. Then someone arrived who couldn't read them and decided that meant they didn't say anything."
Kellan is quiet. The cold brew wafts.
"We'll be in touch," he says.
You stand, and wind the cord back into its bundle, and set it on the table in front of him. "Keep that. A worked example."
He picks it up after you've gone. It takes him most of an hour to notice that the knots, which were tied left to right when you arrived, are now tied right to left, every pendant swapped with its sibling, all the way down to the leaves.
The leaves are unchanged. You cannot invert a leaf.
You can only hold it.