| Sussman and Steele | December 22, 1975 | 19 | Substitution Semantics and Styles |
=> ((LAMBDA (A) ((LAMBDA (A) (ANSWER (* 3 A))) (* 2 A))) (* 1 1)) => ((LAMBDA (A) ((LAMBDA (A) (ANSWER (* 3 A))) (* 2 A))) 1) => ((LAMBDA (A) (ANSWER (* 3 A))) (* 2 1)) => ((LAMBDA (A) (ANSWER (* 3 A))) 2) => (ANSWER (* 3 2)) => (ANSWER 6) Whew!
Note that we have computed factorial of 3 (and are about to give this result to the continuation), but in the process no combination with FACT in the first position has ever been reduced except as the outermost expression. If we think of the computation in terms of evaluation rather than substitution, this means that we never returned a value from any application of the function FACT! It is always possible, if we are willing to specify explicitly what to do with the answer, to perform any calculation in this way: rather than reducing to its value, it reduces to an application of a continuation to its value (cf. [Fischer]). That is, in this continuation-passing programming style, a function always "returns" its result by "sending" it to another function. This is the key idea.
We also note that by our previous observation, this program is essentially recursive in that the expressions produced as intermediate results of the substitution semantics grow to a size proportional to the depth. In fact, the same information is being stored in the nested continuations produced by this program as in the nested products produced by the traditional recursion—what to do with the result.
One might object that this FACT is not the same kind of object as the previous definition, since we can't use it as a function in the same manner. Note, however, that if we supply the continuation (LAMBDA (X) X), the resulting combination (FACT 3 (LAMBDA (X) X)) will reduce to 6, just as with traditional recursion.
One might also object that we are using function values—the primitives =, -, and * are functions which return values, for example. But this is just a property of the primitives; consider a new set of primitives ==, --, and ** which accept continuations (indeed, let == take two continuations: if the predicate is TRUE call the first, otherwise call the second). We can then define fact as follows:
