Guy L. Steele, Jr.

“ In pure continuation-passing style, all evaluations are trivial: no combination is nested within another, and therefore no "hidden temporaries" are required. But if X is a combination, say (G P Q) , then we want to think of G as a function, because we want a value from it, and we will need an implicit temporary place to keep the result while evaluating Y and Z. (An interpreter usually keeps these temporary places in the control stack!) On the other hand, we do not necessarily need a value from F This is what we mean by tail-recursion: F is called tail-recursively, whereas G is not. ”

“ LISP supplies names for the parts of an executable expression and standard operators for constructing expressions and extracting their components. The use of LISP syntax makes the structure of such expressions manifest. We use ALGOL as an expository language, because it is familiar to many people, but ALGOL is not sufficiently powerful to express the necessary concepts ”

“ The labels are names of functions of no arguments. In order to "go to" the labeled code, we merely call the function named by that label.
Simple Assignment Of course, all this sequencing of statements is useless unless the statements have side effects. An important side effect is assignment. For example, one often uses assignment to place intermediate results in a named location (i.e. a variable) so that they may be used more than once later without recomputing them ”

“ The invocation fact (n) computes the product of the integers from 1 to n using the identity n!=n (n-1) ! (n>0) . If n is zero, 1 is returned; otherwise fact calls itself recursively to compute (n-1) !, then multiplies the result by n and returns it. ”

“ At worst, one may need as many labels as there are statements (not counting the eliminated assignment and GO TO statements) .
Compound Expressions At this point we are almost in a position to model the most general form of compound statement. In LISP, this is called the "PROG feature". In addition to statement sequencing and GO TO statements, one can return a value from a PROG by using the RETURN statement. ”

“ If the escape function is never applied, then the value of the escape expression is the value of r. If the escape function is applied to an argument a, however, then evaluation of r is aborted and the escape expression returns a. ”

“ Simple Recursion Iteration Compound Statements and Expressions GO TO and Assignment Continuation-Passing Escape Expressions Fluid Variables Call by Name, Call by Need, and Call by Reference The models require only (possibly self-referent) lambda application, conditionals, and (rarely) assignment. No complex data structures such as stacks are used. ”

“ Now consider what computation steps are implied by
(LAMBDA (A B C ...) (F X Y Z ...) )
When we "apply" the LAMBDA expression we have some values to apply it to; we let the names A, B, C ... refer to these values. ”

“ While its utter simplicity makes lambda calculus ideal for logicians, it is too primitive for use by programmers. The meta-language we use is a programming language called SCHEME {Note Schemepaper} which is based on lambda calculus. ”

“ We have already demonstrated how one could represent any “FORTRAN” program in these terms: all one needs is PROG (with GO and SETQ) , and PRINT to get the answers out. The ultimate generalizaton of this imperative programming style is continuation-passing. {Note Churchwins} [note 1]
Continuation-Passing Recursion Consider the following alternative definition of FACT. It has an extra argument, the continuation, which is a function to call with the answer, when we have it, rather than return a value.
procedure fact (n, c) ; value n, c;
integer n; procedure c (integer value) ”

“ It performs statement S1 before S2, and so may be used for sequencing. S1 is useful only for its side effects. (In ALGOL, S2 must also be a statement, and so is also useful only for side effects, but other languages have compound expressions containing a statement followed by an expression.) The ALGOL compound statement may actually contain any number of statements, but such statements can be expressed as a series of nested two-statement compounds. ”

“ It is not immediately apparent that this sequencing can be expressed in a purely applicative language. We can, however, take advantage of the implicit sequencing of applicative order evaluation. Thus, for example, we may write a two-statement sequence as follows:
( (LAMBDA (DUMMY) S2) S1)
where DUMMY is an identifier not used in S2. ”

“ The identifiers DOLOOP and DUMMY are chosen so as not to conflict with any other identifiers in the program.
Note that, unlike most implementations of DO, there are no side effects in the steppings of the iteration variables. DO loops are usually modelled using assignment statements. For example:
for x := a step b until c do ”