scheme - 让 vs 定义延续中的用法

Question

我试图理解此示例中的call/cc执行:

(let ((x (call/cc (lambda (k) k))))
    (x (lambda (ignore) "hi")))

给出值“hi”。

doc 中描述了执行过程如:

Take the value, bind it to x, and apply the value of x to the value of (lambda (ignore) "hi").

我可以理解 let 中捕获的延续将是“获取值，将其绑定(bind)到 x”，因为这是 let 所做的事情，而不是“应用x"部分的值。

所以我期望输出只是绑定(bind) x 到(lambda (ignore) "hi") 而不是应用它。

例如，define按预期工作:

(define x (call/cc (lambda (k) k)))
(x (lambda (ignore) "hi"))

它定义 x作为该值，但不应用它。

有人可以解释一下这种情况下let和define之间的区别吗？

对此的解释可能也有助于理解正在发生的事情:

(let ((x (call/cc (lambda (k) k)))) (+ (x 1) 1))

我期望它将x绑定(bind)到1并且只求值为2，但它说它需要一个过程。

编辑:我相信剩下要做的工作实际上是绑定(bind) x并评估 let> 表达也。在这种情况下，这是有道理的。另外，这意味着 (let ((x (call/cc (lambda (k) k)))) (+ (x 1) 1)) 永远无法工作。

编辑:确实，这就是它的工作原理。您可以观看this解释此示例的视频。我认为它可以非正式地概括为“let”比“define”更重要，因为它也必须执行表达式。

Answer 1

TL; DR:define 和 let 之间的真正区别在于顶级程序表达式，因为 define 只能在标识符上执行一次，并且通常有顶级语句之间的延续提示。

我将在这个答案中使用 CPS。我使用的常见过程的定义是:

;; returns argument
(define halt values) 

;; call/cc in CPS version
(define (call/cc-k f k)
  (f (lambda (v k-ignore) (k v)) k))

过程中的

let 和 define 执行类似的操作:

(let ()
  (define x (call/cc (lambda (k) k)))
  (x (lambda (ignore) "hi")))

; ==

(let ()
  (letrec ((x (call/cc (lambda (k) k)))
    (x (lambda (ignore) "hi")))

同样的 let 变为:

(let ()
  (let ((x 'undefined))
    (set! x (call/cc (lambda (k) k)))
    (x (lambda (ignore) "hi"))))

在 CPS 中也是如此(尽管我省略了绑定(bind)的更新，因为阴影在此代码中执行相同的操作:

((lambda (x k)
   (call/cc-k
    (lambda (k2 real-k) (real-k k2))
    (lambda (x)
      (x (lambda (ignore k2) (k2 "hi")) k))))
 'undefined halt)

;; ===

((lambda (x k)
   ((lambda (f5 k5) (f5 (lambda (v k-ignore) (k5 v)) k5))
    (lambda (k3 real-k) (real-k k3))
    (lambda (x)
      (x (lambda (ignore k2) (k2 "hi")) k))))
 'undefined halt)

;; ===

((lambda (x k)
   (define hi-k (lambda (x) (x (lambda (ignore k2) (k2 "hi")) k)))
   ((lambda (f5 k5) (f5 (lambda (v k-ignore) (k5 v)) k5))
    (lambda (k3 real-k) (real-k k3))
    hi-k))
 'undefined halt)


;; === this is starting to look like a combinator :-)

((lambda (x k)
   ((lambda (ignore k2) (k2 "hi"))
    (lambda (ignore k2) (k2 "hi")) k))
 'undefined halt)

;; ===

((lambda (x k)
   (k "hi"))
 'undefined halt)

;; ===

(halt "hi")

虽然您的 let 版本执行此操作:

(let ((x (call/cc (lambda (k) k))))
    (x (lambda (ignore) "hi")))


;;; === in terms of lambda instead of let

((lambda (x)
   (x (lambda (ignore) "hi")))
 (call/cc (lambda (k) k)))


;;; === in CPS

(call/cc-k
 (lambda (k real-k) (real-k k))
 (lambda (x)
   (x (lambda (ignore k2) (k2 "hi")) halt)))

;;; ===

(define hi-k (lambda (x) (x (lambda (ignore k2) (k2 "hi")) halt)))
((lambda (k real-k) (real-k k)) (lambda (v k-ignore) (hi-k v)) hi-k))


;;; ===

((lambda (ignore k2) (k2 "hi"))
 (lambda (ignore k2) (k2 "hi"))
 halt)

;;; ===

(halt "hi")

顶级中使用的

define有很大不同，并且由于define不能在无效的Scheme代码中对同一变量执行两次代码顶级评价。为了弥补这一点，我想我们将其重写为:

(define x #f)
(set! x (call/cc (lambda (k) k)))
(x (lambda (ignore) "hi"))

我将跳过define并在延续中编写CPS:

(call/cc-k
 (lambda (k real-k) (real-k k))
 (lambda (v)
   (set!-k x
           v
           (lambda (undefined)
             (x (lambda (ignore k2) (k2 "hi")) halt)))))

;;; ===

(define set-k (lambda (v)
                (set!-k x
                        v
                        (lambda (undefined)
                          (x (lambda (ignore k2) (k2 "hi")) halt)))))
(call/cc-k
 (lambda (k real-k) (real-k k))
 set-k)

;; ===

(define set-k (lambda (v)
                (set!-k x
                        v
                        (lambda (undefined)
                          (x (lambda (ignore k2) (k2 "hi")) halt)))))
((lambda (k real-k) (real-k k))
 (lambda (v k-ignore) (set-k v))
 set-k)


;; ===

(define set-k (lambda (v)
                (set!-k x
                        v
                        (lambda (undefined)
                          (x (lambda (ignore k2) (k2 "hi")) halt)))))
(set-k (lambda (v k-ignore) (set-k v)))

;; ===

(define set-k (lambda (v)
                (set!-k x
                        v
                        (lambda (undefined)
                          (x (lambda (ignore k2) (k2 "hi")) halt)))))
(set!-k x
        (lambda (v k-ignore) (set-k v))
        (lambda (undefined)
          (x (lambda (ignore k2) (k2 "hi")) halt)))

;; ===

(set!-k x
        (lambda (v k-ignore) (set-k v))
        (lambda (undefined)
          ((lambda (v k-ignore) (set-k v)) (lambda (ignore k2) (k2 "hi")) halt)))

;; ===

(set!-k x
        (lambda (v k-ignore) (set-k v))
        (lambda (undefined)
          (set!-k x
                  (lambda (ignore k2) (k2 "hi"))
                  (lambda (undefined)
                    (x (lambda (ignore k2) (k2 "hi")) halt)))))

;;; ===

(set!-k x
        (lambda (v k-ignore) (set-k v))
        (lambda (undefined)
          (set!-k x
                  (lambda (ignore k2) (k2 "hi"))
                  (lambda (undefined)
                    ((lambda (ignore k2) (k2 "hi")) (lambda (ignore k2) (k2 "hi")) halt)))))


;;; ===

(set!-k x
        (lambda (v k-ignore) (set-k v))
        (lambda (undefined)
          (set!-k x
                  (lambda (ignore k2) (k2 "hi"))
                  (lambda (undefined)
                    (halt "hi")))))

;;; ===

(halt "hi")

但这很奇怪，因为如果你尝试这样做，你可能什么也得不到。其原因是顶级表达式由连续提示分隔。因此，call/cc 对每个顶级语句捕获的延续是 halt，而不是程序的其余部分。让我们尝试一下:

(call/cc-k
 (lambda (k real-k) (real-k k)) 
 (lambda (v)
   (set!-k x
           v
           halt)))

(x (lambda (ignore k2) (k2 "hi")) halt)

;; ===

(define set-k
  (lambda (v)
   (set!-k x
           v
           halt)))
((lambda (k real-k) (real-k k)) (lambda (v k-ignore) (set-k v)) set-k)
(x (lambda (ignore k2) (k2 "hi")) halt)

;; ===

(set-k (lambda (v k-ignore) (set-k v)))
(x (lambda (ignore k2) (k2 "hi")) halt)

;; ===

((lambda (v)
   (set!-k x
           v
           halt))
 (lambda (v k-ignore) (set-k v)))
(x (lambda (ignore k2) (k2 "hi")) halt)

;; ===

(set!-k x (lambda (v k-ignore) (set-k v)) halt)
(x (lambda (ignore k2) (k2 "hi")) halt)

;; ===

(set!-k x (lambda (v k-ignore) (set-k v)) halt)
((lambda (v k-ignore) (set-k v))
 (lambda (ignore k2) (k2 "hi"))
 halt)

;; ===

(set!-k x (lambda (v k-ignore) (set-k v)) halt)
(set-k (lambda (ignore k2) (k2 "hi")))

;; ===

(set!-k x (lambda (v k-ignore) (set-k v)) halt)
((lambda (v)
   (set!-k x
           v
           halt))
 (lambda (ignore k2) (k2 "hi")))

;; ===

(set!-k x (lambda (v k-ignore) (set-k v)) halt)
(set!-k x (lambda (ignore k2) (k2 "hi")) halt)

由于延续提示，完整的延续不会被执行，代码真正做的唯一事情就是设置x两次。

你的最后一个例子不起作用，因为x在延续和数字之间切换。

(let ((x (call/cc (lambda (k) k))))
  (+ (x 1) 1))

;; in CPS

(call/cc-k
 (lambda (k real-k) (realk k))
 (lambda (x)
   (x 1 (lambda (v1)
          (+-k v1 1 halt)))))

;; ===

(define k (lambda (x)
            (x 1 (lambda (v1)
                   (+-k v1 1 halt)))))
((lambda (k real-k) (realk k))
 (lambda (v k-ignore) (k v))
 k)


;; ===

(define k (lambda (x)
            (x 1 (lambda (v1)
                   (+-k v1 1 halt)))))
(k (lambda (v k-ignore) (k v)))

;; ===

((lambda (x)
   (x 1 (lambda (v1)
          (+-k v1 1 halt))))
 (lambda (v k-ignore) (k v)))


;; ===

((lambda (v k-ignore) (k v))
 1
 (lambda (v1)
   (+-k v1 1 halt)))

;; ===

(k 1)

;; ===

((lambda (x)
            (x 1 (lambda (v1)
                   (+-k v1 1 halt))))
 1)


;; ===
(1 1 (lambda (v1) (+-k v1 1 halt)))

ERROR: 1 is not a procedure!

YMMV，因此所有这些可能都是噪音，但是当您得知 call/cc 时，您只需查看代码的 CPS 版本，而不必编写 CPS，理解它的工作原理非常容易。快乐黑客!