代码之家 › 专栏 › 技术社区 › Zelphir Kaltstahl

程序开始时的当前延续

continuations racket scheme

2

Zelphir Kaltstahl · 技术社区 · 8 年前

创建返回过程显然是使用continuations可以创建的常见示例,如下例所示:

(define (find-multiple factor)
  (let/cc return
    (for ([num (shuffle (range 2000))])
      (when (zero? (modulo num factor))
        (return num)))))

(find-multiple 43)

(来自 https://beautifulracket.com/explainer/continuations.html#what-are-they-good-for )

虽然我有点理解,开始时的continuation是返回到从某个值调用过程的位置,但我不知道continuation实际上是什么样子。在以下示例中,我可以想象它是什么样子:

(define c #f)
(+ 1 (+ 2 (+ 3 (+ (let/cc here (set! c here) 4) 5)))) ; 15
(c 20) ; 31

续页为:

(lambda (something)
  (+ 1 (+ 2 (+ 3 (+ something 5))))

所以这个表达式被包装在一个lambda中 let/cc 替换为lambda的输入参数。

但对于返回过程,我不知道正确的思考方式是什么,以及继续到底是什么样子。

1 回复 | 直到 8 年前

1

3

Sylwester 8 年前

首先 let/cc 只是语法糖 call/cc . 这些是相等的:

(let/cc here 
  (set! c here) 4)

(call/cc 
 (lambda (here) 
   (set! c here) 4))

所有代码,无论您如何编写,都将以特定的方式运行,每个操作将执行一个步骤,然后调用程序其余部分的继续。这是:

(define c #f)
(+ 1 (+ 2 (+ 3 (+ (let/cc here (set! c here) 4) 5)))) ; 15
(c 20) ; 31

变成这样:

((lambda (c k)
   (call/cc&
    (lambda (here k)
      (set! c here)
      (k 4))
    (lambda (v)
      (+& v 5 (lambda (a1)
                (+& 3 a1 (lambda (a2)
                           (+& 2 a2 (lambda (a3)
                                      (+& 1 a3 (lambda (a4)
                                                 (c 20 k))))))))))))
 #f values)

现在请注意,这里的顺序是显式的,令人惊讶的是,最深的表达式是首先处理的,因为所有其他表达式都取决于首先计算的值。还要注意,续集包括对 (c 20) ,每次。

以下是所用程序的CPS版本:

(define (+& a b k)
  (k (+ a b)))

(define (call/cc& f k)
  (f (lambda (v ign-k) (k v)) k))

最后一个可能是 呼叫/抄送 你见过的。虽然代码中的那个似乎很神秘,因为代码不是连续传递样式,但在方案系统将其设置为CPS之后 呼叫/抄送 甚至都不会被认为是原始的。

对于 (find-multiple 43) continuation就是显示结果的REPL。如果你在这样的地方用过 (+ 1 (find-multiple 43)) 那么延续就是 (lambda (v) (+& 1 v halt))

编辑

一个更简单的示例:

(let ((x (read)))
  (display 
   (call/cc 
    (lambda (return)
      (- 4 (if (< x 4) x (return 10))))))))

现在,当您运行此操作并输入低于4的值时 呼叫/抄送 part没有被使用,但如果它没有注意到这发生在它应该做的下一件事是从 4 . 在CPS中,它如下所示:

(read&
 (lambda (x)
   (call/cc& 
    (lambda (return& k)
      (define (k- v)
        (-& 4 v k))
      (<& x 4 (lambda (p)
                (if p
                    (k- x)
                    (return& 10 k-)))))                          
    (lambda (v)
      (display& v values)))))

这里是&-程序。这些可能已经开始变得熟悉,并有望预测:

(define (<& a b k) (k (< a b)))
(define (-& a b k) (k (- a b)))
(define (display& v k) (k (display v)))
(define (read& k) (k (read)))