Continuations

Practice converting simple functions to CPS. (Use Java).

What is the value of each of the following expressions:

(+ 1 (call/cc (lambda (k) (* 2 (k (k (k 3)))))))
(let ((x (call/cc (lambda (k) (k 3))))) (+ x x))

(+ 1 (call/cc (lambda (k1) 
        (+ 2 (call/cc (lambda (k2) 
                (+ 3 (call/cc (lambda (k3) 
                        (+ 4 (call/cc (lambda (k4) 
                               (k4 (k3 (k2 (k1 100))))))))))))))))

Java Semantics

Be prepared to trace Java fragments including small class hierarchies. Make sure you understand how environments and stores enter the picture in Java. Make sure you clearly understand how inheritance, variable shadowing, and method overriding interact.

Here are some of the Scheme expressions from the midterm re-written in Java. Make sure you can trace them.

And here some examples testing your understanding of inheritance.

Interpreters

For the midterm review, I posted a couple of hard problems Robot and HTML. A very good exercise encompassing much of the important concepts you need to understand is to take the solutions, convert them to Java using visitors, and then convert them to CPS.

Challenge Problem but very instructive

Here is the code for the "same fringe" problem in Scheme. This problem asks you to compare the leaves of two trees (that may have different structures) without traversing the entire trees. In other words it should stop immediately as soon as two leaves are different. The challenge is to rewrite the code in Java. Here is my solution which does not use inner classes but rather builds closures manually.