util/int/test/awa.p

   1 { $Id: awa.p,v 1.2 1994/06/24 10:50:41 ceriel Exp $ }
   2
   3 program ArrayWithoutArray(input, output);
   4 {       We simulate a (read-only) array by constructing a mapping
   5         function   map(n)   which yields the n-th element.
   6         We demonstrate its existence by first printing the length
   7         of the array and then its contents.
   8         This technique was first introduced by F.E.J. Kruseman-Aretz,
   9         in the early sixties.
  10 }
  11
  12 procedure Action(n: integer; function map(n: integer): integer);
  13         {       Action is called when the construction of the virtual
  14                 array is finished.  Actually, all elements now reside
  15                 on the stack.
  16                 n:      the length of the array,
  17                 map:    the mapping function.
  18         }
  19         var i: integer;
  20         begin   { show that the whole array is still there }
  21                 writeln('#elems:', n);
  22                 write('elems:');
  23                 for i:= 1 to n do
  24                         write(map(i))
  25         end {Action};
  26
  27 procedure Construct(n: integer; function oldmap(n: integer): integer);
  28         {       For each value read, Construct will store that value and
  29                 declare a new map function, composed of the old one
  30                 augmented by the new value.
  31                 It then calls itself recursively for the next value.
  32
  33                 n:      element number on this level
  34                 oldmap: map for 1 .. n-1
  35         }
  36         var x: integer;         { the value stored at level n }
  37
  38         function newmap(i: integer): integer;
  39                 { yields elements stored so far }
  40                 begin
  41                         if      { the i-th element is kept on this level}
  42                                 i = n
  43                         then    { yield it }
  44                                 newmap := x
  45                         else    { try lower down the road }
  46                                 newmap := oldmap(i)
  47                 end {newmap};
  48
  49         begin
  50                 read(x);
  51                 if      { it is a valid value }
  52                         x >= 0
  53                 then    { we continue reading values and constructing maps }
  54                         Construct(n + 1, newmap)
  55                 else    { we stop reading and pass the info on to Action }
  56                         Action(n - 1, newmap)
  57         end {Construct};
  58
  59 function EmptyMap(n: integer): integer;
  60         begin
  61                 writeln('Illegal index', n, '; 0 yielded.');
  62                 EmptyMap := 0
  63         end {EmptyMap};
  64
  65 begin
  66         Construct(1, EmptyMap)
  67 end.