1

我正在尝试了解 Scheme 中的 call/cc 运算符。我计划在我的 JavaScript lisp 中实现它。这是我的简单代码：

(letrec ((x 0)
         (f (lambda (r)
                (set! x r)
                (display (r 20))
                (display "10"))))
   (display (call/cc f))
   (x "30"))

我坚持它应该打印 20 然后 30 然后 10。但它会创建无限循环（它会继续打印 30）。这段代码应该如何显示 3 个值，调用 display 3 次？

是否可以创建不消耗堆栈和延续的循环？

我找到了一些关于堆栈溢出的例子，但是这个根本不起作用：

(define x 0) ; dummy value - will be used to store continuation later

(+ 2 (call/cc (lambda (cc)
                (set! x cc)  ; set x to the continuation cc; namely, (+ 2 _)
                3)))         ; returns 5

(x 4) ; returns 6

它用 100% CPU 冻结了 guile 解释器，它看起来正在等待输入。

4

1 回答 1

0

您是否 lisp 实现将用户代码转换为继续传递样式？在这种情况下，这很容易。call/cc这是：

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

查看您的第一个代码，我认为它变成了这样：

((lambda (x k)
   ((lambda (f k)
      (call/cc& f (lambda (v) ; continuation a
                    (display& v (lambda (_) ; continuation b
                                  (x "30" k))))))
    (lambda (r k)
      (set!& x r (lambda (_) ; continuation c
                   (r 20 (lambda (v) ; continuation d
                           (display& v (lambda (_) ; continuation e
                                         (display& "10" k))))))))
    k)
   0
   halt)

这是发生了什么：

  • 我们制作x和f
  • call/cc&来电f
  • x设置为r（续a）
  • r 以 20 作为值被调用
  • 延续 c 被忽略，而是用 20 调用延续 a
  • 显示 20，然后调用延续 b
  • xb用“30”调用
  • 延续 k 被忽略，而是用 30 调用延续 a
  • 30 被显示，然后继续 b 被调用
  • 转到“b调用x”30行并继续

所以打印“20”，然后“30”永远似乎是这段代码的正确结果。重要的是要注意它永远不会显示"10"，因为它调用r并传递了延续，但它被绕过到call/cc原始延续，即延续 a。

至于实现。以前，所有 Scheme 实现都只是将代码转换为继续传递样式是很常见的，但今天更常见的是只做需要的部分。例如。Ikarus 不做 CPS，但为了call/cc工作，它需要做，直到下一个继续提示。

一开始最好call/cc不要突变。例如。

(+ 2 (call/cc (lambda (exit)
                (+ 3 (* 5 (exit 11))))))

现在变成：

(call/cc& (lambda (exit k)
            (exit 11 (lambda (v)
                       (*& 5 v (lambda (v)
                                 (+& 3 v k))))))
          (lambda (v)
            (+& 2 v repl-display)))

现在我们知道exit被调用了，因此整个事情变成了：

((lambda (v) (+& 2 v repl-display)) 11)

其中显示13. 现在将延续作为最后一个论点在纸上看起来不错。在想要支持可变参数的实现中，最好将延续作为第一个参数。

所有的延续都是尾调用，因此堆栈永远不会增长。事实上，如果使用完整的 CPS，您将永远不必返回。所有有趣的东西总是传递给下一个调用，直到程序停止。

于 2019-04-22T22:45:57.387 回答