Fibonacci numbers (occam)

From LiteratePrograms

Other implementations: ALGOL 68 | Alice ML | bc | C | C Plus Plus templates | dc | E | Eiffel | Erlang | Forth | FORTRAN | Haskell | Hume | Icon | Java | JavaScript | Lisp | Logo | Lua | Mercury | OCaml | occam | Oz | Pascal | PIR | PostScript | Python | Ruby | Scala | Scheme | Sed | sh | sh, iterative | Smalltalk | T-SQL | Visual Basic .NET

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.

Contents 1 Function 2 Generator 3 Testing 3.1 Testing the fib function 3.2 Testing the generator 3.3 Compilation

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

Download code