Lecture 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
(Apply-closure (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
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
letcc, but we would prefer a more direct explanation.
letccitself 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 non-numbers.
We wish to change
Pi so that, if the list contains only numbers,
it returns their product; otherwise, it returns the first non-number that it encounters
in the list. We could use an accumulator to do this:
(define Pi-2 (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))))
Pi-2 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 Pi-3 (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 continuation-passing 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 Pi-4 (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
is tail-recursive; hence, the value returned by the
clause is guaranteed to return directly to the caller of
It is worthwhile to note that, in this case, we have converted a properly recursive procedure into a tail-recursive one. If we can do this for all procedures, we will have succeeded at having explained recursion in terms of tail-recursion (and closure-creation, 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
kis traditionally used to recognize the Teutonic contributions to this area.)
(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
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,
(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 CPS-ing