Recursion

This is an example of recursion, written to allow discussion of the different ways of supporting its evaluation. It uses a function, log2, which calculates the smallest integer power of two equal to or larger than the input value. All input and output definitions have been omitted.

Output = log2( Input );
log2( x ) = y
  where
    uint32  y;
    y = if ( x > 1 ) then  1 + log2( x / 2 )
                     else  0  fi;
  end;

When this program fragment is loaded for execution, the graph representing the log2 function will be expanded. A simple expansion scheme might fail, as the graph is recursive. When a recursive function is detected, additional expansion steps may be taken.

• A single instance of the graph is used for both the external task initially calling the recursive function and the internal task calling it.

• A dimension is added to the graph instance, and all streams declared within it, representing the recursion depth.

• The graph input and output streams are actually realized (instead of being replaced with the actual task parameters.)

• The internal (or recursive) function call is replaced by the graph output stream at the next position along the recursion dimension.

• A conditional statement is added, sourcing the graph input streams. It selects which task inputs are used for a given level of recursion.

• The task output streams select the graph output streams, at a position of zero along the recursion dimension.

When the above program fragment is expanded, it is transformed into the following program, where recursion has been replaced with an additional dimension.

dimension  d,r;
uint32  x.d,r;
uint32  y.d,r;

Output = y @.r 0;
x = Input fby.r (x / 2);
y = if ( x > 1 ) then  1 + next.r y  else  0  fi;