git.iko.soy/urbit.org
on 3fae695 help sign in
urbit.org/docs/nock/example.md
364 lines 8.1 kB history raw
1---
2sort: 3
3next: true
4title: Example
5---
7# Nock by hand
9Some people write assembly language by hand. Some of them have a
10good reason to do so. But there's no good reason to write Nock by
11hand, ever.
13Except for the purposes of learning Nock. It's not necessary to
14know Nock to program in Hoon. But it's quite desirable. The
15feeling of understanding the system at two levels is pleasant.
17## Decrement in Nock
19A good practice exercise for Nock is a decrement formula. Ie, a
20formula `f` which implements the partial function that produces
21`(s - 1)` if `s` is a nonzero atom, and otherwise does not
22terminate.
24As we know, the equivalent formula for increment is
26```
27[4 0 1]
28```
30Thus:
32```
33~>zod:dojo .*(42 [4 0 1])
3443
35```
37Of course, increment is built into Nock. So, ha, that's easy.
39The best way to learn Nock is to *stop reading right now*, and
40go write your own decrement formula. There's no substitute for
41doing it yourself. But the second best way is faster...
43## Decrement in Hoon
45How do we decrement? A good way to start is to gaze fondly on
46how we'd do it if we actually had a real language, ie, Hoon.
47Here is a minimal decrement in Hoon:
49```
50=> a=. :: line 1
51=+ b=0 :: line 2
52|- :: line 3
53?: =(a +(b)) :: line 4
54 b :: line 5
55$(b +(b)) :: line 6
56```
58Or for fun, on one line:
60```
61=>(a=. =+(b=0 |-(?:(=(a +(b)) b $(b +(b))))))
62```
64Does Hoon actually work?
66```
67~zod:dojo> =>(42 =>(a=. =+(b=0 |-(?:(=(a +(b)) b $(b +(b)))))))
6841
69```
71Let's translate this into English. How do we decrement the
72subject? First (line 1), we rename the subject `a`. Second
73(line 2), we add a variable, `b`, an atom with value `0`.
74Third (line 3), we loop. Fourth, we test if `a` equals `b` plus
751 (line 4), produce `b` if it does (line 5), repeat the loop with
76`b` set to `b` plus 1 (line 6) if it doesn't. Obviously, while
77the syntax is unusual, the algorithm is anything but deep. We
78are calculating `b` minus one by counting up from `0`.
80(Obviously, this is an O(n) algorithm. Is there a better way?
81There is not. Do we actually do this in practice? Yes and no.)
83Unfortunately we are missing a third of our Rosetta stone. We
84have decrement in Hoon and we have it in English. How do we
85express this in Nock? What will the Hoon compiler generate from
86the code above? Let's work through it line by line.
88Nock has no types, variable names, etc. So line 1 is a no-op.
90How do we add a variable (line 2)? We compute a new subject,
91which is a cell of the present subject and the variable. With
92this new subject, we execute another formula.
94Since `0` is a constant, a formula that produces it is
96```
97[1 0]
98```
100To combine `0` with the subject, we compute
102```
103[[1 0] [0 1]]
104```
106which, if our subject is 42, gives us
108```
109[0 42]
110```
112which we can use as the subject for an inner formula, `g`.
113Composing our new variable with `g`, we have `f` as
115```
116[2 [[1 0] [0 1]] [1 g]]
117```
119which seems a little funky for something so simple. But we
120can simplify it with the composition macro, `7`:
122```
123[7 [[1 0] [0 1]] g]
124```
126and still further with the augmentation macro, `8`:
128```
129[8 [1 0] g]
130```
132If you refer back to the Nock definition, you'll see that all
133these formulas are semantically equivalent.
135Let's continue with our decrement. So what's `g`? We seem to
136loop. Does Nock have a loop instruction? It most certainly does
137not. So what do we do?
139We build a noun called a *core* - a construct which is behind any
140kind of interesting control flow in Hoon. Of course, the Nock
141programmer is not constrained to use the same techniques as the
142Hoon compiler, but it is probably a good idea.
144In Hoon, all the flow structures from your old life as an Earth
145programmer become cores. Functions and/or closures are cores,
146objects are cores modules are cores, even loops are cores.
148The core is just a cell whose tail is data (possibly containing
149other cores) and whose head is code (containing one or more
150formulas). The tail is the *payload* and the head is the
151*battery*. Hence your core is
153```
154[bat pay]
155```
157To activate a core, pick a formula out of the battery, and use
158the entire core (*not* just the payload) as the subject.
160(A core formula is called an *arm*. An arm is almost like an
161object-oriented method, but not quite - a method would be an arm
162that produces a function on an argument. The arm is just a
163function of the core, ie, a computed attribute.)
165Of course, because we feed it the entire core, our arm can
166invoke itself (or any other formula in the battery). Hence, it
167can loop. And this is what a loop is - the simplest of cores.
169We need to do two things with this core: create it, and activate
170it. To be precise, we need two formulas: a formula which
171produces the core, and one which activates its subject. We can
172compose these functions with the handy `7` instruction:
174```
175[8 [1 0] [7 p a]]
176```
178`p` produces our core, `a` activates it. Let's take these in
179reverse order. How do we activate a core?
181Since we have only one formula, it's the battery itself.
182Thus we want to execute Nock with the whole core (already the
183subject, and the entire battery (slot `2`). Hence, `a` is
185```
186[2 [0 1] [0 2]]
187```
189We could also use the handy `9` macro - which almost seems
190designed for firing arms on cores:
192```
193[9 2 [0 1]]
194```
196Which leaves us seeking
198```
199[8 [1 0] [7 p [9 2 0 1]]]
200```
202And all we have to do is build the core, `p`. How do we build a
203core? We add code to the subject, just as we added a variable
204above. The initial value of our counter was a constant, `0`.
205The initial (and permanent) value of our battery is a constant,
206the loop formula `l`. So `p` is
208```
209[8 [1 l] [0 1]]
210```
212Which would leave us seeking
214```
215[8 [1 0] [7 [8 [1 l] [0 1]] [9 2 0 1]]]
216```
218except that we have duplicated the `8` pattern again, since we
219know
221```
222[7 [8 [1 l] [0 1]] [9 2 0 1]]
223```
225is equivalent to
227```
228[8 [1 l] [9 2 0 1]]
229```
231so the full value of `f` is
233```
234[8 [1 0] [8 [1 l] [9 2 0 1]]]
235```
237Thus our only formula to compose is the loop body, `l`.
238Its subject is the loop core:
240```
241[bat pay]
242```
244where `bat` is just the loop formula, and `pay` is the pair `[a
245b]`, `a` being the input subject, and `b` the counter. Thus we
246could also write this subject as
248```
249[l b a]
250```
252and we see readily that `a` is at slot `7`, `b` `6`, `l` `2`.
253With this subject, we need to express the Hoon loop body
255```
256?: =(a +(b)) :: line 4
257 b :: line 5
258$(b +(b)) :: line 6
259```
261This is obviously an if statement, and it calls for `6`. Ie:
263```
264[6 t y n]
265```
267Giving our decrement program as:
269```
270[8 [1 0] [8 [1 6 t y n] [9 2 0 1]]]
271```
273For `t`, how do we compute a flag that is yes (`0`) if `a` equals
274`b` plus one? Equals, we recall, is `5`. So `t` can only be
276```
277[5 [0 7] [4 0 6]]
278```
280If so, our product `y` is just the counter `b`:
282```
283[0 6]
284```
286And if not? We have to re-execute the loop with the counter
287incremented. If we were executing it with the same counter,
288obviously an infinite loop, we could use the same core:
290```
291[9 2 0 1]
292```
294But instead we need to construct a new core with the counter
295incremented:
297```
298[l +(b) a]
299```
301ie,
303```
304[[0 2] [4 0 6] [0 7]]
305```
307and `n` is:
309```
310[9 2 [[0 2] [4 0 6] [0 7]]]
311```
313Hence our complete decrement. Let's reformat vertically so we
314can actually read it:
316```
317[8
318 [1 0]
319 [ 8
320 [ 1
321 [ 6
322 t
323 y
324 n
325 ]
326 ]
327 [9 2 0 1]
328 ]
330```
332which becomes
334```
335[8
336 [1 0]
337 [ 8
338 [ 1
339 [ 6
340 [5 [0 7] [4 0 6]]
341 [0 6]
342 [9 2 [[0 2] [4 0 6] [0 7]]]
343 ]
344 ]
345 [9 2 0 1]
346 ]
348```
350or, on one line without superfluous brackets:
352```
353[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]
354```
356which works for the important special case, 42:
358```
359~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])
36041
361```
363If you understood this, you understand Nock. At least in principle!
364Now, go write an adder. Or don't.