git.iko.soy/urbit.org
on 3bce308 help sign in
urbit.org/tutorials/nock/example.md
363 lines 8.2 kB history raw
1+++
2title = "Example"
3weight = 3
4template = "doc.html"
5aliases = ["docs/learn/nock/example"]
6insert_anchor_links = "right"
7+++
8Some people write assembly language by hand. Some of them have a
9good reason to do so. But there's no good reason to write Nock by
10hand, ever.
12Except for the purposes of learning Nock. It's not necessary to
13know Nock to program in Hoon. But it's quite desirable. The
14feeling of understanding the system at two levels is pleasant.
16## Decrement in Nock
18A good practice exercise for Nock is a decrement formula. Ie, a
19formula `f` which implements the partial function that produces
20`(s - 1)` if `s` is a nonzero atom, and otherwise does not
21terminate.
23As we know, the equivalent formula for increment is
25```
26[4 0 1]
27```
29Thus:
31```
32~>zod:dojo .*(42 [4 0 1])
3343
34```
36Of course, increment is built into Nock. So, ha, that's easy.
38The best way to learn Nock is to **stop reading right now**, and
39go write your own decrement formula. There's no substitute for
40doing it yourself. But the second best way is faster...
42## Decrement in Hoon
44How do we decrement? A good way to start is to gaze fondly on
45how we'd do it if we actually had a real language, ie, Hoon.
46Here is a minimal decrement in Hoon:
48```
49=> a=. :: line 1
50=+ b=0 :: line 2
51|- :: line 3
52?: =(a +(b)) :: line 4
53 b :: line 5
54$(b +(b)) :: line 6
55```
57Or for fun, on one line:
59```
60=>(a=. =+(b=0 |-(?:(=(a +(b)) b $(b +(b))))))
61```
63Does Hoon actually work?
65```
66~zod:dojo> =>(42 =>(a=. =+(b=0 |-(?:(=(a +(b)) b $(b +(b)))))))
6741
68```
70Let's translate this into English. How do we decrement the
71subject? First (line 1), we rename the subject `a`. Second
72(line 2), we add a variable, `b`, an atom with value `0`.
73Third (line 3), we loop. Fourth, we test if `a` equals `b` plus
741 (line 4), produce `b` if it does (line 5), repeat the loop with
75`b` set to `b` plus 1 (line 6) if it doesn't. Obviously, while
76the syntax is unusual, the algorithm is anything but deep. We
77are calculating `b` minus one by counting up from `0`.
79(Obviously, this is an O(n) algorithm. Is there a better way?
80There is not. Do we actually do this in practice? Yes and no.)
82Unfortunately we are missing a third of our Rosetta stone. We
83have decrement in Hoon and we have it in English. How do we
84express this in Nock? What will the Hoon compiler generate from
85the code above? Let's work through it line by line.
87Nock has no types, variable names, etc. So line 1 is a no-op.
89How do we add a variable (line 2)? We compute a new subject,
90which is a cell of the present subject and the variable. With
91this new subject, we execute another formula.
93Since `0` is a constant, a formula that produces it is
95```
96[1 0]
97```
99To combine `0` with the subject, we compute
101```
102[[1 0] [0 1]]
103```
105which, if our subject is 42, gives us
107```
108[0 42]
109```
111which we can use as the subject for an inner formula, `g`.
112Composing our new variable with `g`, we have `f` as
114```
115[2 [[1 0] [0 1]] [1 g]]
116```
118which seems a little funky for something so simple. But we
119can simplify it with the composition macro, `7`:
121```
122[7 [[1 0] [0 1]] g]
123```
125and still further with the augmentation macro, `8`:
127```
128[8 [1 0] g]
129```
131If you refer back to the Nock definition, you'll see that all
132these formulas are semantically equivalent.
134Let's continue with our decrement. So what's `g`? We seem to
135loop. Does Nock have a loop instruction? It most certainly does
136not. So what do we do?
138We build a noun called a **core** - a construct which is behind any
139kind of interesting control flow in Hoon. Of course, the Nock
140programmer is not constrained to use the same techniques as the
141Hoon compiler, but it is probably a good idea.
143In Hoon, all the flow structures from your old life as an Earth
144programmer become cores. Functions and/or closures are cores,
145objects are cores, modules are cores, even loops are cores.
147The core is just a cell whose tail is data (possibly containing
148other cores) and whose head is code (containing one or more
149formulas). The tail is the **payload** and the head is the
150**battery**. Hence your core is
152```
153[bat pay]
154```
156To activate a core, pick a formula out of the battery, and use
157the entire core (**not** just the payload) as the subject.
159(A core formula is called an **arm**. An arm is almost like an
160object-oriented method, but not quite - a method would be an arm
161that produces a function on an argument. The arm is just a
162function of the core, ie, a computed attribute.)
164Of course, because we feed it the entire core, our arm can
165invoke itself (or any other formula in the battery). Hence, it
166can loop. And this is what a loop is - the simplest of cores.
168We need to do two things with this core: create it, and activate
169it. To be precise, we need two formulas: a formula which
170produces the core, and one which activates its subject. We can
171compose these functions with the handy `7` instruction:
173```
174[8 [1 0] [7 p a]]
175```
177`p` produces our core, `a` activates it. Let's take these in
178reverse order. How do we activate a core?
180Since we have only one formula, it's the battery itself.
181Thus we want to execute Nock with the whole core (already the
182subject, and the entire battery (slot `2`)). Hence, `a` is
184```
185[2 [0 1] [0 2]]
186```
188We could also use the handy `9` macro - which almost seems
189designed for firing arms on cores:
191```
192[9 2 [0 1]]
193```
195Which leaves us seeking
197```
198[8 [1 0] [7 p [9 2 0 1]]]
199```
201And all we have to do is build the core, `p`. How do we build a
202core? We add code to the subject, just as we added a variable
203above. The initial value of our counter was a constant, `0`.
204The initial (and permanent) value of our battery is a constant,
205the loop formula `l`. So `p` is
207```
208[8 [1 l] [0 1]]
209```
211Which would leave us seeking
213```
214[8 [1 0] [7 [8 [1 l] [0 1]] [9 2 0 1]]]
215```
217except that we have duplicated the `8` pattern again, since we
218know
220```
221[7 [8 [1 l] [0 1]] [9 2 0 1]]
222```
224is equivalent to
226```
227[8 [1 l] [9 2 0 1]]
228```
230so the full value of `f` is
232```
233[8 [1 0] [8 [1 l] [9 2 0 1]]]
234```
236Thus our only formula to compose is the loop body, `l`.
237Its subject is the loop core:
239```
240[bat pay]
241```
243where `bat` is just the loop formula, and `pay` is the pair `[b
244a]`, `b` being the counter, and `a` the input subject. Thus we
245could also write this subject as
247```
248[l b a]
249```
251and we see readily that `a` is at slot `7`, `b` `6`, `l` `2`.
252With this subject, we need to express the Hoon loop body
254```hoon
255?: =(a +(b)) :: line 4
256 b :: line 5
257$(b +(b)) :: line 6
258```
260This is obviously an if statement, and it calls for `6`. Ie:
262```
263[6 t y n]
264```
266Giving our decrement program as:
268```
269[8 [1 0] [8 [1 6 t y n] [9 2 0 1]]]
270```
272For `t`, how do we compute a flag that is yes (`0`) if `a` equals
273`b` plus one? Equals, we recall, is `5`. So `t` can only be
275```
276[5 [0 7] [4 0 6]]
277```
279If so, our product `y` is just the counter `b`:
281```
282[0 6]
283```
285And if not? We have to re-execute the loop with the counter
286incremented. If we were executing it with the same counter,
287obviously an infinite loop, we could use the same core:
289```
290[9 2 0 1]
291```
293But instead we need to construct a new core with the counter
294incremented:
296```
297[l +(b) a]
298```
300ie,
302```
303[[0 2] [4 0 6] [0 7]]
304```
306and `n` is:
308```
309[9 2 [[0 2] [4 0 6] [0 7]]]
310```
312Hence our complete decrement. Let's reformat vertically so we
313can actually read it:
315```
316[8
317 [1 0]
318 [ 8
319 [ 1
320 [ 6
321 t
322 y
323 n
324 ]
325 ]
326 [9 2 0 1]
327 ]
329```
331which becomes
333```
334[8
335 [1 0]
336 [ 8
337 [ 1
338 [ 6
339 [5 [0 7] [4 0 6]]
340 [0 6]
341 [9 2 [[0 2] [4 0 6] [0 7]]]
342 ]
343 ]
344 [9 2 0 1]
345 ]
347```
349or, on one line without superfluous brackets:
351```
352[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]
353```
355which works for the important special case, 42:
357```
358~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])
35941
360```
362If you understood this, you understand Nock. At least in principle!
363Now, go write an adder. Or don't.