# Fibonacci numbers (occam)

Other implementations: bc | C | C Plus Plus templates | dc | E | Erlang | FORTRAN | Haskell | Icon | Java | JavaScript | Lisp | Lua | occam | Oz | PIR | Prolog | Python | Sed | sh | sh, iterative | T-SQL | Visual Basic .NET

The Fibonacci numbers are the integer sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, ..., in which each item is formed by adding the previous two. The sequence can be defined recursively by

$F(n) = \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ F(n-1)+F(n-2) & n > 1 \\ \end{cases} .$

Fibonacci number programs that implement this definition directly are often used as introductory examples of recursion. However, many other algorithms for calculating (or making use of) Fibonacci numbers also exist.

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.

##  Function

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
:


##  Generator

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)
fibgenbody
:


The 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.

##  Testing

This simple test harness runs the various Fibonacci number implementations.

<<fibnum.occ>>=
fibfunc
FIB
fibgen
PROC fib.test (CHAN BYTE scr!)
CHAN FIB tell.fib:
CHAN INT from.fib:

fibgenprint

SEQ
out.string("Function:*n", 0, scr)
fibfunctest
out.string("*n*nGenerator:*n", 0, scr)
fibgentest
:


###  Testing the fib function

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 auxiliaryfib.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 ! ' '
:


###  Compilation

This occam Fibonacci number demonstration can be compiled using the Kent Retargetable occam Compiler:

kroc -lcourse -o fibnum fibnum.occ

hijacker
hijacker
hijacker
hijacker