CS巴别塔(1)

A Complete Program Inside a Tweet?

Posted in Uncategorized by Kenny Yuan on 2010/09/21

这是一篇无聊的文章,对此不感兴趣的读者可自行选择:关Tab、关窗口、退订、拔网线、砸电脑、自残、自焚、人体炸弹、当黑暗大BOSS毁灭人类、入党……





Boss

Boss





OK,你还在,我也还在,那么我来继续记流水帐:《能否在一条tweet中写一个求值程序?》

看到有人讨论面试问题,其中有人提到用“现场写一个计算器”来作为考题。在瞎掰了很久之后,我决定自己实际试试,因为“光说不练是假把式”么……当然,既然是自我挑战,那目标就设高一点:试着在一条推中写完表达式求值程序……

……嗯……显而易见地,我失败了!不过我在一条推的长度内写完了一个后辍(RPN)表达式的求值程序,共113字符:

(defun r(e)(let((s()))(dolist(x e)(if(numberp x)(push x s)(push(eval(reverse(list(pop s)(pop s)x)))s)))(car s)))

用的是标准的stack解法。

至于将中辍转后辍的程序,我只写出来这个:

(defun v(e)(let((s())(o())(m'((+ 1)(* 2)(- 1)(/ 2))))(dolist(x e)(if(listp x)(setf x(v x)))(if(numberp x)(push x o)(progn(do()((or(null s)(<(cadr(assoc(car s)m))(cadr(assoc x m)))))(push(pop s)o))(push x s))))(r(append(reverse o)s))))

足足有235字符!看来目标是达不到了……(@googollee老大也失败鸟——嗯,我很happy)

不知道有没有哪位读者是语言达人,可以完成这个伟大的目标呢?

最后声明一下:直接eval,或者调用bc这些玩赖的方式肯定能行,但太没技术含量……

——路人甲:还有比这篇日志更没有技术含量的?

——路人乙:大家洗洗睡了吧!

于是,我去准备洗洗睡了……

(如果哪位有好点子,请一定别忘了留言)








Tagged with: ,

一次成功的远距离调试——1亿美元的硬件,1亿英里的距离

Posted in Uncategorized by Kenny Yuan on 2009/05/20

关键词:比天空更青蓝的悠远,比精金更珍贵的飞船……(听起来像不像深蓝判决?哈)

在Practical Common LISP一书(http://gigamonkeys.com/book/)中,讲了这样的一个故事:在那并不十分遥远的1998年,在1亿英里的高空,一架造价 1亿美元的太空船(NASA Deep Space 1:  http://nmp.nasa.gov/ds1/,不过这个网站被GFW了),其控制程序出现了条件竞争的BUG,而这个BUG在地面测试中没有发现(嗯,符合经典的软件规律)。于是,负责这部分代码的人就远程连接上飞船(是真正的远程啊!),从飞船上的LISP程序中调出来REPL窗口,在系统还在运行的时候进行诊断和调试,并修正了BUG,成功地部署,最终完成了任务。

这真正是一次成功的远距离调试——1亿美元的硬件,1亿英里的距离。

Tagged with: ,

浅谈OO编程中必不可少的手段:Multimethod

Posted in Uncategorized by Kenny Yuan on 2009/05/07

浅谈OO编程中必不可少的手段:Multimethod(又名Multiple Dispatch、Generic Function)

这可能是我写得最中规中矩的文章标题了。写这个文章的目的很傻很天真:“在網路上能夠google到的介紹multimethod的漢語文章很少”。有本很出名的书写了一笔(More Effective C++: Item 31),但很快就转而使用替代方案了。所以,我打算写一个这方面的文章给网络补充一下资源。算是遵循 “勿以善小而不为”的古训吧:)

一点历史介绍

在 上世纪的80年代中期,在LISP中出现了CLOS(读成see-loss)系统,它是Common Lisp Object System的缩写。CLOS被提出之后不久正好赶上了ANSI标准的制定。CLOS是如此之优秀,以至于它一字不改就被收录成了ANSI标准。因为它是 ANSI标准的一部分,所以基本上所有的Common LISP都带有CLOS。CLOS提供了很强大的功能,包括class定义,子类化(派生/继承),multimethod,before/after /around,重定义class,改变object的class,重新初始化object等功能(除此之外,CLOS还提供了一个强大的Meta- Object协议)。所有的这些,从功能上超过了任何其它支持OO编程的语言(就如同LISP的Condition超过了其它语言的Exception一 样)。

Multimethod是在设计CLOS的过程中提出来的。因为设计者们发现,不加入Multimethod的话,OO编程实践中 就缺少一个必要的手段。从这个角度来说,虽然Multimethod只能算CLOS中的一碟小菜,但它却是一碟很多人都需要、但是C++和JAVA就是不 给上的小菜(上的都是酸菜???)

——为什么要这么说呢?且慢慢听我道来……

很自然很舒服的面向对象

在多数教科书和随笔文章中,当讲解到面向对象技术时,一般都会举出动物的例子。我临时也编出来一个:
生物分为动物和植物;而动物可分为两栖、爬行和哺乳动物。哺乳动物中有狗有狼还有人,哺乳动物都有一个共同的行为:哺乳;两栖动物都有一个共同的属性:变态。

这个例子能很好的说明OO技术的自然性——它和人类认知中的concept正好对应[注1]:
1、Concept是一个分类方法;
2、Concept有它不同于其它concept的特有属性;
3、同属某个concept的个体有同样的属性;
4、Concept可以有层级关系,子concept拥有父concept的所有特性(但不一定能当成父concept来用,参考Liskov Subst Principle);

从这个角度来说,OO是成功的,因为它用很自然地,符合一般人思维的方式解决了一个复杂的归类问题。(这里暂且不提interface这回事,其实真正的OO是interface的天下,但interface却不是那么“自然”的)

如果我们记住了一个概念,我们就能够了解它所代表的事物的特点和功能,从而能够很好地使用它。OO技术带来了同样强大的(复用)能力——只要知道了class名字,就可以知道object的属性和功能,并方便地使用它们。

上面的例子可以总结成这样的关系:

类别间的关系

  • 植物 is a 生物
  • 动物 is a 生物
  • 两栖动物 is a 动物
  • 爬行动物 is a 动物
  • 哺乳动物 is a 动物
  • 狼 is a 哺乳动物
  • 狗 is a 哺乳动物
  • 人 is a 哺乳动物

行为

  • 两栖动物 can 变态
  • 哺乳动物 can 哺乳


(狼、狗、人的“哺乳”行为可以从“哺乳动物”中继承而来,不需要再进行重复声明)

分类和交互:复杂性之源

世界之所以复杂,不仅仅在于事物的多样性(分类),还在于事物之间的交互。一般意义上的交互是简单的,比如下面这段程序伪码(本想用汉编的,无奈我太笨,学不会,只好用英编了)

对于打印机打印图片,我们可以这样写
function Printer.Print(RMB rmb) Action:
1. Render rmb to memory;
2. Send memory to PrinterDriver;
3. Submit to PrinterDriver
End Action;

(似 乎最近从“瘾科技”开始,不少中文站都在说钞票防伪的事情。我也来PS一杠子:世界上有几十种钞票都是打印不了的,因为有Omron的猎户座防伪专利技 术,当然,在1996发行那种50马克之前,就不会有这个问题。具体例子和应用了此技术的钞币列表请参见:http://www.ybnotes.com /cn/ennewslist.asp?id=434)

现在我们用简单的动植物模型来实际编一些程序。基于食物链方面的常识,我们可以这样总结:
1. Animal.Eat(A Plant);
2. Animal.Eat(An Animal);

于是,我们这样定义动物类型,添加一个方法,名叫“吃”:
class Animal;
class Plant;

function Animal.Eat(Animal victim) Action:
me.Energy += victim.Energy;
End Action;

function Animal.Eat(Plant food) Action:
me.Energy += food.Energy;
End Action;

如果我们定义了猿是动物的子类别:
class Ape derived from class Animal;
那么Ape同样可以去Eat所有的Animal和Plant(child class从super class继承而来的)

你可能注意到了,对于同一个类型“动物”,我们定义了两个同样的方法,都名为“吃”,但是有不同的参数。是的,我们可以这样编程,这东西有个很响亮的名称叫重载overload。在这一点上,编程技术也是符合人们的思维习惯的。

啊——喔——出现了特例!

接下来的文章内容,非常符合作为读者的你的预料:我要开始讲特例了。一般在特例之后都是将程序搞砸,然后再引入清晰的解决方案来显示它有多么好,但是,我不想这样搞。我只想按照自然的思路来进行。不过,特例还是要引入的:)

话说那天下大事,如果真的是这样地简单那该有多好(前面一句请用单田芳的语调来念)。只是事情往往不在最完美的阶段结束,就像好莱坞电影里说的:And death… is only the beginning…

在一般情况下,上面提到的方式运作良好。但事事有例外。比如我们突然发现有种植物叫猪笼草,它竟然可以吃掉小昆虫!
1. Animal.Eat(A Plant);
2. Animal.Eat(An Animal);
3. SomePlant.Eat(An Animal); // 吃动物的植物

其实不只是猪笼草这样的交互特例。前面的例子也省略掉了许多分类方式,比如动物要分为食草、食肉、杂食的,除此之外有微生物。吃昆虫的植物其实也进行光合作用……

如果编一张表格,所有的关系就清楚了。

生物 动物 植物 食肉动物 食草动物 杂食动物 微生物 捕食的植物 猪笼草
生物
动物
植物
食肉动物
食草动物
杂食动物
微生物
捕食的植物
猪笼草

我 目前不打算完成这个表格,因为这个表格搞起来很麻烦(如果是左小龙的话他肯定也不干,除非那表格的体温是37 度:http://www.qidian.com/BookReader/1100289,21986729.aspx)。但即使不完成这个表格,我们也 能知道表格里会有许多重复项目,比如:如果食草动物能吃所有植物,那么它就能吃猪笼草(虽然现实生活中它们基本是不吃的)。有了前者作为规则,后者是不需 要再描述一遍的。一般说来,super class的规则基本上适用child class,但是child class有时候会有特殊规则。如果能够识别child class,对于特殊的child class按照特殊规则处理,没有特殊规则的就按super class的规则进行处理,这样就比较完美了。

用Multimethod编写交互规则

可 能很多人都同意这一条:变化是重构的ringing bell。考虑到植物动物和微生物的分类关系,与它们之间的“吃”与“被吃”的复杂关系。很明显地,重构的结果应该能够表达上面的这个表格中的内容。但手 工编码所有的这些对应关系肯定是last way to go(参见本文的last paragraph)。如果能有一种书写方式将一般规则和特殊规则结合起来——child class拥有特殊规则时就应用特殊规则,否则就应用针对super class书写的一般规则——如果能这样书写就同样自然、同样舒服了:

这种书写方式就是Multimethod:

一上来还是class的定义:
class Organism; // 定义生物
class Animal derived from class Organism;   // 定义动物类型
class Plant derived from class Organism;    // 定义植物类型
class Microbe derived from class Organism;  // 定义微生物类型
class Insect derived from class Animal;     // 定义动物类型
class PredaciousPlant derived from class Plant;  // 定义捕食的植物类型
class Nepenthes derived from class PredaciousPlant; // 定义猪笼草类型
class Herbivores derived from class Animal; // 定义食草动物
class Carnivore derived from class Animal;  // 定义食肉动物
class Omnivore derived from class Carnivore and class Herbivores;   // 定义杂食动物
class Ape derived from class Omnivore;      // 定义猿

然后是Multimethod方式编写的交互规则:

// 生物互吃:暂时不知道如何定义
function Eat(Organism predator, Organism victim) Action:
Print “Don’t known how to eat”;
End Action;

// 草食动物吃植物(包括杂食动物)
function Eat(Herbivores predator, Plant victim);

// 肉食动物吃动物(包括杂食动物)
function Eat(Carnivore predator, Animal victim);

// 捕食的植物号昆虫
function Eat(PredaciousPlant predator, Insect victim);

// 猪笼草吃昆虫
function Eat(Nepenthes predator, Insect victim) Action:
Print “Any special processes for nepenthes”;
End Action;

// 草食植物吃磨菇(包括杂食动物)
function Eat(Herbivores predator, Microbe victim) Action:
If victim.IsMushroomLike then …;
End Action;


// 微生物分解死去的动物
function Eat(Microbe predator, Animal victim) Action:

if victim.IsDead then call decompose(victim);
End Action;


// 微生物分解死去的植物
function Eat(Microbe predator, Plant victim) Action:
if victim.IsDead then call decompose(victim);
End Action;


很简单、很自然,很符合人类思维。

熟悉OO的可能会发现,这写法看起来很像重载,但实际上……它是一个电吹风运行时的机制。Multimethod可以按参数的实际类型决定调用哪个函数,也就是说,你可以按Organism类型传入参数,但它实际是一个吹风机猪笼草对象。在运行时,就会首先用猪笼草类型去匹配,以便决定使用哪个函数。
Multimethod与重载(overload)是有明显的区别的。重载是编译时的机制,在运行时不会起作用:如果你以Organism类型传入两个参数,不管实际上它是什么样的child class object,它只会去调用Eat(Organism, Organism),而不会去尝试区别实际child class。

在LISP中测试Multimethod

学习翠花,直接上代码。因为这些代码的自我说明能力很强,就不多加说明了。

(defclass organism() ()) ;;; 定义生物类型
(defclass animal (organism) ())   ;;; 定义动物类型
(defclass plant (organism) ())     ;;; 定义植物类型
(defclass microbe (organism) ())   ;;; 定义微生物类型
(defclass insect (animal) ())      ;;; 定义动物类型
(defclass predacious-plant (plant) ())   ;;; 定义捕食的植物类型
(defclass nepenthes (predacious-plant) ()) ;;; 定义猪笼草类型
(defclass herbivores (animal) ())  ;;; 定义食草动物
(defclass carnivore (animal) ())   ;;; 定义食肉动物
(defclass omnivore (carnivore herbivores) ())    ;;; 定义杂食动物
(defclass ape (omnivore) ())       ;;; 定义猿

;;; 声明Multimethod函数
(defgeneric eat(predator victim)
(:documentation “Something eats another”))

;;; 生物互吃:暂时不知道如何定义
(defmethod eat((predator organism) (victim organism))
(format t “Organism –> Organism: Don’t known how to eat…”))

;;; 动物吃植物:只有某些动物吃植物
(defmethod eat((predator animal) (victim plant))
(format t “Only some of animals eat plant…”))

;;; 昆虫吃植物:多数昆虫都是吃植物的
(defmethod eat((predator insect) (victim plant))
(format t “Most of the insects eat plant…”))

;;; 草食动物吃植物(包括杂食动物)
(defmethod eat((predator herbivores) (victim plant))
(format t “Herbivores –> Plant”))

;;; 肉食动物吃动物(包括杂食动物)
(defmethod eat((predator carnivore) (victim animal))
(format t “Carnivore –> Animal”))

;;; 捕食的植物号昆虫
(defmethod eat((predator predacious-plant) (victim insect))
(format t “Predacious Plant –> Insect”))

;;; 猪笼草吃昆虫
(defmethod eat((predator nepenthes) (victim insect))
(format t “Nepenthes –> Insect”))

;;; 草食植物吃磨菇(包括杂食动物)
(defmethod eat((predator herbivores) (victim microbe))
(format t “Herbivores –> Mushroom (Microbe)”))

;;; 微生物分解死去的动物
(defmethod eat((predator microbe) (victim animal))
(format t “Deposing dead animal (Microbe –> Animal)”))

;;; 微生物分解死去的植物
(defmethod eat((predator microbe) (victim plant))
(format t “Deposing dead plant (Microbe –> Plant)”))

下面是对eat函数进行各种测试的结果:

LISP> (eat (make-instance ‘organism) (make-instance ‘organism))
Organism –> Organism: Don’t known how to eat…

LISP> (eat (make-instance ‘herbivores) (make-instance ‘organism))
Organism –> Organism: Don’t known how to eat…

LISP> (eat (make-instance ‘ape) (make-instance ‘organism))
Organism –> Organism: Don’t known how to eat…

LISP> (eat (make-instance ‘ape) (make-instance ‘animal))
Carnivore –> Animal

LISP> (eat (make-instance ‘herbivores) (make-instance ‘plant))
Herbivores –> Plant

LISP> (eat (make-instance ‘ape) (make-instance ‘plant))
Herbivores –> Plant

LISP> (eat (make-instance ‘ape) (make-instance ‘ape))
Carnivore –> Animal

LISP> (eat (make-instance ‘insect) (make-instance ‘animal))
Organism –> Organism: Don’t known how to eat…

LISP> (eat (make-instance ‘insect) (make-instance ‘ape))
Organism –> Organism: Don’t known how to eat…

LISP> (eat (make-instance ‘insect) (make-instance ‘nepenthes))
Most of the insects eat plant…

LISP> (eat (make-instance ‘nepenthes) (make-instance ‘animal))
Organism –> Organism: Don’t known how to eat…

LISP> (eat (make-instance ‘nepenthes) (make-instance ‘insect))
Nepenthes –> Insect

LISP> _

在C++中实现Multimethod

在C++中,因为只有重载,而没有multimethod,为了达到同样的效果,你需要这样写:
void Eat(Organism predator, Organism victim)
{
if ( predator
is_a Herbivores )
{
if ( victim is_a Plant )
{

}
else if ( victim
is_a Microbe && victim.IsMushroomLike() )
{

}
}
else if ( predator
is_a … )

}
注:上面的is_a是一个伪操作符,用来判断前者的实际类型可不可以是后者(请联想instanceof)。

这 种方法称为BF法,特点是“霸王硬上弓”,一切全靠if-else和cast。维护这样的一个大型if-else嵌套结构可不是一件容易的事情。当然,如 果使用Visitor模式,肯定是可以解决这样的问题。但那样会导致问题的表达绕了很大的圈子。不直接表达就导致难于理解,而且书写起来很麻烦,扩展/修 改起来也很费力。最致命的一点,它只能处理double-dispatch问题,也就是只有两个继承体系的交互问题,对于三个或三个以上的,就无能为力 了。Multimethod则可以处理多个参数,也就是多个继承体系之间的交互问题,在参数列表中添加一个参数就可以了。

(还有一位被肠子捆住脖子的邪神LOKI,它有一种用模板来实现dispatch的方法,因为很复杂,也不太好用,这里就不再详述了,感兴趣的可以在google猛搜LOKI和独眼龙奥丁的故事)

参考资料

1、我的大脑
2、大搞学术造假的所有的院士、教授、博士、硕士们写的所有论文(这样子能帮他们增加引用不?听说帮人引用论文还能挣钱呢!)

注释

[1]关于Concept
Concept在人类的思维和语言交流之中的重要性无论如何夸大也不过份。如果没有了Concept,我们无法学习,无法描述、无法理解、无法记忆、无法祈使……
在这里我不打算完整说理,举几个例子
例1:请在不使用Concept的情况下,向别人讲解圆面积公式(提示:圆、面积、半径、PI等等都是Concept)
例2:请在不使用Concept的情况下,命令你的小孩放下手中的玩具,坐到这边的椅子上来(玩具,椅子等都是Concept)
例3:请在不使用Concept的情况下,向你的朋友描述你刚刚是如何从家中来到聚会地点的(汽车、路、交通、堵车、步行等等都是Concept)

Tagged with: , ,