TEACH STREAMS Aaron Sloman Dec 2000 It is often useful to write programs that deal with a potentially unlimited sequence of items generated on demand or obtained from source outside the computer. ;;; Some stream manipulators in Pop-11 ;;; First a stream creator for testing the manipulators. define make_counter() -> newcounter; ;;; Create a counter which is a procedure that first returns ;;; 1 then 2 then, ... It is a lexical closure using count ;;; as local memory. lvars count = 1; define counter() -> next; ;;; Return the number and then increment it for next time count -> next; count+1 -> count; enddefine; ;;; return the closure counter -> newcounter; enddefine; ;;; Another one define make_word_gensym(word) -> generator; ;;; given a word, e.g. "e" return a generator which produces ;;; "e1" "e2" "e3" "e4" "e5" lvars counter = 1; define genword() -> newword; ;;; create new word using root word and counter consword(word >< counter) -> newword; ;;; increment counter counter + 1 -> counter; enddefine; ;;; return the closure genword -> generator; enddefine; /* tests ;;; make four generators, two for numbers two for words vars c1 = make_counter(), c2 = make_counter(), w1 = make_word_gensym("a"), w2 = make_word_gensym("b"); ;;; now test the generators c1(), c1(), c1() => ** 1 2 3 c2(), c2(), c2(), c2() => ** 1 2 3 4 c1(), c1(), c1() => ** 4 5 6 w1(), w1(), w1() => ** a1 a2 a3 w2(), w2(), w2(), w2() => ** b1 b2 b3 b4 w1(), w1(), w1() => ** a4 a5 a6 */ define combine_streams(stream1, stream2) -> newstream; ;;; Combine two streams into a new stream of pairs, giving all ;;; possible combinations of items from stream1 and stream2 ;;; If stream1 produces 1, 2, 3, 4, etc, and ;;; stream2 produces a, b, c, d, then the new stream ;;; produces pairs ;;; 1,a, ;;; 2,a, 2,b ;;; 3,a, 3,b, 3,c, ;;; 4,a, .... etc ;;; like the standard way of ordering all the rationals. lvars ;;; next value from each stream laststream1 = stream1(), laststream2 = stream2(), ;;; memory of values from stream2 all_last_2 = [^laststream2], ;;; pointer to last link in memory, used to update memory last_last_2 = all_last_2, ;;; pointer to unused tail of memory, used to go through all of ;;; remembered values for each value from stream1. ;;; The memory is extended each time this gets to [] next_last_2 = all_last_2; ;;; The combiner procedure. Closures of this will be the ;;; combined stream define combined() -> next; ;;; get the values of the generators and make a pair, ;;; assigned to next if next_last_2 == [] then ;;; used all of stream2's values so far with current value from ;;; stream1, so get next from stream1, and extend the stream2 memory ;;; and prepare to iterate over it. ;;; next values from both streams stream1() -> laststream1; stream2() -> laststream2; ;;; Extend memory of stream2 by appending one more element ;;; and make last_last_2 point to last link of extended memory back(last_last_2 nc_<> [^laststream2]) -> last_last_2; ;;; less efficient version would not use last_last_2, and ;;; just do this: ;;; all_last_2 nc_<> [^laststream2] -> all_last_2 ;;; re-start pointer to the beginning of stream 2 memory all_last_2 -> next_last_2; endif; ;;; return current values conspair(laststream1, front(next_last_2)) -> next; ;;; Prepare for next time: ;;; still iterating over stream 2 memory back(next_last_2) -> next_last_2; enddefine; ;;; return the generator combined -> newstream; enddefine; /* tests vars stream = combine_streams( make_counter(), make_counter() ); stream()=> ** [1|1] stream()=> ** [2|1] stream()=> ** [2|2] stream()=> ** [3|1] stream()=> ** [3|2] stream()=> ** [3|3] stream()=> ** [4|1] stream()=> ** [4|2] etc.... ;;; now a stream of numbers combined with a stream of words vars stream2 = combine_streams( make_counter(), make_word_gensym("e") ); stream2()=> ** [1|e1] stream2()=> ** [2|e1] stream2()=> ** [2|e2] stream2()=> ** [3|e1] stream2()=> ** [3|e2] repeat 10 times stream2() endrepeat => ** [3|e3] [4|e1] [4|e2] [4|e3] [4|e4] [5|e1] [5|e2] [5|e3] [5|e4] [5|e5] */ define filter(stream, pred) -> newstream; ;;; make a new stream which is the substream of stream containing ;;; only items that satisfy pred define filtered() -> next; ;;; return next item from generator that satisfies pred lvars next = stream(); until pred(next) do stream() -> next; enduntil enddefine; filtered -> newstream; enddefine; /* tests define isevensum(pair) -> boole; ;;; does a pair contain two numbers than sum to an even number (front(pair) + back(pair)) mod 2 == 0 -> boole; enddefine; ;;; create a filtered combination of two streams of integers. vars evens = filter( combine_streams( make_counter(), make_counter() ), isevensum); ;;; test the combined stream evens()=> ** [1|1] evens()=> ** [2|2] evens()=> ** [3|1] evens()=> ** [3|3] repeat 10 times evens(), endrepeat => ** [4|2] [4|4] [5|1] [5|3] [5|5] [6|2] [6|4] [6|6] [7|1] [7|3] */ /* INDEX of procedures define make_counter() -> newcounter; define make_word_gensym(word) -> generator; define combine_streams(stream1, stream2) -> newstream; define filter(stream, pred) -> newstream; define isevensum(pair) -> boole; */ --- \$poplocal/local/teach/streams --- Copyright University of Birmingham 2000. All rights reserved. ------