By simple loops we mean constructs which enable programs to execute the same piece of code repeatedly in a controlled manner. Variables may be made to take on different values during each repetition, and the number of repetitions may depend on data given to the program.

The simplest kind of imperative construct is the statement sequencer, for example the compound statement in ALGOL:

begin
S1;
S2;
end

This construct has two interesting properties:

• (1) It performs statement S1 before S2, and so may be used for sequencing.
• (2) 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. That is:

begin
S1;
S2;
...
Sn-1;
Sn;
end

is equivalent to:

begin
S1;
begin
S2;
begin
...

begin
Sn-1;
Sn;
end;
end;
end:
end

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:

((fn[dummy] S2) S1)

where dummy is an identifier not used in S2. From this it is manifest that the value of S1 is ignored, and so is useful only for side effects. (Note that we did not claim that S1 is expressed in a purely applicative language, but only that the sequencing can be so expressed.) From now on we will use the form (BLOCK S1 S2) as an abbreviation for this expression, and (BLOCK S1 S2...Sn-1 Sn) as an abbreviation for

(BLOCK S1 (BLOCK S2 (BLOCK ... (BLOCK Sn-1 Sn)...))) 

A more general imperative structure is the compound statement with labels and G0 T0s. Consider the following code fragment due to Jacopini, taken from Knuth: [Knuth 74]

begin 
L1: if B1 then go to L2; S1;
    if B2 then go to L2; S2;
    go to L1;
L2: S3;

It is perhaps surprising that this piece of code can be syntactically transformed into a purely applicative style. For example, in SCHEME we could write:

(in-ns 'categorical.imperative)
(let
    [L1 (fn[]
          (if B1 (L2) (do S1
                          (if B2 (L2) (do S2 (L1))))))
     L2 (fn[] S3)]
  (L1))

As with the D0 loop, this transformation depends critically on SCHEME's treatment of tail-recursion and on lexical scoping of variables. 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.

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:

begin
real a2, sqrtdisc;
a2 := 2*a;
sqrtdisc := sqrt(b^2 - 4*a*c);
root1 := (- b + sqrtdisc) / a2;
root2 := (- b - sqrtdisc) / a2;
print(root1);
print(root2);
print(root1 + root2);
end

It is well known that such naming of intermediate results may be accomplished by calling a function and binding the formal parameter variables to the results:

(fn [a2 sqrtdisc]
  ((fn[root1 root2]
    (do (println root1)
        (println root2)
        (println (+ root1 root2))))
  (/ (+ (- b) sqrtdisc) a2)
  (/ (- (- b) sqrtdisc) a2))

  (* 2 a)
  (sqrt (- (* b b) (* 4 a c))))

This technique can be extended to handle all simple variable assignments which appear as statements in blocks, even if arbitrary G0 T0 statements also appear in such blocks. {Note Mccarthywins}

For example, here is a program which uses G0 TO statements in the form presented before; it determines the parity of a non-negative integer by counting it down until it reaches zero.

begin
L1: if a = 0 then begin parity := 0; go to L2; end;
    a := a - 1;
    if a = 0 then begin parity := 1; go to L2; end;
    a := a - 1;
    go to L1;
L2: print(parity);

This can be expressed in SCHEME:

(let
    [L1 (fn [a parity]
          (if (zero? a) (L2 a 0)
              (L3 (dec a) parity)))
     L3 (fn [a parity]
          (if (zero? a) (L2 a 1)
              (L1 (dec a) parity)))
     L2 (fn [a parity]
          (println parity))]
  (L1 a parity))

The trick is to pass the set of variables which may be altered as arguments to the label functions. {Note Flowgraph} It may be necessary to introduce new labels (such as L3) so that an assignment may be transformed into the binding for a function call. At worst, one may need as many labels as there are statements (not counting the eliminated assignment and GO TO statements).

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 G0 T0 statements, one can return a value from a PROG by using the RETURN statement.

Let us first consider the simplest compound statement, which in SCHEME we call BLOCK. Recall that (BLOCK s1 sz) is defined to be ((lambda (dummy) s2) s1)

Notice that this not only performs Sl before S2, but also returns the value of S2. Furthermore, we defined (BLOCK S1 S2 ... Sn) so that it returns the value of Sn. Thus BLOCK may be used as a compound expression, and models a LISP PROGN, which is a PROG with no G0 T0 statements and an implicit RETURN of the last ``statement'' (really an expression).

Host LISP compilers compile D0 expressions by macro-expansion. We have already seen one way to do this in SCHEME using only variable binding. A more common technique is to expand the D0 into a PROG, using variable assignments instead of bindings. Thus the iterative factorial program:

(oarxnz FACT .
(LAMaoA (n) .
(D0 ((M N (- H 1))
(Ans 1 (* M Ans)))
((- H 0) A"$))))

would expand into:

(DEFINE FACT
. (LAMeoA (M)
(PRO6 (M Ans)
(sszro M n
Ans 1) ~
LP (tr (- M 0) (RETURN Ans))
(ssero M (- n 1)
Ans (' M Ans))
(60 LP))))

where SSETQ is a simultaneous multiple assignment operator. (SSETQ is not a SCHEME (or LISP) primitive. It can be defined in terms of a single assignment operator, but we are more interested here in RETURN than in simultaneous assignment. The SSETQ's will all be removed anyway and modelled by lambda binding.) We can apply the same technique we used before to eliminate G0 T0 statements and assignments from compound statements:

(DEFINE FACT
(LAHBOA (I)
(LABELS ((L1 (LAManA (M Ans)
(LP n 1)))
(LP (LAMaoA (M Ans)
(IF (- M o) (nztunn Ans)
(£2 H An$))))
(L2 (LAMaoA (M An )
(LP (- " 1) (' H flN$)))))
(L1 NIL NlL))))

clojure

We still haven't done anything about RETURN. Let's see…

• ==> the value of (FACT 0) is the value of (Ll NIL NIL)
• ==> which is the value of (LP 0 1)
• ==> which is the value of (IF (= 0 0) (RETURN 1) (L2 0 1))
• ==> which is the value of (RETURN 1)

Notice that if RETURN were the identity function (LAMBDA (X) X), we would get the right answer. This is in fact a general truth: if we Just replace a call to RETURN with its argument, then our old transformation on compound statements extends to general compound expressions, i.e. PROG.

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 Inc!(n, c); value n, c;
integer n: procedure c(integer value);
if n-=0 then c(l) else
begin
procedure l(!mp(d) value a: integer a;
c(mm);
Iacl(n-1, romp):
end;

(in-ns 'categorical.imperative)
(defn fact-cps[n k]
  (if (zero? n) (k 1)
      (recur (dec n) (fn[a] (k (* n a))))))

clojure It is fairly clumsy to use this version of‘ FACT in ALGOL; it is necessary to do something like this:

begin
integer ann
procedure :emp(x); value 2:; integer x;
ans :1 x;
]'act(3. temp);
comment Now the variable "am" has 6;
end;

Procedure fact does not return a value, nor does temp; we must use a side effect to get the answer out.

FACT is somewhat easier to use in SCHEME. We can call it like an ordinary function in SCHEME if we supply an identity function as the second argument. For example, (FACT 3 (LAMBDA (X) X)) returns 6. Alternatively, we could write (FACT 3 (LAHBDA (X) (PRINT X))); we do not care about the value of this, but about what gets printed. A third way to use the value is to write (FACT 3 (LAMBDA (x) (SQRT x))) instead of (SQRT (FACT 3 (LAMBDA (x) x)))

In either of these cases we care about the value of the continuation given to FACT. Thus we care about the value of FACT if and only if we care about the value of its continuation!

We can redefine other functions to take continuations in the same way. For example, suppose we had arithmetic primitives which took continuations; to prevent confusion, call the version of "+" which takes a continuation '++", etc. Instead of writing (- (+ B Z)(* 4 A C)) we can write

(in-ns 'categorical.imperative)
(defn enable-continuation "Makes f take a continuation as an additional argument."[f]
  (fn[& args] ((fn[k] (k (apply f (reverse (rest (reverse args)))))) (last args)) ))
(def +& (enable-continuation +))
(def *& (enable-continuation *))
(def -& (enable-continuation -))


(defn quadratic[a b c k]
(*& b b
    (fn[x] (*& 4 a c
               (fn[y]
                 (-& x y k))))))

where k is the continuation for the entire expression.

This is an obscure way to write an algebraic expression, and we would not advise writing code this way in general, but continuation-passing brings out certain important features of the computation:

• ¹ The operations to be performed appear in the order in which they are

performed. In fact, they must be performed in this order. Continuation- passing removes the need for the rule about left-to-right argument evaluation{Note Evalorder)

• ² In the usual applicative expression there are two implicit temporary values: those of (* B B) and (* 4 A C). The first of these values must be preserved over the computation of the second, whereas the second is used as soon as it is produced. These facts are manifest in the appearance and use of the variable X and Y in the continuation-passing version.

In short, the continuation-passing version specifies exactly and explicitly what steps are necessary to compute the value of the expression. One can think of conventional functional application for value as being an abbreviation for the more explicit continuation-passing style. Alternatively, one can think of the interpreter as supplying to each function an implicit default continuation of one argument. This continuation will receive the value of the function as its argument, and then carry on the computation. In an interpreter this implicit continuation is represented by the control stack mechanism for function returns. Now consider what computational 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. We then determine the values of X, Y, Z … and pass these values (along with "the buck", i.e. control!) to the lambda expression F (F is either a lambda expression or a name for one). Passing control to F is an unconditional transfer. (Note Jrsthack) {Note Hewitthack) Note that we want values from X, Y, Z, … If these are simple expressions, such as variables, constants, or LAMBDA expressions, the evaluation process is trivial, in that no temporary storage is required. 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. A better name for tail-recursion would be "tail-transfer", since no real recursion is implied. This is why we have made such a fuss about tail-recursion: it can be used for transfer of control without making any commitment about whether the expression expected to return a value. Thus it can be used to model statement-like control structures. Put another way, tail—recursion does not require a control stack as nested recursion does. In our models of iteration and imperative style all the LAMBDA expressions used for control (to simulate GO statements, for example) are called in tail-recursive fashion.

Reynolds [Reynolds 72] defines the construction = escape x in r =

to evaluate the expression \(r\) in an environment such that the variable \(x\) is bound to an escape function. 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\). {Note J-operator} (Reynolds points out that this definition is not quite accurate, since the escape function may be called even after the escape expression has returned a value; if this happens, it “returns again"!)

As an example of the use of an escape expression, consider this procedure to compute the harmonic mean of an array of numbers. If any of the numbers is zero, we want the answer to be zero. We have a function hannaunl which will sum the reciprocals of numbers in an array, or call an escape function with zero if any of the numbers is zero. (The implementation shown here is awkward because ALGOL requires that a function return its value by assignment.)

begin
real procedure Imrmsum(a, n. escfun)§ p
real array at integer n; real procedure esciun(real);
begin
real sum;
sum := 0;
for i :1 0 until n-l do
begin
if a[i]=0 then cscfun(0);
sum :1 sum ¢ I/a[i];
enm
harmsum SI sum;
end: .
real array b[0:99]:
print(escape x in I00/hm-m.mm(b, 100, x));
end

If harmsum exits normally, the number of elements is divided by the sum and printed. Otherwise, zero is returned from the escape expression and printed without the division ever occurring. This program can be written in SCHEME using the built-in escape operator CATCH:

abc