C与Scheme流程控制比较
更新日期:
##C语言##
函数内部的流程控制有:
- if … else …
- while
- break
- continue
- goto
函数间流程控制：
- setjmp()和longjmp()
一个程序的状态依赖于当前内存内容（如代码、全局变量、堆、栈）和寄存器的内容。寄存器内容包括stack pointer（sp），stack base pointer（bp）以及progran counter（pc）。C语言函数间的流程控制的实现简单的说就是setjmp()保存了寄存器的内容，而longjmp()则将先前保存的寄存器内容重新装载到寄存器中，从而将程序状态改变到setjmp()调用时的状态。
一个setjmp()、longjmp()的例子：
#include <stdio.h>
#include <stdlib.h>
#include <setjmp.h>
int main() {
jmp_buf env;
int i;
i = setjmp(env);
printf("i = %d\n",i);
if(i != 0) return 0;
longjmp(env, 2);
printf("Does this line get printed?\n");
return 0;
}
运行的结果：
i = 0
i = 2
第一次成功调用setjmp()返回0，然后调用longjmp()传入参数2，这导致程序返回到setjmp()并且返回2，继续执行满足if语句程序退出。
使用setjmp()时，最常见的错误就是对setjmp()进封装，用一个函数来调用它。
一个错误用例：
int a(char* s, jmp_buf env) {
int i;
i = setjmp(env);
printf("Setjmp returned -- i = %d, 0x%x\n", i, (unsigned)s);
printf("s = %s\n", s);
return i;
}
int b(int i, jmp_buf env) {
printf("In B: i = %d. Calling longjmp(env,i)\n",i);
longjmp(env, i);
}
int main() {
jmp_buf env;
if(a("Jim", env) != 0) return 0;
b(3, env);
return 0;
}
在本人的测试机上运行程序会有如下输出：
Setjmp returnd -- i = 0, 0x8048622
s = Jim
In B: i = 3. Calling longjmp(env, i)
Setjmp returned -- i = 3, 0x3
Segmentation fault (core dumped)
我们来看看为什么会发生这种情况。当main()被调用的时候，栈的情形如下图所示：
Stack
|----------------|
| |
| |
| |
| |
| |
| | <-------- sp
| env[0] |
| env[1] |
| env[2] | pc = main
| env[3] |
| .... |
| env[8] |
| other stuff | <------- bp
|--------------- |
当main()调用a()，参数由右到左被压入栈中，pc、bp寄存器的值也被压入栈中，同时pc、bp和sp寄存器存入新值，如下图所示：
Stack
|----------------|
| |
| | <--------- sp, bp
/------------- | old bp in main |
| | old pc in main |
| "Jim" <--- | s = "Jim" |
| /--- | pointer to env |
| \--> | env[0] |
| | env[1] |
| | env[2] | pc = a
| | env[3] |
| | .... |
| | env[8] |
\------------> | other stuff |
|--------------- |
在a()中首先为局部变量i分配空间：
Stack
|----------------|
| | <--------- sp
| i | <--------- bp
/------------- | old bp in main |
| | old pc in main |
| "Jim" <--- | s = "Jim" |
| /--- | pointer to env |
| \--> | env[0] |
| | env[1] |
| | env[2] | pc = a
| | env[3] |
| | .... |
| | env[8] |
\------------> | other stuff |
|--------------- |
接着调用setjmp()，这会使得当前sp、bp和pc寄存器的值被保存到env中。最后a()输出“i = 0”和“s = Jim”并且返回到main()中。现在栈中的情况看起来好像跟调用a()之前是一样的，除了env中保存了一些调用setjmp()时的老的寄存器的值，栈如下图所示：
Stack
|----------------|
| |
| |
| |
| |
| |
| | <----------- sp
| env[0] |
| env[1] |
| env[2] | pc = main
| env[3] |
| .... |
| env[8] |
| other stuff | <------------ bp
|--------------- |
然后main()调用b()，栈如下图所示：
Stack
|----------------|
| |
| | <--------- sp, bp
/------------- | old bp in main |
| | old pc in main |
| | i = 3 |
| /--- | pointer to env |
| \--> | env[0] |
| | env[1] |
| | env[2] | pc = b
| | env[3] |
| | .... |
| | env[8] |
\------------> | other stuff |
|--------------- |
在b()中longjmp()被调用，寄存器中的值被保存在env中的值所替换，也就是说现在寄存器中的值是替换成了a()调用setjmp()是的寄存器的值，但是栈中的值并没有变，现在的栈如下图所示：
Stack
|----------------|
| | <--------- sp
| i = 2 | <--------- bp
/------------- | old bp in main |
| | old pc in main |
| | s?? = 3 |
| /--- | pointer to env |
| \--> | env[0] |
| | env[1] |
| | env[2] | pc = a
| | env[3] |
| | .... |
| | env[8] |
\------------> | other stuff |
|--------------- |
现在问题出来了参数s的值变成了3，当要输出字符串s时，访问了一个错误的地址最终导致了core。
##Scheme语言##
在C中setjmp()只是保存了寄存器的值，这就对流程控制有一些限制，只能在函数内部或者在更高层的调用函数间跳跃。可能大家回想如果我们不但保存寄存器的值，还保存栈中的值会这么样呢？既保存寄存器又保存栈的值正式某些编译器（如Guile，Gambit Scheme[1]）实现scheme语言中的continuation的方法。(吐槽:学术界和工程界的差别就在于一个把问题描述的尽量复杂抽象，而另一个却要尽量把问题简单化，虽然这种差别是有意义的，但写continuation的文档也太TM云里雾里了吧！好吧我理解能力差……)
###Continuation定义###
在scheme语言中有一个函数叫做call-with-current-continuation(简称call/cc)，这个函数有一个参数（在下文中我们都称该参数为receiver)。receiver必须是一个只有一个参数的函数，并且这个参数就是continuation，它是一个形如(lambda (x) …)的lambda表达式。当(call/cc receiver)调用时内部会保存当前的寄存器和栈的值,宾且执行(receiver continuation)，当continuation调用时就会将保存的寄存器和栈值重新加载。我们可以用如下两个步骤来得到continuation函数的表达式：
- 将表达式用口代替
- 将结果表达式封装为一个形如(lambda (口) …)的lambda表达式
我们来看一个例子，(+ 3 (* 4 (call/cc receiver)))产生的continuation表达式为：
（lambda (口)
(+ 3 (* 4 口)))
###几个例子###
1.从循环中退出
首先定义一个循环函数：
(define infinite-loop
(lambda (procedure)
(letrec ((loop (lambda ()
(procedure)
(loop))))
(loop))))
procedure执行时遇到某些条件我们可能想要退出循环，遗憾的是在scheme中并没有提供C语言中的return功能，但是我们可以通过call/cc来实现与return相同的功能，定义如下：
(define procedure
(lambda (args)
(let ((receiver (lambda (return)
(infinite-loop
(lambda ()
(if *exit-condition-met*
(return exit-value)
*action-to-be-performed*))))))
(call/cc receiver))))
在上面的代码中为了便于理解我们将传递给receiver的continuation命名为为return，这样看起来跟C语言中的return更为相似。
利用上面的框架我们实现一个从0数到n并退出的程序：
(define count-to-n
(lambda (n)
(let ((receiver (lambda (return)
(let ((count 0))
(infinite-loop
(lambda ()
(if (= count n)
(return count)
(begin
(display "The count is:")
(display count)
(display "\n")
(set! count (+ count 1))))))))))
(call/cc receiver))))
运行(count-to-n 4)结果为：
The count is:0
The count is:1
The count is:2
The count is:3
4
根据上面提到的两个步骤，我们可以知道return形如(lambda (口) 口)，即(return count)的返回值既是count，所以最后一行的结果显示为4。
2.利用continuation实现loop
代码如下：
(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)))
(display current-values)
(if (< (car current-values) 5)
(continue (cons continue
(map (lambda (x) (+ x 1))
current-values)))
(display "Done!"))))))
运行((loop-with-current-value ‘(1 2 3))得到结果：
(1 2 3)(2 3 4)(3 4 5)(4 5 6)(5 6 7)Done!
在get-continuation-with-values中将continuation与values连接在一起并且返回，((loop-with-current-value ‘(1 2 3))运行时，第一次调用get-continuation-with-values得到的值为’(continuation 1 2 3)，接着将continue赋值为continuation，将current-values赋值为’(1 2 3)，如果current-values的第一个值小于5，则将continue与’(2 3 4)链接成为’(continuation 2 3 4)，因为continue是一个continuation其形式为(lambda (口) 口)，所以continuae调用的结果就是返回’(continuation 2 3 4)并且流程跳到给here-with-values赋值的地方，然后继续执行，当if条件满足则退出。
##总结##
Schmeme中的continuation的实现在思路上跟C中的setjmp()是相同的，但实现更复杂，功能也就更加强大。可以说setjmp()实现的功能是continuation的子集，但我们可以借助setjmp()来方便理解，利用continuation可以实现更加复杂的功能，比如用户态的进程即协程(coroutine)等。