Dynamic Process Creation

Recursion in occam

Recursion in occam has traditionally been prevented for two main reasons — one practical and one engineered. Firstly, the lack of dynamic memory allocation would have imposed a restriction on the depth of recursion. Secondly, the scoping of names in occam is such that they only become visible at the end of their declaration (where the ‘:’ appears). For PROCs, this means that any use of its own name inside the code body is invalid, unless a different PROC of the same name is in scope — in which case it will be used. It is possible to fake recursion however, often quite convincingly, by using the scoping of names to an advantage [Poo92]. In an arbitrary PROC called ‘foo’, any previously defined PROCs also called ‘foo’ are in scope and perfectly valid. This technique will fail on some KRoC implementations however — when the same name is defined at the outermost level multiple times, the UNIX linker will mostly likely stop with a “multiply defined symbol” error. The tranx86 translator partially handles this by only allowing one entry-point

for any given name per file processed. However, the same top-level PROC name in separate source files will also usually result in a similar error on UNIX platforms — which is a problem generally, not just for recursion. A version of unbounded recursion using a special locally defined PROC — with a very similar name — has been implemented in a development version of the KRoC/Sparc by Wood in [Woo00]. The Linux version of KRoC implements recursion using a different mechanism, by adding support directly to the occam compiler. The support for recursion in KRoC/Sparc also uses a Brinch-Hansen style memory allocator, but with with all support for such in the translator (octran) and run-time kernel only. For this implementation, recursive PROCs are declared using the ‘RECURSIVE’ or

‘REC’ keywords

— the latter being shorthand for the former. For example:

RECURSIVE PROC thing (...)
.
.. body of thing
:
This has the effect of bringing the name ‘thing’ into scope early, thereby permitting its use within the body of ‘thing’. A classic example for parallel recursion in occam is the parallel recursive Sieve of Eratosthenes. The original code for this is given in Appendix A of Moores’s CCSP paper, [Moo99], and requires very little change — just the addition of the ‘RECURSIVE’ keyword. The newcode for the ‘sieve’ process, augmented with channel-direction specifiers, is:

RECURSIVE PROC sieve (VAL INT count, CHAN INT in?, out!)
IF
count = 0
id (in?, out!) -- just copy in to out
TRUE
INT n:
SEQ
in ? n
out ! n
CHAN INT c:
PAR
filter (n, in?, c!)
sieve (count-1, c?, out!)
:

The ‘count’ parameter is used to limit the recursion. An initial value of 169 will allow for all the primes between 2 and 1000000 to be generated. When the ‘sieve’ process receives its first input (from ‘in?’), it outputs it down the prime output channel ‘out!’, then starts a network of subprocesses: a filter to filter out all multiples of ‘n’, in parallel with a recursive call to sieve. When ‘count’ reaches zero, the recursion stops. Some time after new filter processes stop being created, the pipeline will start to produce invalid primes