8 Assignment 8: Registerization and Trampolining

Note

This assignment is going to be a relatively easy one since you also have to prepare for your mid-term exam and a9.

Answer the questions which mention briefly describe as racket comment (roughly in a paragraph or two) in your .rkt file.

Assignment

1. Consider the following definition of fibonacci.

   (define apply-k

   (λ (k v)

   (match k

   (`(make-inner-fib-k ,fib-sub1-n^ ,k^)

   (let* ((k k^)

   (v (+ fib-sub1-n^ v)))

   (apply-k k v)))

   (`(make-outer-fib-k ,n^ ,k^)

   (let* ((k (make-inner-fib-k v k^))

   (n (sub1 (sub1 n^))))

   (fib-cps n k)))

   (`(init-k) v))))

   (define make-inner-fib-k

   (λ (fib-sub1-n^ k^)

   `(make-inner-fib-k ,fib-sub1-n^ ,k^)))

   (define make-outer-fib-k

   (λ (n^ k^)

   `(make-outer-fib-k ,n^ ,k^)))

   (define init-k

   (λ ()

   `(init-k)))

   (define fib-cps

   (λ (n k)

   (cond

   ((zero? n)

   (let* ((k k)

   (v 1))

   (apply-k k v)))

   ((zero? (sub1 n))

   (let* ((k k)

   (v 1))

   (apply-k k v)))

   (else

   (let* ((k (make-outer-fib-k n k))

   (n (sub1 n)))

   (fib-cps n k))))))

   • Briefly describe about the style used/what is unique about this program when compared to the regular definition of fibonacci.

   • Registerize fib-cps. You should use the same name. In your submission, you should use the same function name as given above.

   • Give the correct invocation of fib-cps function that would return 8.

2. Given the following definition of times-cps:

   (define times-cps

   (λ (ls k)

   (cond

   [(null? ls) (k 1)]

   [(zero? (car ls)) (k 0)]

   [else (times-cps (cdr ls) (λ (times-cdr) (k (* (car ls) times-cdr))))])))

   (define empty-k

   (λ (jumpout)

   `(empty-k ,jumpout)))

   • Make times-cps Representation independent with respect to continuations. Use data-structure representation of continuations and trampolinize your program. In your trampolined version of times-cps, use empty-k as the initial continuation helper function. You should use the same function name as given above.

   • Run two different invocations of your function in bi-tramp (available in class notes).

Brainteaser

Let us take a little break from teasing our brains.

Just Dessert

No desserts for this week ;)