关于 EOPL3 练习 6.31 的提示

Question

我正在阅读EOPL 3rd edition。现在我卡在练习 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.

我无法解决这个问题，因为我不知道结果程序应该是什么看起来像。例如，考虑下面的程序：

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

CPS后得到如下程序：

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

这里，K位置和(f x K)位置的过程是接续。这问题是我对 K 的数据结构版本的看法非常模糊看起来像。一种可能性是：

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

但是因为简单的表达式被看成一个整体，所以不知道如何将 +(1, v1, v2) 转换为 sum-cont1、sum-cont2 之类的东西，如 chapter 5. 结果我只能在数据结构中用问号? 表示。不知道等效程序的样子，它是不可能为我解决这个练习。任何人都可以给一些提示吗？谢谢！

Answer 1

您在 CPS 转换中犯了一个错误，请查看第 216 页，其中显示 (cps-of-exp <<+((f x), 33, (g y))>> K) 最终成为

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

所以

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

会变成

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

您添加了 (proc (v0) v0) 并错过了 K。

将其转化为数据结构的任务是应用去功能化。每个过程都由一个数据结构代替。回顾第 5 章第 3 节第 163 页，其中介绍了一个示例。 apply-cont 函数将数据结构转回继续过程。

在我们的例子中，我们希望数据结构表示调用函数 f 和 g，一个表示调用带有一个值和 2 个参数的 plus 函数。对于加号延续，我们将需要 2 个值。 g continuation 会将 2 个值放入其 continuation，而 f continuation 会将 1 个值放入其 continuation。

像这样：

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

与

(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)

关于 EOPL3 练习 6.31 的提示

Hints About Exercise 6.31 of EOPL3

interpreter

programming-languages

continuation-passing