In Sections 2.2 and 2.3 we notice that the
functions sum
and factorial
are called repeatedly until
the problem has been reduced to a problem of size zero. No results are
returned by any of these calls until a call is made for a problem of
size zero. For each of the calls made for problems of size greater than
zero, a record of the computation remaining to be done must be saved. We
formalize the concept of representing the remaining computation as
a monad (function of one argument) with the following definition.2
Given a compound expression e and a subexpression f of e, the continuation of f in e is the computation in e, written as a monad, which remains to be done after first evaluating f. When the continuation of f in e is applied to the result of evaluating f, the result is the same as evaluating the expression e. Let c be the continuation of f in e. The expression e may then be written as c f.
Continuations provide a ``factorization'' of expressions into two parts; f which is evaluated first and c which is later applied to the result of f. Continuations are helpful in the analysis of algorithms.