# Page:Scheme - An interpreter for extended lambda calculus.djvu/20

 Sussman and Steele December 22, 1975 19 Substitution Semantics and Styles

```=> ((LAMBDA (A)
((LAMBDA (A)
(* 2 A)))
(* 1 1))
=> ((LAMBDA (A)
((LAMBDA (A)
(* 2 A)))
1)
=> ((LAMBDA (A)
(* 2 1))
=> ((LAMBDA (A)
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.
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: