Iteration

How iteration is done

The mechanism used to perform iteration described in the two papers on Full Metal Jacket is now obsolete, though it will make a limited comeback when we examine macros. Iteration is now performed in Full Metal Jacket by means of feedback. This, however, poses a problem: how do we get feedback in an acyclic graph?

The answer is that while the visible graphs are acyclic, the underlying graphs through which the data really flow are cyclic whenever iteration is used.

Iteration uses two special linked vertices called start+ and repeat+. The start+ vertex has an equal number of inputs and outputs. When a value is received on every input of start+, each value is output on the corresponding output. The repeat+ vertex has the same number of inputs as start+, each of which has the same type. An edge connected to an input on repeat+ really sends its values to the corresponding input on start+.

So repeat+ is just an extension of start+, and has no independent existence. Its inputs can be treated as the inputs of the start+ vertex to which it is linked.

Counting

count

start+ repeatedly outputs a value, starting with 0, to = and unless+. Unless 10 is less than or equal to the value, it is transcribed (see blue output), then incremented by add1, and then sent back to the input of start+, and another iteration begins.

zeroth iteration:

InputsVertexOutputs
0 start+ 0
10
0		 <= NIL
NIL
0		 unless+ 0
0 add1 1
1 repeat+

first iteration:

InputsVertexOutputs
1 start+ 1
10
1		 <= NIL
NIL
1		 unless+ 1
1 add1 2
2 repeat+

...

tenth iteration:

InputsVertexOutputs
10 start+ 10
10
10		 <= T
T
10		 unless+
add1
repeat+
count output

Reading a file and printing its contents

Similary, we can print the contents of a file. Files should really be obsolete: a modern operating system should have different types of objects and the ability to address them as if they were in main memory. Better still, there shouldn't be an operating system. Programming languages should run on the bare metal. But, for now, we're stuck with Unix.

openFile takes a file name and a mode, and outputs a channel from which the data in the file can be read. unless+ has three inputs and two outputs. Unless the end of file has been reached (tested by EOFp), the first value output is the second value input, a line of the file; and the second value output is the third value input, the channel through which the file's contents are read.

rubaiyat rubaiyat output

Newton's method

Next, we compose a function containing feedback, which implements Newton's method for calculating the square root of a number. This is done by first approximating the square root, and then repeatedly calculating better values until the differences are small:

    repeat
        a' ← (x / a + a) / 2
    until |a' - a| < 0.000001;
    return a'

where x is the number whose square root we want, a is the current approximation, and a' is the next approximation. The value of x remains the same in each iteration, so must be sticky.

The first input is the number we want the square root of, and the second is our initial approximation. We hard-coded the accuracy as 0.000001, but could, instead, have made it a third input.

newtonSqrt

First, √10.0 is calculated using the built-in function. Our implementation of Newton's method is correct to the accuracy chosen, even with 1.0 as the first approximation.

newtonSqrt call newtonSqrt output

Balancing inputs

It is important that the same number of values arrive at each input of a vertex in any computation. If they do not, a queue will build up, containing the excess values.

During a call,

  1. One value is transmitted from each ingate.
  2. One value is received on each outgate.
  3. If N values are received on each input of when+ and unless+, and A values are sent from each output of when+, then N-A values will be sent from each output of unless+.
  4. One value is received on each input of start+, N values are sent from each output, and N-1 values are received on each input of repeat+. (NB This is only what appears to happen. When executing, values are really sent directly to start+, bypassing repeat+.)
  5. All other vertices receive N values on each of their inputs, and send N values from their outputs.

The above rules can be applied statically, to verify that the same number of inputs is received on each input of a vertex. If this does not happen, it indicates a bug, even when the function being checked returns correct values.

Previous Up Next

© Copyright Donald Fisk 2015, 2016