Hints About Exercise 6.31 of EOPL3

Question

I am reading EOPL 3rd edition. Now I am stuck on exercise 6.31.

Exercise 6.31 Write a translator that takes the output of cps-of-program and produces an equivalent program in which all the continuations are represented by data structures, as in chapter 5. Represent data structures like those constructed using define-datatype as lists. Since our language does not have symbols, you can use an integer tag in the car position to distinguish the variants of a data type.

I can't solve this one because I have no idea what the result program should look like. For example, consider the program below:

+(1, (f x), (g y))

After CPS we got the following program:

(f x
   (proc (v1)
      (g y
         (proc (v2)
            (proc (v0) v0)
             +(1, v1, v2)))))

Here, the procedure in the position K as in (f x K) is the continuation. The question is I have a very vague view on how the data structure version of K looks like. One possibility is:

(f x
   (call-cont g
              (y)
              (sum-cont 1
                        ?
                        (end-cont))))

However, because simple expressions are regarded as a whole, I don't know how to convert +(1, v1, v2) to something like sum-cont1, sum-cont2 as in chapter 5. As a result, I can only use a question mark ? in the data structure representation. Without knowing how the equivalent program looks like, it is impossible to solve this exercise for me. Could anyone please give some hints? Thanks!

Answer 1

You made a mistaken in your CPS transformation, check page 216 which shows that (cps-of-exp <<+((f x), 33, (g y))>> K) ends up being

(f x
   proc (v1)
      (g y
         proc (v2)
            (K +(v1, 33, v2))))

so

+(1, (f x), (g y))

would get transformed to

(f x
   proc (v1)
      (g y
         proc (v2)
            (K +(1, v1, v2))))

You had added (proc (v0) v0) and missed out K.

---

The task of turning it into data structures is to apply defunctionalization. Each procedure is replaced by a data structure. Look back to chapter 5 section 3 page 163 which covers an example of this. The apply-cont function turns the data structures back into continuation procedures.

In our case we want data structures to represent calling the functions f and g and one to represent calling the plus function with one value and 2 arguments. For the plus continuation we will require 2 values. The g continuation will put 2 values into its continuation and the f continuation will put one value into its continuation.

So like this:

(f-cont x (g-cont y (plus-ynn-cont 1 (exit-cont))))

with

(apply-cont (f-cont x k))
 = (apply-cont k (f x))

(apply-cont (g-cont y k) val)
 = (apply-cont k (g y) val)

(apply-cont (plus-ynn z k) val1 val2)
 = (apply-cont k (+ z val1 val2))

(apply-cont (exit-cont) val)
 = (print val)