Section 17: The Meaning of Function Calls 



There are at least three motivations for examining in depth what function calls mean.
(f a)
, and we interpret
it as
((Eval f env) (Eval a env))which relies on two things: that functions in program text are represented as procedures in Scheme, and that application in the source is performed through a function call in Scheme. As an alternative, we could choose to represent functions as a data structure, and write
(Applyclosure (Eval f env) (Eval a env))Though this appears to abstract over all dependencies on Scheme, it does not: for instance, we still rely on Scheme's function call mechanism for much of the interpreter (such as the calls to
Applyclosure
or Eval
).
Indeed, this reliance pervades the interpreter. Since there is no direct analog
to Scheme's procedure call mechanism in most machine instruction sets, we
must find a better way to explain function calls if we want a primitive explanation
of our features.(error ...)
mean? So far, we have encoded error
using letcc
, but we would prefer a more direct explanation.letcc
itself mean? That too has been modeled
with letcc
, which is not satisfying.Consider the following procedure, which computes the product of a list of numbers:
(define Pi (lambda (l) (cond ((null? l) 1) (else (* (car l) (Pi (cdr l)))))))
Now suppose the argument l
may be corrupt and may contain nonnumbers.
We wish to change Pi
so that, if the list contains only numbers,
it returns their product; otherwise, it returns the first nonnumber that it encounters
in the list. We could use an accumulator to do this:
(define Pi2 (lambda (l) (local ((define Pi/acc (lambda (l acc) (cond ((null? l) acc) ((number? (car l)) (Pi/acc (cdr l) (* (car l) acc))) (else (car l)))))) (Pi/acc l 1))))
Suppose Pi2
is passed a corrupt list. In that case, the helper function
would have multiplied all the numbers found until the erroneous input is encountered.
To avoid the wasted multiplications, we can defer the multiplication until we
are certain the list has been completely traversed and found to be a legal input.
The multiplication is delayed by wrapping it in a thunk:
(define Pi3 (lambda (l) (local ((define Pi/acc (lambda (l acc) (cond ((null? l) (acc)) ((number? (car l)) (Pi/acc (cdr l) (lambda () (* (car l) (acc))))) (else (car l)))))) (Pi/acc l (lambda () 1)))))
This program does indeed avoid unnecessary multiplications. However, suppose we
were to modify the *
primitive so that it prints out its
arguments before returning their product; then the three programs would not all
produce the same (printed) output on legal lists.
Problem: What will the outputs be? Will any two be the same? Use the reduction rules to determine what they will print. 
The upshot is that an intensional aspect of the program's behavior has not been preserved. To get back the same order of evaluation while still deferring computation, we use a transformation called continuationpassing style (CPS), wherein we replace the thunk with a ``promise'' that the rest of the computation has been completed before it is evaluated. For example:
(define Pi4 (lambda (l) (local ((define Pi/k (lambda (l k) (cond ((null? l) (k 1)) ((number? (car l)) (Pi/k (cdr l) (lambda (rp) (k (* (car l) rp))))) (else (car l)))))) (Pi/k l (lambda (x) x)))))
Why does the (else ...)
clause work? It is because Pi4
is tailrecursive; hence, the value returned by the else
clause is guaranteed to return directly to the caller of Pi4
.
It is worthwhile to note that, in this case, we have converted a properly recursive procedure into a tailrecursive one. If we can do this for all procedures, we will have succeeded at having explained recursion in terms of tailrecursion (and closurecreation, etc). Indeed, any compiler for a language that allows proper recursion must do something similar; thus, studying CPS can provide us with insight into and techniques for designing compilers.
The following steps must be taken to CPS a program:
k
. (The letter k
is traditionally used to recognize
the Teutonic contributions to this area.)a
, write (k a)
.(lambda (itrec) body)
(``itrec
'' is an abbreviation for ``input to the rest of
the computation''). The original contents of that clause are placed inside
the extra argument (lambda (itrec) ...)
, enclosed in a call
on the continuation k, with the selected recursive call replaced by itrec
.We illustrate this with an example:
(define Pi (lambda (t) (cond ((leaf? t) t) (else (* (Pi (left t)) (Pi (right t)))))))
Then the CPS'ed version, Pi/k
, is
(define Pi/k (lambda (t k) ; rule 1 (cond ((leaf? t) (k t)) ; rule 2a (else ; rule 2b (Pi/k (left t) (lambda (itrec) (k (* itrec (Pi (right t))))))))))
However, there is still a call to Pi
left, which needs to be converted.
To eliminate it, we simply repeat the conversion process on the body of the embedded
continuation. As a result, the body of the continuation is converted to
(Pi/k (right t) (lambda (x) (k (* itrec x))))
so that the final output is
(define Pi/k (lambda (t k) ; rule 1 (cond ((leaf? t) (k t)) ; rule 2a (else ; rule 2b (Pi/k (left t) (lambda (itrec) (Pi/k (right t) (lambda (x) (k (* itrec x))))))))))
Note: In the process of CPSing Pi* , we have made
an explicit decision about the order of evaluation: specifically, that
the right child will be traversed before the left. 