7thGen

今天翻到另外一篇老文章（最近对旧闻着迷，觉得新闻都是那么的烂），是 AI 和 Lisp 大牛，现任 Google 研究院的头子 Peter Norvig 2001年写的 Teach Yourself Programming in Ten Years（郭晓刚君有一个非常好的中文译文），名字一看就是调侃满大街那种《21天精通 C++》之类的东西的，但是这个其实不光出书人的问题，这是一种世界共通的浮躁，浮躁是失败之源，所以看看这种文字真是舒服。

里面提到一个观点，引用了 Alan Perlis（1922-1990，ACM 第一任主席，图灵奖得主）的话：“如果一门语言不能影响你对编程的想法，那它就不值得去学”，然后进一步建议要精通编程，就至少得掌握半打编程语言，其中要有一种带类抽象（class abstraction）的（例如 C++），一种支持函数抽象（functional abstraction）的（例如 Lisp），一种支持语法抽象（syntactic abstraction）的（再次的例如 Lisp），一种支持描述性规约（declarative specification）的（例如 Prolog），一种支持协程（coroutine）的语言（如 Scheme），最后还要有一种支持并行处理（parallelism）的（如 Erlang）。这些都是很有趣的概念——而且不少并不被我国广大编程人员熟悉——正好被勾起一点感觉，就顺便说说函数编程里的重要概念，Continuation，作为 Tao of Ruby 中函数编程部分的一点素材吧。

什么是 Continuation

Continuation，简单地说就是一种超级 goto ，支持 Continuation 的语言允许显式的创建一种叫做 Continuation 的对象，将创建时系统所有的上下文信息保存在里面，然后程序员可以在需要的任何时候回到这个状态继续执行下面的代码。这个机制能够赋予程序员对程序时间极其强大和直接的控制力——你可以暂停一段计算，然后在一段时间之后继续执行。这种机制其实是为函数编程的核心观念服务的。函数编程的核心观念可以描述为：

所有程序都是函数的求值过程（包括函数的定义也是）
函数的求值过程是孤立、无状态的

Continuation 在不破坏这种状态隔离的同时提供了非常灵活的控制跳转手段，使得一些关键性的算法得以方便的实现。下面我们来看一个例子，amb 函数（算子）及其应用。

神奇的 amb

amb 的意思是 ambiguous，即“模糊函数”，最早是现代 AI 技术和 LISP 元老，John McCarthy在 1963 年提出的，它的定义是这样的：

函数 amb 接受 0 或多个参数输入，输入参数既可以是原子也可以是其他函数，其值计算满足所有下面的这些要求：

如果输入参数多于 0 个，则求值为其中不确定的某一个。

如果输入参数个数为 0（即无输入参数），则求值失败，抛出一个异常。

在全局范围内，求值过程应该尽可能的有效，而避免异常抛出。

对于大多数人来说，这个函数不要说实现，就是看定义都要半天才能转过弯来，让我们稍微做一些分析。首先，无参数调用 amb() 必然失败；其次，这个函数的实现与求值环境有关，不能够简单的检查传入参数来判断求值，由于定义 3，下面这个例子里，第一个 amb 求值必须返回为 true ，因为返回 false 会导致求值 amb() ，结果是失败。

if amb(false, true) 
  return 1
else
  return amb()
end

有趣的东西啊——但是有什么用处呢？这个有兴趣看 McCarthy 论文的可以得到比较深刻的答案，没耐心的么，用个例子来说明： amb 可以用来实现“生成-测试”系统，即所谓的“探索”系统。SCIP（ Structure and Interpretation of Computer Programs，MIT 的计算机科学专业的教材，用 Scheme 语言来讲解计算机编程理论，第一版是 1984 年出版的，最新的第二版是 1993 出版的，大学一年级用，我国教育工作者们都应该汗颜 -_-bb ）的作者 Gerry Sussman 有一篇论文，叫做 Building Robust Systems (pdf)，里面从生物进化五大特性出发，研究出通用的健壮计算机系统的五大基础功能，其中之一就是“生成-测试”：系统应该允许人们创建返回多项选择的函数，然后对这些结果进行同步测试，找出合适的结果；如果结果不够好，系统能够自动回溯。当然这可能导致指数级增长的运行时间，但是这是进化必须付出的代价。其实逻辑编程语言如 Prolog 不就是这么干的么？下面用 SCIP 中的一道习题来说明如何用 amb 函数来模拟类似 Prolog 的描述性规约（declarative specification）编程，也就是“生成-测试”模式。

Baker, Cooper, Fletcher, Miller, and Smith live on different floors of an apartment house that contains only five floors. Baker does not live on the top floor. Cooper does not live on the bottom floor. Fletcher does not live on either the top or the bottom floor. Miller lives on a higher floor than does Cooper. Smith does not live on a floor adjacent to Fletcher’s. Fletcher does not live on a floor adjacent to Cooper’s. Where does everyone live?

要你给 Baker，Cooper，Fletcher，Miller 和 Smith 五个人分一栋五层楼的房子，这帮人很麻烦，Baker 不住顶楼，Cooper 不住底楼，Fletcher 既不住顶楼也不住底楼，Miller 要比 Cooper 楼层高，Smith 不要和 Fletcher 楼层挨着，Fletcher 也不要和 Cooper 楼层挨着，那么？

假定我们已经有了 amb 函数的实现，那么下面就是这个题目的 Ruby 解法，注意，由于语法的问题，我们把 Ruby 的 amb 函数实现为 Amb 类的 choose 方法，所以下面的代码和上面的有些差别。

require "amb"

def must(amb, p)
  amb.choose if !p
end

def distinct?(list)
  list.uniq.length == list.length
end

amb = Amb.new

baker = amb.choose(1, 2, 3, 4, 5)
cooper = amb.choose(1, 2, 3, 4, 5)
fletcher = amb.choose(1, 2, 3, 4, 5)
miller = amb.choose(1, 2, 3, 4, 5)
smith = amb.choose(1, 2, 3, 4, 5)

must(amb, distinct?([baker, cooper, fletcher, miller, smith]))
must(amb, baker != 5)
must(amb, cooper != 1)
must(amb, fletcher != 5)
must(amb, fletcher != 1)
must(amb, miller > cooper)
must(amb, (smith - fletcher).abs != 1)
must(amb, (fletcher - cooper).abs != 1)

puts "baker: #{baker}, copper: #{cooper}, fletcher: #{fletcher}, miller: #{miller}, smith: #{smith}"

运行结果如下（自行检验）：

oasis:Ruby neo$ ruby scip-4.3.2.rb 
baker: 3, copper: 2, fletcher: 4, miller: 5, smith: 1

嗯，会 Prolog 的可以看看多么的相似，不会的可以体验下这和一般的命令式编程（imperative programming）有多么大的差别，描述完事实，问问题就行了。这个魔法的核心就是那个 amb ，正是因为它别具一格的特性，自动完成了生成-测试-回溯的过程。好了，我们知道了这个 amb 的不同凡响之处，终于可以回到我们关于 Continuation 的主题，这个 amb 的实现，如果不是“必须使用” Continuation 的话，至少也是“不用的话够你一折腾”的水平。下面我们来看 Ruby 里 amb 的实现。

Continuation 实践： amb 的 Ruby 实现

Ruby Quiz 提供了一个标准的 amb 函数实现，其实元祖是来自 Teach Yourself Scheme in Fixnum Days 这本书里的 Scheme 实现，由于 Ruby 语言支持 return 语法，所以可以比原先 Scheme 的实现简单了一些—— Scheme 的实现不得不多用了一次 callcc 来模拟 return，下面就是这个简化之后的版本：

class Amb
  def initialize
    @backtrack_points = [proc{fail RuntimeError, "no choice found"}]
  end

  def choose(*choices)
    choices.each do |choice|
      callcc do |cont|
        @backtrack_points << cont
        
        if choice.respond_to? :call
          return choice.call
        else
          return choice
        end
      end
    end
    @backtrack_points.pop.call
  end
end

下面是测试用例。

require "amb"

amb = Amb.new
amb.choose(1, 2, 3, 4)
=> 1
amb.choose(proc{amb.choose}, 1)
=> 1
amb.choose(proc{amb.choose}, 3, proc{amb.choose}, 2)
=> 3

if amb.choose(false, true)
  1
else
  amb.choose
end
=> 1

这个实现非常简短，除了边界初始化的代码之外，核心的 choose 方法就 10 来行，简要说明几个要点，其中妙味还需自行体会。

方法 Kernel#callcc 产生一个当前位置的 Continuation 对象，其实例方法 Continuation#call 能够回到创建该对象的位置，并从创建它的 callcc 块之后的代码开始执行，其实这个方法还有返回值，但是我们这个例子不用这个特性。
全局变量 @backtrack_points 保存每个条件测试的状态，采取的方式是堆栈，压栈的位置是第9行，而弹出的位置是18行。
在代码的任何位置出现 amb.choose 的无参数调用，那么都会去到18行，从 @backtrack_points 弹出一个 Continuation 对象，然后调用它的 call 方法，这等价于一次回溯，然后测试下一个输入，直到所有输入都测试完毕，如果再次出现 amb.choose 的无参数调用，则说明满足所有条件的选择不存在，程序失败；或者不出现 amb.choose 的无参数调用，那么程序执行成功。所以这等价于一个深度优先的搜索过程。

附1 Continuation 和 Co-routine

Co-routine 是和 Continuation 很有关联的一种函数编程特性，一般翻译作协程，这个名字明显的和 Sub-routine（子程）相对应，用来表示调用端和被调用端的平等协作地位。Ruby 中的 Co-routine 是借助纤程对象 Fiber 来实现的。

下面这个例子展示了 Fiber 的最简单用法，类方法 Fiber.yield 使控制流立刻跳转到当前代码段之后的第一行代码，同时把当前状态保存在 Fiber 对象中，可以在之后用实例方法 Fiber#resume 来回到该状态继续执行。所以这个例子就是个简单的循环而已，打印出前20个菲波纳契数。

fib = Fiber.new do  
x, y = 0, 1 
  loop do  
    Fiber.yield y 
    x,y = y,x+y 
  end 
end 

20.times { puts fib.resume }

下面这个例子稍微复杂一些，但是语言机制和上例完全一样。它展示了利用 Fiber 对象来实现在两个方法之间来回交换控制流的方法，这是典型的协程例子。

g = Fiber.new { |x|
  puts "G1: #{x}"
  x = Fiber.yield(x+1)   # Can't use resume here: double resume error
  puts "G2: #{x}"
  x = Fiber.yield(x+1)
}

f = Fiber.new { |x|
  puts "F1: #{x}"
  x = g.resume(x+1)
  puts "F2: #{x}"
  x = g.resume(x+1)
  puts "F3: #{x}"
}

f.resume(100)

与 Continuation 类似，Co-routine 也提供特殊的流程跳转，但是二者之间也存在明显的区别，限于篇幅就不展开了，这个讨论比较有教益：Continuation vs. Co-routine。

附2 Ruby 版本的变迁

其实 Ruby 在 1.8 和 1.9 版本之间，Continuation 和 Co-routine 特性有了不小的变化。主要有二：

Continuation 被从语言核心移出成为标准库，必须显式的引用 continuation 模块，然后遗留代码就可以正常运行了。其实 Matz 原来打算完全去掉这个特性的——原因是"no compelling use cases"，但是经过Ruby社区的一场大讨论，以 Avi Bryant（此人 Smalltalk 老鸟，dabbledb 和 Seaside 框架的作者）为首的一批大牛力挺 Continuation，于是最后是这个折衷的结果。
加入了 Fiber（纤程）这种轻量级线程，其实现方式就是 Co-routine（中文版本）。这是 1.9 中除了 VM 之外最引入注目的新特性，配合正在讨论中的本地线程，Ruby 将具有更加完善的并发处理机制，以不同的实现适应不同的需求。

7thGen

Continuation in Ruby