Section 19: The True Meaning of Function Calls

## 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)
((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))
(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:

1. 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
...)))
```
2. "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)))
```
3. 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.

At this point, we are left with only the following: `cond`, `set!`, selector functions, `Eval` and the `Push-app-*` 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, `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.