时间戳

首页 > 解决方案 > 方案：继续编译

functional-programming - 方案：继续编译

问题描述

我目前在 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 中，因为当前的延续可能类似于显示？

标签： functional-programmingcompiler-constructionscheme

解决方案

这个对吗？

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

推荐阅读