This assignment is very tough and possibly addictive. The objective is to show that an input/output structure common to modern languages is hard to implement in older languages. When we use traditional languages, our minds are often completely shut out off to the possibility of solutions that are natural in other languages that we will consider later in the course.

The input/output structure we are concerned with is streams. Think of a stream as a sequence of tokens (strings, integers, etc.) except that they are not generated by a "producer" procedure until demanded by a "consumer" procedure. To illustrate the importance of streams we use an example from the DOS world. What happens on a DOS machine (version 5.0) when you issue a command such as type file.txt | more? The output from the type command is generated and stored somewhere. Then the more command is executed on the stored data. What's wrong with this? If file.txt has more than 65,000 characters, it barfs. The reason is DOS cannot create a file that large to store the data for more to work with. Now suppose we view the more command as a consumer of tokens and the type command as a producer of tokens. Then the more command goes into action first and requests the next token from type. Then type produces the next token, more grabs it, and outputs it to the screen. The cycle repeats until type has no more tokens to produce.

In this homework you will attempt to build a general stream manipulation utility in C or C++, your choice. Please feel free to do this as you please but here are some C hints that will work.

1. Create a STREAM data structure which saves arguments and functions. STREAM variables will be created by a producer (the consumer will add functions and arguments that will have to be invoked to get the next token), moved around and invoked by a consumer (it will apply the named functions to the named arguments).

2. Build a function that produces a stream variable - this function will be the last one called in a producer.

3. Build a function that consumes a stream variable - this function will be invoked when the next token is required.

As an example, let CONS be the procedure of two arguments that constructs a stream by attaching a named token (first arg) to an existing stream (second arg), let FIRST be the procedure of one argument that returns the value of the next token in the named (first arg) stream, let EMPTY be the procedure which returns true iff the named stream has no tokens, let REST be the procedure that returns a stream that is identical to the named stream except without the first token. Then the functions TIMES, which multiplies all tokens of a named stream (second arg) by a number specified in the first argument, and MERGE, which merges two streams in increasing order, might look like this:

   STREAM *TIMES(int n, STREAM *s)
   {
      if (EMPTY(s)) return NULL;
      return CONS(n*FIRST(s),TIMES, n, REST(s));
   }

   STREAM *MERGE(STREAM *s1, STREAM *s2)
   {
      if (EMPTY(s1) && EMPTY(s2)) return NULL;
      if (EMPTY(s1)) return s2;
      if (EMPTY(s2)) return s1;
      if (FIRST(s1) < FIRST(s2)) return CONS(FIRST(s1), MERGE, REST(s1), s2);
      else return CONS(FIRST(s2), MERGE, REST(s2), s1);
   }