git.iko.soy/urbit.org
on ff9676a help sign in
urbit.org/docs/nock/example.md
365 lines 8.1 kB history raw
1---
2navhome: /docs/
3sort: 3
4next: true
5title: Example
6---
8# Nock by hand
10Some people write assembly language by hand. Some of them have a
11good reason to do so. But there's no good reason to write Nock by
12hand, ever.
14Except for the purposes of learning Nock. It's not necessary to
15know Nock to program in Hoon. But it's quite desirable. The
16feeling of understanding the system at two levels is pleasant.
18## Decrement in Nock
20A good practice exercise for Nock is a decrement formula. Ie, a
21formula `f` which implements the partial function that produces
22`(s - 1)` if `s` is a nonzero atom, and otherwise does not
23terminate.
25As we know, the equivalent formula for increment is
27```
28[4 0 1]
29```
31Thus:
33```
34~>zod:dojo .*(42 [4 0 1])
3543
36```
38Of course, increment is built into Nock. So, ha, that's easy.
40The best way to learn Nock is to *stop reading right now*, and
41go write your own decrement formula. There's no substitute for
42doing it yourself. But the second best way is faster...
44## Decrement in Hoon
46How do we decrement? A good way to start is to gaze fondly on
47how we'd do it if we actually had a real language, ie, Hoon.
48Here is a minimal decrement in Hoon:
50```
51=> a=. :: line 1
52=+ b=0 :: line 2
53|- :: line 3
54?: =(a +(b)) :: line 4
55 b :: line 5
56$(b +(b)) :: line 6
57```
59Or for fun, on one line:
61```
62=>(a=. =+(b=0 |-(?:(=(a +(b)) b $(b +(b))))))
63```
65Does Hoon actually work?
67```
68~zod:dojo> =>(42 =>(a=. =+(b=0 |-(?:(=(a +(b)) b $(b +(b)))))))
6941
70```
72Let's translate this into English. How do we decrement the
73subject? First (line 1), we rename the subject `a`. Second
74(line 2), we add a variable, `b`, an atom with value `0`.
75Third (line 3), we loop. Fourth, we test if `a` equals `b` plus
761 (line 4), produce `b` if it does (line 5), repeat the loop with
77`b` set to `b` plus 1 (line 6) if it doesn't. Obviously, while
78the syntax is unusual, the algorithm is anything but deep. We
79are calculating `b` minus one by counting up from `0`.
81(Obviously, this is an O(n) algorithm. Is there a better way?
82There is not. Do we actually do this in practice? Yes and no.)
84Unfortunately we are missing a third of our Rosetta stone. We
85have decrement in Hoon and we have it in English. How do we
86express this in Nock? What will the Hoon compiler generate from
87the code above? Let's work through it line by line.
89Nock has no types, variable names, etc. So line 1 is a no-op.
91How do we add a variable (line 2)? We compute a new subject,
92which is a cell of the present subject and the variable. With
93this new subject, we execute another formula.
95Since `0` is a constant, a formula that produces it is
97```
98[1 0]
99```
101To combine `0` with the subject, we compute
103```
104[[1 0] [0 1]]
105```
107which, if our subject is 42, gives us
109```
110[0 42]
111```
113which we can use as the subject for an inner formula, `g`.
114Composing our new variable with `g`, we have `f` as
116```
117[2 [[1 0] [0 1]] [1 g]]
118```
120which seems a little funky for something so simple. But we
121can simplify it with the composition macro, `7`:
123```
124[7 [[1 0] [0 1]] g]
125```
127and still further with the augmentation macro, `8`:
129```
130[8 [1 0] g]
131```
133If you refer back to the Nock definition, you'll see that all
134these formulas are semantically equivalent.
136Let's continue with our decrement. So what's `g`? We seem to
137loop. Does Nock have a loop instruction? It most certainly does
138not. So what do we do?
140We build a noun called a *core* - a construct which is behind any
141kind of interesting control flow in Hoon. Of course, the Nock
142programmer is not constrained to use the same techniques as the
143Hoon compiler, but it is probably a good idea.
145In Hoon, all the flow structures from your old life as an Earth
146programmer become cores. Functions and/or closures are cores,
147objects are cores modules are cores, even loops are cores.
149The core is just a cell whose tail is data (possibly containing
150other cores) and whose head is code (containing one or more
151formulas). The tail is the *payload* and the head is the
152*battery*. Hence your core is
154```
155[bat pay]
156```
158To activate a core, pick a formula out of the battery, and use
159the entire core (*not* just the payload) as the subject.
161(A core formula is called an *arm*. An arm is almost like an
162object-oriented method, but not quite - a method would be an arm
163that produces a function on an argument. The arm is just a
164function of the core, ie, a computed attribute.)
166Of course, because we feed it the entire core, our arm can
167invoke itself (or any other formula in the battery). Hence, it
168can loop. And this is what a loop is - the simplest of cores.
170We need to do two things with this core: create it, and activate
171it. To be precise, we need two formulas: a formula which
172produces the core, and one which activates its subject. We can
173compose these functions with the handy `7` instruction:
175```
176[8 [1 0] [7 p a]]
177```
179`p` produces our core, `a` activates it. Let's take these in
180reverse order. How do we activate a core?
182Since we have only one formula, it's the battery itself.
183Thus we want to execute Nock with the whole core (already the
184subject, and the entire battery (slot `2`). Hence, `a` is
186```
187[2 [0 1] [0 2]]
188```
190We could also use the handy `9` macro - which almost seems
191designed for firing arms on cores:
193```
194[9 2 [0 1]]
195```
197Which leaves us seeking
199```
200[8 [1 0] [7 p [9 2 0 1]]]
201```
203And all we have to do is build the core, `p`. How do we build a
204core? We add code to the subject, just as we added a variable
205above. The initial value of our counter was a constant, `0`.
206The initial (and permanent) value of our battery is a constant,
207the loop formula `l`. So `p` is
209```
210[8 [1 l] [0 1]]
211```
213Which would leave us seeking
215```
216[8 [1 0] [7 [8 [1 l] [0 1]] [9 2 0 1]]]
217```
219except that we have duplicated the `8` pattern again, since we
220know
222```
223[7 [8 [1 l] [0 1]] [9 2 0 1]]
224```
226is equivalent to
228```
229[8 [1 l] [9 2 0 1]]
230```
232so the full value of `f` is
234```
235[8 [1 0] [8 [1 l] [9 2 0 1]]]
236```
238Thus our only formula to compose is the loop body, `l`.
239Its subject is the loop core:
241```
242[bat pay]
243```
245where `bat` is just the loop formula, and `pay` is the pair `[b
246a]`, `b` being the counter, and `a` the input subject. Thus we
247could also write this subject as
249```
250[l b a]
251```
253and we see readily that `a` is at slot `7`, `b` `6`, `l` `2`.
254With this subject, we need to express the Hoon loop body
256```
257?: =(a +(b)) :: line 4
258 b :: line 5
259$(b +(b)) :: line 6
260```
262This is obviously an if statement, and it calls for `6`. Ie:
264```
265[6 t y n]
266```
268Giving our decrement program as:
270```
271[8 [1 0] [8 [1 6 t y n] [9 2 0 1]]]
272```
274For `t`, how do we compute a flag that is yes (`0`) if `a` equals
275`b` plus one? Equals, we recall, is `5`. So `t` can only be
277```
278[5 [0 7] [4 0 6]]
279```
281If so, our product `y` is just the counter `b`:
283```
284[0 6]
285```
287And if not? We have to re-execute the loop with the counter
288incremented. If we were executing it with the same counter,
289obviously an infinite loop, we could use the same core:
291```
292[9 2 0 1]
293```
295But instead we need to construct a new core with the counter
296incremented:
298```
299[l +(b) a]
300```
302ie,
304```
305[[0 2] [4 0 6] [0 7]]
306```
308and `n` is:
310```
311[9 2 [[0 2] [4 0 6] [0 7]]]
312```
314Hence our complete decrement. Let's reformat vertically so we
315can actually read it:
317```
318[8
319 [1 0]
320 [ 8
321 [ 1
322 [ 6
323 t
324 y
325 n
326 ]
327 ]
328 [9 2 0 1]
329 ]
331```
333which becomes
335```
336[8
337 [1 0]
338 [ 8
339 [ 1
340 [ 6
341 [5 [0 7] [4 0 6]]
342 [0 6]
343 [9 2 [[0 2] [4 0 6] [0 7]]]
344 ]
345 ]
346 [9 2 0 1]
347 ]
349```
351or, on one line without superfluous brackets:
353```
354[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]
355```
357which works for the important special case, 42:
359```
360~zod:dojo> .*(42 [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])
36141
362```
364If you understood this, you understand Nock. At least in principle!
365Now, go write an adder. Or don't.