[关键字]
goto, goto with parameters, stack, stackless, continuation
[参考资料]
http://c2.com/cgi/wiki?ContinuationsAreGotos
http://c2.com/cgi/wiki?ContinuationsInCee
http://c2.com/cgi/wiki?SingleUseContinuation
[正文]
这是一个不常见控制流的系列，把参考资料优先放在头部也是不常见的。
最早我们接触编程语言里的的goto，然后我们被告知不要使用goto，使用goto会破坏结构化程序设计。我记得第一次学计算数学的《计算线性代数》、《数值分析》等计算数学入门课程时，我们书上很多算法都是用为代码形式给出，这类算法很多都是迭代型的，只有迭代收敛或超时超出迭代次数就退出。用编程语言的写法，如果没有提供循环这种特性，就只能用1、1、label+goto是实现迭代；2、递归做法。所以递归当然可以完成迭代的任务，这是另一回事。所以goto我们是很熟悉的。实际上if-else-then、while、for、call-function都可以用goto做到。只是由于直接使用goto会导致代码及其难读和不可维护，所以才出现结构程序设计。但即使如此，大部分语言都保留了goto的能力以备不时之需。
我觉得非计算机系的人学语言挺亏的，就像非数学系的人学高等数学很亏一样（当然后面可以弥补，但如果一开始就从正确的入口进去，何必走弯路？）。之所以这么说，是因为数学分析会先把极限的概念、episode-xigema收敛证明法讲解的非常透彻，然后基于这个坚实的概念再往上学微积分，这样学微积分，如果你想剖丁解牛，你就有机会分解下层抽象去做推理，这也解释了另一个软件术语的含义「抽象泄漏法则」，你不得不透过抽象背后的逻辑去理解事物的本质。编程也是这样的，C语言的函数调用直接从汇编的层面看，函数调用栈是一个非常重要的概念，这样能理解函数调用的栈顶保存，参数传递顺序，函数返回前的清空函数栈、恢复上层函数栈顶等动作。从而对函数调用开销有直观的理解，并且也容易去区分和理解栈上变量、堆上变量之间生命周期的区别，并且对寄存器有直观的理解。
<未完待续，这节不好写，慢慢来>
2014年3月10日星期一
2014年3月8日星期六
探索那些不常见的控制流（2）
尾（巴）递归，尾调用优化，尾递归优化
tailrecursion, tailcall optimization and tailreursion eliminate
最早学scheme的时候就玩过尾递归（tailrecursion），不过当时只是在形式上玩了下，也大概理解尾递归可以让编译器重用函数调用栈，而不会导致函数调用栈溢出发生，同时模糊的说这种写法可以和迭代的效率相当。我们一群人学scheme的时候，只是皮毛的把SICP的前2章的内容和题目看掉、做掉。那段时间我狂看C++的那些书籍，学STL我就直接硬着头皮大致看掉《STL源码剖析》（我才发现要学一个东西未必要按部就班从Prime开始，直接跳过Prime书籍直接看深入一点的书籍也是大有好处的，不用先非常熟悉使用，过了很久之后才想起来去看下源码，才发现之前很多用法实际上多绕了很多弯路，MFC没用过，但我看过《MFC深入浅出》前几章，大概知道那些繁杂的要点在哪，这样就不会心里有惧怕感。）；学模板我就看了《The C++ Template》这书，这样就对那些特化、偏特化、typename，template template class，编译时多态（元编程，MetaProgram）等概念有比Prime系统性的一些了解，后面还粗略看了《Morden C++ Template》，知道boost和loki；学C++运行时多态，我看了《Internal C++ Object Model》，这样就知道了class对象的内存分布，也就是虚函数表是最重要的，对象的构造、析构等也与内存分布息息相关，而且虽然不学COM，但知道COM要做ABI也是要知道C++的内存分布的，《COM本质论》前几章也在讲这个。SICP的习题都是一环扣一环，后面的习题直接给予前面的习题来继续做，这样我印象很深的是，抽象是如何被一步步封装起来的，对于每道习题，只要之前习题已经搭建的那些抽象（函数）是坚实的，就可以被用来组合新的抽象，这样我对于「任何软件问题都可以通过添加抽象层解决」这句话就有深入一点的理解，并且印象深刻。scheme由于概念简洁，function是一等公民，所以你会一直专注在解决问题本上上，而不用像C++那样一个又一个特性让你话费大把时间去学习和积累。函数式编程一些重要的概念：惰性求值、无副作用、无状态、不变性等基本概念都深入到我脑子里，以后我用其他语言的时候会不断重新发现这些概念。
想起来之前的那些事就顺便多写了这些，最近开始系统性重新学习和发现那些以前有些清晰有些模糊的概念：tailrecursion, tailcalloptimization, tailrecursioneliminate, continuation passing style, call-with-current-continuation,closure,coroutine,concept, constraint template arguments, lambda, recursion function等等。我想一边把这些编程语言相关的外在概念都梳理一遍，同时系统性学习编译原理、类型理论，再结合实战研究编程语言的实现，希望把这个角落清扫一遍。
恩，本系列以小步迭代方式进行。本节实际上是从下面页面的代码片段拿过来注释了下尾巴递归的概念。
http://c2.com/cgi/wiki?TailRecursion
#include <stdio.h>
#include <stdlib.h>
/**
*非尾巴递归，return的时候需要做调用自己和一次乘法
*/
int factorial0(int n) {
if (n == 0) return 1;
return n * factorial0(n - 1);
}
/**
*尾巴递归，return的时候只做一件事：递归调用自己
*/
int factorialimpl(int n, int accumulator) {
if (n == 0) return accumulator;
return factorialimpl(n - 1, n * accumulator);
}
int factorial1(int n) {
return factorialimpl(n, 1);
}
/**
*如果编译器能够识别并为尾巴递归做优化，则尾巴递归
*等价于如下代码，不需要反复进入和退出嵌套的调用栈
*/
int factorial2(int n, int accumulator) {
beginning:
if (n == 0) return accumulator;
else {
accumulator *= n;
n -= 1;
goto beginning;
}
}
/**
*因此，尾巴递归的性能将和下面的迭代等价
*/
int factorial3(int n, int accumulator) {
while (n != 0) {
accumulator *= n;
n -= 1;
}
return accumulator;
}
/**
*这就是尾巴递归的故事，用C语言描述
*/
int main(){
return 0;
}
上面的c代码演示了什么是尾巴递归，尾巴递归必须在函数返回前只做一件事，那就是递归调用自己。尾巴递归调用的重点在于递归调用返回到上一层调用栈的时候，上一层调用栈并不需要利用这个返回值做点什么事（否则，上层调用栈就必须保留栈上下文），而是直接返回给上上层调用栈。那么对于一定要对递归调用结果「做点什么事」的需求来说，就必须把要参与「做点什么事」的那些数据和函数传递给下层调用栈，比如这个例子里通过accumulator把结果传递给递归调用函数。
那么尾巴递归调用就保证了在尾巴递归的时候不需要保留上层函数调用栈上下文。所以如果编译器能识别尾巴递归调用，则可以对尾巴递归调用做「tailrecursion eliminate」，也就是例中的示意代码。消除了递归调用，从而把递归变成迭代。但这个前提是编译器会帮你做这件事，否则就算你写的代码是尾巴递归调用，但编译器不做「tailrecursion eliminate」的话，则没有这些福利。scheme、lua等语言都有对尾巴递归调用做消除。
进一步的，如果一个函数调用虽然不是经典的「tailrecursion」，但是在return之前只做一件事，就是调用某个其他子过程。则上层函数调用栈也不需要保存，则这个时候编译器可以做「tailcall optimization」，也就是尾调用优化。我们来下下例子：
http://c2.com/cgi/wiki?TailCallOptimization
/**
*进一步的，尾调用优化
*/
int bar(int a){
printf("bar called with arg %d\n", a);
return a * a;
}
int foo(int b){
return bar(b * b);//函数返回前只做一件事，调用只过程，并且把b*b的结果传入到子过程
}
/**
*然而，这个例子里，foo的栈如果被优化掉，则a的生命周期
*被破坏，所以用栈上变量a是不安全的。
*/
int bar(int *b){
return *b * 10;
}
int foo(){
int a = 5;
return bar(&a);
}
tailrecursion, tailcall optimization and tailreursion eliminate
最早学scheme的时候就玩过尾递归（tailrecursion），不过当时只是在形式上玩了下，也大概理解尾递归可以让编译器重用函数调用栈，而不会导致函数调用栈溢出发生，同时模糊的说这种写法可以和迭代的效率相当。我们一群人学scheme的时候，只是皮毛的把SICP的前2章的内容和题目看掉、做掉。那段时间我狂看C++的那些书籍，学STL我就直接硬着头皮大致看掉《STL源码剖析》（我才发现要学一个东西未必要按部就班从Prime开始，直接跳过Prime书籍直接看深入一点的书籍也是大有好处的，不用先非常熟悉使用，过了很久之后才想起来去看下源码，才发现之前很多用法实际上多绕了很多弯路，MFC没用过，但我看过《MFC深入浅出》前几章，大概知道那些繁杂的要点在哪，这样就不会心里有惧怕感。）；学模板我就看了《The C++ Template》这书，这样就对那些特化、偏特化、typename，template template class，编译时多态（元编程，MetaProgram）等概念有比Prime系统性的一些了解，后面还粗略看了《Morden C++ Template》，知道boost和loki；学C++运行时多态，我看了《Internal C++ Object Model》，这样就知道了class对象的内存分布，也就是虚函数表是最重要的，对象的构造、析构等也与内存分布息息相关，而且虽然不学COM，但知道COM要做ABI也是要知道C++的内存分布的，《COM本质论》前几章也在讲这个。SICP的习题都是一环扣一环，后面的习题直接给予前面的习题来继续做，这样我印象很深的是，抽象是如何被一步步封装起来的，对于每道习题，只要之前习题已经搭建的那些抽象（函数）是坚实的，就可以被用来组合新的抽象，这样我对于「任何软件问题都可以通过添加抽象层解决」这句话就有深入一点的理解，并且印象深刻。scheme由于概念简洁，function是一等公民，所以你会一直专注在解决问题本上上，而不用像C++那样一个又一个特性让你话费大把时间去学习和积累。函数式编程一些重要的概念：惰性求值、无副作用、无状态、不变性等基本概念都深入到我脑子里，以后我用其他语言的时候会不断重新发现这些概念。
想起来之前的那些事就顺便多写了这些，最近开始系统性重新学习和发现那些以前有些清晰有些模糊的概念：tailrecursion, tailcalloptimization, tailrecursioneliminate, continuation passing style, call-with-current-continuation,closure,coroutine,concept, constraint template arguments, lambda, recursion function等等。我想一边把这些编程语言相关的外在概念都梳理一遍，同时系统性学习编译原理、类型理论，再结合实战研究编程语言的实现，希望把这个角落清扫一遍。
恩，本系列以小步迭代方式进行。本节实际上是从下面页面的代码片段拿过来注释了下尾巴递归的概念。
http://c2.com/cgi/wiki?TailRecursion
#include <stdio.h>
#include <stdlib.h>
/**
*非尾巴递归，return的时候需要做调用自己和一次乘法
*/
int factorial0(int n) {
if (n == 0) return 1;
return n * factorial0(n - 1);
}
/**
*尾巴递归，return的时候只做一件事：递归调用自己
*/
int factorialimpl(int n, int accumulator) {
if (n == 0) return accumulator;
return factorialimpl(n - 1, n * accumulator);
}
int factorial1(int n) {
return factorialimpl(n, 1);
}
/**
*如果编译器能够识别并为尾巴递归做优化，则尾巴递归
*等价于如下代码，不需要反复进入和退出嵌套的调用栈
*/
int factorial2(int n, int accumulator) {
beginning:
if (n == 0) return accumulator;
else {
accumulator *= n;
n -= 1;
goto beginning;
}
}
/**
*因此，尾巴递归的性能将和下面的迭代等价
*/
int factorial3(int n, int accumulator) {
while (n != 0) {
accumulator *= n;
n -= 1;
}
return accumulator;
}
/**
*这就是尾巴递归的故事，用C语言描述
*/
int main(){
return 0;
}
上面的c代码演示了什么是尾巴递归，尾巴递归必须在函数返回前只做一件事，那就是递归调用自己。尾巴递归调用的重点在于递归调用返回到上一层调用栈的时候，上一层调用栈并不需要利用这个返回值做点什么事（否则，上层调用栈就必须保留栈上下文），而是直接返回给上上层调用栈。那么对于一定要对递归调用结果「做点什么事」的需求来说，就必须把要参与「做点什么事」的那些数据和函数传递给下层调用栈，比如这个例子里通过accumulator把结果传递给递归调用函数。
那么尾巴递归调用就保证了在尾巴递归的时候不需要保留上层函数调用栈上下文。所以如果编译器能识别尾巴递归调用，则可以对尾巴递归调用做「tailrecursion eliminate」，也就是例中的示意代码。消除了递归调用，从而把递归变成迭代。但这个前提是编译器会帮你做这件事，否则就算你写的代码是尾巴递归调用，但编译器不做「tailrecursion eliminate」的话，则没有这些福利。scheme、lua等语言都有对尾巴递归调用做消除。
进一步的，如果一个函数调用虽然不是经典的「tailrecursion」，但是在return之前只做一件事，就是调用某个其他子过程。则上层函数调用栈也不需要保存，则这个时候编译器可以做「tailcall optimization」，也就是尾调用优化。我们来下下例子：
http://c2.com/cgi/wiki?TailCallOptimization
/**
*进一步的，尾调用优化
*/
int bar(int a){
printf("bar called with arg %d\n", a);
return a * a;
}
int foo(int b){
return bar(b * b);//函数返回前只做一件事，调用只过程，并且把b*b的结果传入到子过程
}
/**
*然而，这个例子里，foo的栈如果被优化掉，则a的生命周期
*被破坏，所以用栈上变量a是不安全的。
*/
int bar(int *b){
return *b * 10;
}
int foo(){
int a = 5;
return bar(&a);
}
2014年3月2日星期日
探索那些不常见的控制流（1）
http://coolshell.cn/articles/10975.html
这篇文章介绍了一个“蝇量级” C 语言协程库的实现。
里面使用宏封装了下，不过我不喜欢宏，觉得宏把简单的东西隐藏而不可见。因为我并不会真正直接用这些宏，只是为了搞清楚如何在C里实现yiled，去掉宏之后，我们可以很清晰的看懂代码的结构和流程。
下面的代码从http://www.chiark.greenend.org.uk/~sgtatham/coroutine.h解析：
#include <stdio.h>
#include <stdlib.h>
/**
*单线程coroutine，不可重入
*/
int function(void){
static int i,state = 0;
switch(state){
case 0:
for(i=0;i<10;i++){
state = 1;
return i;
case 1:;
}
}
}
/**
*多线程coroutine，可重入
*/
typedef void* ccr_context_handle;
typedef struct tag_ccr_context{
int state;
int i;
}ccr_context;
int ascending(ccr_context_handle* ccr_context_handle_pointer) {
ccr_context* this = (ccr_context*)*ccr_context_handle_pointer;
if(!this){
this = malloc(sizeof(ccr_context));
*ccr_context_handle_pointer = this;
this->state = 0;
}
if(this){
switch(this->state){
case 0:;
for (this->i=0;this->i<10; this->i++) {
this->state = 1;
return this->i;
case 1:;
}
}
free(*ccr_context_handle_pointer);
*ccr_context_handle_pointer = 0;
return -1;
}
}
/**
*C测试代码
*/
int main(){
printf("\n");
int i=0;
for(i=0;i<10;i++){
printf("%d",function());
}
printf("\n");
ccr_context_handle handle = 0;
do {
int ret = ascending(&handle);
if(ret!=-1){
printf("%d",ret);
}
}while(handle);
printf("\n");
return 0;
}
当我继续搜索，上述代码在这个页面出现：
http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html
这个页面里描述了在C语言里做coroutine。以及一个典型的生产者消费者模型。在C里面做协程并不轻松，底下更本质的原因是因为C语言里对continuation的支持很低阶，什么是continuation我们会在后面的节里给出。
这篇文章介绍了一个“蝇量级” C 语言协程库的实现。
里面使用宏封装了下，不过我不喜欢宏，觉得宏把简单的东西隐藏而不可见。因为我并不会真正直接用这些宏，只是为了搞清楚如何在C里实现yiled，去掉宏之后，我们可以很清晰的看懂代码的结构和流程。
下面的代码从http://www.chiark.greenend.org.uk/~sgtatham/coroutine.h解析：
#include <stdio.h>
#include <stdlib.h>
/**
*单线程coroutine，不可重入
*/
int function(void){
static int i,state = 0;
switch(state){
case 0:
for(i=0;i<10;i++){
state = 1;
return i;
case 1:;
}
}
}
/**
*多线程coroutine，可重入
*/
typedef void* ccr_context_handle;
typedef struct tag_ccr_context{
int state;
int i;
}ccr_context;
int ascending(ccr_context_handle* ccr_context_handle_pointer) {
ccr_context* this = (ccr_context*)*ccr_context_handle_pointer;
if(!this){
this = malloc(sizeof(ccr_context));
*ccr_context_handle_pointer = this;
this->state = 0;
}
if(this){
switch(this->state){
case 0:;
for (this->i=0;this->i<10; this->i++) {
this->state = 1;
return this->i;
case 1:;
}
}
free(*ccr_context_handle_pointer);
*ccr_context_handle_pointer = 0;
return -1;
}
}
/**
*C测试代码
*/
int main(){
printf("\n");
int i=0;
for(i=0;i<10;i++){
printf("%d",function());
}
printf("\n");
ccr_context_handle handle = 0;
do {
int ret = ascending(&handle);
if(ret!=-1){
printf("%d",ret);
}
}while(handle);
printf("\n");
return 0;
}
当我继续搜索，上述代码在这个页面出现：
http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html
这个页面里描述了在C语言里做coroutine。以及一个典型的生产者消费者模型。在C里面做协程并不轻松，底下更本质的原因是因为C语言里对continuation的支持很低阶，什么是continuation我们会在后面的节里给出。
订阅：
博文 (Atom)