4 Gluing Programs Together
The other new kind of glue that functional languages provide enables whole
programs to be glued together. Recall that a complete functional program is
just a function from its input to its output. If f and g are such programs, then
(g . f ) is a program that, when applied to its input, computes
g (f input)
The program f computes its output, which is used as the input to program g.
This might be implemented conventionally by storing the output from f in a
temporary file. The problem with this is that the temporary file might occupy
so much m emory that it is impractical to glue the programs together in this way.
Functional languages provide a solution to this problem. The two programs f
and g are run toge ther in strict s ynchronization. Program f is started only
when g tries to read some input, and runs only for long enough to deliver the
output g is trying to read. Then f is suspended and g is run until it tries to read
another input. As an added bonus, if g terminates without reading all of f ’s
output, then f is aborted. Program f can even be a nonterminating program,
producing an infinite amount of output, since it will be terminated forcibly as
soon as g is finished. This allows termination conditions to be separated from
loop bodies — a powerful modularization.
Since this method of evaluation runs f as little as pos sible, it is called “lazy
evaluation”. It makes it practical to modularize a program as a generator that
constructs a large number of possible answers, and a selector that chooses the
appropriate one. While some other systems allow programs to be run together
in this manner, only functional languages (and not even all of them) use lazy
evaluation uniformly for every function call, allowing any part of a program to
be modularized in this way. Lazy evaluation is perhaps the most powerful tool
for modularization in the functional programmer’s repertoire.
We have described lazy evaluation in the context of functional languages,
but surely so useful a feature should be added to nonfunctional languages —
or should it? Can lazy evaluation and side-effects coexist? Unfortunately, they
cannot: Adding lazy evaluation to an imperative notation is not actually impos-
sible, but the combination would make the programmer’s life harder, rather than
easier. Because lazy evaluation’s power depends on the programmer giving up
any direct control over the order in which the parts of a program are executed,
it would make programming with side effects rather difficult, because predicting
in what order —or even whether— they might take place would require knowing
a lot about the context in which they are embedded. Such global interdepen-
dence would defeat the very modularity that —in functional languages— lazy
evaluation is designed to enhance.
4.1 Newton-Raphson Square Roots
We will illustrate the power of lazy evaluation by programming some numerical
algorithms. First of all, consider the Newton-Raphson algorithm for finding
9