偶素研究程序设计语言的,近来一直研究continuation(连续),这是一个从lisp语言发展出来的一个概念，近几年不断应用发展到ML,python,Ruby等语言中，促进了程序设计概念方面的一些革新，也改变着我们对程序的看法。
可能内容不太好理解，大家都没兴趣。但我希望能够起一个抛砖引玉的功能，能够有一个对程序设计语言有兴趣的人能够觉得我讲的东东有意思，俺就觉得不再孤独，非常满足了:P
1.什么是continuation?
首先我们要理解求值上下文这个概念，把环境限定在lisp语言。比如(+ (* 5 2) 10)，这是一个lisp表达式，我们看看这个表达式的计算过程,我们区分现在正在求的值（当前计算）和剩下待求的值(剩余计算):
1.[+, （_ (* 5 2) 10)]
2.[(* 5 2),((+ _) 10)]
3.[*,((+ ((_ 5) 2)) 10)]
4.[5,((+ ((* _) 2)) 10)]
5.[* 5, ((+ (_ 2)) 10)]
6.[2,((+ ((* 5) _)) 10)]
7.[* 5 2 , (+ _ 10)]
8.[10, (+ _ 10)]
9.[+ 10, (_ 10)]
10.[10, (+ 10 _)]
11.[+ 10 10, (_)]
12.[20,_]
大家可以很清楚看到当方括号左边的表达式计算到一个值（常数或者函数）[需要注意一下就是(+ 10)也是一个函数，所以也是一个值]，就把这个值发 送给右边的表达式，然后右边的表达式进行解析，找下一个要计算的值。我们把右边这个表达式就叫做程序的continuation,表示剩下来将要进行的计 算。
现在大家不难理解，表达式的continuation是隐含在表达式结构中的，进行表达式计算过程中，变换表达式的同时就在变换 contination。我们没办法利用这个continuation做什么，但同时想想，如果在某个点把continuation保存下来放到一个变量 中，然后什么时候再把这个变量调出来使用，这样，我们就有了一个我们自己定制的程序状态，任意构造这其中的1....10计算过程。计算将变得时分强大。
再来看个例子
(define cont (lambda () #f))
(+ (call/cc (lambda (k)
( set! cont k)
(* 5 2)
10)
我们看看它的计算过程
......
[(call/cc (lambda (k) (set! cont k) (* 5 2))), (+ _ 10)]
[(set ! cont k) (* 5 2) ,(+ _ 10)]
这时把cont的状态更新为了记录下来了为(+ _ 10)
其他步骤都一样，呵呵，我们得到了最关键的一步，记录程序中任何时刻剩余计算(contintuation)的能力。
当我们计算(cont 20)
时，计算过程从
[20, (+ _ 10)]
开始，我们得到了 30
嗯，这就是call/cc最初的想法。
------------------------------
continuation的应用(1):
从循环中退出
看一段程序:
(define product
(lambda (ls)
(let f ((gs ls))
(cond
((null? gs) 1)
((= (car gs) 0) 0)
(else (* (f (cdr ls)) (car gs)))))))
这段程序输入一个list, 然后计算list里面所有元素的乘积
先解释一下一些常数:
null？表示是否为空
car 表示取表头元素
cdr 去list中出去表头后剩下的list
let f (参数 参数值) (...f) 表示f是递归函数。
(define 函数名 (lambda (参数) (函数体)))表示定义函数
（product '(1,2,3,4,5)) 我们将会得到120
仔细分析一下这个函数，我们发现有个毛病
它是个递归的结构，如果参数所在那个表中有个是0的话，我们指导程序肯定是会得到0的，但product中还是会多次乘上这个0,有没有办法直接退出了？？
来看看call/cc的解决方案吧:
(define product
(lambda (ls)
(call/cc (lambda (k)
(let f ((gs ls))
(cond
((null? gs) 1)
((= (car gs) 0) (k 0))
(else (* (cdr gs) (car gs)))))))
))
来看(product '(1,2,3,0,4))
清晰看到几个中间状态
k 记录的剩余计算就是(_)
当碰到
(= (car '(0,4) 0) 候，计算转变为
[0,(_)]
程序直接退出，product的返回值为0，狠像C语言中的exit()函数，但是这里我们从原理上分析了exit:-P
----------------------------------------
用continuation循环
试想如果lisp程序中没有for和while,程序将如何写，如果我们还希望有异常退出呢？
看看下段程序
(define get-continuation-with-values
(lambda (values)
(let ((receiver (lambda (proc) (cons proc values))))
(call/cc receiver))))
(define loop-with-current-value
(lambda (values)
(let ((here-with-values (get-continuation-with-values values)))
(let ((continue (car here-with-values)
(current-values (cdr here-with-values)))
(write-line current-values)
(if < (car current-values 100)
(continue (cons continue
(map (lambda (x) (+ x 1))
current-values)))
(write-line "done"))))))
我们看(loop-with-current-value '(1 2 3))
执行的效果是，打印list，然后list里每个元素+1,再打印，循环，直至list里的第一个元素到达100,退出。
1 2 3
2 3 4
.....
100 101 102
done
这个程序体现了几个特点
1.高阶函数在函数式程序设计语言中的应用
看map函数，输入一个函数f，然后再输入一个list,结果是f作用在list中的每个元素上，然后再组成一个新的list
2.lisp语言中untype特性
大家观察一下here-with-values，再本事例中，它有四个元素，第一个元素是一个continuation,也就是说它的type是一个函 数，后面三个元素是整数，这我们每次传送到下循环体中的是一个头元素为函数，后面元素为整数的混合连表，lisp是可以的，其它基于 strong type的语言则是不行的，比如ML，这也就是lisp的魅力所在，也是lisp的困难所在！！
3.隐式的保存continuation
大家看(let (here-with-values (get-continuation-with-values values)))
这句，执行的是
(call/cc (lambda (proc (cons proc values)))
这样当前的continuation被保存在proc中，然后保存到了here-with-values中
然后(let (continue (car here-with-values))就把proc取到continue中了
再执行(contiune (cons continue .....)
时，程序控制转到
（ define loop-with-current-value
(lambda (values)
(let ((here_with_values (_))
(let ((continue (car here-with-values)
(current-values (cdr here-with-values)))
(write-line current-values)
(if < (car current-values 100)
(continue (cons continue
(map (lambda (x) (+ x 1))
current-values)))
(write-line "done"))))))
)
这就是这段程序的妙处所在！
------------------------------------------
continuation的应用(4)
模拟调试器
lisp语言的调试困难，没有好用的调试器:-(，没办法解决么？
continuation为我们提供了解决方案，假定我们现在在lisp的解释器环境中，希望能够在源程序中修改某个点，让程序执行到断点的时候断掉，然后可以从解释器环境中重新恢复到断点处，相当于基本实现一个断点功能。
首先第一不就是定义一个断点函数，这个函数输入一个参数时，保存断点，然后退出到解释器环境。
(define break
(lambda (arg)
(let ((exit) (lambda (cont)
(set! resume-computation (lambda () (cont arg) ;;保存断点
(write-line "execute paused. Try (recume-computation)");打印信息
((escaper (lambda () arg)))))) ；退出到解释器环境
(call/cc exit-procudure))
现在困难的地方在怎么退出到解释器环境中
直接的想法就是构造一个解释器环境中的continuation,以为lisp解释器也是一个lisp程序啊，这个continuation必须对全部解释执行的程序可见，所以为全局变元，另外要退回到正确的位置。
1.构造全句变元
(define escape-thunk (lambda () "escape-thunk initialize")
2.将全局continuation定到正确的位置
(define escape-thunk-init
(lambda (continue)
(set! escape-thunk continue)))
((call/cc escape-thunk-init))
呵呵，特别注意call/cc外面的两个括号，为什么是两个括号，大家想清楚了么？？如果是一个括号的话，保存的是记录点到现在执行函数的一个镜像，如果是两个括号则是(_)，退后到定义的括号里面了，这点真是狠神奇。
3.利用全局变量escape-thunk构造一个退回函数了
(define escaper
(lambda (procedure)
(lambda args
(escape-thunk (lambda () (apply produre args))))))))
来看源程序
（define flatten-list
(lambda (arg)
(cond
((null? arg) '())
((not (list? arg)) (list (break arg)))
(else
(append (flattern-list (car arg))
(flattern-list (cdr arg))))))))))
只是加了一个break
结果了
(flattern '(1 2 3))
"Execution paused. Try (recume-computation)"
value 3
==>(recume-computation)
"Execution paused. Try (recume-computation)"
value 2
==>(recume-computation)
"Execution paused. Try (recume-computation)"
value 1
==>(recume-computation)
"Execution paused. Try (recume-computation)"
value 3
(1 2 3)
大家想想序列为什么是3,2,1？？
--------------------------------
continuation的应用[5]
协子程序(coroutine)
编写过进程间通信的程序员多多少少都知道进程间通信、进程同步等概念。多进程(多线程)是这样一种模式，多个进程在一起运行，进程之间并不清楚对方，进程 知道调度器，调度器知道所有的进程，比如某个进程A正在运行，现在发生了一次中断，A被调度器调度出去，B被调度进来，A和B之间并无直接通信。
协子程序是这样一种模型，没有进程调度器了，进程彼此之间都知道对方，然后进程自己把控制传给另外一个进程，比如打牌程序A和B，A打完了，把控制传给B说，该你打了。
我们来看continuation编写协子程序实例
协子程序构造者(coroutine-maker)
(define coroutine-maker
(lambda (proc)
(let ((saved-continution '())
(let ((update-continuation! (lambda (v)
(write-line "updateing")
(set! saved-continuation v))))
(let ((resumer (resume-maker update-continuation!))
(first-time #t))
(lambda (value)
(if first-time
(begin
(set! first-time #f)
(proc resumer value))
(saved-continuation value))))))))))
可以看到构造者输入一个函数，然后构造一个恢复者(resumer),判定是否第一次执行，如果第一次执行就改标志位，并调度另一个构造者
来看resume--maker
(define resume-maker
(lambda (update-proc!)
(lambda (next-coroutine value)
(let ((receiver (lambda (continuation)
(update-proc! contiuantion)
(next-coroutine value)
(call/cc receiver))))
resume-maker完成两个工作，先保存执行点的continuation，然后调度下一个协子程序执行
然后就是ping pang 程序了
(define ping
(let ((ping-procedure (lambda (resume value)
(write-line "pinging 1")
(resume pong value)
(write-line "pinging 2")
(resume pong value)
(write-line "pinging 3")
(resume pong value))))
(coroutine-maker ping-procedure)))
(define pong
(let ((pong-procedure (lambda (resume value)
(write-line "pinging 1")
(resume ping value)
(write-line "pinging 2")
(resume ping value)
(write-line "pinging 3")
(resume ping value))))
(coroutine-maker pong-procedure)))
(ping 1)
执行结果是
"pinging 1"
"ponging 1"
"pinging 2"
"ponging 2"
"pinging 3"
"ponging 3"
value:1
这个程序挺有意思的地方在于 :
ping-procedure和pong-procedure都维护了一个内部的save-continuation,然后
都只执行了一次(proc resumer value),然后当从别处返回控制后都是执行(saved-continuation value)
resume这个高介函数完成了两个功能，记录当前的continuation到save-contination, 然后执行ping value或者pong value
let 语句的语义是先于返回值之前执行的，所以resumer和update-continuation都只构造一次，不存在重复构造,需细细体会let语句在函数式程序设计语言中的应用
==========================
Author:magicring
From:kyxk
|
