1

我目前在 OCaml 中为方案的子集编写编译器，并且无法理解如何使用延续进行编译。我发现了一些很棒的资源，即：

使用 anormal-paper 中介绍的异常转换，我现在有代码，其中函数调用要么绑定到变量，要么返回。

例子：

(define (fib n)
  (if (<= n 1)
      n
      (+ (fib (- n 1)) 
         (fib (- n 2)))))

变成：

(define (fib n)
  (let ([c (<= n 1)])
    (if c
        n
        (let ([n-1 (- n 1)])
          (let ([v0 (fib n-1)])
             (let ([n-2 (- n 2)])
               (let ([v1 (fib n-2)])
                 (+ v0 v1)))))))

为了进行 cps 转换，我现在必须：

  1. 为所有非原始函数添加 cont 参数
  2. 在尾部位置调用 cont 参数
  3. 转换所有非原始函数调用，使它们逃脱 let-binding 并成为一个额外的 lambda，其中前一个 let-bound 变量作为唯一参数，前一个 let-body 作为主体

结果将如下所示：

(define (fib n k)
  (let ([c (<= n 1)])
    (if c
        (k n)
        (let ([n-1 (- n 1)])
          (fib n-1 
            (lambda (v0) 
              (let ([n-2 (- n 2)]) 
                (fib n-2
                  (lambda (v1) 
                    (k (+ v0 v1))))))))))

这个对吗？

csmu 课程还讨论了 CPS 中的程序如何不需要堆栈并且永不返回。那是因为我们不需要保存要返回的地址，而闭包以及其他数据类型都存储在堆上，并且使用闭包使引用保持活动状态？

csmu 还谈到了 call/cc 的脱糖：

(call/cc) => ((lambda (k f) (f k k)))

使用这种脱糖时，如何：

(+ 2 (call/cc (lambda (k) (k 2))))

在 MIT-Scheme 返回 4 中，因为当前的延续可能类似于显示？

4

2 回答 2

1

这个对吗？

(define (fib n k)
  (let ([c (<= n 1)])
    (if c
        (k n)
        (let ([n-1 (- n 1)])
          (fib n-1 
            (lambda (v0) 
              (let ([n-2 (- n 2)]) 
                (fib n-2
                  (lambda (v1) 
                    (k (+ v0 v1))))))))))

你得到一个A+

csmu 课程还讨论了 CPS 中的程序如何不需要堆栈并且永不返回。那是因为我们不需要保存要返回的地址，而闭包以及其他数据类型都存储在堆上，并且通过使用闭包来保持引用保持活动状态？

确切地！有关这种技术的深入阅读，请参阅鸡肉编译过程。

csmu 还谈到了 call/cc 的脱糖：

(call/cc) => ((lambda (k f) (f k k)))

这看起来不太对劲。这是call/cc来自马特·梅特的脱糖-

call/cc => (lambda (f cc) (f (lambda (x k) (cc x)) cc))
于 2020-06-04T14:11:19.293 回答
0

使用延续编译的想法的本质是，您希望对传递给每个函数的参数的评估进行排序，并在评估该参数后将其值发送给传递的延续。

以 CPS 形式重写代码的语言要求是尾递归的，否则它将堆叠空帧，然后仅返回。如果实现语言不强制执行尾递归，则需要应用更复杂的方法来获取 cps 代码的非增长堆栈。

请注意，如果您这样做，您还需要更改原语的签名。原语也将传递一个延续，但它们会立即在传递的延续中返回答案，它们不会创建其他延续。

关于理解如何使用延续进行编译的最佳参考仍然是 Andrew W. Appel 的书，您不需要更多。

于 2020-06-05T09:48:45.813 回答