Principles of Programming Languages: Lecture 16

Lecture 16, Comp 311

The Meaning of Function Calls

There are at least three motivations for examining in depth what function calls mean.

In LC, a function call looks like (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 Apply-closure 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.
What does (error ...) mean? So far, we have encoded error using letcc, but we would prefer a more direct explanation.
Finally, what does 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 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))))

Suppose 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 Pi-4 is tail-recursive; hence, the value returned by the else clause is guaranteed to return directly to the caller of Pi-4.

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:

Add an extra parameter to every recursive function. Call this parameter k. (The letter k is traditionally used to recognize the Teutonic contributions to this area.)
Each clause in a conditional is treated separately:
1. For each result clause a, write (k a).
2. For each recursive clause, pick the recursive call that will be evaluated first. Make the body for the new clause a recursive call which takes an extra argument, which is of the form (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 CPS-ing Pi*, we have made an explicit decision about the order of evaluation: specifically, that the right child will be traversed before the left.

Corky Cartwright / cork@cs.rice.edu