From Wikisource
Jump to navigation Jump to search
This page has been validated.
Steele and Sussman March 10, 1976 10 LAMBDA: The Ultimate Imperative


Up to now we have thought of SCHEME’s LAMBDA expressions as functions, and of a combination such as (G (F X Y)) as meaning “apply the function F to the values of X and Y, and return a value so that the function G can be applied and return a value ...” But notice that we have seldom used LAMBDA expressions as functions. Rather, we have used them as control structures and environment modifiers. For example, consider the expression:


This is defined to be an abbreviation for:


We do not care about the value of this BLOCK expression; it follows that we do not care about the value of the (LAMBDA (DUMMY) ...). We are not using LAMBDA as a function at all.

It is possible to write useful programs in terms of LAMBDA expressions in which we never care about the value of any lambda expressoin. 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}

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);
    if n=0 then c(1) else
            procedure temp(a) value a; integer a;
            fact(n-1, temp);

   (LAMBDA (N C)
      (IF (= N 0) (C 1)
          (FACT (- N 1)
                (LAMBDA (A) (C (* N A)))))))

It is fairly clumsy to use this version of FACT in ALGOL; it is necessary to