Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1688384
  • 博文数量: 177
  • 博客积分: 9416
  • 博客等级: 中将
  • 技术积分: 2513
  • 用 户 组: 普通用户
  • 注册时间: 2006-01-06 16:08
文章分类

全部博文(177)

文章存档

2013年(4)

2012年(13)

2011年(9)

2010年(71)

2009年(12)

2008年(11)

2007年(32)

2006年(25)

分类: Python/Ruby

2012-05-10 09:06:22

这一篇将讲述[原]重新开始学习Scheme(1) 里的first class continuation。关于continuation这个单词的翻译,有那么几种,有“延续”、“继续”、“续延”。个人认为,“续延”应当算是最好的了。这个翻译是由裘宗燕老师提出来的。

Continuation是由Scheme引入函数式编程中的。这个概念相当重要,但是理解起来却比较困难——也许对于我来说困难,但对于别人来说并不一定是这样。说它重要,是因为应用面比较广,比如协作例程、异常处理;还可以模拟别的编程语言里的return、实现无条件跳转等。其最大,也是最广泛的应用之一就是用于web服务器的开发。

在对任意一个Scheme表达式求值时,必须记录两件事:
  1. 对什么求值
  2. 对求出的值做什么
第二件事便是continuation。

这个定义相当简单。例如:
对于表达式(if (null? x) (quote ()) (cdr x))有六个continuations,分别等待如下值:
  1. (if (null? x) (quote ()) (cdr x))的值
  2. (null? x)的值
  3. null?的值
  4. x的值
  5. cdr的值
  6. x的值
其中,(cdr x)的值没有列出来是因为她就是第一个continuation等待的值。从这里可以看出,continuation是一个计算环境,它在等待一些计算,只有这些计算完成后,才能进行该计算环境相关的计算。也就是说,continuation是一个函数。

Scheme允许用call-with-current-continuation函数(间写为call/cc)对任意表达式的continuation进行捕捉。call/cc必须以一个函数p为参数,而函数p又必须只有一个参数k,这个参数k就是被捕获的continuation,也是一个函数。call/cc构造当前的continuation并传递给p。每当k被应用于一个值,它就返回call/cc的continuation的值,而这个值最终就是应用call/cc的值——或者说是(call/cc p)的值。例如:
  1. (call/cc
  2.   (lambda (k)
  3.     (* 5 4)))

  4. (call/cc
  5.   (lambda (k)
  6.     (* 5 (k 4))))

  7. (+ 2
  8.    (call/cc
  9.      (lambda (k)
  10.        (* 5 (k 4)))))
第一个例子中,call/cc捕获的continuation就是返回一个值,并将其传递给匿名函数。这个匿名函数并没有使用k,因此,其结果为20。第二个例子中的continuation与第一个相同,只不过在匿名函数中将continuation应用于4,因此结果为4。第三个例子中的continuation是对其等待的值进行+2操作,因此,结果为6。

上有个例子:
  1. (define the-continuation #f)
  2. (define (test)
  3.   (let ((i 0))
  4.     ; call/cc calls its first function argument, passing
  5.     ; a continuation variable representing this point in
  6.     ; the program as the argument to that function.
  7.     ;
  8.     ; In this case, the function argument assigns that
  9.     ; continuation to the variable the-continuation.
  10.     ;
  11.     (call/cc (lambda (k) (set! the-continuation k)))
  12.     ;
  13.     ; The next time the-continuation is called, we start here.
  14.     (set! i (+ i 1))
  15.     i))
通过这个例子可以看出,continuation为什么又叫first class continuation——因为它和函数一样,是一等公民。这个例子里面用到的call/cc是call-with-current-continuation的一个别名。

下面再来看两个比较复杂一点的例子。
例1:
  1. (let ([x (call/cc
  2.           (lambda (k) k))])
  3.   (x (lambda (ignore) "hi")))
这个例子中,call/cc将捕获的continuation传递给(lambda (k) k),然后将该函数结果绑定到x由于函数(lambda (k) k)返回k,因此,x被绑定为continuation自身。之后,将x的值应用于对表达式(lambda (ignore) "hi")求值的结果(函数f)。由于x是一个continuation,因此,此时continuation变为对表达式(lambda (ignore) "hi")的求值 ,此时continuation变为将该求值的结果应用到该结果自身。同时,因为x所绑定的continuation改变了,因此x所绑定的值也被修改为这个结果(函数f),并应用到f,即(f f),因此,结果为"hi"。

例2:
  1. (((call/cc
  2.    (lambda (k) k))
  3.   (lambda (x) x))
  4.  "HEY!")
其实这个例子与例1是一样的,只不过写法不一样而已。但这个例子更具有迷惑性,你可能比较容易猜到结果,却不知道怎么得出这个结果的。我的理解也不一定正确,列在这里供大家参考:
call/cc捕获当前的continuation,因为(lambda (k) k),所以当前的continuation被返回并直接应用于(lambda (x) x),此时continuation就变为对(lambda (x) x)求值,然后应用到(lambda (x) x),最后将结果应用到"HEY!",即((f f) "HEY!")。

下面这个例子就比较有意思了:
  1. (define retry #f)
  2. (define factorial
  3.   (lambda (x)
  4.     (if (= x 0)
  5.         (call/cc
  6.          (lambda (k)
  7.            (set! retry k)
  8.            1))
  9.         (* x (factorial (- x 1))))))
这里保存了continuation到retry中。那么这个continuation是什么样呢?以(factorial 4)为例:
  1. (* 4 (factorial 3))
  2. (* 4 (* 3 (factorial 2)))
  3. (* 4 (* 3 (* 2 (factorial 1))))
  4. (* 4 (* 3 (* 2 (* 1 (factorial 0)))))
  5. (* 4 (* 3 (* 2 (* 1 (call/cc (lambda (k) (set! retry k) 1))))))
因为(lambda (k) (set! retry k) 1)中并没有应用k,因此,这个continuation应当是,返回当前值(此时为1)并乘以4!,或者说,将4!乘到当前值上。扩展到n的情况,则应当为:以参数为基数,做基数×n!操作。因此(factorial 4)然后(retry n)的结果应该是n*4!。

前面提到continuation的应用如协作例程、异常处理、模拟别的编程语言里的return、实现无条件跳转,下面就来看看。
return语句:
  1. (define (f return)
  2.   (return 2)
  3.   3)
  4. (display (f (lambda (x) x))) ; displays 3
  5. (display (call-with-current-continuation f)) ; displays 2
无条件跳转:
  1. (define product
  2.   (lambda (ls)
  3.     (call/cc
  4.       (lambda (break)
  5.         (let f ([ls ls])
  6.           (cond
  7.             [(null? ls) 1]
  8.             [(= (car ls) 0) (break 0)]
  9.             [else (* (car ls) (f (cdr ls)))]))))))
计算过程中碰到第一个0,该函数便会立刻退出,相当于break的功能。

异常处理:可以参考。因为里面涉及到了其他的一些Scheme特性,而我还没有搞懂,因此暂时不做描述。

协作例程(coroutines):
  1. ;;; A naive queue for thread scheduling.
  2. ;;; It holds a list of continuations "waiting to run".
  3. (define *queue* '())
  4. (define (empty-queue?)
  5.      (null? *queue*))
  6.  
  7. (define (enqueue x)
  8.      (set! *queue* (append *queue* (list x))))

  9. (define (dequeue)
  10.      (let ((x (car *queue*)))
  11.        (set! *queue* (cdr *queue*))
  12.        x))

  13. ;;; This starts a new thread running (proc).
  14. (define (fork proc)
  15.      (call/cc
  16.       (lambda (k)
  17.         (enqueue k)
  18.         (proc))))

  19. ;;; This yields the processor to another thread, if there is one.
  20. (define (yield)
  21.      (call/cc
  22.       (lambda (k)
  23.         (enqueue k)
  24.         ((dequeue)))))

  25. ;;; This terminates the current thread, or the entire program
  26. ;;; if there are no other threads left.
  27. (define (thread-exit)
  28.      (if (empty-queue?)
  29.          (exit)
  30.          ((dequeue))))

  31. (define (do-stuff-n-print str)
  32.      (lambda ()
  33.        (let loop ((n 0))
  34.          (when (< n 10)
  35.          (display (format "~A ~A\n" str n))
  36.          (yield)
  37.          (loop (+ 1 n))))))
  38.  
  39. ;;; Create two threads, and start them running.
  40. (fork (do-stuff-n-print "This is AAA"))
  41. (fork (do-stuff-n-print "Hello from BBB"))
  42. (thread-exit)
这个例子稍显繁琐,下面会给出一个简化的实现。这里先说明一下这段代码完成何种功能:其中有一个全局变量queue,并定义了enqueue和dequeue函数来向queue中添加或取出一个元素。(fork proc)首先将当前的continuation插入队列,然后执行proc;而yield是首先将当前的continuation添加到队列尾部,然后将队首的continuation取出来并执行。do-stuff-n-print循环打印格式化后的str字串AAA(题外话:这里有个命名的let,名字为loop,其与内嵌的函数定义一样),每循环一次,就对yield进行求值,先保存当前的continuation(即开始下一次循环),然后取出队首的continuation(即对下当前fork之后的表达式求值),然后执行该求值过程。因此,程序执行第二个fork,即先打印BBB,然后取出队首的continuation,即第二次执行打印AAA的loop,然后是yield——保存AAA的执行——执行BBB的第二次loop——……

这个例子可以简化为:
  1. (define lwp-list '())
  2. (define lwp
  3.   (lambda (thunk)
  4.     (set! lwp-list (append lwp-list (list thunk)))))

  5. (define start
  6.   (lambda ()
  7.     (let ([p (car lwp-list)])
  8.       (set! lwp-list (cdr lwp-list))
  9.       (p))))

  10. (define pause
  11.   (lambda ()
  12.     (call/cc
  13.       (lambda (k)
  14.         (lwp (lambda () (k #f)))
  15.         (start)))))

  16. (lwp (lambda () (let f () (pause) (display "h") (f))))
  17. (lwp (lambda () (let f () (pause) (display "e") (f))))
  18. (lwp (lambda () (let f () (pause) (display "y") (f))))
  19. (lwp (lambda () (let f () (pause) (display "!") (f))))
  20. (lwp (lambda () (let f () (pause) (newline) (f))))
  21. (start)
这段程序的执行永远不会自动停止。其中,lwp将函数放入列表尾部,start函数取出列表的第一个元素(函数)并执行它,pause函数捕获一个continuation,在这个continuation的处理函数中,把一个对该continuation求值的函数,通过lwp函数放入列表中,然后对start函数求值。然后分别将含有打印"h"、"e"、"y"、"!"语句的函数放入列表中。此后调用start函数,其过程如下:
  1. 取出函数(lambda () (let f () (pause) (display "h") (f)))
  2. 将f绑定为不接受参数的函数,该函数依次执行(pause)、(display "h")和(f)——无限循环
  3. 执行(pause),即将含有(display "h")和(f)作为continuation的函数放入列表尾部
  4. 执行(start)
  5. 取出函数(lambda () (let f () (pause) (display "e") (f)))
  6. 将f绑定为不接受参数的函数,该函数依次执行(pause)、(display "e")和(f)——无限循环
  7. 执行(pause),即将含有(display "e")和(f)作为continuation的函数放入列表尾部
  8. 执行(start)
  9. 取出函数(lambda () (let f () (pause) (display "y") (f)))
  10. 将f绑定为不接受参数的函数,该函数依次执行(pause)、(display "y")和(f)——无限循环
  11. 执行(pause),即将含有(display "y")和(f)作为continuation的函数放入列表尾部
  12. 执行(start)
  13. 取出函数(lambda () (let f () (pause) (display "!") (f)))
  14. 将f绑定为不接受参数的函数,该函数依次执行(pause)、(display "!")和(f)——无限循环
  15. 执行(pause),即将含有(display "!")和(f)作为continuation的函数放入列表尾部
  16. 执行(start)
  17. 取出函数(lambda () (let f () (pause) (newline) (f)))
  18. 将f绑定为不接受参数的函数,该函数依次执行(pause)、(newline)和(f)——无限循环
  19. 执行(pause),即将含有(newline)和(f)作为continuation的函数放入列表尾部
  20. 执行(start)
  21. 取出函数(lambda () (k #f)))
  22. 执行k,即输出"h",调用(f)
  23. 执行(pause),即将含有(display "h")和(f)作为continuation的函数放入列表尾部
  24. 执行(start)
  25. 取出函数(lambda () (k #f)))
  26. 执行k,即输出"e",调用(f)
  27. 执行(pause),即将含有(display "e")和(f)作为continuation的函数放入列表尾部
  28. 执行(start)
  29. 取出函数(lambda () (k #f)))
  30. 执行k,即输出"y",调用(f)
  31. 执行(pause),即将含有(display "y")和(f)作为continuation的函数放入列表尾部
  32. 执行(start)
  33. 取出函数(lambda () (k #f)))
  34. 执行k,即输出"!",调用(f)
  35. 执行(pause),即将含有(display "!")和(f)作为continuation的函数放入列表尾部
  36. 取出函数(lambda () (k #f)))
  37. 执行k,即输出换行符,调用(f)
  38. 执行(pause),即将含有(newline)和(f)作为continuation的函数放入列表尾部
  39. 回到20

最后,留下一个问题供大家讨论吧——我目前不知道怎么来解释这个问题。这就是著名的阴阳谜题:
  1. (let* ((yin
  2.          ((lambda (cc)
  3.             (display #\@) cc)
  4.           (call/cc
  5.            (lambda (c) c))))
  6.        (yang
  7.          ((lambda (cc)
  8.             (display #\*) cc)
  9.           (call/cc
  10.            (lambda (c) c)))))
  11.     (yin yang))
其结果看起来应当是这样:
  1. @*@**@***@****@*****@******@*******@********@*********@**********@***********@************@*************@**************@***************@****************@*****************@******************@*******************@********************@*********************@**********************@***********************@************************@*************************@**************************@***************************@****************************@*****************************@******************************@*******************************@********************************@*********************************@**********************************@***********************************@************************************@*************************************@**************************************@***************************************@****************************************@*****************************************@******************************************@*******************************************@********************************************@*********************************************@*********************
这段程序的执行永远不会自动停止。

PS. 由于我自己并没有太理解continuation,因此,这篇就更像一个信息的翻译和聚合,并没有太多自己的理解在里面。写完这篇,我对于continuation依然还是懵懵懂懂的,更谈不上运用它。也许随着时间的流逝,随着对Scheme的熟悉,会逐渐熟悉continuation吧。

参考

阅读(5133) | 评论(3) | 转发(0) |
给主人留下些什么吧!~~

vivoid2014-05-19 10:00:02

您这都是翻译的内容

fera2012-05-14 10:44:27

当初花了相当长的时间从面向过程思维转向面向对象思维,如今要转向函数式思维,估计更需要时间

fera2012-05-12 23:36:11

难道就没有行家来评论吗?看来发错地方了