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