4. Iteration

1. Introduction

In this section, I will talk about iterators, which are used for repetition in Sather.

2. Syntax for looping

Loops start at loop and end at end; Loops contain at least one iterator. Iterator names end with !.

The loop terminates when a iterator indicate the break.

loop
    (something)
    iterator
    (something)
end;

You can put iterators anyplace in the loop.
In the following example,

The while! iterator is located at the first line of the loop in the top_while.
It is at the end of the loop in the bottom_while.
It is in the middle in the middle_while.

01:     -- primitive counting prime numbers program
02:     
03:     class MAIN is
04:     
05:        top_while(n:INT) is
06:           i:INT := 0;
07:           #OUT + "Top while test:\n";
08:           loop
09:     	 while!(i < n);
10:     	 #OUT + "repeat: " + i + "\n";
11:     	 i := i+1;
12:           end;
13:           #OUT + "\n";
14:        end;
15:     
16:        bottom_while(n:INT) is
17:           i:INT := 0;
18:           #OUT + "Bottom while test:\n";
19:           loop
20:     	 #OUT + "repeat: " + i + "\n";
21:     	 i := i+1;
22:     	 while!(i < n);
23:           end;
24:           #OUT + "\n";
25:        end;
26:     
27:        middle_while(n:INT) is
28:           i:INT := 0;
29:           #OUT + "Middle while test:\n";
30:           loop
31:     	 #OUT + "before while: " + i + "\n";
32:     	 while!(i < n);
33:     	 #OUT + "after while: " + i + "\n";
34:     	 i := i+1;
35:           end;
36:           #OUT + "\n";
37:        end;
38:     
39:     
40:     
41:        
42:        main(av:ARRAY{STR}) is
43:           if av.size = 2 then
44:     	 n:INT := av[1].cursor.get_int;
45:     	 top_while(n);
46:     	 bottom_while(n);
47:     	 middle_while(n);
48:           else
49:     	 #ERR + "Usage: while N\n"
50:           end;
51:        end;
52:     end;

$ ./while 5
Top while test:
repeat: 0
repeat: 1
repeat: 2
repeat: 3
repeat: 4

Bottom while test:
repeat: 0
repeat: 1
repeat: 2
repeat: 3
repeat: 4

Middle while test:
before while: 0
after while: 0
before while: 1
after while: 1
before while: 2
after while: 2
before while: 3
after while: 3
before while: 4
after while: 4
before while: 5

Iterator while! repeats the loop while the argument is true, which is similar to other languages. On the other hand, until! exit from the loop when the argument is true. Iterator bleak! is to exit from the loop unconditionally.

01:     -- primitive counting prime numbers program
02:     
03:     class MAIN is
04:     
05:        until_test(n:INT) is
06:           i:INT:=0;
07:           loop
08:     	 #OUT + i + "\n";
09:     	 if i= n then break!; end;
10:     	 until!(i = 1000);
11:     	 i := i+1;
12:           end;
13:        end;
14:        
15:        main(av:ARRAY{STR}) is
16:           if av.size = 2 then
17:     	 n:INT := av[1].cursor.get_int;
18:     	 until_test(n);
19:           else
20:     	 #ERR + "Usage: until_break N\n"
21:           end;
22:        end;
23:     end;

3.Iterators defined in the INT class

The INT class has iterators, which are useful to simplify the programs. Following shows a simple program which uses the INT iterators and the output. See http://www.icsi.berkeley.edu/~sather/Documentation/Library/LibraryBrowser/short-INT.html for detailed information.

int_iter.sa

01:     -- iterators of INT class
02:     -- 
03:     -- downto!(once i:SAME):SAME
04:     -- **** 	Yield successive integers from self down to `i' inclusive.
05:     -- for!(once i:SAME):SAME
06:     -- **** 	Yields `i' successive integers starting with self.
07:     -- product!(i:SAME):SAME
08:     -- **** 	Yields the product of all previous values of `i'.
09:     -- step!(once num,once step:SAME):SAME
10:     -- **** 	Yield `num' integers starting with self and stepping by `step'.
11:     -- stepto!(once to,once by:SAME): SAME
12:     -- **** 	Yield succeeding integers from self to `to' by step `by'. Might quit immediately if self is already `beyond'.
13:     -- sum!(i:SAME):SAME
14:     -- **** 	Yields the sum of all previous values of `i'.
15:     -- times!
16:     -- **** 	Yields self times without returning anything.
17:     -- times!:SAME
18:     -- **** 	Yield successive integers from 0 up to self-1.
19:     -- up!:SAME
20:     -- **** 	Yield successive integers from self up.
21:     -- upto!(once i:SAME):SAME
22:     ----------------
23:     
24:     class MAIN is
25:     
26:        test_downto(start, last:INT)
27:           pre start >= last
28:        is
29:           #OUT + "Test for " + start + ".downto!(" + last + "): "; 
30:           loop
31:     	 #OUT + start.downto!(last) + " ";
32:           end;
33:           #OUT + "\n";
34:        end;
35:     
36:        test_for(start, last :INT)
37:           pre start <= last
38:        is
39:           #OUT + "Test for " + start + ".for!(" + last + "): ";
40:           loop
41:     	 #OUT + start.for!(last) + " "; 
42:           end;
43:           #OUT + "\n";
44:        end;
45:     
46:        test_step(start, last, step :INT) is
47:           #OUT + "Test for " + start + ".step!(" + last + ", " + step + "): ";
48:           loop
49:     	 #OUT + start.step!(last, step) + " "; 
50:           end;
51:           #OUT + "\n";
52:        end;
53:     
54:        test_stepto(start, last, step :INT) is
55:           #OUT + "Test for " + start + ".stepto!(" + last + ", " + step + "): ";
56:           loop
57:     	 #OUT + start.stepto!(last, step) + " "; 
58:           end;
59:           #OUT + "\n";
60:        end;
61:     
62:        test_times0(n:INT) 
63:           pre n>=0
64:        is
65:           #OUT + "Test for " + n + ".times!: ";
66:           loop
67:     	 n.times!;
68:     	 #OUT +  "Hey! "; 
69:           end;
70:           #OUT + "\n";
71:        end;
72:     
73:        test_times1(n:INT) 
74:           pre n>=0
75:        is
76:           i:INT;
77:           #OUT + "Test for " + n + ".times! returning INT: ";
78:           loop
79:     	 i := n.times!;
80:     	 #OUT +  "Hey!(" + i + ") "; 
81:           end;
82:           #OUT + "\n";
83:        end;
84:     
85:        test_up(n:INT)
86:           pre n >= 0
87:        is
88:           i:INT;
89:           #OUT + "Test for " + n + ".up!: ";
90:           loop
91:     	 i := n.up!;
92:     	 #OUT + i  + " ";
93:     	 if i = n+ 9 then #OUT + "break\n"; break!; end;
94:           end;
95:        end;
96:     
97:        test_upto(start, last :INT) is
98:           #OUT + "Test for " + start + ".upto!(" + last +  "): ";
99:           loop
100:     	 #OUT + start.upto!(last) + " "; 
101:           end;
102:           #OUT + "\n";
103:        end;
104:      
105:        test_product(m,n:INT)
106:           pre n >= m
107:        is
108:           p:INT;
109:           #OUT + "Test for product!: " + m + " * ... * " + n + " = ";
110:           loop
111:     	 p := INT::product!(m.upto!(n));
112:           end;
113:           #OUT + p + "\n";
114:        end;
115:     
116:        test_sum(m,n:INT)
117:           pre n >= m
118:        is
119:           p:INT;
120:           #OUT + "Test for sum!: " + m + " + ... + " + n + " = ";
121:           loop
122:     	 p := INT::sum!(m.upto!(n));
123:           end;
124:           #OUT + p + "\n";
125:        end;
126:        
127:        main(av:ARRAY{STR}) is
128:           if av.size = 4 then
129:     	 a:ARRAY{INT} :=#(3);
130:     	 i:INT;
131:     	 loop
132:     	    i:= 3.times!;
133:     	    a[i]:= av[i+1].cursor.get_int;
134:     	 end;
135:     	 test_times0(a[1]);
136:     	 test_times1(a[1]);
137:     	 test_up(a[0]);
138:     	 test_upto(a[0],a[1]);
139:     	 test_downto(a[1], a[0]);
140:     	 test_for(a[0], a[1]);
141:     	 test_step(a[0], a[1], a[2]);
142:     	 test_stepto(a[0], a[1], a[2]);
143:     	 test_sum(a[0], a[1]);
144:     	 test_product(a[0], a[1]);
145:     
146:           else
147:     	 #ERR + "Usage: int_iter MIN MAX STEP\n"
148:           end;
149:        end;
150:     end;

$ sacomp -chk int_iter.sa -o int_iter
$ ./int_iter 1 6 2
Test for 6.times!: Hey! Hey! Hey! Hey! Hey! Hey! 
Test for 6.times! returning INT: Hey!(0) Hey!(1) Hey!(2) Hey!(3) Hey!(4) Hey!(5) 
Test for 1.up!: 1 2 3 4 5 6 7 8 9 10 break
Test for 1.upto!(6): 1 2 3 4 5 6 
Test for 6.downto!(1): 6 5 4 3 2 1 
Test for 1.for!(6): 1 2 3 4 5 6 
Test for 1.step!(6, 2): 1 3 5 7 9 11 
Test for 1.stepto!(6, 2): 1 3 5 
Test for sum!: 1 + ... + 6 = 21
Test for product!: 1 * ... * 6 = 720

4. Iterators defined in the ARRAY class

The ARRAY type has several iterators such as ind!, elt! and set!. Following code (array_iter.sa) shows a simple example.

See http://www.icsi.berkeley.edu/~sather/Documentation/Library/LibraryBrowser/short-ARRAY%7B_%7D.html for detailed information.

array_iter.sa

01:     -- example of iterators in the ARRAY class
02:     
03:     class MAIN is
04:     
05:        const a1:ARRAY{INT}:=|1,2,3,4,5|;
06:        const a2:ARRAY{INT}:=|7,11,13,17,19|;
07:     
08:        show_array(a:ARRAY{INT}, name:STR) is
09:           i,j:INT;
10:           loop
11:     	 i:=a.ind!;
12:     	 j:=a.elt!;
13:     	 #OUT + name + "[" + i + "] = " + j + ", ";
14:           end;
15:           #OUT + "\n";
16:        end;
17:     
18:        ipro(a1,a2:ARRAY{INT}):INT 
19:           pre a1.size = a2.size
20:        is
21:           p:INT;
22:           loop
23:     	 p := INT::sum!(a1.elt! * a2.elt!);
24:           end;
25:           return p;
26:        end;
27:     
28:        add_arr(a1, a2:ARRAY{INT}):ARRAY{INT} 
29:           pre a1.size = a2.size
30:        is
31:           ar :ARRAY{INT} := #(a1.size);
32:           loop
33:     	 ar.set!(a1.elt! + a2.elt!);
34:           end;
35:           return ar;
36:        end;
37:     
38:        main is
39:           #OUT + "a1 = " + a1 + "\n" + "a2 = " + a2 + "\n\n";
40:           show_array(a1, "a1");
41:           show_array(a2, "a2");
42:           #OUT + "a1 + a2 = " + add_arr(a1, a2) + "\n";
43:           #OUT + "inner product of a1 and a2 = " + ipro(a1, a2) + "\n";
44:        end;
45:     end;

takafumi@suse:~/doc/monthly/06-05/sather> sacomp -chk array_iter.sa -o array_iter
takafumi@suse:~/doc/monthly/06-05/sather> ./array_iter
a1 = {1,2,3,4,5}
a2 = {7,11,13,17,19}

a1[0] = 1, a1[1] = 2, a1[2] = 3, a1[3] = 4, a1[4] = 5, 
a2[0] = 7, a2[1] = 11, a2[2] = 13, a2[3] = 17, a2[4] = 19, 
a1 + a2 = {8,13,16,21,24}
inner product of a1 and a2 = 231

5. Iterators defined in the STR class

Following shows a simple example and its output. See http://www.icsi.berkeley.edu/~sather/Documentation/Library/LibraryBrowser/short-STR.html for detailed information.

str_iter.sa

01:     -- iterators of STR class
02:     -- 
03:     -- chunk!(chunk_size: INT): STR
04:     -- **** 	Yield successive chunks of self, defined by the chunk size "size"
05:     -- elt!(once beg:INT):CHAR
06:     -- **** 	Yield the characters of self in order starting at `beg'. Self may be void. Modified (ben)
07:     -- elt!(once beg,once num:INT):CHAR
08:     -- **** 	Yield 'num' characters of self in order starting at `beg'. Self may be void. Modified (ben)
09:     -- elt!:CHAR
10:     -- **** 	Yield the characters of self in order. Self may be void. Modified (ben)
11:     -- ind!:INT
12:     -- **** 	Yield the induces of the characters of self in order. Self may be void. Modified (ben)
13:     -- separate!(s:$STR):STR
14:     -- **** 	On the first iteration just outputs `s', on successive iterations it outputs self followed by `s'. Useful for forming lists,
15:     -- ____loop_#OUT_+_",_".separate!(a.elt!)_end;
16:     -- split!(once c: CHAR): STR
17:     -- **** 	Yield successive substrings that are separated by the character "c"
18:     ----------------------------------------------------------------------------------------
19:     
20:     
21:     class MAIN is
22:     
23:        test_chunk is
24:           s:STR := "abcdefghijklmnopqrstuvwxyz@";
25:           s1:STR;
26:           loop
27:     	 s1 := s1 + s.chunk!(3) + " ";
28:           end;
29:           #OUT + "Test of (" + s + ").chunk!(3): " + s1 + "\n";
30:        end;
31:     
32:        test_split is
33:           s:STR:= "192.168.1.1";
34:           #OUT + "Test of (" + s + ").split('.'): ";
35:           loop
36:     	 #OUT +  (s+".").split!('.') + "   ";  -- add "." at the end
37:           end;
38:           #OUT + "\n";
39:     
40:        end;
41:     
42:        test_separate is
43:           a:ARRAY{INT}:=|1,2,3,4,5,6,7|;
44:           #OUT + "Test of \"     \".separate(" + a + ".elt!): ";
45:            loop
46:     	  #OUT + "     ".separate!(a.elt!);
47:           end;
48:            #OUT  + "\n";
49:        end;
50:        
51:        main is
52:           test_chunk;
53:           test_split;
54:           test_separate;
55:        end;
56:     end;

takafumi@suse:~/doc/monthly/06-05/sather> sacomp str_iter.sa -o str_iter
takafumi@suse:~/doc/monthly/06-05/sather> ./str_iter
Test of (abcdefghijklmnopqrstuvwxyz@).chunk!(3): abc def ghi jkl mno pqr stu vwx yz@ 
Test of (192.168.1.1).split('.'): 192.   168.   1.   1.   
Test of "     ".separate({1,2,3,4,5,6,7}.elt!): 1     2     3     4     5     6     7

6. User defined iterators

You can define your own iterators easily.

It is completely the same as typical function definition except the iterator name ends with '!'. The arguments qualified by once are evaluated once when the iterator is called first. The iterator returns a value when it meets yield with stopping the operation. The operation starts again when the iterator is called next time.

Following code defines a iterator that produces geometric sequences (geo!(once a0, once r:FLTD):FLTD).

01:     -- iterator for geometrical progressions
02:     
03:     class MAIN is
04:     
05:        geo!(once a0, once r:FLTD):FLTD is
06:           a:FLTD:=a0;
07:           loop
08:     	 yield a;
09:     	 a := a * r;
10:           end;
11:        end;
12:        
13:        main is
14:           g1, g2 : FLTD;
15:           #OUT + "User defined iterator: geo!(a0, r, FLTD)\n";
16:           loop
17:     	 10.times!;
18:     	 g1 := geo!(1.0d, 2.0d);
19:     	 g2 := geo!(1.0d, 0.5d);
20:     	 #OUT + g1 + " * " + g2 + " = " + (g1*g2) + "\n";
21:           end;
22:        end;
23:     end;

takafumi@suse:~/doc/monthly/06-05/sather> sacomp geo.sa -o geo
takafumi@suse:~/doc/monthly/06-05/sather> ./geo
User defined iterator: geo!(a0, r, FLTD)
1 * 1 = 1
2 * 0.5 = 1
4 * 0.25 = 1
8 * 0.125 = 1
16 * 0.0625 = 1
32 * 0.03125 = 1
64 * 0.015625 = 1
128 * 0.0078125 = 1
256 * 0.00390625 = 1
512 * 0.00195312 = 1

You can exit from the loop explicitly using quit. The quit is effective only in the loop. The while!, for instance, can be defined like as follows.

   my_while!(predicate :BOOL) is
      loop
	 if predicate then yield;
	 else quit; 
	 end;
      end;
   end;

6. Summary

I have explained about the iterators briefly using simple examples. I will explain how to define classes in the next section.