方案：继续编译

Question

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

• cmsu编译器课程的cps幻灯片：https://www.cs.umd.edu/class/fall2017/cmsc430/
• 关于另一个CS课程的说明：https://www.cs.utah.edu/~mflatt/past-courses/cs6520/public_html/s02/cps.pdf
• Matt Mights以标准格式和cps发布帖子：http://matt.might.net/articles/a-normalization/和http://matt.might.net/articles/cps-conversion/

使用在普通纸中引入的普通变换，我现在有了将函数调用绑定到变量或返回的代码。

示例：

(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. 调用尾部位置的连续参数
3. 转换所有非原始函数调用，以使它们逃脱let绑定，并以以前的let-bound变量作为唯一参数和前面的let-body成为额外的lambda。作为身体

结果看起来像：

(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还讨论了取消呼叫/ cc的方式：

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

使用此类减半缩法时，如何做：

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

在MIT方案中返回4？

Answer 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 +💯