Algol 68 Genie

warshall.a68

     
   1  CO
   2  
   3  @section Synopsis
   4  
   5  Warshall's algorithm for transitive closures.
   6  
   7  This code demonstrates a68g's small refinement preprocessor.
   8  At the University of Nijmegen a preprocessor much like this one was used
   9  as a front-end to FLACC in freshman programming courses in the 1980's.
  10  
  11  See: 
  12  
  13    C.H.A. Koster, H. Meijer.
  14    Systematisch programmeren in Algol 68, Deel I en II.
  15    Kluwer, Deventer [1978, 1981].
  16  
  17  CO
  18  
  19  # Suppose a compiler finds four procedures that call each other
  20    according below matrix.
  21    Entry calls[j, k] means procedure 'j' calls 'k' directly.
  22  #
  23  
  24  INT n = 4;
  25  
  26  MODE RELATION = [n, n] BOOL;
  27  
  28  RELATION calls = ((FALSE, TRUE, FALSE, FALSE),
  29                    (FALSE, FALSE, TRUE, FALSE),
  30                    (FALSE, FALSE, FALSE, TRUE),
  31                    (FALSE, FALSE, FALSE, FALSE)
  32                   );
  33  
  34  # Warshall's algorithm computes the transitive closure.
  35    Entry warshall[j, k] means that 'j' calls 'k', either
  36    directly or indirectly.
  37  # 
  38  
  39  PROC warshall = (RELATION direct) RELATION:
  40       (transitive closure);
  41  
  42  print relations.
  43  
  44  # The refinements follow below #
  45     
  46     transitive closure:
  47        RELATION indirect := direct;
  48        construct indirect;
  49        indirect.
  50     
  51        construct indirect:
  52           FOR m TO n
  53           DO FOR s TO n
  54              DO FOR t TO n
  55                 DO indirect[s, t] := indirect[s, t] OR (indirect[s, m] AND indirect[m, t])
  56                 OD
  57              OD
  58           OD.
  59  
  60     print relations:         
  61        printf ($"direct:"l$);
  62        printf (($n(n)(g)l$, calls));
  63        printf ($"indirect:"l$);
  64        printf (($n(n)(g)l$, warshall (calls))).