next up previous
Next: 3.1 Scheme Example Up: Recursion, Iteration and Functional Previous: 2.3 The Factorial Function

3 Continuations

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.



Subsections
next up previous
Next: 3.1 Scheme Example Up: Recursion, Iteration and Functional Previous: 2.3 The Factorial Function
2002-11-26