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