UNB/ CS/ David Bremner/ teaching/ cs4613/ tutorials/ Lab Tutorial 08

Continuation passing style

In Lecture 16 we briefly discussed continuation passing style where each function takes an extra argument for the closure to be called instead of returning. While tedious to write, this style is sometimes generated by compilers, and allows the same kind of tricks as let/cc, without language support for continuations.

Handin this weeks tutorial via the handin server, by 16:30 on Wednesday.

CPS Fibonacci

Complete the following continuation passing style Fibonacci function

(define (fib/k n l)
  (cond
    [(<= n 1) (l 1)]
    [else (fib/k (- n 1)
                 (lambda (v) ....))]))

(define (fibSecondK v n next-l)
  (fib/k (- n 2) (lambda (second-v) ....)))

Your solution should pass the following tests

(define (fib n)
  (cond
    [(<= n 1) 1]
    [else (+ (fib (- n 1)) (fib (- n 2)))]))

(test (fib/k 0 identity) 1)
(test (fib/k 3 (lambda (x) (fib/k x identity))) 3)
(test (fib/k 4 (lambda (x) "hello")) "hello")
(test (fib/k 5 (lambda (x) (list 5 x))) '(5 8))
(test (fib 10) (fib/k 10 identity))
(test (fib/k 10 (lambda (x) 3)) 3)
(test (fib 12) (fib/k 10 (lambda (x) (+ (fib 11) x))))
(test (fib 15) (fib/k 15 identity))
(test (fib 23) (fib/k 23 identity))
(test (fib 30) (fib/k 30 identity))