Fibonacci numbers (occam)
There are several different ways to approach Fibonacci number generation in occam. We'll start with the simplest, and then take a look at a less straightforward (but potentially more efficient) solution.
One way to compute the Fibonacci numbers is to simply use a
FUNCTION that finds the nth by computing all of the Fibonacci numbers up to n each time it is called. Since occam doesn't support recursion, the sequence of numbers must be computed iteratively (although occam's multiple-assignment capabilities make this easier than it might otherwise have been).
<<fibfunc>>= INT FUNCTION fib (VAL INT n) INT fib.num, next.fib.num: VALOF SEQ fib.num, next.fib.num := 0, 1 SEQ i = 0 FOR n fib.num, next.fib.num := next.fib.num, (fib.num + next.fib.num) RESULT fib.num :
An alternative approach to finding the Fibonacci numbers is to compute them in a lazy fashion, using a generator process. This approach works best when the Fibonacci numbers are required to be provided in sequence, but not necessarily needed all at the same time.
The generator process takes as arguments two channels, one for receiving commands, and one for output of a new number.
<<fibgen>>= PROC fib.gen (CHAN FIB in, CHAN INT out) :
FIB protocol used by the generator's command channel,
in, allows a process to request that a new Fibonacci number be output, and to terminate or reset the generator:
<<FIB>>= PROTOCOL FIB CASE quit reset give.num :
Internally, the generator process stores the current Fibonacci number and the next number in the sequence. These are initialized to 0 and 1 respectively whenever the generator is reset.
<<fibgenbody>>= INT fib.num, next.fib.num: PROC init () fib.num, next.fib.num := 0, 1 :
The actual operation of the generator is purely sequential. It begins by initializing the current and next Fibonacci numbers, and then enters a loop in which it awaits commands. The loop terminates if the
quit message is received. The
reset message causes the generator to reinitialize its stored Fibonacci numbers. The
give.num message causes the generator to output the current Fibonacci number, and compute the next number in the sequence.
<<fibgenbody>>= SEQ init() INITIAL BOOL done IS FALSE: WHILE NOT done in ? CASE quit done := TRUE reset init() give.num SEQ out ! fib.num fib.num, next.fib.num := next.fib.num, (fib.num + next.fib.num)
Several additional features could be added to this simple implementation. One useful addition would be to store every computed number in an internal array. This memoization would eliminate the need to do any recomputation after a reset of the generator. Another possibility, which would work best in combination with memoization, is to provide a command that would allow a consumer to request a specific Fibonacci number.
This simple test harness runs the various Fibonacci number implementations.
<<fibnum.occ>>= PROC fib.test (CHAN BYTE scr!) CHAN FIB tell.fib: CHAN INT from.fib: SEQ out.string("Function:*n", 0, scr) out.string("*n*nGenerator:*n", 0, scr) :
 Testing the
The Fibonacci function is run iteratively, and the results for each value of n are printed to the screen.
<<fibfunctest>>= SEQ n = 0 FOR 40 SEQ out.int(fib(n), 0, scr) scr ! ' '
 Testing the generator
The Fibonacci generator process is placed in parallel with an anonymous sequential process. This sequential process prints the first 40 Fibonacci numbers, resets the generator, and then again prints the first 40 Fibonacci numbers.
<<fibgentest>>= PAR fib.gen(tell.fib, from.fib) SEQ fib.gen.print(40) scr ! '*n' tell.fib ! reset fib.gen.print(40) scr ! '*n' tell.fib ! quit
The actual interaction with the generator is carried out by the auxiliary
fib.gen.print procedure, which iteratively requests a new Fibonacci number, receives the requested number, and prints it to the screen.
<<fibgenprint>>= PROC fib.gen.print (VAL INT max.fib.num) INT fib.num: SEQ n = 0 FOR max.fib.num SEQ tell.fib ! give.num from.fib ? fib.num out.int(fib.num, 0, scr) scr ! ' ' :
This occam Fibonacci number demonstration can be compiled using the Kent Retargetable occam Compiler:
kroc -lcourse -o fibnum fibnum.occ