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