AMB in ruby

昨天，读了g9的一篇文章,里面谈到了continuation和AMB。这两个概念，我恰巧都不知道。于是乎，一头扎了进去，出不来了。本打算昨天晚上能把代码读懂，写篇文章记录一下学习心得。不料天资驽钝，到下班也没看懂，晚上还要看欧洲杯。所以文章也没写成。
  今天，忙了一整天也没功夫继续昨天的半拉子工程。快下班了，才想起来那件事。于是乎，又一头扎了进去。灵感迸发于一头雾水许久之后。我看懂了，心情激动自不用说。
先上代码：

def must(amb,p)
amb.choose if !p
end
require "continuation"
class Amb
	def initialize
		@backtrack_points=[proc{fail RuntimeError, "no choice found"}]
	end
	
	def choose(*choices)
		choices.each do |choice|
			Kernel.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
def distinct?(list)
list.uniq.size == list.size
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)

其实，大多数代码都很好懂，只要是略懂ruby的语法。难点在于类Amb的方法choose:

def choose(*choices)
		choices.each do |choice|
			Kernel.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

这个callcc方法是个什么东西呢？于是，去查了官方文档，知道是关于continuation的。

引用

Continuation objects are generated by Kernel#callcc . They hold a return address and execution context, allowing a nonlocal return to the end of the callcc block from anywhere within a program. Continuations are somewhat analogous to a structured version of C's setjmp/longjmp (although they contain more state, so you might consider them closer to threads).

这段文字，说实话我当时没看懂，更准确的说是我根本看不进去。真的很晦涩，那时看来。现在看了，真的很好懂。翻译成中文：
Kernel.callcc方法会产生continuation对象。continuation中保存了一个返回地址和执行的上下文，允许从一个程序内部的任何地方，非局部的跳转到callcc 块的末尾。Continuation有点类似于c中setjmp/longjmp的结构化版本。（continuation中包含了更多的状态，你可以认为它更接近于线程）

现在我的理解，continuation就是带上下文的goto嘛。

有了这样的理解，我们再来看上面的代码。

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)

每一行调用带参数的choose方法，都会把当前的continuation对象压入堆栈@backtrack_points。这样在调用

must(amb,distinct?([baker,cooper,fletcher,miller,smith]))

之前，成员变量@backtrack_points中已经压入了5个continuation对象。

must方法中，如果条件不满足就会调用Amb的choose方法，单不会传入任何参数。这样，实际上只会执行

@backtrack_points.pop.call

而不会执行

choices.each do |choice|
			Kernel.callcc do |cont|
                                @backtrack_points << cont
				if choice.respond_to? :call
					return choice.call
				else
					return choice
				end
			end
		end

但是，实际上@backtrack_points.pop是把最近的那个continuation弹出了，然后调用了它的call方法。这一步就会发生跳转和上下文切换。从哪里跳到哪里呢？从

must(amb,distinct?([baker,cooper,fletcher,miller,smith]))

跳到：

Kernel.callcc do |cont|
				@backtrack_points << cont
				if choice.respond_to? :call
					return choice.call
				else
					return choice
				end
			end

我们很容易看出，最近的那个continuation是对应于smith=amb.choose(1,2,3,4,5)这行调用。这还不准确，准确来说是对应于

	def choose(*choices)
		choices.each do |choice|
			Kernel.callcc do |cont|
				@backtrack_points << cont
				if choice.respond_to? :call
					return choice.call
				else
					return choice
				end
			end
                        # 此处。此时choice=1
		end
		@backtrack_points.pop.call
	end

正如我在代码中的注释所指的，就是那一行。还记得这句话吗：

引用

ontinuation中保存了一个返回地址和执行的上下文，允许从一个程序内部的任何地方，非局部的跳转到callcc 块的末尾。

记住是callcc块的末尾。然后，切换上下文来确保我们能继续上次中断的执行，那个each的下次迭代开始了，choice的值是2，然后调用Kernel.callcc，并把当前的continuation对象传给cont. callcc的块执行把cont压入@backtrack_points，然后判断变量choice是否定义了call方法（这句似乎多余）。如果没有定义call方法，就返回当前的choice值。
返回到哪里去呢？当前的continuation对象中不是包含返回地址吗？它指向哪里呢？它对应于哪次调用呢？是这里：

smith=amb.choose(1,2,3,4,5)

所以它返回这里，于是乎，smith=2了。

然后接着执行下条语句

must(amb,distinct?([baker,cooper,fletcher,miller,smith]))

如果distinct?([baker,cooper,fletcher,miller,smith])还是false那么还会再次进行不带参数的choose调用。从而，再次回朔，再次尝试。

解释到这里，感觉上好像是这样一句话：
如果不行，那就从头再来。
当然，这里的头指的是最近的回朔点。

这样就可以，进行多层次的枚举了。实际上就是穷举法嘛。直到找到一个能通过的组合。

这段代码要解决的问题是这样的：

引用

Baker, Cooper, Fletcher, Miller, 和Smith住在一动5层公寓的不同楼层。Baker不在顶楼住。Cooper不在底楼住。Fletcher既不在顶楼也不在底楼。Miller住的楼层比Cooper住的高。Smith和Fletcher的楼层不相邻。Fletcher和Cooper的楼层不相邻。问每个人住的楼层。

我是不是要补一张图呢？需要吗？先找一个好的作图工具吧。