浏览 3876 次
|
锁定老帖子 主题：健壮系统续：Amb的代码
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2007-05-14
Trustno1转的帖子后面还有一篇续文，给出了些具体代码。看样子Continuation挺有用，为什么Ruby2.0里要去掉Continuation呢？虽说YMRV不再支持Ruby的green thread，造成Continuation的实现困难，但不能说因为技术问题就废掉一个功能吧？原文在这里：http://blog.csdn.net/g9yuayon/archive/2007/04/23/1575731.aspx
==================华丽的转贴分界线=========================================
上篇帖子里聊到Sussman认为构造出健壮软件需要我们的系统支持continuation, 回溯，和生成-测试的方法。生成-测试最直观简单的方式是为系统提供多项结果。系统一个一个地测试这些结果，并接受符合要求的一个。Sussman举了一个例子：平方根函数通常返回正根，而抛弃那个负根。那按照生成-测试的方法，一个平方根函数应该将负根和正根一起返回，然后由系统决定到底哪个根更好。后来他进一步提到（第20页最后一段）可以返回正负根的AMB值。昨天写帖子写得头晕眼花，竟然忘记讨论这坨精彩的函数（编程意义上）。今天补上。我们可以看到一个简单（简单不等于浅显哈）的抽象，居然能实现众多美妙的功能。一个看似无意创造的玩具，竟然是有助于揭示构建辉煌软件大厦的秘密。
AMB这个操作符历史久远。AI大牛，LISP的奠基人，John McCarthy在这篇1961年的论文里首次提出了模糊函数（ambiguous function）。我们一般把这个函数简写为AMB。似乎最近俺读的文章也好，书也好，都越来越年代久远。不过不怕打击喜欢追新的老大们：现在流行和将要流行的技术背后的理念都至少有20年的历史。比如这个AMB函数，虽然1961年就被提出，但知道1987年还有研究它的论文发表。互联网？Google一下Douglas Engelbart。面向对象？Google一下Simula和Alan Kay。垃圾收集？Google一下LISP。BPEL？Google一下Robin Milner。作为编程语言的XML? Google一下S-Expression。元编程？Google一下Metaobject Protocol和CLOS。这其实符合技术革新的规律：大学里新奇的编程手段差不多要20年到30年才被大众接受。新理念提出后，还得被无数学者验证，润色，完善；还需要无数工程师实现，优化，改进，推广。所以说呢，如果老大们不满足于赶潮而憧憬弄潮，慢下来，向后看，也许是不错的手段。跑题老，还是说这个AMB操作符。俺最早在SICP上读到关于AMB的讨论。SICP也算是一本奇书。大一的入门教材，问世20来年了，里面的内容仍然让人拍案叫绝。每年翻开这本书，都能学到一点新的东西。书的第三章已经开始详细讨论并发和stream。第四章详细讲述了梦幻般的meta-circularity，接着就是现在开始热门的lazy evaluation，和logic programming。而第五章干脆教我们搭建一个简单的寄存器机器。又跑题了。最近越来越像老人家，变得唠叨。通俗讲，amb接受0或多个参数，并不确定地返回其中一个参数。比如说，amb(1, 2)可能返回1，也可能返回2。如果amb没有参数，那它不返回任何值，并抛出异常。也就是说，amb()一定挂掉。同时，amb的参数可以是一个函数（对用C/C++语言的老大来说，就是一个函数指针），amb返回的值必须是不会抛出异常的参数。比如说，amb(amb, 1)必须返回1，因为amb()会抛出异常。同理，amb(1, amb)也必须返回1。显然，amb的实现不能是简单的检测每个参数。比如下面这段代码里的amb(false, true)必须返回true, 不然else里的amb()就会被调用，导致这段代码抛出异常。
if amb(false, true)
return 1 else return amb() end 那这种不确定的函数到底有什么用呢？呵呵，用处大了。它正好简单地模拟了生成-测试：我们有一系列备选答案。我们把这些答案传给amb，他返回不会失败的那个。这不正好符合生成-测试的定义么？其实哪怕编程中这个函数也有妙用。比如说下面这道题（SICP4.3.2）：
Baker, Cooper, Fletcher, Miller, 和Smith住在一动5层公寓的不同楼层。Baker不在顶楼住。Cooper不在底楼住。Fletcher既不在顶楼也不在底楼。Miller住的楼层比Cooper住的高。Smith和Fletcher的楼层不相邻。Fletcher和Cooper的楼层不相邻。问每个人住的楼层。
有了amb这个函数，我们可以这么解决这道题（为了方便大多数人，我把Scheme代码移植到Ruby代码了。调用amb()变成了amb.choose）：
 看哈，每一行语句直接对应题目的条件。没有循环。没有递归。全靠amb这个看似简单的函数。运行的结果是：
 有Scheme运行环境的老大们可以运行下面的代码（在实现amb以后）。结果一样。
 第一次看到这段代码，我只觉得背后妖风阵阵。从来没有想到过，程序能写到这个地步。每一行语句居然和题目条件切合。比伪代码还为伪代码，但偏偏可以运行。那到底amb怎么实现？为什么俺要专门说这个函数呢？原因是这个函数的实现要用到continuation和回溯。当然不用continuation也能实现。比如用Java也行（友情提示：thread + 匿名类）。不过用continuation的方法最为简洁。Ruby代码不过10来行。所以我们先简介一下continuation。
Continuation到底有多重要一直有争议。Matz在邮件组里说Ruby 2.0会去掉continuation, 因为没有”compelling use cases”，结果引来一场讨论。Avi Brant就力挺continuation，毕竟他的Seaside框架就是基于continuation技术的。对了，Avi在今年的ETech会议上做了报告，批评RoR方法落后。这里有会议笔记，非常有教育意义。简单说，continuation就是高级goto，好比C下面的setjmp/longjmp + Solaris下的getContext()。它允许程序记住某一点的所有状态，然后在其它时刻回到那一点，继续执行。用Ruby举例（Ruby的callcc和Scheme的用法没有本质区别）：Ruby的函数Kernel#callcc生成一个Continuation对象，并把这个
知道了Continuation和回溯的概念，实现Amb也就容易了。因为是Ruby，我用了一个类来封装变量backtrack_points。这个实现的本质是深度优先搜索。每一步的状态用Continuation保存起来，回溯时使用。这本写得很好的Scheme入门书上也有amb的实现。Ruby Quiz提供了类似的代码，是从同一本书的Scheme代码直接移植的。不过Scheme不支持return, 所以它的实现用了两个call/cc。外层的用于模拟return （所谓的escaping continuation）。所以移植的代码不是那么容易理解。在Ruby里用了return语句后，代码要干净清晰得多：
 困。。。代码的解释改天继续。也许这段代码很直观不需要解释呢？哪位老大读到了这里，说说看？先谢谢了。
声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2007-05-14
从代码上看这里ruby的Amb实现只是返回第一个符合条件的解，好像不符合文章中说的呀，有哪位熟悉SICP的可以解释一下？
|
| 返回顶楼 | |
|
发表时间：2007-05-15
这里一开始确实都是只返回一个值，但是注意must里面无参数的choose，这个是重新洗牌，返回另外一个可能的结果
|
| 返回顶楼 | |
|
发表时间：2007-05-15
厌倦发呆 写道 这里一开始确实都是只返回一个值，但是注意must里面无参数的choose，这个是重新洗牌，返回另外一个可能的结果
偶的意思是如果这个楼层的排列有多个解，那么用这里的Amb实现就永远只会返回第一个解，而不是文章中说的任意一个。 |
| 返回顶楼 | |
|
发表时间：2007-05-15
Readonly 写道 厌倦发呆 写道 这里一开始确实都是只返回一个值，但是注意must里面无参数的choose，这个是重新洗牌，返回另外一个可能的结果
偶的意思是如果这个楼层的排列有多个解，那么用这里的Amb实现就永远只会返回第一个解，而不是文章中说的任意一个。 |
| 返回顶楼 | |
|
发表时间：2007-05-16
看了一下SICP里面关于amb的描述，这里有一段：
引用 On the other hand, if we have a machine that can execute only one process (or a few concurrent processes), we must consider the alternatives sequentially. One could imagine modifying an evaluator to pick at random a branch to follow whenever it encounters a choice point. Random choice, however, can easily lead to failing values. We might try running the evaluator over and over, making random choices and hoping to find a non-failing value, but it is better to systematically search all possible execution paths. The amb evaluator that we will develop and work with in this section implements a systematic search as follows: When the evaluator encounters an application of amb, it initially selects the first alternative. This selection may itself lead to a further choice. The evaluator will always initially choose the first alternative at each choice point. If a choice results in a failure, then the evaluator automagically46 backtracks to the most recent choice point and tries the next alternative. If it runs out of alternatives at any choice point, the evaluator will back up to the previous choice point and resume from there. This process leads to a search strategy known as depth-first search or chronological backtracking.47 amb本身是返回随机值，但是通常用深度优先的实现就返回第一个符合条件的了，这下弄明白了。 |
| 返回顶楼 | |
