1b: Tree Addressing

+cap

Tree head.

Tests whether the tree address .a is in the head or the tail of a $noun. Produces the constant $atom %2 if it is within the head (subtree +2), or the constant $atom %3 if it is within the tail (subtree +3).

Specifically, +cap just checks whether the second-to-most significant bit of the input is 1 or 0.

Accepts

.a is an $atom.

Produces

A constant $atom.

Source

++  cap
  ~/  %cap
  |=  a=@
  ^-  ?(%2 %3)
  ?-  a
    %2        %2
    %3        %3
    ?(%0 %1)  !!
    *         $(a (div a 2))
  ==

Examples

> (cap 4)
%2

> (cap 6)
%3

> (cap (add 10 9))
%2

The below fails because address +1 is neither the head nor the tail.

> (cap 1)
! exit

> (cap 0x40))
%2

> `@`0x40
64

> (cap 'a')
%3

> `@`'a'
97

---

+mas

Address within head/tail.

Computes the tree address of $atom .a within either the head (+2) or tail (+3) of a $noun.

Specifically, +mas just replaces the two most significant bits of the input with 01.

Accepts

.a is an $atom.

Produces

An $atom.

Source

++  mas
  ~/  %mas
  |=  a=@
  ^-  @
  ?-  a
    ?(%2 %3)  1
    ?(%0 %1)  !!
    *         (add (mod a 2) (mul $(a (div a 2)) 2))
  ==

Examples

> (mas 3)
1

> (mas 4)
2

(cap a) fails computes whether address .a is in the head or the tail.

> (mas 5)
3

> (cap 5)
%2

> (mas 7)
3

> (cap 7)
%3

> (mas 11)
7

> (mas (mas 11))
3

> (cap (mas 6))
%3

Address +0 is in neither the head nor the tail.

> (mas 0)
! exit

Address +1 is in neither the head nor the tail.

> (mas 1)
! exit

Discussion

            1
          /   \
         /     \
        2       3              <--here are the head (`+2`) and the tail (`+3`)
       / \      /\
      4   5    6  7
     /\   /\  /\  /\
     (continues...)

Running (mas 7) in the Dojo will return 3, because address +3 is what +7 now occupies. The tree below helps illustrate the relationship. With parentheses are .a values (if .a is in subtree +3), and without parentheses are the values returned with (mas a).

            1(3)                       ::new/(old) addresses
           /    \
          2       3
         (6)     (7)
        / \       /\
       /   \     /  \
      4     5   6    7
     (12) (13) (14) (15)
    / \    / \ / \   / \
       (continues...)

Notice how the old values in the head (subtree +2) were not illustrated in this case, because +7 is within the tail (subtree +3).

---

+peg

Address within address.

Computes the absolute address of .b, a relative address within the subtree .a.

Specifically, +peg just concatenates the bits of the input, excluding the most significant bit of either, and then sets the next most significant bit after the concatenation to 1.

Accepts

.a is an $atom.

.b is an $atom.

Produces

An $atom.

Source

++  peg
  ~/  %peg
  |=  [a=@ b=@]
  ?<  =(0 a)
  ^-  @
  ?-  b
    %1  a
    %2  (mul a 2)
    %3  +((mul a 2))
    *   (add (mod b 2) (mul $(b (div b 2)) 2))
  ==

Examples

> (peg 4 1)
4

> (peg 1 4)
4

> (peg 4 2)
8

> (peg 4 8)
32

> (peg 4 (peg 4 2))
32

> (peg 8 45)
269

> (cap (peg 4 2))
%2

Discussion

In other words, the subtree at address .a is treated as a tree in its own right (starting with root +1, head +2, and tail +3). Relative address .b is found with respect to .a, and then its absolute address, within the greater tree, is returned.

Running (peg 3 4) in the Dojo, for example, will return 12. Looking at a tree diagram makes it easy to see why.

                 1
               /   \
              /     \
             /       \
            /         \
           2           3       <- here is the subtree `+3`. The subtree address is `a` in `(peg a b)`
          / \         / \
         /   \       /   \
        4     5     6     7
       / \   / \   / \   / \
      8  9  10 11 12 13 14  15
     /\  /\ /\ /\ /\ /\ /\  /\
         (continues...)

When we consider subtree at address +3 by itself, it has relative addresses that are structured in the same way as its parent tree's absolute addresses. The absolute addresses are given in parentheses in the diagram below. Notice how relative address +4 is at the same position as absolute address +12.

            1(3)                        <- new/(old) addresses
           /    \
          2       3
         (6)     (7)
        / \       /\
       /   \     /  \
      4     5   6    7
    (12) (13) (14)  (15)
    / \    / \ / \   / \
       (continues...)

---