日历

September 2009
M T W T F S S
« Aug   Oct »
 123456
78910111213
14151617181920
21222324252627
282930  

冒号课堂§4.2:逻辑范式

冒号课堂

第四课 重温范式(2)

4.2 逻辑范式——当算法失去了控制

郑晖

摘要

再谈逻辑式编程


道常无为而无不为

《老子•道经》

!预览

  • 评价代码的复杂度,长短只是一个因素。程序员不是打字员,花在思考上的时间和精力远远超过花在键盘上

  • 算法=逻辑+控制。其中逻辑是算法的核心,控制主要用于改进算法的效率

?提问

  • 衡量软件复杂度是由代码的长度决定的吗?

  • 为什么逻辑式的编码一般比过程式的更简洁?

  • 逻辑式编程相比命令式编程有哪些优势和劣势?

:讲解

问号提出:“逻辑式编程不是也很特别吗?前面似乎介绍得也不多。”

“那我们就用逻辑式语言Prolog再实现一次quicksort吧。”冒号说着将幻灯片翻页——

/*快速排序法的Prolog实现 */
/* 定义划分法 */
partition(_,[],[],[]).                             /* 划分递归终点 */
partition(Pivot,[X|Rest],[X|Small],Big) :- 
X < Pivot, partition(Pivot,Rest,Small,Big).        /* 比基准小的归入Small */
partition(Pivot,[X|Rest],Small,[X|Big]) :- 
X >= Pivot, partition(Pivot,Rest,Small,Big).       /* 比基准大的归入Big */

/* 定义排序法 */
qsort([],[]).                                      /* 排序递归终点 */
qsort([Pivot|Rest],Sorted) :- 
partition(Pivot,Rest,Small,Big),                   /* 按基准划分子列 */
      qsort(Small,SortedSmall),                    /* 对前面的子列递归 */
      qsort(Big,SortedBig),                        /* 对后面的子列递归 */
      append(SortedSmall,[Pivot|SortedBig],Sorted)./* 子列合并 */ 

逗号挠挠头:“看不太懂哦,好在我记住了您的一句话:容忍无知。我忍了!”

大伙都乐了。

“本节课的焦点不是语言而是范式,因此对Prolog代码不详加解说。我只简单地说三点:首先,Prolog代码是由一系列事实(fact)、规则(rule)和查询(query)语句组成的[1]。其次,与大多数语言不同的是,大写字母或下划线开头的标识符是变量,其他的是常量或函数。请注意,这不是约定俗成,而是语法规定。最后,符号‘:-’等价于if;逗号‘,’等价于and。比如,我们可以用Prolog来表达一个断言:如果一个人未婚且为男士,那么他就是一光棍。”冒号转身在黑板上写下——

/* X is bachelor if X is unmarried and male*/
bachelor (X) :- unmarried(X) , male(X). 

听见下面一阵嘀咕声,冒号忽地闪过一个念头:这个例子该不会触动了满足条件的某位同学的心事吧?顿了一会,继续说道:“逻辑式实现的排序虽不比函数式更简洁,但比起过程式来还是绰绰有余的。毕竟同属声明式,省去了不少有关变量赋值、迭代和流程控制方面的代码。我们再看一个更加典型的范例。”

黑板上出现了一幅树状图形——

图4-1. 家谱

家谱

冒号简作说明:“这是一个三代家谱图。已知每人的性别和父辈,要求判断任意两人之间的关系。我们先用Java来试一试——”

class Person
{
    private Person parent;
    private boolean isMale;

    public Person(Person parent, boolean isMale)
    {
        this.isMale = isMale;
        this.parent = parent;
    }

    private boolean isSibling(Person other)
    {
        return parent == other.parent && parent != null && this != other;
    }

    public String getRelation(Person other)
    {
        if (other == null || this == other) return null;

        if (parent == other) return isMale ? "son" : "daughter";

        if (other.parent == this) return isMale ? "father" : "mother";

        if (parent == null) // this是老祖宗
        {
            if (other.parent == null) return null;

            if (other.parent.parent == this) return isMale ? "grandfather" : "grandmother";

            return null;
        }

        if (other.parent == null) // other是老祖宗
        {
            if (parent.parent == other) return isMale ? "grandson" : "granddaughter";

            return null;
        }

        // 非直系
        if (isSibling(other)) return isMale ? "brother" : "sister";

        if (parent.isSibling(other.parent)) return "cousin";

        if (parent.isSibling(other)) return isMale ? "nephew" : "niece";

        if (isSibling(other.parent)) return isMale ? "uncle" : "aunt";

        return null;
    }

    public static void main(String[] args)
    {
        Person a = new Person(null, true);
        Person b = new Person(a, true);
        Person c = new Person(a, true);
        Person d = new Person(a, false);
        Person e = new Person(b, false);
        Person f = new Person(b, true);
        Person g = new Person(c, false);
        Person h = new Person(d, true);
        Person i = new Person(d, false);
        Person j = new Person(d, true);
        // 以下省略。。。
     }
}

“这段代码很平凡,毋需多言。再来看看逻辑式语言的做法。”冒号不愿过多地纠缠于细节,随即又换成了Prolog代码——

/* 规则 */
/* 上下两代直系关系 */
father(X,Y)        :- parent(X,Y), male(X).
mother(X,Y)        :- parent(X,Y), female(X).
child(X,Y)         :- parent(Y,X).
son(X,Y)           :- parent(Y,X), male(X).
daughter(X,Y)      :- parent(Y,X), female(X).

/* 祖孙关系 */
grandparent(X,Y)   :- parent(X,Z), parent(Z,Y).
grandfather(X,Y)   :- grandparent(X,Y), male(X).
grandmother(X,Y)   :- grandparent(X,Y), female(X).
grandchild(X,Y)    :- grandparent(Y,X).
grandson(X,Y)      :- grandparent(Y,X), male(X).
granddaughter(X,Y) :- grandparent(Y,X), female(X).

/* 平辈关系 */
/* 若X与Y有相同的父辈Z,且X不是Y,则X与Y是同胞*/
sibling(X,Y)       :- parent(Z,X), parent(Z,Y), X\==Y. 
brother(X,Y)       :- sibling(X,Y), male(X).
sister(X,Y)        :- sibling(X,Y), female(X).
cousin(X,Y)        :- parent(Z,X), parent(W,Y), sibling(Z,W).

/* 上下两代旁系关系 */
uncle(X,Y)         :- parent(Z,Y), brother(X,Z).
aunt(X,Y)          :- parent(Z,Y), sister(X,Z).
nephew(X,Y)        :- parent(Z,X), sibling(Z,Y), male(X).
niece(X,Y)         :- parent(Z,X), sibling(Z,Y), female(X).

/* 定义一个普适关系relation,方便查询 */
relation(R, X, Y)       :-  relations(Rs), member(R,Rs), Q =..[R,X,Y], call(Q).

/* 事实 */
/* 关系列表 */
relations([parent,father,mother,son,daughter,grandparent,grandfather,
grandmother,grandchild,grandson,granddaughter,
                sibling,brother,sister,cousin,uncle,aunt,nephew,niece]).

parent(a,b). parent(a,c). parent(a,d).
parent(b,e). parent(b,f).
parent(c,g).
parent(d,h). parent(d,i). parent(d,j).

male(a).
male(b).
male(c).
female (d).
female (e).
male(f).
female (g).
male(h).
female (i).
male(j). 

叹号没有看出名堂:“Prolog代码并不比Java代码简短多少啊。”

“评价代码的复杂度,长短只是一个因素。程序员不是打字员,花在思考上的时间和精力远远超过花在键盘上。”冒号指出,“就拿此例来说,Java代码虽然并不复杂,但有不少的选择分支语句,次序很重要。稍有不慎,就会出现逻辑错误。另外如果我们把关系分得更细致些,比如区分叔伯舅、姑姨婶、堂兄表妹等;再加入姻亲关系,比如姑嫂婆媳、妯娌连襟等。这时你再来改写这段代码试试?”

引号听得头皮有些发麻:“那一定需要不少重重嵌套的if-else语句了。”

问号提出的问题更让人头痛:“如果我们不限于三代,再加上曾孙女、曾叔父之类的关系呢?”

逗号联想到一则笑话:“话说一对父子与一对母女联姻,作父亲的娶了那位女儿,作儿子的娶了那位母亲。本来关系已经够颠倒错乱了,雪上加霜的是这两对夫妇又各自有了子女,那位父亲终于精神崩溃了。”

大家哄笑着:这下彻底乱套啰。

“前面的Java代码之所以没有嵌套,得益于及时退出的一些return语句。如果考虑到超过三代的关系以及多重交叉的关系,许多语句都得改写。可见上述代码是多么地脆弱!” 冒号就棍打腿,“再看Prolog代码,如果要求更细的血亲关系、增加姻亲关系或三代以上的关系,只需引入新的规则和事实即可,不会影响原有代码。下面列出几个示范语句——”

/* 规则 */
/* 配偶原则 */
father(X,Y)          :- spouse(Z,X), mother(Z,Y).
mother(X,Y)        :- spouse(Z,X), father(Z,Y).
husband(X,Y)      :- spouse(X,Y), male(X).
wife(X,Y)            :- spouse(X,Y), female(X).

/* 父系的堂、姑兄弟姐妹 */
paternal_cousin(X,Y) :- father(Z,X), father(W,Y), sibling(Z,W).
/* 母系的舅、姨兄弟姐妹 */
maternal_cousin(X,Y) :- mother(Z,X), mother(W,Y), sibling(Z,W).

/* 姻亲关系 */
father_in_law(X,Y) :- spouse(Y,Z), father(X,Z).
mother_in_law(X,Y) :- spouse(Y,Z), mother(X,Z).
son_in_law(X,Y)    :- spouse(X,Z), daughter(Z,Y).
daughter_in_law(X,Y) :- spouse(X,Z), son(Z,Y).

/* 曾祖孙关系 */
great_grandparent(X,Y) :- grandparent(Z,Y), parent(X,Z).
great_grandchild(X,Y)  :- grandchild(Z,Y), child(X,Z).

/* 事实 */
/* 新引入的关系 */
relations([husband,wife, paternal_cousin,maternal_cousin,
father_in_law,mother_in_law,son_in_law,daughter_in_law,
great_grandparent,great_grandchild]).

parent(pa,a).
spouse(a,as).
spouse(ds,d).
spouse(cs,c). 

句号方悟其妙:“这样的代码既无层层嵌套,也无次序分别。比起过程式,编写轻松得多,程序的可维护性和可扩展性也更高。”

“此外另有妙处。逻辑式与过程式和函数式的一个不同之处是,它没有明显的输入、输出之分。上面的程序不仅可以用来判断任意二人之间的关系,还能倒过来通过关系来找人。”冒号板书了几行字——

输入查询:relation(R,a,ds) /* a与ds的关系是什么? */

输出结果:R=father_in_law

输入查询:great_grandparent (pa,X) /* pa是谁的曾祖?*/

输出结果:X=e;X=f;X=g; X=h; X=i; X=j;

引号义务作翻译:“这告诉我们两件事:a与ds是翁婿关系,pa有曾孙e、f、g、h、i和j。”

“逻辑式语言着眼于关系而非函数,对付这类问题正是它的拿手好戏。”冒号声音逐渐高亢,“大家应该都听说过等式‘算法+数据结构=程序’吧?这是Pascal设计者Niklaus Wirth的一本著作的书名,它刻画了过程式尤其是结构化编程的思想。后来Robert Kowalski进一步提出:算法=逻辑+控制。其中逻辑是算法的核心,控制主要用于改进算法的效率。在逻辑式编程中,程序员只需表达逻辑,而控制交给编程语言的解释器或编译器去管理。”

“所以程序员的负担大大减轻了。”问号接口道,“逻辑式编程听起来真是不错,但不知Prolog程序能否与Java程序对接呢?”

冒号回答:“任何程序之间的对接都是可能的,只是不同的对接方式在复杂度和效率上有所差异而已。除了通过程序之间的通讯(如socket)或可执行文件的直接调用外,Prolog与C、C++、Java、C#、VB、Perl、JavaScript等多种语言之间,还能借助工具进行源代码转换[2]或通过双向编程接口互嵌代码。具体到Java,一方面可以通过JNI (Java Native Interface)与Prolog引擎相连[3],另一方面可以利用Prolog引擎的Java实现来完成JVM上的集成[4]。”

句号请求:“能否总结一下逻辑式编程的优缺点?”

冒号欣然应允:“由于逻辑式编程模拟人类的逻辑思维,故而在机器证明、专家系统、自然语言处理、博弈等人工智能领域如鱼得水,同时在非学术领域的知识管理、智能决策分析等方面也能大显身手。同为声明式,它与函数式一样比命令式更简洁、更抽象、更少副作用,运用得当能大大提高生产效率,还能用于快速原型(rapid prototyping)开发。但缺点是运行效率偏低,可掌控性较差,与常规的过程式思维差异较大,更适合基于规则(rule-based)而不是基于状态(state-based)的应用[5] 。此外,相对而言逻辑式语言还不够成熟和完善。”

逗号“抗议”道:“我怎么感觉经过这么一反刍,胃里的负担更重了?”

冒号略带歉意地笑了笑:“在所有编程范式中,函数式与逻辑式与传统思维方式的差别最大,此前的介绍又过于简单,因此今天特意多谈了些。既然有人提意见,那就我就适可而止了。最后请允许我画蛇添足:在代表计算机最高水平的人工智能领域中,这两种范式发挥着举足轻重的作用。单凭这一点,它们也是值得学习和借鉴的。好了,大家先休息十分钟,出去活动活动筋骨吧。”

,插语

  1. 用数学逻辑的话来说,事实与规则是公理,查询就是待证的定理。

  2. 如Prolog Café和P#能分别将Prolog代码转化为Java代码和C#代码。

  3. 比如JPL通过JNI与Prolog FLI (Foreign Language Interface)将Java与SWI-Prolog桥接起来。

  4. 比如JIProlog(Java Internet Prolog)是一个用Java实现的Prolog解释器,为Java和Prolog提供双向API。类似的还有JLog等。

  5. 交互式或事件驱动式应用通常是基于状态的。

。总结

  • 代码的长度不是衡量软件复杂度的唯一标准。其中的逻辑结构越复杂、越微妙、受需求变化的影响越大,软件越难控制和维护。

  • 算法=逻辑+控制。逻辑式编程将算法中的控制部分大都移交给编程语言,编程人员主要关注算法的核心逻辑。这样大大减轻了程序员的负担,编码也更简洁易懂,更具可维护性和可扩展性。

  • 有别于过程式和函数式,逻辑式没有明显的输入和输出之分。

  • 逻辑式编程不仅适用于人工智能方面的学术领域,同样广泛适用于各种涉及知识管理、决策分析等方面的应用领域。

  • 相对于命令式,逻辑式更简洁、更抽象、更少副作用,能提高生产效率,还能用于快速原型开发。但在运行效率、可掌控性、语言成熟度等方面有所欠缺。另外,因其思维方式独特而鲜为人用,适合基于规则而非基于状态的应用 。

“”参考

  1. Michael Lee Scott.Programming Language Pragmatics.San Francisco:Morgan Kaufmann,2000.620-650

  2. Robert A. Kowalski.Algorithm = Logic + Control.Communications of the ACM,1979,22(7):424-436

Be Sociable, Share!

相关文章

分享/保存
 请您评分1星(很差)2星(不行)3星(一般)4星(不错)5星(很棒) (已有2人评分,平均分为:5.00 / 5)

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

  

  

  

This blog is kept spam free by WP-SpamFree.