Lesson 7 – A Four-Point Buc

Introduction


In the last lesson, we started to study basic recursion.  In this lesson, we'll take a deeper dive, particularly looking at how a modified subject is created before recursion takes place.

The important thing to learn here is that when we recurse in hoon, any wings which are modified as part of the recursive call (to the $ arm) have their modifications evaluated first, but only applied (simultaneously) when we return to our trap’s $ arm (or gate’s $ arm, if no trap is used).

This “simultaneously” part can be difficult to understand. In this lesson, we’re going to write a generator with a hard-coded number of recursions. Having a fixed number of iterations will help us better understand exactly what is going on in each cycle. Predicting the output of this generator is critical.

We suggest you read through this entire lesson, attempt to write out the output on paper using your own mental faculties, and then (and only then) create the generator and run it.

Goal

Write a generator which takes two @uds as arguments and produces a list of cells of those arguments, and iterations of those arguments based on some changes applied recursively.

Standard Library


list

SyntaxSummary
(list <type>)Produces a type, which is a list of items having a specified type.

++list is a standard library function known as “mold generator”.
++list takes one argument, a type, and produces a mold of a list of that type.

In prior generators, we’ve cast our output as either an atomic aura, a cell of atomic auras, or a tape (which is `(list @tD)`, a list of ASCII characters).
In this lesson, we will cast our output as a list of cells, each of two atoms w/ specified auras.

Exercise

Try this in dojo:

=test [[%one %two] [%three %four] [%five %six] ~]
`(list [@tas @tas])`test
~[[%one %two] [%three %four] [%five %six]]
=five [0 1 2 3 4 5 ~]
`(list @p)``(list @)`five
~[~zod ~nec ~bud ~wes ~sev ~per]

Note that before casting to (list @p), it is necessary to first cast to (list @). That is because @ud cannot be cast to @p directly. Therefore, we must first cast to a list of raw atoms.

=letters ~[['a' 'b'] ['c' 'd'] ['e' 'f']]
`(list @)`letters
Nest-fail
`(list [@ @])`letters
~[[97 98] [99 100] [101 102]]

Note that our first attempt fails. That is because our list ‘letters’ is NOT a list of letters, so it cannot be cast to a list of atoms. It is a list of cells of two letters. Therefore, we can cast it to a list of cells of two atoms.


flop

SyntaxSummary
(flop <type>) Reverses the order of a list.

++flop is an arm in the Hoon standard library used to reverse the ordering of a list.
It accepts a (list) and produces a (list) with the same elements in reverse order.

In the first example above, we created a list of cells of two @tas atoms. We can flip the order of that list, using flop.

Exercise

Try this in dojo:

(flop `(list [@tas @tas])`test)
~[[%five %six] [%three %four] [%one %two]]
(flop `(list [@t @t])`letters)
~[['e' 'f'] ['c' 'd'] ['a' 'b']]

Note that we must use the explicit `(list )` cast in these examples. While the nouns we’ve created do have the form of a list, the compiler does not know that they are lists unless we say so explicitly.
We could also solve this by casting as a list when creating.

=letters `(list [@t @t])`~[['a' 'b'] ['c' 'd'] ['e' 'f']]
(flop letters)
~[['e' 'f'] ['c' 'd'] ['a' 'b']]

Let us clear our subject before moving on.

=test
=five
=letters


Generator

|=  [a=@ud b=@ud]
=/  cycle=@ud  4
=|  output=(list [@ud @ud])
|-  ^-  (list [@ud @ud])
?:  =(cycle 0)
  (flop output)
%=  $
  a  +(a)
  b  (add a b)
  output  :-([a b] output)
  cycle  (dec cycle)
==

Walkthrough

  • |= [a=@ud b=@ud]
    |= creates a gate which takes a cell of two @ud arguments

    • =/ cycle=@ud 4
      =/ creates an @ud with a face of ‘cycle’ and gives it a value of 4. This will be used to cause recursion 4 times

      • =/ output=(list [@ud @ud]) [~]
        =/ creates a list of cells of @uds and gives it a value, [~]. We could just as easily have used =| here, and that is actually better style, but we wanted to explicitly state the starting value here is [~].

        • ^- (list [@ud @ud])
          ^- casts our output as a list of cells of two @ud values ([@ud @ud])

          • |-
            |- creates a trap, this will be the point at which evaluation continues if we should call the $ arm.

            • ?: =(cycle 0)
              ?: creates a test with branching outcomes - if the test (is cycle is equal to 0), then we will take the output list, flop it, and print it - if the test is false, recurse with modified values.

              • (flop output)
                If the test is true, take our list (output) and produce a list with the same items in reverse order.
                This is the noun which the generator will eventually print, when cycle is equal to 0)
              • %=  $
                  a  +(a)
                  b  (add a b)
                  output  :-([a b] output)
                  cycle  (dec cycle)
                ==

                If the test is false, we must recurse with modifications.
                This is the tricky part - let’s focus on the first three changes.

                1. %= takes a wing and resolves it with changes.
                2. The modified value of a will be +(a).
                3. The modified value for b is a function of a, but the important thing to note is that, while a will also be modified for recursion, this evaluation of b uses the current value of a(i.e., before incrementing).
                4. If our input for the generator is [1 1]:
                  • The first cell in our output will be [1 1], as output :-([a b] output) is evaluated with existing values of a and b, not the new values used for recursion.
                5. The second cell in our list will be [2 2]:
                  • a = +(a) = 1 + 1 = 2
                  • b = (add a b) = 1 + 1 = 2
                6. You might instinctively expect [2 3], since we’ve already incremented ‘a’ before ‘b’ is modified, however: the modified values are used only for next recursion! The subject is not modified until the call to $ takes place.

                  Even though in a linear reading would suggest that ‘a’ is incremented before ‘b’ is modified for the recursion, and both are modified before ‘output’ has [a b] appended to its head, the reality is that nothing is modified in the current subject -- all modified values are used only for the call to $ and following resolution of the arm.”

Flow

  1. Request an input of a cell of two @ud values and form a gate
    |=  [a=@ud b=@ud]
  2. Evaluate the $ arm of the gate
  3. Add to the subject a value with face, “cycle”; type, @ud; and value, 4
    =/  cycle=@ud  4
  4. Add to the subject a value with face, “output”; type, list of cells of two @uds; and initial value, null
    =|  output=(list [@ud @ud])
  5. Cast the evaluation of the following expression as a list of cells of two @uds
    ^-  (list [@ud @ud])
  6. Form a trap, having one arm called $, which is evaluated immediately
    |-
  7. create a branching test, checking whether =(cycle 0)
    ?:  =(cycle 0)
  8. If cycle is equal to 0, return ‘output’, flopped (i.e., reverse the order of the list)
     (flop output)
  9. If cycle is not equal to 0, recurse back into $, with the following changes applied. In the next step, we’ll discuss what happens if the input argument to the generator is [1 1]
    %=  $
      a       +(a)
      b       (add a b)
      output  :-([a b] output)
      cycle   (dec cycle)
    ==

Stepthrough

Let's talk through each pass of the generator, assuming the input is [1 1]

  • Pass 1
    • a will become +(a) = 2
      b will become (add a b) = 1 (pre-modification value of a) + 1 = 2
      output will add a cell of a and b (pre modification values) = [[1 1] ~]
      cycle will become (dec cycle) = 3
  • Pass 2
    • a will become +(a) = 3
      b will become (add a b) = 2 (pre-modification value of a) + 2 = 4
      output will add a cell of a and b (pre modification values) = [[2 2] [1 1] ~]
      cycle will become (dec cycle) = 2
  • Pass 3
    • a will become +(a) = 4
      b will become (add a b) = 3 (pre-modification value of a) + 4 = 7
      output will add a cell of a and b (pre modification values) = [[3 4] [2 2] [1 1] ~]
      cycle will become (dec cycle) = 1
  • Pass 4
    • a will become +(a) = 5
      b will become (add a b) = 4 (pre-modification value of a) + 7 = 11
      output will add a cell of a and b (pre modification values) = [[4 7] [3 4] [2 2] [1 1] ~]
      cycle will become (dec cycle) = 0
  • Final Pass
    • With =(cycle 0) the list will be reversed (flop output) and will print as ~[[1 1] [2 2] [3 4] [4 7]]

Readings

Homework

  1. Comment each line of the Ackermann Function and submit with your comments.
    Your comments should focus on Hoon operations and program flow. It is not necessary to have nor to demonstrate understanding of the mathematics.
  2. Write a generator to produce the Euler primes, k2-k+n (for k = 1 to n-1).
    Note: your program will produce a set of primes if given one of "Euler's lucky numbers": 1, 2, 3, 5, 11, 17, or 41.
    You may assume that the user will give a valid sample.
    See here for more details