Examples#
Building Nock expressions from scratch can be a challenge, but it is invaluable to understanding how Nock works in practice. It also helps you understand why compilers make the decisions they do.
Incrementing a Number#
Nock provides only one built-in arithmetic operator: opcode 4, which adds one to a number.
:subject 41
Subject set to: 41
[4 0 1]
42
That means to grab the value in the subject at address 1 (the entire subject) and increment it directly.
Decrementing a Number#
A decrement operator is more involved. (The algorithm itself is a classic problem in Nock’s history.)
The high-level idea is that if you only have the ability to increment and check for equality, then you can build a decrement operator by counting up from zero and checking whether adding one to the current number equals the source number. If it does, then the current number is one less than the source number, thus its decrement.
We need a few pieces of Nock code to put this together. Let’s call the source number a and the other working variable number b.
First off, we can pin a constant to start counting from using opcode 1:
[1 0]
We can compare the increment of a number b to a using opcode 5:
[5 a [4 b]]
(We ignore for a moment how we get a and b; they will be parts of the subject retrieved with opcode 0 or supplied as constants with opcode 1.)
We need two different paths based on whether the comparison is true or false, mediated by opcode 6.
[6 [5 a [4 b]] <true-path> <false-path>]
The true-path is easy: we just return b, since we’ve found the decrement. The false-path is more involved: we need to increment b and try again. We can do this by recursively calling our decrement operator with the same a and the incremented b. How do we invoke our own operator recursively? We use an opcode 9 with an opcode 10 to alter the subject for the recursive call.
Finally, we need the ability to pin new variables such as the starting value b. We’ll do this using opcode 8, after which point we can refer to the new variable at address 2.
Let’s build this piece by piece.
:a [1 43]
Variable 'a' set to: [1 43]
:b [1 0]
Variable 'b' set to: [1 0]
:test [5 a [4 b]]
Variable 'test' set to: [5 [1 43] 4 1 0]
Check the test case (should return false):
test
1
:show test
test = [5 [1 43] 4 1 0]
The source constant a is hardcoded as 43, but that’s okay for now. We won’t be able to work with b as a constant, however, so we’ll come back to this expression later.
The next bit we need is how to edit an atom, where x is the address of b (rather than its value):
[10 [x 4 b] 0 1]
This edits the noun and returns that entire edited noun. That yields something like this, adjusted against the reference subject:
[10 [1 4 1 0] 0 1]
1
Finally, we need to recurse on the edited value:
[9 2 10 [x 4 b] 0 1]
If opcode 9 is *[a 9 b c], then here b is the memory slot of the new subject formed with c, which is the edited noun from above.
(We can’t demonstrate the opcode 9 in isolation.)
Putting it all together, we get the full decrement operator:
[8 [1 0] 8 [1 6 [5 [1 43] 4 0 6] [0 6] 9 2 10 [6 4 0 6] 0 1] 9 2 0 1]
The [9 2 0 1] at the tail is the actual evaluation: from the entire unedited subject, execute the arm at address 2, which is the operator we just built.
Here is the same formula with each piece labelled. S is the subject it is run against.
[8 [1 0][0 S] 8 [1 B][B 0 S], a core 9 2 0 1]B = [6 [5 [1 43] 4 0 6] [0 6] 9 2 10 [6 4 0 6] 0 1]On the first pass the core is [B 0 S]: the test asks whether 43 = 0 + 1, which is false, so the edit makes [B 1 S] and arm 2 runs again. The counter climbs one step per pass until the core is [B 42 S], where 43 = 42 + 1 holds and [0 6] returns 42. The subject S rides along in the tail of the core the whole time, unused.
[8 [1 0] 8 [1 6 [5 [1 43] 4 0 6] [0 6] 9 2 10 [6 4 0 6] 0 1] 9 2 0 1]
42
That works! It’s still too brittle: the constant a is hardcoded, so we want to make it flexible by supplying the sample positionally rather than as a constant. We can do that by changing how we pin a and b at the start and referring to the sample at address 6 via [0 6].
[8 [1 43] 8 [1 0] 8 [1 6 [5 [0 14] 4 0 6] [0 6] 9 2 10 [6 4 0 6] 0 1] 9 2 0 1]
42
The core now has one more pinned value, so every address below the counter moves down a level:
[8 [1 43][43 S] 8 [1 0][0 43 S] 8 [1 B][B 0 43 S] 9 2 0 1]B = [6 [5 [0 14] 4 0 6] [0 6] 9 2 10 [6 4 0 6] 0 1]In the core [B b a S], address 2 is B, 6 is b, 14 is a and 15 is the original subject S. The test reads a with [0 14] instead of carrying it as the constant [1 43].
Now a can come from anywhere. Replace the first [1 43] with [0 1], and a is the subject itself: the formula decrements whatever it is run against.
:subject 43
Subject set to: 43
[8 [0 1] 8 [1 0] 8 [1 6 [5 [0 14] 4 0 6] [0 6] 9 2 10 [6 4 0 6] 0 1] 9 2 0 1]
42
This is very nearly what Hoon compiles its own ++dec to. Try it on other subjects. (Be careful with 0: no counter b ever satisfies 0 = b + 1, so the loop counts up forever. Hoon’s ++dec checks for 0 first and crashes instead.)
Length of a List#
A Nock list is a rightwards-branching tuple, where at each point there is a head and a tail until a terminating atom (0, sometimes written as ~).
The following are equivalent representations of a list of five elements:
[1 [2 [3 [4 [5 0]]]]]
[1 2 3 4 5 0]
Thus to get the length, we need the following components:
A way to check if the list is populated (i.e., is a cell).
A way to get the tail of the list.
A way to increment a counter.
A way to recurse until the list is empty (i.e., is an atom).
With those pieces, it’s not hard to see an algorithm:
Start with a counter at 0.
If the list is a cell, increment the counter and recurse on the tail.
If the list is an atom and that atom is zero, return the counter.
Let’s build this piece by piece.
We start by pinning a counter at 0 using opcode 1:
[1 0]
(We’ll compose it in using an opcode 8.)
We branch conditionally using opcode 6:
[list 6 <cell-check> <true-path> <false-path>]
To check if the list is a cell, we can use opcode 3:
[list 3 0 1]
To get the tail of the list, we can use opcode 2:
[list 0 3]
To increment the counter, we can use opcode 4:
[4 0 <address-of-counter>]
To recurse, we can use opcode 9 with an opcode 10 to alter the subject for the recursive call:
[9 <address-of-operator> 10 [<address-of-list> 0 3] 0 <address-of-counter>]
Let’s put it all together.
:subject [1 2 3 4 5 0]
Subject set to: [1 2 3 4 5 0]
[8 [1 0] 8 [1 6 [3 0 7] [9 2 10 [7 0 15] 10 [6 4 0 6] 0 1] [0 6]] 9 2 0 1]
5
Here is the formula laid out by its parts:
[8 [1 0][0 list] 8 [1 L][L 0 list] 9 2 0 1]L = [6 [3 0 7] [9 2 10 [7 0 15] 10 [6 4 0 6] 0 1] [0 6]]In the core [L c list], address 6 is the counter, 7 is the list, 14 is its head and 15 is its tail. Each pass drops one element and adds one to the counter, so [1 2 3 4 5 0] takes five passes and the sixth finds the atom 0.
This full formula deserves a bit more commentary because of the nested opcodes 10 and the trailing 9.
Both the list in question and the counter need to be changed; so the tail of the list is taken as the new list before recursing
[10 [7 0 15] ...], and the counter is incremented before recursing[10 [6 4 0 6] ...].The entire static formula pinned at
2is retrieved by the trailing9and evaluated against the incoming subject at[0 1].
Interestingly, the reference version of +lent uses a slightly different approach, using opcode 5 to check for equality with zero rather than opcode 3 to check for being a cell. This works because the only atom that can terminate a list is zero. Thus we can check if the rest of the list is equal to zero directly.
[5 [1 0] 0 7]
Since our formula above doesn’t check for zero explicitly, it will return the length of any right-branching structure, even if it doesn’t terminate in zero. We leave it as an exercise to the reader to modify the formula to check for zero explicitly.
Cores#
The idea of a core is that a collection of constant executable Nock formulas can be bundled with references to each other in a consistent layout, allowing for more complex behavior. That is, if you know where a function is located in a core, you can call it from another function in the same core by referring to its address. Thus you can compose arbitrarily complex behavior from a set of simpler formulas.
(How to order the functions in a core depends on decisions made by the higher-level language compiler; Hoon, for instance, builds a complex data structure called a $set which orders arms by the hash of their names.)
Here is an example of a formula that builds a core. It pins a battery C of three formulas as a constant and pairs it with the subject:
[[1 [8 [1 0] [1 4 0 6] 0 1] [1 42] 1 43] 0 1]
[[1 C] 0 1][C S]C = [F [1 42] 1 43]F = [8 [1 0] [1 4 0 6] 0 1][[4 0 6] 0 x]: a gate whose arm [4 0 6] increments its sampleNote that with two opcode 1 formula pins, we will need to evaluate the core twice to actually run the target arm. This is why we distinguish an arm (which requires two evaluations with opcode 9) from a leg (which requires only an opcode 0 lookup).
An evaluation of a leg requires pinning the core with opcode 8 then looking up the leg with opcode 0 adjusted for the relative address:
:subject 43
Subject set to: 43
[8 [1 [8 [1 0] [1 4 0 6] 0 1] [1 42] 1 43] 0 10]
[1 42]
[8 [1 C] 0 10][1 42], returned as data, not runTo get the value instead, run the arm with opcode 9, and hand it to the gate that F builds. This takes three opcodes 9:
[8 [1 [8 [1 0] [1 4 0 6] 0 1] [1 42] 1 43] 8 [9 4 0 1] 9 2 10 [6 7 [0 3] 9 10 0 1] 0 2]
43
[8 [1 C][C S] 8 [9 4 0 1][C S] and pin the gate G it builds: the subject is [G C S] 9 2 10 [6 7 [0 3] 9 10 0 1][C S] (address 3 here), run: 42 0 2]9 2 runs its arm [4 0 6]: 42 + 1 = 43You can grab the leg without the third opcode 9, but it doesn’t evaluate it so you have to grab the tail of the opcode 1 or evaluate it separately as with an opcode 2.
Here address 21 of [C S] is the tail of [1 42], which is 42 itself:
[8 [1 C] 8 [9 4 0 1] 9 2 10 [6 7 [0 3] 0 21] 0 2][1 42] instead of running it[8 [1 [8 [1 0] [1 4 0 6] 0 1] [1 42] 1 43] 8 [9 4 0 1] 9 2 10 [6 7 [0 3] 0 21] 0 2]
43
What’s Missing?#
Nock is mathematically complete, but it doesn’t seem to have many affordances that programmers expect from a language. Nock leaves some pragmatic elements of programming and the computer environment to its evaluator, or runtime environment.
Boolean logic (
AND,XOR,NOT, etc.) must be implemented out of Nock primitives rather than being axiomatically supplied as operators.Side effects (like printing) will be handled by raising special noun patterns to the Nock evaluator.
Memory is entirely handled by the Nock evaluator.
Type systems are not part of Nock itself, but can be layered on top of it.
Evaluation rules are defined, but their implementation is omitted. You can use a tree-walking interpreter, a bytecode interpreter, or something even more clever to run Nock in practice. (In fact, you can treat Nock as a spec and not run it at all, as long as you get the same answer!)
How would you implement the Boolean operators in Nock? (Properly “loobeans”, since
0isTRUEand1isFALSEin Nock.) See Opcode 6 for a starting point.
Quines#
Nock quines are Nock expressions that evaluate to themselves. They result trivially from opcode 0, which simply looks up a part of the subject. If the subject is the expression itself, then looking up address 1 returns the entire expression.
:subject [0 1]
Subject set to: [0 1]
This formula will reproduce itself from that subject:
[[0 1] [0 1]]
[[0 1] 0 1]
Other quines are possible as well, and left as an exercise for the reader.
Finally, more examples are available at urbit/benchmark which features a variety of compiled Nock expressions and corresponding Hoon source that have been used for benchmarking and testing.