Lesson 6 – Measure (counter) and Cut Once

Introduction

We occasionally will want the operations of a generator to run more than once, or in some cases many times before producing a result.  This process of iterative use the same code repeatedly is known as “recursion.”  In this lesson and the next, we’re going to look at how recursion works in Hoon.

Generally, recursion works by (re)calling an arm from that same arm’s body. That is, we may say at the end of some arm, "run this arm again, but with changed starting conditions." In order to change the starting condition values when calling the arm again, we will use the rune %=,

  • We can use either standard tall form, or irregular syntax of %= when initiating recursion. Both of the following examples are using %= to call the arm $ with changes and are identical.
    • Notation 1:
      %=  $
      <face1>  <new value>
      <face2>  <new value 2>
      ==
    • Notation 2:
      $(<face1> <new value>, <face2> <new value>)
  • There must be some condition in the code that will cause the recursion loop to close/end, and finalize its calculations otherwise, we will have an infinite loop.
    • Note: If you create an infinite loop, use CTRL+C to interrupt.

Goal

Write a generator that take an @ud input, repeats some code the number of times indicated by the input, before exiting with a different operation, and printing the results. In this case, we'll write the word "measure" input times before writing the word "cut" once

Rune List


%= cen·tis

SyntaxSummary
%=  wing1   wing  hoon   wing  hoon        ...   wing  hoon ==Resolve a wing with changes. Here, we will look especially at cases where wing1 resolves to an arm. However, %= can also be used to resolve a leg of the subject with changes.
wing1(wing hoon, wing hoon, … wing hoon)

%=  is used to resolve a wing of the subject (an arm or a leg) with changes.

  • The first child is the wing to be resolved.  
  • The remaining children must be in pairs of a wing + some hoon to evaluate.

In the case of resolving a leg with changes, we produce a new a copy of the leg, with the specified changes.

Documentation on urbit.org

Exercise

Try this in dojo:

=wing [p=1 q=2]
wing
[p=1 q=2]
%=  wing
p  2
q  3
==
[p=2 q=3]
=wing

(note: the final line clears wing from your subject)

In the case of resolving an arm with changes, we make the specified changes to the arm and evaluate it.

Exercise

Try this in dojo:

=b 8
=a |=  a=@ud
(add a b)
(a 6)
14
(a(b 7) 6)
13

Note that a(b 7) is irregular form of %= a b 7 ==. That is to say, a(b 7) calls a with b modified to 7, and %= a b 7 == says "give me a, with b modified to 7" (the same thing).

Further note that if you want to call this gate, you'd need to do (%= a b 7 == 6) or %- %= a b 7 == 6 (both of which are also identical notation).


|- bar·hep

SyntaxSummary
|-  hoonProduce a trap (a core with one arm $) and evaluate it.

Produces a trap, a simple core like a gate, except not taking a sample.

|- is often used as a “recursion point” within another arm.  First, set up any counters/faces which will be updated during recursion, then create our |- trap.  This way, when we recurse back, we will not reset those counter values.

  • |- takes one child:
    • Some hoon expression to evaluate.
Documentation on urbit.org

Exercise

Try this in dojo:

=foo  =/  a  42
=/  b  0
|-
?:  =(a +(b))
  b
$(b +(b))
foo
41

$ buc

Recall that $ is the name of the one arm of a gate or trap. Recall also that “wing” means a part of “the subject” and that wings that are computational in nature are called arms. Therefore, we can use %= to resolve an arm with changes, by writing:

$(<face> <hoon>, <face2> <hoon2>, <face3> <hoon3>)
or
%= $
<face> <hoon>
<face2> <hoon2>
<face3> <hoon3>
==

This %= call allows us to perform recursion of a gate or trap’s arm with changed values for the faces we indicate.

weld

SyntaxSummary
(weld "a tape" "another tape")Standard Library function to weld together two tapes, or in other words combine two tapes into one.

Exercise

Try this in dojo:

(weld "and a-one" " and a-two")
"and a-one and a-two"


Required Concepts


Bunt value

A bunt value is a default value for a given type. These default values are arbitrary, and fairly easy to determine (e.g. for atoms the bunt is 0), but it is important to identify the bunt values of various types.


Exercise

Test this in dojo:

=a =@ud
a
ud=0
=a =tape
a
tape=""


Walkthrough


|=  counter=@ud
=|  output=tape
|-  ^-  tape
?:  (gth counter 0)
  %=  $
    output  (weld "measure " output)
    counter  (dec counter)
  ==
(weld output "cut")

  • |= counter=@ud
    |= creates a gate and requests one argument, an @ud

    • =| output=tape
      =| declares a tape with a face of “output” that is given the bunt value (an empty tape)

      • ^- tape
        ^- casts the product of this generator as a tape

        • |-
          |- creates a trap, this will be the point to which the generator recurses, if the generator requires recursion

          • ?: (gth counter 0)
            ?: creates a test with branching outcomes - if the test (is counter greater than zero) is true, the lines between %= and == will be performed, causing recursion - if the test is false, (weld output “cut”) will be performed and the generator will output. Note that we should use ?. here to put the recursion beneath the shorter code of the final line (line 9), but for demonstrative purposes, we've put it above to make it clear that that happens first, so long as counter != 0.

            • %=  $
                output  (weld "measure " output)
                counter  (dec counter)
              ==

              %= resolves a wing with changes - effectively what’s going on here is that your urbit is told to resolve $, which you will recall is the arm of the generator (and in actuality, now, the arm of barhep), but this time to do it with different starting parameters. That is, the first time this generator processes, output will be blank and counter will be the input @ud. When %= is called here, your urbit must rerun the whole generator (up to |-) with two changes: output will have “measure “ welded to it, and counter will be one less than it was previously

            • (weld output "cut")
              (weld output “cut”) appends “cut” to the end of the tape that is output

Flow

  1. Request an input and form a gate
    |=  counter=@ud
  2. Evaluate the arm, $, of the gate
  3. Declare a value with a face of “output” that is a tape, and give it a standardized value that is different for each type (called a “bunt value”) which in the case of a tape is simple an empty tape
    =|  output=tape
  4. Cast the output of the evaluation of $ as a tape. This also states clearly the endpoint of the evaluation, so it is also telling the gate to end when this is achieved.
    ^-  tape
  5. Form a trap, with one arm called $, that is evaluated immediately
    |-
  6. Set a branching test, and check whether (gth counter 0) the counter input is greater than 0, and branch based on the results
    ?:  (gth counter 0)
  7. If counter is greater than 0, restart this program from the trap (Step 5), with the following changes: weld “measure “ to the beginning of the output tape, decrement the counter by 1
    %=  $
      output  (weld "measure " output)
      counter  (dec counter)
    ==
  8. If the counter less than or equal to 0, terminate the program with one final change: weld “cut” to the end of the output tape
    (weld output "cut")

Reading

Homework

  1. Do Exercises 1.5(a) and (c) from the reading 1.5 Lists above, and check your answers against the solutions at the bottom of the page.
  2. Submit the provided solution after adding your own comments to explain each line.
  3. Write a generator that implements decrement without using the standard library functions of sub or dec (hint: count up to one less than the input value using recursion).