scheme - 哪个最简单的评估模型可以解释 call/cc？

Question

TL;DR: call/cc 做什么，（半）正式地说？

长版：我对延续和 call/cc 隐约熟悉，但对形式的理解并不强。我想要一个。

在SICP 视频讲座中，我们看到了替代模型和元循环解释器。在 Shriram Krishnamurti 的编程语言课程中，我们看到了一种环境和商店传递风格。在我参加 uni 的编译器课程中，我通过操作堆栈来评估 Java 表达式。

最简单的可以表达 call/cc 的评估模型是什么，如何在其中表达 call/cc？

标签： schemesemanticsevaluationinterpretationcallcc

Answer 1

TL;DRcall/cc允许您利用 Schemes 内部代码，以便您可以使用延续，而无需以延续传递样式编写代码。最好的评估模型是替代模型，因为您不使用set并从 CPS 代码中查看它

想象一下这个小程序。

(define (sum-list lst)
  (cond ((null? lst) 0)
        ((number? (car lst)) (+ (car lst) (sum-list (cdr lsr))))
        (else (sum-list (cdr lsr)))))

(display (sum-list '(1 2 3 4))) ; displays 10

1337想象一下，如果你达到这个else词，你希望结果是这样的。如果不重写整个事情，你会怎么做？你不能。然而，大多数 Scheme 实现都会将 CPS 转换为您的代码，而更改它是微不足道的：

(define (sum-list& lst k)
  (null?& lst
          (lambda (nlst?)
            (if& nlst?
                 (lambda ()
                   (k 0))
                 (lambda ()
                   (car& lst
                         (lambda (car-lst)
                           (number?& car-lst
                                     (lambda (ncl?)
                                       (if& ncl?
                                            (lambda ()
                                              (cdr& lst
                                                    (lambda (clst)
                                                      (sum-list& clst
                                                                 (lambda (sclst)
                                                                   (+& car-lst sclst k))))))
                                            (lambda ()
                                              (cdr& lst
                                                    (lambda (clst)
                                                      (sum-list& clst k))))))))))))))
(sum-list& '(1 2 3 4)
           (lambda (sum)
             (display& sum halt)))

cond是一个宏，所以它是if&你看到的调用。我知道你在想什么。为什么不首先告诉程序员这样做呢？只是在开玩笑！

如果您将第二个延续中的第二个更改if&为(lambda () (k 1337))您就完成了。和 CPS 一样漂亮，它的读写是可怕的，但是既然编译器这样做了，就不能有一种方法能够以第一种方式编写代码并仍然获得代码控制流吗？两全其美是启用的call/cc。call/cc这是在 CPS 中：

(define (call/cc& f& continuation)
  (define (exit& value actual-continuation)
    (continuation value))
  (f& exit& continuation))

它根本没有多大作用。它通过exit&了，它在调用时忽略程序的真正延续，并使用调用的原始延续来call/cc&调用值。使用该列表'(1 2 3 #f)，您将有 3 个嵌套的延续等待添加结果，但所有这些都需要取消。如果您在计算之前选择延续的值，它会自动取消。就是这样。当你用它编写代码时，你不需要做完整的 CPS，只需要call/cc像这样想的延续：

(define (sum-list lst)
  (call/cc
   (lambda (k)
     (define (helper lst)
       (cond ((null? lst) 0)
             ((number? (car lst))
              (+ (car lst) (helper (cdr lst))))
             (else (k 1337))))
     (helper lst))))

这在 CPS 中被转换为：

(define (sum-list& lst k)
  (call/cc&
   (lambda (k& real-k)
     (define (helper& lst k)
       (null?& lst
               (lambda (nlst?)
                 (if& nlst?
                      (lambda ()
                        (k 0))
                      (lambda ()
                        (car& lst
                              (lambda (car-lst)
                                (number?& car-lst
                                          (lambda (ncl?)
                                            (if& ncl?
                                                 (lambda ()
                                                   (cdr& lst
                                                         (lambda (clst)
                                                           (helper& clst
                                                                    (lambda (sclst)
                                                                      (+& car-lst sclst k))))))
                                                 (lambda ()
                                                   (k& 1337 real-k))))))))))))
     (helper& lst real-k))
     k))


(sum-list& '(1 2 3 4)
           (lambda (sum)
             (display& sum halt)))

call/cc总是可以避免的。我们的示例可以重写为返回 1337，如下所示：

(define (sum-list lst)
  (define (helper lst sum)
    (cond ((null? lst) sum)
          ((number? (car lst)) (helper (cdr lst) (+ sum (car lst))))
          (else 1337)))
  (helper lst 0))

这是尾递归，而不是创建延续它累积。为了完整起见，这里是它的 CPS 版本：

(define (helper& lst sum k)
  (null?& lst
          (lambda (nlst)
            (if& nlst
                 (lambda () (k sum))
                 (lambda ()
                   (car& lst
                       (lambda (cl)
                         (number?& cl
                                 (lambda (ncl?)
                                   (if& ncl?
                                        (lambda ()
                                          (cdr& lst
                                                (lambda (cdrl)
                                                  (+& sum
                                                      cl
                                                      (lambda (scl)
                                                        (helper& cdrl
                                                                 scl
                                                                 k))))))
                                        (lambda () (k 1337))))))))))))


(define (sum-list& lst k)
  (helper& lst 0 k))