示例分析CALL/CC

说明：此文内容纯属个人看法，无所谓对错，欢迎拍砖！

call/cc(call-with-current-continuation)是函数编程的顶级概念，虽然我们用到的场合不是太多，但重要性非比寻常。

call/cc的魔力在于迫使运行的程序通过时光隧道返回到从前的某个时刻。

从返回的方式看我们可以有多种理解，下面是最常见的两种：

1、逐步退回：一步就是一次函数调用。执行call/cc时，程序自动执行函数返回操作（RET），直到返回的位置与call/cc的要求一致。

2、直接跳转：程序的指令系统直接切换到call/cc的位置，被抛掉的运行节点和对象留给GC处理。

命令式语言（如C/C++/PASCAL）可以很方便的实现第一种返回方式，比如使用异常和长跳转，但由于基于栈运行和缺乏GC支持，很难实现第二种返回方式。我们不在这里讨论语言的分类问题，而是通过一个例子，凭想象来推测一下call/cc背后都发生了些什么。

void b(function cc)
{
  = "b";
  cc(); // 返回a()中创建cc对象后的下一条指令位置
}

void a()
{
  callcc cc() { = "a" }; // 创建cc对象，这里是个函数
  b(cc);
}

现在运行函数a()并登记其运行过程：

a()开始执行。
|__创建call/cc函数cc()。
|__跳过cc()的返回执行代码。
|__将cc传递到b()函数中加以执行。
...b()开始执行
...|__打印字符'b'
...|__执行cc()。
......cc()开始执行
......|___中断b()回到a()，指令系统指向cc()的返回执行代码。
|__打印字符'a'
|__回到步骤4。

cc在第9步直接中断b()的运行回到a()并将指令系统指向cc()的返回执行代码，这一步是怎么发生的呢？

一、可以确定cc至少携带了以下两个信息:

1、a()的运行时信息（比如栈基址）。
2、cc返回执行代码的地址。

我们用结构ccrec来描述它们：

// call/cc 信息结构定义
struct ccrec {
  void * addr; // 函数运行时信息的地址
  unsigned long next; // 下一条指令的位置
}

指令系统可以假定为以下设计：

// 指令系统结构定义
struct isrec {
  struct ccrec current; // 当前运行时信息
  struct isrec *prior; // 上一级调用的指令系统结构
}

struct isrec *current; // 当前指令系统结构

void *get_call_base() // 提取当前运行时信息
{
  return current->current.addr;
}

unsigned long get_next_instruction() // 返回下一条指令的地址
{
  return current->current.next;
}

void set_next_instruction(unsigned long next) // 设置下一条指定的地址
{
  current->current.next = next;
}

二、callcc创建cc对象后在其内部保存以上两条信息：

// callcc 指令的处理过程
void * cc = create_function(); // 创建 cc 函数
struct ccrec * rec = create_new_ccrec(); 
rec->addr = get_call_base(); // 提取当前函数运行时信息
rec->next = get_next_instruction(); // 下一条即将执行的的指令
save_ccrec(cc, rec); // 保存信息到cc对象

三、cc执行时重置了指令系统的状态:

// 提取call/cc返回信息

struct ccrec * rec = load_ccrec(cc);

// 执行返回操作

while (rec->addr != get_call_base())
  exec_return(); //==> 它做了什么？

// 设置下一条指令

set_next_instruction(rec->next);

函数exec_return()不应该太复杂，大致的是如下的代码：

// 函数返回操作函数
void exec_return()
{
  // 1. 加锁休眠垃圾回收并返回当前指令系统结构
  struct isrec * curr = begin_return(); 

  // 2. 将当前运行时信息登记到垃圾回收系统
  gc_notify(curr);
 
  // 3. 设置指令系统，返回上一级调用
  current = curr->prior; 

  // 4. 完成返回操作后开锁，重新激活垃圾系统
  end_return(); 
}

这样的想象和推测单从理解上说应该是完备的，基于这个理解，我们试着做些更深层次的发挥。