git.iko.soy/urbit.org
on 4166e68 help sign in
urbit.org/tutorials/nock/example.md
362 lines 8.2 kB history raw
1+++
2title = "Example"
3weight = 3
4template = "doc.html"
5aliases = ["docs/learn/nock/example"]
6+++
7Some people write assembly language by hand. Some of them have a
8good reason to do so. But there's no good reason to write Nock by
9hand, ever.
11Except for the purposes of learning Nock. It's not necessary to
12know Nock to program in Hoon. But it's quite desirable. The
13feeling of understanding the system at two levels is pleasant.
15## Decrement in Nock
17A good practice exercise for Nock is a decrement formula. Ie, a
18formula `f` which implements the partial function that produces
19`(s - 1)` if `s` is a nonzero atom, and otherwise does not
20terminate.
22As we know, the equivalent formula for increment is
24```
25[4 0 1]
26```
28Thus:
30```
31~>zod:dojo .*(42 [4 0 1])
3243
33```
35Of course, increment is built into Nock. So, ha, that's easy.
37The best way to learn Nock is to **stop reading right now**, and
38go write your own decrement formula. There's no substitute for
39doing it yourself. But the second best way is faster...
41## Decrement in Hoon
43How do we decrement? A good way to start is to gaze fondly on
44how we'd do it if we actually had a real language, ie, Hoon.
45Here is a minimal decrement in Hoon:
47```
48=> a=. :: line 1
49=+ b=0 :: line 2
50|- :: line 3
51?: =(a +(b)) :: line 4
52 b :: line 5
53$(b +(b)) :: line 6
54```
56Or for fun, on one line:
58```
59=>(a=. =+(b=0 |-(?:(=(a +(b)) b $(b +(b))))))
60```
62Does Hoon actually work?
64```
65~zod:dojo> =>(42 =>(a=. =+(b=0 |-(?:(=(a +(b)) b $(b +(b)))))))
6641
67```
69Let's translate this into English. How do we decrement the
70subject? First (line 1), we rename the subject `a`. Second
71(line 2), we add a variable, `b`, an atom with value `0`.
72Third (line 3), we loop. Fourth, we test if `a` equals `b` plus
731 (line 4), produce `b` if it does (line 5), repeat the loop with
74`b` set to `b` plus 1 (line 6) if it doesn't. Obviously, while
75the syntax is unusual, the algorithm is anything but deep. We
76are calculating `b` minus one by counting up from `0`.
78(Obviously, this is an O(n) algorithm. Is there a better way?
79There is not. Do we actually do this in practice? Yes and no.)
81Unfortunately we are missing a third of our Rosetta stone. We
82have decrement in Hoon and we have it in English. How do we
83express this in Nock? What will the Hoon compiler generate from
84the code above? Let's work through it line by line.
86Nock has no types, variable names, etc. So line 1 is a no-op.
88How do we add a variable (line 2)? We compute a new subject,
89which is a cell of the present subject and the variable. With
90this new subject, we execute another formula.
92Since `0` is a constant, a formula that produces it is
94```
95[1 0]
96```
98To combine `0` with the subject, we compute
100```
101[[1 0] [0 1]]
102```
104which, if our subject is 42, gives us
106```
107[0 42]
108```
110which we can use as the subject for an inner formula, `g`.
111Composing our new variable with `g`, we have `f` as
113```
114[2 [[1 0] [0 1]] [1 g]]
115```
117which seems a little funky for something so simple. But we
118can simplify it with the composition macro, `7`:
120```
121[7 [[1 0] [0 1]] g]
122```
124and still further with the augmentation macro, `8`:
126```
127[8 [1 0] g]
128```
130If you refer back to the Nock definition, you'll see that all
131these formulas are semantically equivalent.
133Let's continue with our decrement. So what's `g`? We seem to
134loop. Does Nock have a loop instruction? It most certainly does
135not. So what do we do?
137We build a noun called a **core** - a construct which is behind any
138kind of interesting control flow in Hoon. Of course, the Nock
139programmer is not constrained to use the same techniques as the
140Hoon compiler, but it is probably a good idea.
142In Hoon, all the flow structures from your old life as an Earth
143programmer become cores. Functions and/or closures are cores,
144objects are cores, modules are cores, even loops are cores.
146The core is just a cell whose tail is data (possibly containing
147other cores) and whose head is code (containing one or more
148formulas). The tail is the **payload** and the head is the
149**battery**. Hence your core is
151```
152[bat pay]
153```
155To activate a core, pick a formula out of the battery, and use
156the entire core (**not** just the payload) as the subject.
158(A core formula is called an **arm**. An arm is almost like an
159object-oriented method, but not quite - a method would be an arm
160that produces a function on an argument. The arm is just a
161function of the core, ie, a computed attribute.)
163Of course, because we feed it the entire core, our arm can
164invoke itself (or any other formula in the battery). Hence, it
165can loop. And this is what a loop is - the simplest of cores.
167We need to do two things with this core: create it, and activate
168it. To be precise, we need two formulas: a formula which
169produces the core, and one which activates its subject. We can
170compose these functions with the handy `7` instruction:
172```
173[8 [1 0] [7 p a]]
174```
176`p` produces our core, `a` activates it. Let's take these in
177reverse order. How do we activate a core?
179Since we have only one formula, it's the battery itself.
180Thus we want to execute Nock with the whole core (already the
181subject, and the entire battery (slot `2`)). Hence, `a` is
183```
184[2 [0 1] [0 2]]
185```
187We could also use the handy `9` macro - which almost seems
188designed for firing arms on cores:
190```
191[9 2 [0 1]]
192```
194Which leaves us seeking
196```
197[8 [1 0] [7 p [9 2 0 1]]]
198```
200And all we have to do is build the core, `p`. How do we build a
201core? We add code to the subject, just as we added a variable
202above. The initial value of our counter was a constant, `0`.
203The initial (and permanent) value of our battery is a constant,
204the loop formula `l`. So `p` is
206```
207[8 [1 l] [0 1]]
208```
210Which would leave us seeking
212```
213[8 [1 0] [7 [8 [1 l] [0 1]] [9 2 0 1]]]
214```
216except that we have duplicated the `8` pattern again, since we
217know
219```
220[7 [8 [1 l] [0 1]] [9 2 0 1]]
221```
223is equivalent to
225```
226[8 [1 l] [9 2 0 1]]
227```
229so the full value of `f` is
231```
232[8 [1 0] [8 [1 l] [9 2 0 1]]]
233```
235Thus our only formula to compose is the loop body, `l`.
236Its subject is the loop core:
238```
239[bat pay]
240```
242where `bat` is just the loop formula, and `pay` is the pair `[b
243a]`, `b` being the counter, and `a` the input subject. Thus we
244could also write this subject as
246```
247[l b a]
248```
250and we see readily that `a` is at slot `7`, `b` `6`, `l` `2`.
251With this subject, we need to express the Hoon loop body
253```hoon
254?: =(a +(b)) :: line 4
255 b :: line 5
256$(b +(b)) :: line 6
257```
259This is obviously an if statement, and it calls for `6`. Ie:
261```
262[6 t y n]
263```
265Giving our decrement program as:
267```
268[8 [1 0] [8 [1 6 t y n] [9 2 0 1]]]
269```
271For `t`, how do we compute a flag that is yes (`0`) if `a` equals
272`b` plus one? Equals, we recall, is `5`. So `t` can only be
274```
275[5 [0 7] [4 0 6]]
276```
278If so, our product `y` is just the counter `b`:
280```
281[0 6]
282```
284And if not? We have to re-execute the loop with the counter
285incremented. If we were executing it with the same counter,
286obviously an infinite loop, we could use the same core:
288```
289[9 2 0 1]
290```
292But instead we need to construct a new core with the counter
293incremented:
295```
296[l +(b) a]
297```
299ie,
301```
302[[0 2] [4 0 6] [0 7]]
303```
305and `n` is:
307```
308[9 2 [[0 2] [4 0 6] [0 7]]]
309```
311Hence our complete decrement. Let's reformat vertically so we
312can actually read it:
314```
315[8
316 [1 0]
317 [ 8
318 [ 1
319 [ 6
320 t
321 y
322 n
323 ]
324 ]
325 [9 2 0 1]
326 ]
328```
330which becomes
332```
333[8
334 [1 0]
335 [ 8
336 [ 1
337 [ 6
338 [5 [0 7] [4 0 6]]
339 [0 6]
340 [9 2 [[0 2] [4 0 6] [0 7]]]
341 ]
342 ]
343 [9 2 0 1]
344 ]
346```
348or, on one line without superfluous brackets:
350```
351[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]
352```
354which works for the important special case, 42:
356```
357~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])
35841
359```
361If you understood this, you understand Nock. At least in principle!
362Now, go write an adder. Or don't.