Section 19: The True Meaning of Function Calls 



In this lecture, we will make repeated use of three key transformations used in building software: representation independence, switching representations, and CPS.
We begin by CPSing our interpreter:
((var? M) (k (lookup M env))) ((app? M) (Eval (apprator M) env (lambda (f) (Eval (apprand M) env (lambda (a) (Apply f a k))))))
We then make it representation independent,
((var? M) (Pop k (lookup M env))) ((app? M) (Eval (apprator M) env (Pushappf M env k)))
where
(define Pushappf (lambda (M env k) (lambda (f) (Eval (apprand M) env (lambda (a) (Apply f a k))))))
and
(define Pop (lambda (k v) (k v)))
Then in Pushappf
we rewrite the last procedure to
(lambda (a) (Pushappa f k))
with
(define Pushappa (lambda (f k) (lambda (a) (Apply f a k))))
Now in Pushappf
, which now looks like this,
(define Pushappf (lambda (M env k) (lambda (f) (Eval (apprand M) env (lambda (a) (Pushappa f k))))))
we replace the lambda
with (list 'appf M env k)
to
get
(define Pushappf (lambda (M env k) (list 'appf M env k)))
and Pushappa
is modified similarly, so we assume that all continuations
have distinguishing tags.
Puzzle: The last time we wanted to make our representations independent of the
underlying Scheme representations, we created
makeclosure and expressed closures in terms of that.
Since our continuations are quite similar to closures, why can't we
use makeclosure to represent continuations as well? 
Given these definitions, we can now write down the code for Pop
.
Recall that Pop
needs to examine the tag at the front of the continuation
to determine what to do.
(define Pop (lambda (k v) (if (list? k) (case (car k) ((appf) (let ((M (cadr k)) (env (caddr k)) (k (cadddr k))) ((lambda (f) (Eval (apprand M) env (Pushappa f k))) v)))) (k v))))
(Note that we should be able to transform the continuations one at a time. Hence,
Pop
includes both methods of invoking continuations.) But we know
that ((lambda ...) ...)
is just let
, so we can rewrite
the appf
case as:
(let ((M (cadr k)) (env (caddr k)) (k (cadddr k))) (let ((f v)) (Eval (apprand M) env (Pushappa f k))))
We will find it convenient to also add a continuation with tag stop
which is used to halt computation. This is the default initial continuation.
A register machine has a number of registers, an unbounded amount of memory, assignment to memory, assignment to registers, and a goto statement.
By now, the interpreter has only tail recursive calls to Eval
and to Pop
; the different variations on Push
are all
trivial. We now undertake the following steps:
(define =M=) (define =env=) (define =k=)Thus, we can eliminate all parameters for procedures by assigning to the parameter registers instead. For instance, the interpreter looks like
(define Eval (lambda () (cond ...)))
(define Main (lambda (M) (set! =M= M) (set! =env= (emptyenv)) (set! =k= 'stop)))
(define Eval (lambda () ((var? =M=) (set! =k= =k=) ; redundant (set! val (lookup =M= =env=)) (Pop)) ((app? =M=) (set! =k= (Pushappf =M= =env= =k=)) (set! =M= (apprator =M=)) ; destroys M! (set! =env= =env=) (Eval)) ...)) (define val) (define Pop (lambda () (case (car k) ((pushappf) (let ((M ...) (env ...) (k ...) (f val)) (set! =k= (Pushappa f k)) (set! =M= (apprand M)) (set! =env= env) (Eval))) ...)))Now we're left only tailrecursive function calls.
At this point, we are left with only the following: cond
, set!
,
selector functions, Eval
and the Pushapp*
and Pop
procedures. All of these can be trivially implemented at the machine level: most
correspond directly to machine instructions, while the Push
procedures
allocate enough space to put the pointers in, and return a pointer to that newly
allocated memory. We have already seen how to implement such procedures before
with an array of memory. Hence, the only unnatural assumption left in our interpreter
is that we have an unlimited amount of memory.
Example: Consider the factorial function:
(define ! (lambda (n) (if (= n 0) 1 (* n (! ( n 1)))))) First, we CPS it: (define ! (lambda (n) (!/k n (lambda (x) x)))) (define !/k (lambda (n k) (if (= n 0) (k 1) (!/k ( n 1) (lambda (v) (k (* n v))))))) and then make it representationally independent: (define ! (lambda (n) (!/k n Stop))) (define !/k (lambda (n k) (if (= n 0) (Pop k 1) (!/k ( n 1) (Push n k))))) where (define Stop (lambda (x) x)) (define Push (lambda (n k) (lambda (m) (k (* n m))))) (define Pop (lambda (k m) (k m))) We can represent our continuations more directly by using a list. This change only involves modifying the helper functions, leaving the main code untouched: (define Stop '()) (define Push cons) (define Pop (lambda (k m) (if (null? k) m (Pop (cdr k) (* (car k) m))))) It is easy to see that the lists we get will always consist of
numbers. In other words, (define Stop 1) (define Push *) (define Pop *) and voilà, we get the C version of 