10.6 An Extended Example--Fibonacci Sequences

No attempt will be made here to illustrate all the visibility details discussed so far in this chapter in practical examples. However, the principle that information can be kept hidden from portions of the program that do not need it is important, for code that cannot see some entities that it should not, can also not modify those entities, resulting in safer and easier-to-debug code. The next example illustrates the use of a module (local to the program module) to generate the next number in a special sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... known as the Fibonacci Sequence.

The Fibonacci Sequence is defined by
F1 = 0, F2= 1 and Fi+1 = Fi-1 + Fi
thereafter.

That is, after the first two numbers, all subsequent ones in the sequence are generated by adding the previous two. In the Modula-2 solution that follows, FibGen has a body that initializes the sequence, and local variables to maintain the (current) ultimate and penultimate values in the sequence. All of this is invisible to the surrounding program module, which is interested only in the exported procedure NextFib, and not any other details involved.

If the module were declared within a procedure, by the way, that initialization body would execute whenever the procedure were entered. After all, the module would exist only inside the procedure, according to the scope rules for procedures. This way, the initialization takes place once.

MODULE Fibonacci;

(* by R. Sutcliffe
   To demonstrate hiding in local modules
   revised 1994 04 11 *)
 
(* This module generates and prints the first twenty numbers in the Fibonacci sequence. *)

FROM STextIO IMPORT
  WriteString, WriteLn;
FROM SWholeIO IMPORT
  WriteCard;
  
PROCEDURE OutputVal (index, num : CARDINAL);
BEGIN
  WriteCard (index, 2);
  WriteString (" )  ");
  WriteCard (num, 5);
  WriteLn;
END OutputVal;
(*-------------------------------------*)

MODULE FibGen;
EXPORT NextFib;
VAR
  ult, penult, temp: CARDINAL; (* hidden *)
PROCEDURE NextFib ( ) : CARDINAL;
BEGIN
  temp := ult;
  ult := ult + penult;
  penult := temp;
  RETURN ult;
END NextFib;

(* The module body initializes the two local variables before being used *)
BEGIN
  ult := 0;
  penult := 1;
END FibGen;

(*-------------------------------------*)

(* Main Program Starts *)
VAR
  fib, count : CARDINAL;
BEGIN
  WriteString(" The first 20 Fibonacci Numbers are: ");
  WriteLn;
  OutputVal (1, 0);
  (* the first Fib num is written out before one starts calcs *)
  FOR count := 2 TO 20
    DO  (* Then, the rest *)
      fib := NextFib( );
      OutputVal (count, fib);
    END;
  WriteString ("There you have it ");
END Fibonacci.

The output from this program was:

 The first 20 Fibonacci Numbers are: 
 1 )      0
 2 )      1
 3 )      1
 4 )      2
 5 )      3
 6 )      5
 7 )      8
 8 )     13
 9 )     21
10 )     34
11 )     55
12 )     89
13 )    144
14 )    233
15 )    377
16 )    610
17 )    987
18 )   1597
19 )   2584
20 )   4181
There you have it 

Notice how one keeps the entities being manipulated hidden from the surrounding scope and update them only through an exported procedure. One uses the fact that ult and penult are global to FibGen to maintain their values between calls to the procedure NextFib. However, these two variables are not visible in the outer scope and so the main program cannot change them except by calling NextFib.


Contents