栈编程和函数控制流: 从 continuation 与 CPS 讲到 call/cc 与协程

原标题：尾递归优化 快速排序优化 CPS 变换 call/cc setjmp/longjmp coroutine 协程 栈编程和控制流 讲解

本文为部分函数式编程的扩展及最近接触编程语言控制流的学习和思考，主题是栈编程和控制流相关，涉及内容有 堆栈编程总结， 函数式语言的CPS变换，python 如何实现尾递归优化装饰器及其思想方法的总结应用，快速排序的算法导论写法的一种视角/分析，C 语言setjmp/longjmp 函数的作用和实现分析，如何实现 C/C++ 下的协程库编写的一些思路和要点分析。虽然是大杂烩，但是主要内容都与栈和控制流相关。主要服务于不久后进行的网络编程项目中协程库部分的前情提要，另外也为将来进一步学习魔法预备。

---

递归与栈

首先理解栈程序模型，其函数调用是依据压栈进行的，这里给一副图加深印象：



函数调用最后返回的时候 callee 需要从栈恢复 callee save 寄存器然后返回到 caller，caller 再恢复 caller save 寄存器，这一步就是占用内存的消费。

---

尾递归

我们是否能够把递归变成 \(O(1)\) 空间的呢？实际上是可以的，但是这对程序有条件，就是尾递归。下面来看几个程序:

int fib(int n){                        int sum(int n) {
    if(n < 2) return 1;                    if(n<1) return 0;
    return fib(n-1) + fib(n-2);            return sum(n-1) + n;
}                                      }

int sum2(int n, int acc){              int fact(int n, int acc){
    if(n<1) return acc;                    if(n<1) return acc;
    return sum2(n-1, acc + n);             return fact(n-1, acc * n);
}                                      }

这里一共有四个程序，我们很容易理解只有下面的两个可以 \(O(1)\) 返回，这是因为中间的运算是无必要的，函数调用者不需要在递归调用返回后进行其他运算再返回，这样我们汇编层面不需要压栈保存寄存器从而直接 jmp 到函数调用就行了。一直运行到最后一个函数调用就能 a0 作为返回值返回结束函数。上面的阶层函数写成伪代码就是这样：

fact:
let register a0 as n, a1 as acc
label 1: if (n<1) a0 = acc, ret
label 2: acc = acc * n
label 3: n = n-1
label 4: goto label 1

这种就是尾递归和尾递归优化。

---

Python 尾递归优化

我们在 Python 里可以写一个装饰器让通用的尾递归函数可以进行优化从而去掉运行的堆栈。废话少说，直接上代码：

class TailRecurseException:
    def __init__(self, args, kwargs):
        self.args = args
        self.kwargs = kwargs
def tail_call_optimized(g):
    def func(*args, **kwargs):
        f = sys._getframe()
        if f.f_back and f.f_back.f_back \
            and f.f_back.f_back.f_code == f.f_code:
            # 抛出异常
            raise TailRecurseException(args, kwargs)
        else:
            while 1:
                try:
                    return g(*args, **kwargs)
                except TailRecurseException, e:
                    args = e.args
                    kwargs = e.kwargs
    func.__doc__ = g.__doc__
    return func
@tail_call_optimized
def factorial(n, acc=1):
    "calculate a factorial"
    if n == 0:
        return acc
    return factorial(n-1, n*acc)

你看懂了吗？一开始看可能有点一头雾水，当然我们不了解 Python 的运行堆栈的概念就无法理解。结合 decorator 的编程方法，我们可以做这样的思想实验：我们先伪装一个函数把参数控制权给偷过来（装饰器内自定义函数即中间人），注意装饰器一旦装饰，其原函数（factorial）内部递归将转接到装饰器内的自定义函数（func）中。然后我们知道是递归的时候就清空栈，然后重新调用一个原函数传入新的参数。

具体实现涉及一些小技巧，比较魔幻，下面讲解:

• 装饰器启动后，我们调用 factorial 100，此时实际调用的是 func 100，然后 func 100 会调用 g 100
• g 99 进入原来的 factorial 99，然后 return func 98（注意这里递归调用是被掉包了）
• func 98 将再次进入 func，此时的堆栈是： func 100 -> g 100 -> func 99
• func 发现发生了递归，于是其抛出一个异常，并且把这个最新递归调用的参数给异常带走了
• 一旦异常发生，栈将直接清空直到回到第一次调用产生的地方，那就是第一个 func 中 while 1 中的抓异常的地方
• 然后我们完成了清空栈的目的，然后再调用 g 99 ，就等价于尾递归控制权直接给下一任返回

感觉这里是不是好像 DNS 查询里的迭代查询？就本来建立了一条查询链的 local 向服务器 A 发起 “查询” 调用，服务器 A 向 B 发起又一次 “查询” 调用，直到返回后再返回给 local。这样效率不好而且涉及占用服务器资源，连接必须等待。改进则变成了 local 向 A 查询，A 说你去向 B 查询，A 又向 B 查询。这里的 A 只是计算出 B，即上文中的 “参数”，在这里，函数调用是 “查询” 函数，而参数则是服务器的名字。

---

快排递归优化版

（本节和后续主题内容无关）对巨量数据进行快速排序真正用起来是会爆栈的，但是我们清楚的认识到快速排序的代码并不算尾递归，所以很明显他无法进行尾递归优化，但是其实我们还是可以优化一部分寄存器的保存和恢复的操作的，那就是进行剪枝，当然这种写法很难说不算尾递归优化 idea 的启发。算法导论永远的神。

    public int patition(int[]nums, int l, int r){
        int pivot = nums[r-1];
        while(l<r-1){
            while(l<r-1&&nums[l]<=pivot)l++;
            if(l<r-1) nums[--r] = nums[l];
            while(l<r-1&&nums[r-1]>pivot) r--;
            if(l<r-1)nums[l++] = nums[r-1];
        }
        nums[l] = pivot;
        return l;
    }
    public void qs(int[]nums, int l, int r){
        int sep;
        while(l<r){
            sep = patition(nums, l, r);
            qs(nums, l, sep);
            l = sep + 1;
        }
    }
    public void qs_v2(int[]nums, int l, int r){
        int sep;
        while(l<r){
            sep = patition(nums, l, r);
            qs_v2(nums, sep+1, r);
            r = sep;
        }
    }

分析我就不做了，很容易理解的本来是对左右子树分别递归下去，但是由于我们知道树的左边界或者右边界是固定的，很容易想到消除一部分递归调用，即左树，左树的左树，左树的左树的左树都在 while 循环里面搞定了，即减少了一半的寄存器压栈出栈，最后结果就是节约一点点空间。说这是一种尾递归优化是因为他的思想和尾递归优化是一致的。

---

尾调用

但是其实尾递归优化是没有意义的，这是因为我们很容易就能把尾递归程序写成循环的形式，像 Java （Java 8）这种纯 OO 语言编译器本身就不提供尾递归优化，因为程序员总是能在希望提高性能时手动完成尾递归到循环的转换，而 C/C++ 的编译器如 gcc/g++ 就提供该优化，具体实现方案则正如上文提到的那样是不进行寄存器的保存和恢复直接 jmp。

但是我们知道 CS 的发展历程很多时候一个 idea 并不总是在本地方有用的，尾递归程序员本身可以写成循环，我们遵循唯物主义的教导从特殊到一般分析，对于尾递归的更一般的情况尾调用来说，程序员是无法在不改变 Coupling 情况下优化的，这时候这个尾调用优化不进行寄存器的保存和恢复就大显身手。然而 Java 出于某些堆栈计数依赖的原因并不提供，希望编写高性能（）的 Java 程序时留意。

所以为什么有尾调用的需求，正常不是我们返回值然后调用新的函数不就行了吗？这其实很好理解，比如有一个应用——异步编程，我们在 C# 和 javascript 编程里面已经见的多了，那就是大名鼎鼎的异步编程，此时这个尾调用实际上是一个回调函数，这样实际上尾调用会延迟在另一个核心里运行，我并不需要等待他的返回就行执行其他的程序流。接下来就要具体讲解这种尾调用的编程风格。

---

闭包与柯里化

前面 Python 的曲线尾递归优化的 中间插一腿 的思路能帮助我们理解 Continuation Passing Style 编程。虽然这个东西理论上好像很复杂，搞魔法的可能可以用逻辑学/形式逻辑里程序等价于证明的 Curry-howard Correspondence 理论相关的东西来讲。我这里比较低级，只做一些简单的笔记，我们先从讲解函数式语言里容易理解的 闭包（closure) 概念开始。

函数式编程里面函数是一等公民，除了参数就就没有变量了，因为变量会存在 state ，这个东西会导致函数调用有副作用，所以要实现循环都用递归来实现的，参数传值。

我们来看一段 Common Lisp 代码：

(define f (lambda (x) (lambda (t) (+ x t))))

这里的 (lambda (t) (+ x t)) 就是一个闭包函数，他能够读取到 (lambda (x) ...) 函数的内部变量 x 的值并且用来做计算，但是这个变量对闭包函数来说是其外部的。

闭包的概念即这个函数把他的外部给包了起来，这么说，当定义的时候，闭包函数的外部是某个函数，而当他作为高阶函数返回给别人的时候，他就出到另外的环境了，函数的 Scope 变了但是他还能访问到之前的那个外部环境，这就是因为他是把之前定义的地方的外部状态给封闭打包了。

如果还是不理解闭的包是外部的包，请想象成你想办法把房子打包了然后吃下去了，当你到别的地方的时候，你又还是住在你自己的房子里活动。

当然 OOP 里的类这种封装实际上也有闭包，我们可以认为成员变量的 properties 就是内部变量，而 selector 就是闭包函数能够给外部人一种手段访问内部变量，当然这里的成员变量是 mutable 的，FP 里的是 immutable 的。

Curry-ing 就是一种多参数函数的闭包改写方法，λx.λy.x+y 即是 (lambda (x y) (+ x y) 的闭包改写。接下来我们会讲 CPS 和 CPS 变换，这两者的关系就和 闭包与柯里化 的关系差不多。

---

回调

闭包函数能够把内部变量通过某些控制后暴露给外部，那么接下来讲回调。Callback 实际上很常用，比如异步常常就是用 callback 实现的，callback 本质上是一种 CPS 模式。

算了不讲了，回调很容易理解，就是异步编程里面另一个线程去执行的尾调用而已。

如果程序有连续的太多的异步调用，代码里面就会引发回调地狱，这一点不好看，就像 Lisp 那种括号语言，偷到的代码最后一页肯定全是括号。

---

CPS 和 CPS 变换

CPS 是一种 style，式如其名，就是函数的调用参数里面有一个 continuation，而程序不会直接返回而是随着这个 continuation 运行下去，所以说这是一个控制流上的 style。

CPS 变换则是完成这种风格转换的变换，当然我们可以通过人工来变换，但是实际上熟悉 FP 中 everything is data 的概念，我们顺理成章地可以通过操纵程序数据用程序完成 CPS 变换。

为了缓解枯燥 () 这里插播一个魔法知识点：

「CPST 就是 Gödel–Gentzen 变换的 Curry–Howard 像而已，这有什么难理解的？」 CPS 变换有什么作用？ - Belleve的回答

这句话的理解可能得搞魔法的那群人才看得懂，这里 Curry-Howard Correspondence 是一个理论说命题的证明和程序是同构的，然后 Gödel–Gentzen 变换 不过是逻辑学里的一个定理：对于任意的经典逻辑下的证明，我们可以把它转换为一个直觉主义逻辑下证明而不损失任何证明能力，对于经典逻辑和自觉逻辑的区别请有兴趣的同学自行学习魔法。所以 CPS 变换的一个程序其实是哥德尔-根岑变换这个定理的证明通过 Curry-Howard 同像理论在程序集中的一个对应。

回来讲 CPS，前面我们都是从尾调用的角度讲的，这样其实这个时候对 CPS 的印象已经很清楚了，应该就是一个函数指针的回调而已呗。下面再从非尾调用的函数的角度来看一下 CPS 的样子。

对于尾递归本身是一个 \(O(n)\) 空间的递归程序，可以优化到 \(O(1)\) 并且还能避免数据过大导致的 Stack Overflow 问题，但是对于普通的递归来说，\(O(n)\) 的空间消耗的必须的，因为他一定要保存状态回退/回溯。 如果能把递归转换成尾调用的编程风格，即CPS 变换也就能优化一个栈溢出的问题，把栈空间消耗放到堆上去而已。

当然我们其实知道人工用 数据结构 + 循环 完全模拟递归调用也可以达到目的，比如下面的快速排序程序（头条校招面试题）：

    public void qsort(int[]nums, int l, int r){
        Deque<int[]> s = new ArrayDeque<int[]>();
        s.addLast(new int[]{l, r});
        int count = 0;
        while(!s.isEmpty()){
            int[] temp = s.pollFirst();
            if(temp[0]>=temp[1])continue;
            l = temp[0]; r = temp[1];
            int sep = patition(nums, l, r); //经典分区代码略
            s.addLast(new int[]{l, sep});
            s.addLast(new int[]{sep+1, r});
        }
    }

树形递归其实有点超纲了（其实只是为了复习一下题目），我们还是看回比较正常的递归吧：

 int sum(int n) {               int sum2(int n, int acc){
     if(n<1) return 0;              if(n<1) return acc;
     return sum(n-1) + n;           return sum2(n-1, acc + n);
 }                              }

对 sum 来说需要先计算出 sum(n-1) 才能计算出 sum，而 sum2 这种也不是 CPS 风格（这是依赖特定程序结构而人工才能改写的），下面给出 CPS 风格的编程 (请回顾将函数结果作为参数持续运行下去)：

#如果理不清请多看几遍：
def sum_cps(n, c):
  if n == 0:
    return c(0)
  else:
    return sum_cps(n-1, lambda x: c(n + x))
sum_cps(10000, lambda x:x)

我们可以看见，这种情况下的 CPS 变换（尽管是人工） 是一种奇技淫巧，因为他不是用 栈/队列 等数据结构来实现调用的模拟，而是用闭包来实现的，我们复习 FP 里面闭包是可以通过参数实现局部变量（成员对象放堆上）的（这里涉及 FP 语言的编译器和解释器，就和我们当时用编写 scheme 解释器那种，值得注意的是一般还涉及 GC），所以可以用尾递归形式配合编译器把爆栈问题解决掉。

实际的运行好像就不算回溯的版了，而是一个类似自底向上的链式求解过程：sum 100 -> sum 99 ->... 而关键的栈部分或者说 acc 部分已经通过闭包的形式存在了这个 lambda 匿名函数中去了！

结论是 CPS 编程本质是基于闭包的无栈编程（当然其解释器如何工作则另说）。

当然程序上的 CPS 变换 太过于复杂，我目前还是先略过，附上论文地址供将来学习魔法的时候异步回调学习。。。。Representing Control: A study of the CPS transformation 以及一个 PL 课程：PL

---

setjmp 与 longjmp

那么如果所有的函数都 CPS 变换后，就能用简单的方法实现一个名为call/cc的在 FP 中实现控制流的函数，这个函数本身是无法用 FP 语言定义的，为了能够理解 call/cc 与 CPS 变换的关系，我们想要知道 call/cc 干什么，在那之前我们先学习 C 语言中的一个简化版的 call/cc。

对这个的学习也是 C 语言异常控制的一个思路。但是 jmp 系列只能保存寄存器通过恢复PC来实现跳转，共用一个栈，所以协程还是老实用 ucontext 好了（jmp 系列也能实现，到时候看一下），不过 CPS 的 style 对于实现 协程 yield 不是很友好吗，毕竟协程就是为了用户态实现 sequential 运行的迷你线程。

#include <setjmp.h>
int setjmp(jmp_buf env);
// 返回值：若直接调用则返回0，若从 longjmp 调用返回则返回非0值
void longjmp(jmp_buf env, int val);

jmp 系列函数内容特别简单，甚至能让人推出他的汇编实现。当然这里还有一些要点值得注意的，第一点，我们已经说了他是共享栈的，所以千万不能让某个函数 return 之后再跳过来，到时候由于 sp 指针对应的栈很有可能已经被新程序用过了，此时引用内存变量涉及编译器对栈的使用，马上会导致未定义行为。

结论是如果想要实现协程，我们应当编写 while 循环，或不使用栈上的变量而只使用堆的，或者人工编写另一套栈，这就变成了无栈编程，反而更难受。ucontext 的结构体内容中就包含栈空间的指针，这个实现可能和内核的 signal handler 注册的时候能指定栈的实现相关，想实现协程的可以再深入学习。不过感觉就是 6.s081 里用户线程的 lab thread 那种感觉？我觉得很有道理，毕竟 xv6 里面 user proc 是不会分散到 multicore 上运行的，所以这个 lab thread 本质就是协程啊哈哈哈（对于协程的理解本文是采用构建不并行的最小化程序目的理解的，然后协程分为无栈协程和有栈协程），虽然目的是方便上面（user space）调度，但是协程实际上使用，也可以保留能并行的功能，但是我主要理解是依据协程是另一种意义上的基于 continuation 的控制流。

所以这里再附送一个 lab thread 里面的 thread 结构体代码如下，也许这个就是 ucontext 的简化版吧。

---

call/cc

讲完 setjmp 和 longjmp ，再来讲 lisp 里面的 call/cc。这个有点复杂，全程是 call with current continuation。

continuation 的概念上文已经很熟悉了，这里再指定在 lisp 中的概念，continuation 是当 call/cc 被调用时创建的当前调用 call/cc 上下文中的 continuation。第二点是发生什么，具体来说就是 call/cc 会打包当前的 continuation 然后传给其参数（打包后类似与 jmp 系列中的 jmp_env），当这个 continuation 被调用的时候，其参数会被返回。下面看一个具体例子：

(+ 1 (call/cc (lambda (k) (k (+ 2 3)))))

可能你很难理解，我们拆开来分析吧！当前我们正处于 (call/cc ...) 的语境下，马上可以分析出其 continuation 是：(+ 1 ...) 请留意这个 ...，因为他是我们调用 (continuation return-value) 后 return-value 返回的地方(即取代 call/cc 的函数调用)！

然后我们再看 call/cc 的参数，这个东西将会被调用，即控制流转到这个 lambda (k) (k (+ 2 3)) 函数中去，而 k 将会被 call/cc 传 continuation 进来！其具体流程用 python 讲解：

#原代码等价于：
  f = lambda k: k(2+3)
  plus(1, call/cc(f))
#call/cc 执行时等价于：
  def continuation(x):
    plus(1, x)
    f(continuation)
#结果：
    f(continuation)
  = continuation(2+3)
  = plus(1, 2+3)
  = 6

在分析具体流程的时候是不是很容易有一种 CPS 的感觉？这种 CPS 的感觉实际上就是 continuation 作为了一个间接的参数实现了即我们本来要做一件事情，中间插一脚给 call/cc 调用的函数，之后再 continuation 回来到 call/cc 上，只不过 CPS 编程中吧 continuation 放到了参数里而已。我们可以发现如果写程序的时候我们完全用 CPS 来写，call/cc 的实现将轻而易举（call/cc 此时本身也用 CPS 写了）！比如下面这段 javascript 代码（代码来自知乎）：

function callcc(f, k) {
  return f(k);
}

callcc(function(x) {return x(4 * 3);},
       function(y) {return 1 + y;});

所以这也解释了为什么能实现 CPS 变换之后 call/cc 的实现就变简单了（直接有 continuation 不用打包），因为 call/cc 就是 CPS 编程的不用参数版！

(define call/cc (lambda (f k) (f (lambda (v k0) (k v)) k)))

当然要完整学习 CPS 变换太长时间了了，我得留个坑，这个东西涉及 PL 的魔法，凡人避免走火入魔。

---

coroutine

本来感觉协程和本文的内容好像也没有什么关系？非也，coroutine 可以把本来的多次回调变成一个连续的过程，协程就是 continuation 的带调度管理器的版本，不如说是扩展化的 continuation。下面讲解协程怎么去实现。

第一点是，我们希望协程是 sequential 运行的而不是 parallel 的，这样才能有效避免使用各种并发控制手段如锁，并且因为程序本身知道所有同步信息，能够最大效率排列协程的运行，而不存在锁与轮询的浪费空转。

协程分有栈和无栈的，对于栈的处理这个我们上面讲 jmp 的时候讲过了。

我这里再提一个点，如果你想实现自己的协程库，要考虑的处理栈的处理，还有一个关键是对阻塞 I/O 的处理。为什么要关心这个呢？这是因为我们用 协程 主要是网络引用下写的，所以必然涉及到 read 和 write 等阻塞式系统调用，这时候整个线程都会阻塞，我们必须解决让协程挂起，一种方案是通过单独的线程去完成阻塞调用，一种是 hook 系统调用。hook 的原理也很简单，我们曾经学习过程序员自我修养链接装载与库，很容易想到通过链接时的同名函数覆盖即可实现 hook，当然涉及hook中调用原来函数则要使用dlsym 去查询 so，具体的很多内容我忘记了，我们之后会重新复习链接装载与库这本书（当然也配合APUE里面还是齐全的）再来编写协程库的博客。

在I/O复用模式(事件驱动，Linux下的select、poll 和 epoll 负责将底层 socket 的时分（理论上是包封）复用给封装出来)下本来是异步的，这个另说，接下来我们将会系统学习网络编程和 Unix 高级编程。（待补充...）

建议学习的协程库开源项目：libgo

---

总结

...（留个坑)