#### 12.1 The Representation of DataStream

A DataStream is basically represented as a pair (a,g) of an Array(T) (a cache) and a Generator(T) structure (a generator of not yet accessed elements). We choose a record to form the pair structure and additionally store whether the stream is known to be eventually constant.

ToDo 63
rhx 51 03-Oct-2006: Maybe we also want to consider periodic streams whose period is longer than 1. Should turn the boolean value in the representation into an element of MachineInteger which represents the length of the period counting backwards from #s on.
388representation: DataStream 388  (386)
Rep == Record(
representation: DataStream: generator 389a,
representation: DataStream: cache 389b,
representation: DataStream: is it a constant stream from some point on? 390
);

It is important that the representation is a mutatble data structure. Not only do we need to update the cache, but it is also important for the definition of recursive definitions that can only be made using destructive operations.

In our representation a stream is a generator of elements of T together with an array that stores the generated elements.

If the generator runs out of elements, the stream is continued ad infinitum by repeating the last element. In that case the stream is said to be eventually constant.

A stream represents infinitely many elements from T. Therefore, an empty stream is not a valid concept. In other words

s := stream(generate {});
s.0;

will throw a runtime exception.

One entry in the record above is a generator that provides the elements of the stream. This generator is consumed (i. e., destructively modified) while accessing elements from the stream.

389arepresentation: DataStream: generator 389a  (388)
gen: Generator T

Uses Generator 617.

We store the already generated elements in an array that grows in size as we get/access more and more elements. So there are two important numbers:

1. the size of the array cache (its number of maximal entries) and
2. the number n of elements that are valid inside the array structure.
389brepresentation: DataStream: cache 389b  (388)
cache: PrimitiveArray T,
size: I,
numberOfElements: I

Uses I 47.

We could have used an Array data structure, but that would have introduced another layer of access. An Array basically is given by cache and size from above.

For some streams the generator gen might run out of elements. In this case the stream is continued with the last generated element and is turned into an eventually constant stream.

An eventually constant stream is only recognized after the the last element of the generator gen has been accessed. In other words, after executing the code

s := stream(generate yield 0);
b := constant? s;
s0 := s.0;   b0 := constant? s;
s1 := s.1;   b1 := constant? s;

b and b0 will be false whereas b1 will be true.

For the code

s := stream 0;
b := constant? s;

b will be true.

If constant? is true then the constant value that is stored in position numberOfElements1 in the cache.

390representation: DataStream: is it a constant stream from some point on? 390  (388)
constant?: Boolean