Jupyter at Bryn Mawr College |
|||
Public notebooks: /services/public/dblank / CS245 Programming Languages / 2014-Fall / Assignments |
This assignment is designed to:
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":
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.
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:
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.
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.
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:
;; 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.
At this point, you could:
Problem 6: Explain each of these ideas and answer the related questions. Can you think of other ideas you could use continuations for?
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: