git.iko.soy/urbit.org
on b93c19b help sign in
urbit.org/reference/library/1b.md
272 lines 5.0 kB history raw
1+++
2title = "1b: Tree Addressing"
3weight = 2
4template = "doc.html"
5+++
6Check out the Nock [explanation](@/docs/learn/nock/_index.md) for more
7information on the tree-addressing system.
9### `++cap`
11Tree head
13Tests whether the tree address `a` is in the head or the tail of a noun.
14Produces the constant atom `%2` if it is within the head (subtree `+2`), or
15the constant atom `%3` if it is within the tail (subtree `+3`).
18#### Accepts
20`a` is an atom.
22#### Produces
24A constant atom.
26#### Source
28```
29 ++ cap
30 ~/ %cap
31 |= a=@
32 ^- ?($2 $3)
33 ?- a
34 $2 %2
35 $3 %3
36 ?(%0 %1) !!
37 * $(a (div a 2))
38 ==
39```
41#### Examples
43```
44 > (cap 4)
45 %2
47 > (cap 6)
48 %3
50 > (cap (add 10 9))
51 %2
53 > (cap 1) ::address '1' is in neither the head nor the tail
54 ! exit
56 > (cap 0x40))
57 %2
58 > `@`0x40
59 64
61 > (cap 'a')
62 %3
63 > `@`'a'
64 97
65```
67---
68### `++mas`
70Address within head/tail
72Computes the tree address of atom `a` within either the head (`+2`) or tail
73(`+3`) of a noun.
75#### Accepts
77`a` is an atom.
79#### Produces
81An atom.
83#### Source
85```
86 ++ mas
87 ~/ %mas
88 |= a=@
89 ^- @
90 ?- a
91 1 !!
92 2 1
93 3 1
94 * (add (mod a 2) (mul $(a (div a 2)) 2))
95 ==
96```
98#### Examples
100```
101 > (mas 3)
102 1
104 > (mas 4)
105 2
107 > (mas 5)
108 3
109 > (cap 5) ::`(cap a)` computes whether address `a` is in the head or the tail
110 %2
112 > (mas 7)
113 3
114 > (cap 7)
115 %3
117 > (mas 11)
118 7
120 > (mas (mas 11))
121 3
123 > (cap (mas 6))
124 %3
126 > (mas 0)
127 ! exit ::address `0` is in neither the head nor the tail
129 > (mas 1)
130 ! exit ::address `1` is in neither the head nor the tail
131```
133#### Discussion
135```
136 1
137 / \
138 / \
139 2 3 <--here are the head (`+2`) and the tail (`+3`)
140 / \ /\
141 4 5 6 7
142 /\ /\ /\ /\
143 (continues...)
144```
146Running `(mas 7)` in the Dojo will return `3`, because address `+3` is what
147`+7` now occupies. The tree below helps illustrate the relationship. With
148parentheses are `a` values (if `a` is in subtree `+3`), and without parentheses
149are the values returned with `(mas a)`.
151```
152 1(3) ::new/(old) addresses
153 / \
154 2 3
155 (6) (7)
156 / \ /\
157 / \ / \
158 4 5 6 7
159 (12) (13) (14) (15)
160 / \ / \ / \ / \
161 (continues...)
162```
164Notice how the old values in the head (subtree `+2`) were not illustrated in
165this case, because `+7` is within the tail (subtree `+3`).
167---
168### `++peg`
170Address within address
172Computes the absolute address of `b`, a relative address within the subtree
173`a`.
175#### Accepts
177`a` is an atom.
179`b` is an atom.
181#### Produces
183An atom.
185#### Source
187```
188 ++ peg
189 ~/ %peg
190 |= [a=@ b=@]
191 ?< =(0 a)
192 ^- @
193 ?- b
194 $1 a
195 $2 (mul a 2)
196 $3 +((mul a 2))
197 * (add (mod b 2) (mul $(b (div b 2)) 2))
198 ==
199```
201#### Examples
203```
204 > (peg 4 1)
205 4
207 > (peg 1 4)
208 4
210 > (peg 4 2)
211 8
213 > (peg 4 8)
214 32
216 > (peg 4 (4 2))
217 32
219 > (peg 8 45)
220 269
222 > (cap (peg 4 2)) ::`(cap a)` computes whether address `a` is in the head or the tail
223 %2
225```
227#### Discussion
229In other words, the subtree at address `a` is treated as a tree in its own
230right (starting with root `+1`, head `+2`, and tail `+3`). Relative address
231`b` is found with respect to `a`, and then its absolute address, within the
232greater tree, is returned.
234Running `(peg 3 4)` in the Dojo, for example, will return `12`. Looking at
235a tree diagram makes it easy to see why.
237```
238 1
239 / \
240 / \
241 / \
242 2 3 <- here is the subtree `+3`. The subtree address is `a` in `(peg a b)`
243 / \ / \
244 / \ / \
245 4 5 6 7
246 / \ / \ / \ / \
247 8 9 10 11 12 13 14 15
248 /\ /\ /\ /\ /\ /\ /\ /\
249 (continues...)
250```
252When we consider subtree at address `+3` by itself, it has relative addresses
253that are structured in the same way as its parent tree's absolute addresses.
254The absolute addresses are given in parentheses in the diagram below.
255Notice how relative address `+4` is at the same position as absolute address
256`+12`.
258```
259 1(3) ::new/(old) addresses
260 / \
261 2 3
262 (6) (7)
263 / \ /\
264 / \ / \
265 4 5 6 7
266 (12) (13) (14) (15)
267 / \ / \ / \ / \
268 (continues...)
269```
272---