Principles of Programming Languages: Lecture 20

Lecture 20, Comp 311

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 (app-rator M) env
	    (lambda (f)
	      (Eval (app-rand M) env
		(lambda (a)
		  (Apply f a k))))))

We then make it representation independent,

((var? M) (Pop k (lookup M env)))
((app? M) (Eval (app-rator M) env
	    (Push-app-f M env k)))

where

(define Push-app-f
  (lambda (M env k)
    (lambda (f)
      (Eval (app-rand M) env
	(lambda (a)
	  (Apply f a k))))))

and

(define Pop
  (lambda (k v)
    (k v)))

Then in Push-app-f we rewrite the last procedure to

(lambda (a)
  (Push-app-a f k))

with

(define Push-app-a
  (lambda (f k)
    (lambda (a)
      (Apply f a k))))

Now in Push-app-f, which now looks like this,

(define Push-app-f
  (lambda (M env k)
    (lambda (f)
      (Eval (app-rand M) env
	(lambda (a)
	  (Push-app-a f k))))))

we replace the lambda with

 (list 'app-f M env k)

to get

(define Push-app-f
  (lambda (M env k)
    (list 'app-f M env k)))

and Push-app-a 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 make-closure and expressed closures in terms of that. Since our continuations are quite similar to closures, why can't we use make-closure 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)
	((app-f) (let ((M (cadr k))
			(env (caddr k))
			(k (cadddr k)))
		   ((lambda (f)
		      (Eval (app-rand M) env
			(Push-app-a 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 app-f case as:

(let ((M (cadr k))
       (env (caddr k))
       (k (cadddr k)))
  (let ((f v))
    (Eval (app-rand M) env
      (Push-app-a 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.

The True Meaning of Function Calls, or, From Tail-Recursion to Register Machines

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:

Making the parameters of TR functions into global variables, such as
```
(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
      ...)))
```
``Initializing'' the parameters (registers). We place the term in quotes since it needs to be done each time the procedures are invoked (see below). In addition, we add a procedure to initiate the interpreter:
```
(define Main
  (lambda (M)
    (set! =M= M)
    (set! =env= (empty-env))
    (set! =k= 'stop)))
```
Calling functions without arguments after assigning the arguments into the appropriate registers:
```
(define Eval
  (lambda ()
    ((var? =M=)
      (set! =k= =k=)                         ; redundant
      (set! val (lookup =M= =env=))
      (Pop))
    ((app? =M=)
      (set! =k= (Push-app-f =M= =env= =k=))
      (set! =M= (app-rator =M=))             ; destroys M!
      (set! =env= =env=)
      (Eval))
    ...))

(define val)

(define Pop
  (lambda ()
    (case (car k)
      ((push-app-f) (let ((M ...)
			   (env ...)
			   (k ...)
			   (f val))
		      (set! =k= (Push-app-a f k))
		      (set! =M= (app-rand M))
		      (set! =env= env)
		      (Eval)))
      ...)))
```
Now we're left only tail-recursive function calls. We can test this in the following manner. First, we define Goto:
```
((call/cc
   (lambda (k)
     (set! Goto k)
     (lambda () "hello world"))))
```
Now for each tail call, instead of writing (proc), we write (Goto proc) instead.

Puzzle: Why is Goto an appropriate name for the above continuation? What does the (proc) to (Goto proc) transformation help prove, and how?
Comment: The Goto code does not work in DrScheme because it evaluates each top level form in a separate control thread; it does not permit control from one thread to cross to another one. Hence, you cannot use the Goto form for tail calls in course assignments.

At this point, we are left with only the following: cond, set!, selector functions, Goto and the Push-app-* 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, Pop is Pi in accumulator style. Hence, we can make the representation even more concise:

(define Stop
  1)

(define Push
  *)

(define Pop
  *)

and voilà, we get the C version of ! in a loop.

Shriram Krishnamurthi / shriram@cs.rice.edu