Section 2.1.6 briefly introduced the notion of a stream, which is used to implement the two basic representations considered in this work. We discuss streams in more detail here.
A stream is simply an infinite sequence. Clearly a machine with finite resources cannot store an infinite sequence in memory. However we can represent some infinite sequences as programs which successively generate elements of the sequence. We refer to these sequences as computable streams, and the programs which generate them are used extensively when performing exact real arithmetic on a computer.
As mentioned in section 2.2, the important point to note about streams is that because the elements are evaluated successively, we can only examine a finite initial sub-sequence of the stream. Because computers are finite and we can only store a finite number of digits in memory at any one time, we must decide each output digit on the basis of a finite number of input digits from the start of the sequence representing the number. This is quite different from the way arithmetic is usually performed on finite strings of digits in which the entire numeral can be accessed.
A computable stream is normally implemented as a function which takes
no parameters, but which, when evaluated, returns the first element
(head) of the sequence and a new function computing the
remainder (tail) of the infinite sequence. The language ML could
be used to define a stream of elements of type 'a as follows:
datatype 'a Stream = Stream of unit ('a * ('a Stream))
One feature of this particular datatype is that it requires explicit evaluation of the function to obtain each element of the sequence. Lazy functional languages such as Haskell [22] allow streams to be handled more neatly as lazy lists. This is one of the motivations for using Haskell to implement the calculator (see section 6.2.1). For example, in Haskell one could implement a function to produce a stream counting from some number n as follows:
from n = (n : from (n+1)) > from 0 [ 0, 1, 2, 3, 4, ... <ctrl-c>
The from function generates the digit at the head of the
sequence, and uses a function to generate the remainder of the
sequence by recursively calling itself. When evaluated the function
will generate digits from the sequence indefinitely unless
interrupted.
An operation on this stream might be defined as follows:
add (a:x) (b:y) = (a + b : add x y) > add (from 0) (from 1) [ 1, 3, 5, 7, 9, ... <ctrl-c>
This style of programming is used extensively in the implementation, as described in chapter 6.