git.iko.soy/urbit.org
on 979ae21 help sign in
urbit.org/hoon/reference/stdlib/1b.md
273 lines 5.0 kB history raw
1+++
2title = "1b: Tree Addressing"
3weight = 2
4template = "doc.html"
5+++
7Check out the Nock [explanation](@/docs/nock/_index.md) for more
8information on the tree-addressing system.
10### `++cap`
12Tree head
14Tests whether the tree address `a` is in the head or the tail of a noun.
15Produces the constant atom `%2` if it is within the head (subtree `+2`), or
16the constant atom `%3` if it is within the tail (subtree `+3`).
19#### Accepts
21`a` is an atom.
23#### Produces
25A constant atom.
27#### Source
29```hoon
30 ++ cap
31 ~/ %cap
32 |= a=@
33 ^- ?($2 $3)
34 ?- a
35 $2 %2
36 $3 %3
37 ?(%0 %1) !!
38 * $(a (div a 2))
39 ==
40```
42#### Examples
44```
45 > (cap 4)
46 %2
48 > (cap 6)
49 %3
51 > (cap (add 10 9))
52 %2
54 > (cap 1) ::address '1' is in neither the head nor the tail
55 ! exit
57 > (cap 0x40))
58 %2
59 > `@`0x40
60 64
62 > (cap 'a')
63 %3
64 > `@`'a'
65 97
66```
68---
69### `++mas`
71Address within head/tail
73Computes the tree address of atom `a` within either the head (`+2`) or tail
74(`+3`) of a noun.
76#### Accepts
78`a` is an atom.
80#### Produces
82An atom.
84#### Source
86```hoon
87 ++ mas
88 ~/ %mas
89 |= a=@
90 ^- @
91 ?- a
92 1 !!
93 2 1
94 3 1
95 * (add (mod a 2) (mul $(a (div a 2)) 2))
96 ==
97```
99#### Examples
101```
102 > (mas 3)
103 1
105 > (mas 4)
106 2
108 > (mas 5)
109 3
110 > (cap 5) ::`(cap a)` computes whether address `a` is in the head or the tail
111 %2
113 > (mas 7)
114 3
115 > (cap 7)
116 %3
118 > (mas 11)
119 7
121 > (mas (mas 11))
122 3
124 > (cap (mas 6))
125 %3
127 > (mas 0)
128 ! exit ::address `0` is in neither the head nor the tail
130 > (mas 1)
131 ! exit ::address `1` is in neither the head nor the tail
132```
134#### Discussion
136```
137 1
138 / \
139 / \
140 2 3 <--here are the head (`+2`) and the tail (`+3`)
141 / \ /\
142 4 5 6 7
143 /\ /\ /\ /\
144 (continues...)
145```
147Running `(mas 7)` in the Dojo will return `3`, because address `+3` is what
148`+7` now occupies. The tree below helps illustrate the relationship. With
149parentheses are `a` values (if `a` is in subtree `+3`), and without parentheses
150are the values returned with `(mas a)`.
152```
153 1(3) ::new/(old) addresses
154 / \
155 2 3
156 (6) (7)
157 / \ /\
158 / \ / \
159 4 5 6 7
160 (12) (13) (14) (15)
161 / \ / \ / \ / \
162 (continues...)
163```
165Notice how the old values in the head (subtree `+2`) were not illustrated in
166this case, because `+7` is within the tail (subtree `+3`).
168---
169### `++peg`
171Address within address
173Computes the absolute address of `b`, a relative address within the subtree
174`a`.
176#### Accepts
178`a` is an atom.
180`b` is an atom.
182#### Produces
184An atom.
186#### Source
188```hoon
189 ++ peg
190 ~/ %peg
191 |= [a=@ b=@]
192 ?< =(0 a)
193 ^- @
194 ?- b
195 $1 a
196 $2 (mul a 2)
197 $3 +((mul a 2))
198 * (add (mod b 2) (mul $(b (div b 2)) 2))
199 ==
200```
202#### Examples
204```
205 > (peg 4 1)
206 4
208 > (peg 1 4)
209 4
211 > (peg 4 2)
212 8
214 > (peg 4 8)
215 32
217 > (peg 4 (4 2))
218 32
220 > (peg 8 45)
221 269
223 > (cap (peg 4 2)) ::`(cap a)` computes whether address `a` is in the head or the tail
224 %2
226```
228#### Discussion
230In other words, the subtree at address `a` is treated as a tree in its own
231right (starting with root `+1`, head `+2`, and tail `+3`). Relative address
232`b` is found with respect to `a`, and then its absolute address, within the
233greater tree, is returned.
235Running `(peg 3 4)` in the Dojo, for example, will return `12`. Looking at
236a tree diagram makes it easy to see why.
238```
239 1
240 / \
241 / \
242 / \
243 2 3 <- here is the subtree `+3`. The subtree address is `a` in `(peg a b)`
244 / \ / \
245 / \ / \
246 4 5 6 7
247 / \ / \ / \ / \
248 8 9 10 11 12 13 14 15
249 /\ /\ /\ /\ /\ /\ /\ /\
250 (continues...)
251```
253When we consider subtree at address `+3` by itself, it has relative addresses
254that are structured in the same way as its parent tree's absolute addresses.
255The absolute addresses are given in parentheses in the diagram below.
256Notice how relative address `+4` is at the same position as absolute address
257`+12`.
259```
260 1(3) ::new/(old) addresses
261 / \
262 2 3
263 (6) (7)
264 / \ /\
265 / \ / \
266 4 5 6 7
267 (12) (13) (14) (15)
268 / \ / \ / \ / \
269 (continues...)
270```
273---