 |
Figure 1. A program and a user interacting via a text terminal.
Suppose the outside world is a simple text terminal (see Figure 1). Then, the interesting effects are: outputting characters to the terminal screen, and inputting characters from the terminal keyboard. The behaviour of a program could be described by a sequence of the basic effects, so it is natural to use sequential compositions of effects to build programs with nontrivial behaviour. This is what is provided in the typical imperative languages.
Figure 1. A program and a user interacting via a text terminal.
As an example, consider a program that reads some numbers separated by white space, and outputs the sum of the numbers. In an imperative language, it would look something like this:
program = sumNumbers 0
sumNumbers acc =
if end_of_input
then putNumber acc
else do n <- getNumber
sumNumbers (acc+n)
getNumber = ...
putNumber = ...getNumber and putNumber as reusable components. By taking a step back and
reflecting on what a program is, we can perhaps find ways of
composing programs other than the sequential composition of
effects. Having more versatile ways of composing programs is
likely to give us more opportunities to construct reusable
subprograms.
We choose to view programs as defining stream processors, that is, a program describes some kind of process that consumes an input stream and produces an output stream. This view goes back to Landin [Lan65]. We use the symbol shown in Figure 2 to denote a stream processor.
Figure 2. A stream processor.
A stream processor can be seen as a function on streams. A program that interacts with a text terminal could be seen as a function from a stream of characters to a stream of characters. When the program is run, the function is applied to the stream of characters received from the keyboard and the resulting stream of characters is output to the screen.
In a lazy functional language, streams can be represented as ordinary lists. A program that interacts with a text terminal can thus be built using ordinary list functions. The typical lazy functional solution to the number-summing problem looks something like this:
The input stream is chopped into words, the words are converted to numbers, the numbers are summed and converted back into characters that can be output to the screen.program = show . sum . map read . words
Let us compare this solution with the imperative one. In both
solutions, subprograms for parsing and printing numbers are reusable. In
the functional solution the number-summing function is reusable as
well. And although we have used a standard function to sum a list of
numbers, the above program can execute in constant space, since in a lazy
language, computations are performed on demand. Likewise, input
from the terminal is read on demand, allowing the computation
of the sum to be interleaved with the reading and parsing of
keyboard input. (If we tried to use the sum function in the
imperative solution, we would first have to read all the numbers
and store them in a list, and then call the sum
function. The program would thus not run in constant space.)
In the functional solution, the program is no longer expressed as a composition of basic effects. Instead, we have built the program from a number of stream processors in a pipe line.
We have now seen two ways of describing stream processors:
