理解call/cc

By guenchi at 2019-05-08 • 1人收藏 • 305人看过

理解call/cc

第一次见call/cc,顿时懵逼。百思不得其解。

后来想明白了,发现大多数网上的讲解有误。属于生拿结果套解法,看起来没有错,但是顺着这个错误的思路,就死活理解不了。

比如以下的程序:

(+ (*
    (call/cc 
        (lambda (c)
            (+ (c 2) 3))) 5) 8)

一般网上的讲解是这样的,call/cc内部的lambda参数c一旦调用,就忽略掉下一条语句(+ 3),直接返回到call/cc处,所以等价于代码

(+ (* 2 5) 8)

得出18。

看起来一切都很美好,代码跑起来也符合18的结果。但是,让你接着理解,使用call/cc,就懵逼了吧。因为跟着错误的思路,你根本无法理解它的用处。

比如 (set! this c),这是什么鬼。

以下是正确理解的思路:

call/cc表达式,提取当前位置的延续。

那么,上一个例子,可以先简化为

(+ (* (call/cc …)5) 8)

什么叫当前位置的延续呢?

比如

(+ (* x 5) 8)

对于x来说,它的延续就是它将要被做的事。这里就是,*5然后+8。

这个延续如何用代码表示呢?

(lambda (k)
    (+ (* k 5) 8))

那么对于x 也就是(call/cc …)的延续就是

(lambda (k)
    (+ (* k 5) 8))

现在来看(call/cc ...)语句内部,当call/cc取得当前位置的延续后,它需要一个回调函数来使用这个延续。对吧?因为从这里控制流开始向回调函数处跳转,而不是返回到(call/cc ...)所在的当前栈。

也就是说,(+ (* (call/cc …)5) 8) 的加法和乘法是永远也不会执行的!从call/cc开始,就走了,走了,永远也不回来了。去哪了,去(call/cc f)的回调函数f那里了。

这就是网上通常解释的错误之处,解释成(call/cc ...)表达式的结果,去执行(+ (* x 5) 8)了。因为这里有一个陷阱,(call/cc ...)在这里太容易看成是求值结果得到x,然后值x被带入(+ (* x 5) 8)求值了。因为这是call/cc于scheme例程所格格不入的地方。

然后来看回调函数f:

(lambda (c)
    (+ (c 2) 3))

f被以call/cc得到的延续为参数调用,同时这个延续也作为f的回调函数,请注意后一点。

参数c在这里带入

(lambda (k)
    (+ (* k 5) 8))

那么回调函数f在这里的求值就是:

((lambda (c)
    (+ (c 2) 3)) 
(lambda (k)
    (+ (* k 5) 8)))

注意 这里的求值是永远不会被返回的。(普通scheme程序这里会得到21)

因为回调函数f,在求值时将控制流传递给了它的回调函数c,如果使用有return的语言来表达的话。

var f = function(c){
    var x = c(2);
    return x;
    x+3;
}

x+3是永远不会执行的。

这样的返回方式是call/cc的特殊之处,正是这样,它才能暴露出整个程序的控制流。

所以整个程序的求值返回了

((lambda (c)
    (c 2))
(lambda (k)
    (+ (* k 5) 8)))

的结果。

注意这个结果和(+ (* x 5) 8)这个外层函数一点关系都没有,它已经成为过去了。

那么现在我们就很好理解

(set! this c)
(this 10)

这样的写法了。延续c只不过被储存了起来,随时调用罢了。而这个c在当下与过去的外层函数一点关系没有了。

(+ (*
    (call/cc 
        (lambda (c)
            (set! this c) 
        1)) 5) 8)

在这个例子里,因为回调函数也就是延续c一直没有被调用。

那么call/cc的回调函数会返回1,结果是13。

但这里我们把延续存起来了,于是:

(this 2)

相当于

((lambda (c)
    (c 2))
(lambda (k)
    (+ (* k 5) 8)))

得到 18

(this 3)

相当于

((lambda (c)
    (c 3))
(lambda (k)
    (+ (* k 5) 8)))

得到 23

可以看到这里的 this 等于c 和原函数 (+ (* x 5) 8) 一点关系没有了。

4 个回复 | 最后更新于 2019-05-22
2019-05-19   #1

同感,网上的文章和一些教程看得糊里糊涂,断断续续用了两三个月才理解得差不多。


仔细看了看这篇文章,发现和自己的理解有些出入,可能是自己的理解有误吧。


文中有这样一句话:“也就是说,(+ (* (call/cc …)5) 8) 的加法和乘法是永远也不会执行的!从call/cc开始,就走了,走了,永远也不回来了。去哪了,去(call/cc f)的回调函数f那里了。”

我有点不明白,“加法和乘法永远不会执行了”这句话是什么意思。


就我自己的观点,call/cc捕捉了当前程序的执行状态,并以延续参数的形式传递给一个函数。然后当前程序就被冻结了,程序的执行权交给了接受延续参数的函数。在延续参数接受一个参数时,就返回到原来的程序执行点,将剩下的部分完成。好像并不是永远都不回来了。


文中的set! 作用说的很清楚,就是把当前延续赋给变量,可以让变量保存延续,以供多次调用。


“那么现在我们就很好理解

1
2
(set! this c)
(this 10)

这样的写法了。延续c只不过被储存了起来,随时调用罢了。而这个c在当下与过去的外层函数一点关系没有了。”这个”一点关系都没有了”还是感觉不太好懂。


例如:

(define Con #f)
(+ (*
   (call/cc 
        (lambda (c)
          (set! Con c) 
          1)) 
   5)
8)
这样以来,Con之中就保留了相应的延续。
(Con 2) => 18 (Con 3) => 21 这是毋庸置疑的。
比较有意思的是 (define a (Con 2)) ,运行这段代码后,会得到18,但是变量a的值还是未定义,因为程序控制权已经转移到了Con所指的延续。对a的定义就永远不会执行了。


还是感谢guenchi将了call/cc的理解,这对于加深自己的理解是有好处的。

下面附上我自己看到的一些例子。


(let* ((yin ((lambda(foo) (newline) foo)
      (call/cc (lambda(bar) bar))))
       (yang ((lambda(foo) (display #\c) foo)
       (call/cc (lambda(bar) bar)))))
  (yin yang))
;;最著名的当然是这个了
(define product
  (lambda(ls)
    (call/cc
     (lambda(break)
       (let f ([ls ls])
  (cond
   [(null? ls) 1]
   [(= (car ls) 0) (braek 0)]
   [else (* (car ls) (f (cdr ls)))]))))))
;;在发现一个数是0时直接返回0,因为0*anything = 0 没有必要往后算了。
(define retry #f)

(define factorial
  (lambda (x)
    (if (= x 0)
     (call/cc (lambda (k) (set! retry k)1))
     (* x (factorial (- x 1))))))
;;例如,运行了(factorial 5)之后,会得到120,运行(retry 2),会得到240,哈哈
(define lwp-list '())

(define lwp
  (lambda (thunk)
    (set! lwp-list (append lwp-list (list thunk)))))

(define start
  (lambda ()
    (let ([p (car lwp-list)])
      (set! lwp-list (cdr lwp-list))
      (p))))

(define pause
  (lambda ()
    (call/cc
     (lambda (k)
       (lwp (lambda () (k #f)))
       (start)))))
;;想要实验一下,运行一下代码:
(lwp (lambda () (let f () (pause) (display "h") (f))))
(lwp (lambda () (let f () (pause) (display "e") (f))))
(lwp (lambda () (let f () (pause) (display "y") (f))))
(lwp (lambda () (let f () (pause) (display "!") (f))))
(lwp (lambda () (let f () (pause) (newline) (f))))
(start) 
;;还蛮有意思的,这个是TSPL上的例子,弄了好久才弄明白。
(define (Y f)
  ((lambda (u)
     (u (lambda (x)
   (lambda (n) ((f (u x)) n)))))
   (call/cc (call/cc (lambda (x) x)))))
;;利用call/cc写的Y组合子,(call/cc call/cc)和(lambda(f) (f f)) 在CBV上是等价的(call by value),但我至今也无法理解......
(define (fact n)
   (let ((r 1) (k 'void))
      (call/cc (lambda (c) (set! k c) 'void))
      (set! r (* r n))
      (set! n (- n 1))
      (if (= n 1) r (k 'recurse))))
;;利用call/cc实现循环求阶乘。

2019-05-20   #2

我也是刚接触call/cc, 感觉某种意义上来说, call/cc这个语法挺硬核的... 我觉得 guenchi  已经讲的很清楚了. 从自身体验来说, 我觉得主要这几个点可以帮助理解:

  1. 定义  tspl https://www.scheme.com/tspl4/further.html#./further:h3 3.3 提到了定义, 

  2. 等价形式  cps https://www.scheme.com/tspl4/further.html#./further:h4 3.4 提到了实际上延续的等价形式 (这些在 guenchi 的文章里都提到了)

  3. 实现方式  https://karczmarczuk.users.greyc.fr/TEACH/Doc/EssProgLan.pdf eopl 中 5.5 Continuation-Passing Interpreters 实现了简单的以continuation 构成解释器.



这些可以帮助理解到底什么是延续. 我自己是先看的eopl再接触的call/cc, 还是花了相当的时间才理解其作用.(当然我看的没有很认真... 

2019-05-21   #3

回复#1 @include :

文中有这样一句话:“也就是说,(+ (* (call/cc …)5) 8) 的加法和乘法是永远也不会执行的!从call/cc开始,就走了,走了,永远也不回来了。去哪了,去(call/cc f)的回调函数f那里了。”

我有点不明白,“加法和乘法永远不会执行了”这句话是什么意思。



意思是函数永远不会返回到当前调用栈了 

而这个栈的信息被call/cc内部机制储存了起来

当call/cc内部处理完毕 被执行的是被储存的后续调用信息 而不是函数当前所在的栈

(除非call/cc 内部没有发现下一步的控制流 也就是没有调用回调函数)



这个加法和乘法只是被复制了一份

被执行的不是原有式子中的加法和乘法了


请参考 Chez Scheme的发展 论文,Chez Scheme的高效call/cc实现就是用复制储存当前栈信息的方式。

2019-05-22   #4

回复#3 @guenchi :

多谢解答。 “call/cc捕捉的是栈的信息而非栈” 学习了。

登录后方可回帖

登 录
信息栏

Scheme中文社区

推荐实现 ChezScheme / r6rs / r7rs large
theschemer.org
Q群: 724577239

精华导览

社区项目

包管理器:Raven
HTTP服务器:Igropyr (希腊火)
官方插件:vscode-chez

社区目标:

完善足以使Scheme工程化和商业化的库,特别是开发极致速度的Web服务器和ANN模块。

一直以来Scheme缺少一个活跃的中文社区,同时中文资料的稀少,导致大多数因为黑客与画家和SICP而接触Scheme的朋友,在学完SICP后无事可做,不能将Scheme转换为实际的生产力。最后渐渐的放弃。
同时Chicken等实现,却因效率问题无法与其他语言竞争。本社区只有一个目的,传播Scheme的文明之火,在最快的编译器实现上,集众人之力发展出足够与其他语言竞争的社区和库。


友情链接:

Clojure 中文论坛
函数式·China


Loading...