让 vs 在延续中定义用法

let vs define usage in continuations

我试图理解此示例中的 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 中捕获的延续将是 "Take the value, bind it to x" 因为那是 let 所做的但不是"apply the value of x"部分。

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

例如,define 按预期工作:

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

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

谁能解释一下 letdefine 在这种情况下的区别?

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

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

我希望它将 x 绑定到 1 并计算为 2,但它说它需要一个 过程.

编辑:我相信还有待完成的 work 实际上是 bind x 和 evaluate let 表达式也。在那种情况下,这是有道理的。此外,这意味着 (let ((x (call/cc (lambda (k) k)))) (+ (x 1) 1)) 永远无法工作。

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

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

call/cc 接受一个参数,一个接受一个参数的函数,并调用该函数。传递给它的参数(The continuation)本身是一个参数的函数,当被调用时,使 call/cc return 成为它的参数。如果从未调用该函数,则 call/cc return 的参数为 return 的任何值。所以...

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

此时,x 持有一个延续,当用一个值调用时,使 call/cc return 该值。即使 call/cc 已经退出,调用该延续也会使其再次跳转到该点。

(x (lambda (ignore) "hi")))

现在调用了 continuation,其中的 lambda(称为 A)接受一个参数和 returns "hi"。所以它跳回

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

并且 x 现在绑定到那个 lambda A,因为调用延续就像 call/cc 只是 return 编辑它。

(x (lambda (ignore) "hi")))

现在调用 x,即 A,忽略其参数,returns "hi"。使用 define 的示例以相同的方式工作:x 绑定到一个值,然后当调用该值时,x 绑定到一个新值,并使用该新值调用。

(let ((x (call/cc (lambda (k) k))))    ; binds x to the value of (call/cc ...)
    (x (lambda (ignore) "hi")))        ; applies x to the value of (lambda ...)

翻译为

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

变成

(let ((x #f))
  (set! x (lambda (ignore) "hi"))
  (x (lambda (ignore) "hi")))

和带 define 的代码翻译相同(为了解释 this 代码片段;internal,非顶级 defines).

letdefine 都计算表达式以找出变量绑定的值——这就是您所询问的,就好像它们在这方面有所不同一样。他们不是。

您的第三个代码段翻译为

(let ((x #f))
  (set! x (call/cc (lambda (k) k)))
  (+ (x 1) 1))

变成

(let ((x #f))
  (set! x 1)
  (+ (x 1) 1))

变成

(let ((x #f))
  (+ (1 1) 1))

TL; DR:definelet 之间的真正区别在于顶级程序表达式,因为 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))

letdefine 在一个过程中做类似的事情:

(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 中相同(虽然我省略了绑定的更新,因为阴影在这段代码中做同样的事情:

((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 理解它是如何工作的是很容易的。快乐黑客!