git.iko.soy/urbit.org
on c19bc7a help sign in
urbit.org/docs/reference/library/1b.udon
276 lines 5.1 kB history raw
1:- :~ navhome/'/docs/'
2 sort/'2'
3 title/'1b: Tree Addressing'
4 ==
6;>
8# 1b: tree addressing
10Check out the Nock [explanation](docs/nock/explanation/) for more
11information on the tree-addressing system.
13### `++cap`(#anchors-in-markdown))
15Tree head
17Tests whether the tree address `a` is in the head or the tail of a noun.
18Produces the constant atom `%2` if it is within the head (subtree `+2`), or
19the constant atom `%3` if it is within the tail (subtree `+3`).
22#### Accepts
24`a` is an atom.
26#### Produces
28A constant atom.
30#### Source
32```
33 ++ cap
34 ~/ %cap
35 |= a=@
36 ^- ?($2 $3)
37 ?- a
38 $2 %2
39 $3 %3
40 ?(%0 %1) !!
41 * $(a (div a 2))
42 ==
43```
45#### Examples
47```
48 > (cap 4)
49 %2
51 > (cap 6)
52 %3
54 > (cap (add 10 9))
55 %2
57 > (cap 1) ::address '1' is in neither the head nor the tail
58 ! exit
60 > (cap 0x40))
61 %2
62 > `@`0x40
63 64
65 > (cap 'a')
66 %3
67 > `@`'a'
68 97
69```
71---
72### `++mas`
74Address within head/tail
76Computes the tree address of atom `a` within either the head (`+2`) or tail
77(`+3`) of a noun.
79#### Accepts
81`a` is an atom.
83#### Produces
85An atom.
87#### Source
89```
90 ++ mas
91 ~/ %mas
92 |= a=@
93 ^- @
94 ?- a
95 1 !!
96 2 1
97 3 1
98 * (add (mod a 2) (mul $(a (div a 2)) 2))
99 ==
100```
102#### Examples
104```
105 > (mas 3)
106 1
108 > (mas 4)
109 2
111 > (mas 5)
112 3
113 > (cap 5) ::`(cap a)` computes whether address `a` is in the head or the tail
114 %2
116 > (mas 7)
117 3
118 > (cap 7)
119 %3
121 > (mas 11)
122 7
124 > (mas (mas 11))
125 3
127 > (cap (mas 6))
128 %3
130 > (mas 0)
131 ! exit ::address `0` is in neither the head nor the tail
133 > (mas 1)
134 ! exit ::address `1` is in neither the head nor the tail
135```
137#### Discussion
139```
140 1
141 / \
142 / \
143 2 3 <--here are the head (`+2`) and the tail (`+3`)
144 / \ /\
145 4 5 6 7
146 /\ /\ /\ /\
147 (continues...)
148```
150Running `(mas 7)` in the Dojo will return `3`, because address `+3` is what
151`+7` now occupies. The tree below helps illustrate the relationship. With
152parentheses are `a` values (if `a` is in subtree `+3`), and without parentheses
153are the values returned with `(mas a)`.
155```
156 1(3) ::new/(old) addresses
157 / \
158 2 3
159 (6) (7)
160 / \ /\
161 / \ / \
162 4 5 6 7
163 (12) (13) (14) (15)
164 / \ / \ / \ / \
165 (continues...)
166```
168Notice how the old values in the head (subtree `+2`) were not illustrated in
169this case, because `+7` is within the tail (subtree `+3`).
171---
172### `++peg`
174Address within address
176Computes the absolute address of `b`, a relative address within the subtree
177`a`.
179#### Accepts
181`a` is an atom.
183`b` is an atom.
185#### Produces
187An atom.
189#### Source
191```
192 ++ peg
193 ~/ %peg
194 |= [a=@ b=@]
195 ?< =(0 a)
196 ^- @
197 ?- b
198 $1 a
199 $2 (mul a 2)
200 $3 +((mul a 2))
201 * (add (mod b 2) (mul $(b (div b 2)) 2))
202 ==
203```
205#### Examples
207```
208 > (peg 4 1)
209 4
211 > (peg 1 4)
212 4
214 > (peg 4 2)
215 8
217 > (peg 4 8)
218 32
220 > (peg 4 (4 2))
221 32
223 > (peg 8 45)
224 269
226 > (cap (peg 4 2)) ::`(cap a)` computes whether address `a` is in the head or the tail
227 %2
229```
231#### Discussion
233In other words, the subtree at address `a` is treated as a tree in its own
234right (starting with root `+1`, head `+2`, and tail `+3`). Relative address
235`b` is found with respect to `a`, and then its absolute address, within the
236greater tree, is returned.
238Running `(peg 3 4)` in the Dojo, for example, will return `12`. Looking at
239a tree diagram makes it easy to see why.
241```
242 1
243 / \
244 / \
245 / \
246 2 3 <- here is the subtree `+3`. The subtree address is `a` in `(peg a b)`
247 / \ / \
248 / \ / \
249 4 5 6 7
250 / \ / \ / \ / \
251 8 9 10 11 12 13 14 15
252 /\ /\ /\ /\ /\ /\ /\ /\
253 (continues...)
254```
256When we consider subtree at address `+3` by itself, it has relative addresses
257that are structured in the same way as its parent tree's absolute addresses.
258The absolute addresses are given in parentheses in the diagram below.
259Notice how relative address `+4` is at the same position as absolute address
260`+12`.
262```
263 1(3) ::new/(old) addresses
264 / \
265 2 3
266 (6) (7)
267 / \ /\
268 / \ / \
269 4 5 6 7
270 (12) (13) (14) (15)
271 / \ / \ / \ / \
272 (continues...)
273```
276---