	Jupyter at Bryn Mawr College
Public notebooks: /services/public/dblank / CS245 Programming Languages / 2014-Fall / Assignments

Principles of Programming Languages¶

Blank, Fall 2012¶

Assignment #5: Call Stack Elimination¶

Due: Thursday, October 23, 2014 at beginning of class¶

This assignment is designed to:

Understand the limits of our language as it is so far
Explore continuations
Write functions in Continuation-Passing Style
Eliminate the need for a call stack

Recall the factorial function:

(define fact
  (lambda (n)
    (if (= n 1)
        1
        (* n (fact (- n 1))))))

(fact 5)

Let's take a look at the trace:

(define fact
  (trace-lambda "fact" (n)
    (if (= n 1)
        1
        (* n (fact (- n 1))))))

(fact 5)

We see that a value is returned, and then that result is used further. In other words, we have to multiply the result after the recursive call. The easiest way to handle this is to have a "call stack":

save where you are in the computation (push onto stack)
go off and compute (recursive) function
return, pop off the stack where you were
continue

When we use functions from other languages to implement Calc functions, we use a stack of function calls. Of course, for those languages that have a limited stack, this is a problem if we want to have the kinds of semantics/behavior that Scheme has.

Can we avoid the call stack? How to implement Scheme in a language that uses a call stack for functions?

The Big Idea: What if we could abstract all of the "computation that is left to do"? Then, we could do that computation without having to use a stack. Here, we introduce the idea of a continuation.

Continuations¶

To use the idea of a continuation, we will write functions in continuation-passing style (CPS). If we can write the evaluator in CPS, then we might be able to avoid the call stack problem.

To write and use functions in CPS:

add an extra parameter, k (for continuation), to each function in CPS
Whenever you get a result, "pass" it to the continuation (call the continuation with the result)
If you need to do some computation after the function call, create a new continuation, and do the rest of the computation in the continuation.

A continuation will be a function that takes a result, does anything that it needs to do to it, and pass that to the previous continuation.

This moves all recursion into tail call position.

CPS Examples¶

Follow these examples by reading the comments:

(define fact-cps
  (lambda (n k)             ;; first, add k as a parameter
    (if (= n 1)
        (k 1)               ;; if you get a result, pass it to the continuation
        (fact-cps (- n 1)   ;; since there is computation to do after the call
           (lambda (v)          ;; create a continuation, and do the rest
             (k (* v n)))))))   ;; don't forget to pass the result to the continuation

To start off the computation, we need to supply an initial continuation. This toplevel continuation doesn't have any further work to do, so it just returns the value. In other words, the initial continuation is the identity function.

(fact-cps 5 (lambda (i) i))

Let's see what the trace looks like:

(define fact-cps
  (trace-lambda "fact-cps" (n k)             ;; first, add k as a parameter
    (if (= n 1)
        (k 1)               ;; if you get a result, pass it to the continuation
        (fact-cps (- n 1)   ;; since there is computation to do after the call
           (lambda (v)          ;; create a continuation, and do the rest
             (k (* v n)))))))   ;; don't forget to pass the result to the continuation

(fact-cps 5 (lambda (i) i))

This trace is very different from the regular fact trace. Notice that when we return a value, there is nothing left to do, and no need for a "call stack"---there is no computation left to do after the return.

This is called "tail call optimization" (TCO). In many languages, including C in special circumstances, tail calls that just return can be recognized, and then optimized into assembly language that doesn't push the call onto the stack... it is realized that the function can just return what the recursive function returns.

In Scheme, this isn't an "optimization" but is how the language is designed. Note that if you make it an optional optimization, then you are saying that this code may or may not run! Crazy!

Let's consider member?, and write it in CPS:

(define member?
  (lambda (item lst)
    (cond
     ((null? lst) #f)
     ((eq? item (car lst)) #t)
     (else (member? item (cdr lst))))))

(define member?-cps
  (lambda (item lst k)
    (cond
     ((null? lst) (k #f))
     ((eq? item (car lst)) (k #t))
     (else (member?-cps item (cdr lst) k)))))

(member?-cps 'a '(b c a) (lambda (v) v))

This works, but is not interesting.

Problem 1: Why isn't member? interesting? Why didn't we create a continuation?

Let's write my-length as a regular recursive function and in CPS:

(define my-length
  (lambda (lst)
    (cond
     ((null? lst) 0)
     (else (+ 1 (my-length (cdr lst)))))))

(my-length '(1 2 3 4))

(define my-length-cps
  (lambda (lst k)
    (cond
     ((null? lst) (k 0))
     (else (my-length-cps (cdr lst)
              (lambda (v)
                (k (+ 1 v))))))))

(my-length-cps '(1 2 3 4) (lambda (v) v))

Let's write Fibonacci in CPS. First, the regular fib function.

(define fib
  (lambda (n)
    (cond
     ((= n 0) 1)
     ((= n 1) 1)
     (else (+ (fib (- n 1))
              (fib (- n 2)))))))

(define fib-cps
  (lambda (n k)
    (cond
     ((= n 0) (k 1))
     ((= n 1) (k 1))
     (else (fib-cps (- n 1)
             (lambda (v1)
               (fib-cps (- n 2)
                 (lambda (v2) 
                    (k (+ v1 v2))))))))))

This is interesting because it has two recursive calls, both of which need to be put into tail call positions. We do that by putting the second one in the continuation of the first.

(fib-cps 5 (lambda (i) i))

Problem 2: re-write 6 different recursive functions (perhaps from homework or the first exam) in CPS form. Make sure that these are not trivial (like member?) but are functions that require the creation of a continuation. Test them to make sure that they work.

Wait! This doesn't help!¶

However, this doesn't yet help... we are still using recursion, and the host language (e.g., Python, Java, C, etc.) still must have a call stack.

But, now that we have abstracted the "computation left to do", let's see if we can "factor out" the recursive function calls. That is, we move the recursive function calls out from inside the CPS functions.

Let's make these changes:

We define apply-cont to apply a continuation to a result
We define make-cont to wrap the procedure

;; tag a continuation, like define-datatype does:

(define make-cont
  (lambda (f)
    (list 'continuation f)))

;; Is it a tagged continuation?

(define continuation?
  (lambda (item)
    (and (list? item) 
         (> (length item) 0)
         (eq? (car item)
              'continuation))))

;; Be able to apply it, like before:

(define apply-cont
  (lambda (k v)
    (if (continuation? k)
        ((cadr k) v)
        (error 'apply-cont "invalid continuation: ~a" k))))

Now, we can use these and re-write my-length:

(define my-length-cps
  (lambda (lst k)
    (cond
     ((null? lst) (apply-cont k 0))
     (else (my-length-cps (cdr lst)
              (make-cont (lambda (v)
                            (apply-cont k (+ 1 v)))))))))

(my-length-cps '(1 2 3 4) (make-cont (lambda (v) v)))

That is nice, but it didn't change anything!

However, rather than applying the continuation to the result, let's just return the function representing the rest of the computation and the result in a list:

(define apply-cont
  (lambda (k v)
    (if (continuation? k)
        (list k v)           ;;; WE CHANGED THIS LINE!
        (error 'apply-cont "invalid continuation: ~a" k))))

Now, when we attempt to run the function, we get a partial result, and a continuation representing what is left to do:

(my-length-cps '(1 2 3 4) (make-cont (lambda (v) v)))

Problem 3: Explain what we have at this point.

We could then apply that continuation to the result:

(define result (my-length-cps '(1 2 3 4) (make-cont (lambda (v) v))))

result

(apply (cadar result) (cdr result))

We could continue until there are no continuations left.

Problem 4: Keep applying the continuations until you get an answer.

Problem 5: Re-write the 6 functions to use your new continuation functions. Test them all to make sure that they work.

What can you do with these continuations?¶

At this point, you could:

save the continuation (say, to a file), and continue the continuation later. How would that be useful?
do the computation again; why?
create a debugger; how?
go back in time; how?
interleave the continuations from different computations in a particular order (prioritize some, or evenly execute); why? what would this be useful for?

Problem 6: Explain each of these ideas and answer the related questions. Can you think of other ideas you could use continuations for?

But how does this help eliminate the call stack?¶

To get rid of the call stack completely, we introduce the idea of a trampoline). A trampoline is a method where continuations are bounced inside a loop, rather than recursive calls that go deeper and deeper.

Here is a version of a trampoline for our continuations:

(define trampoline
  (lambda (result)
    (let loop ((result result))
      (if (and (list? result) 
               (> (length result) 0)
               (continuation? (car result)))
          (loop (apply (cadar result) (cdr result)))
          result))))

(trampoline (my-length-cps '(1 2 3 4) (make-cont (lambda (v) v))))

No call stack!

Problem 7: Explain how we could use these ideas in our language Calc.

For further reading, see:

Jupyter at Bryn Mawr College