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