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.
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;
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.
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:
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
For the code
b will be true.If constant? is true then the constant value that is stored in position numberOfElements− 1 in the cache.