朋友啊朋友,你可曾找到了我?

前些日子和代码时间的主页君录制了一期关于Prolog的podcast,昨天终于放了出来在这里.

问题来了

有朋友听了之后开始试着整Prolog,遇到了个问题。他看的是Seven Languages In Seven Weeks。书中的第一个例子就有了疑问(Day 1 -> Basic Inferences And Variables)。这个例子的代码是这样的:

likes(wallace, cheese).  
likes(grommit, cheese).  
likes(wendolini, sheeps).

friends(X, Y) :-  
    \+(X = Y),
    likes(X, Z),
    likes(Y, Z).

如果只是简单的提问,这段代码是没有问题的,比如说:

|?- friends(wallace, wendolini).
  no
|?- friends(wallace, grommit).
  yes

然而事情并没有完。这位朋友是个老江湖,他看了下一部分关于existential query的章节之后,马上回来问了一个问题:

|?- friends(X, Y).
  no

这下事情就尴尬了,不是说好了可以generalize出来solution的么?请走进这一期的《走近Prolog》,让我们看看Prolog怎么会好用到“没朋友”了呢?

逻辑错了

我们首先来看看原书中对于\+ /1的解释:

In English, for X to be a friend of Y, X cannot be the same as Y. Look at the first part to the right of :-, called a subgoal. \+ does logical negation, so \+(X = Y) means X is not equal to Y.  

而\+ /1其实并不是逻辑否这么简单。文档当中是这么说的:

\+ +P
Fails if the goal P has a solution, and succeeds otherwise.  

就是说,如果Prolog觉得如果有可能找到一个满足P为真的方法,那么这个term就是为否。猛一听上去,这和逻辑否又有什么区别呢?在P是一个已经完全可以判断的term的时候,两者是没有区别的;然而当P存在没有确定的argument的时候,可就不一定了。比如这里,如果X等于wallace,Y等于grommit的时候,要判定的问题就变成了:

  \+(wallace=grommit)

因为wallace和grommit并不相等,所以整个term就是真,\+在这里确实就是逻辑否。

那么如果有non-ground argument呢?比如你提问:

|?- friends(wallace, Y).

那么\+ /1在这里要判定的问题就变成了:

  \+(wallace = Y)

这样的话,因此此时Y没有ground,但假如在Y也等于wallace的情况下,就可以使得括号内的term为真,从而使得整个term为否了。而Prolog就在此时unify了Y和wallace,以达到括号内为真。因此,当你提出这个提问的时候,在第一步就卡壳了,根本没有后面的两个likes什么事儿。

那么你如果事逼一点会问,如果两个argument我都不确定呢?

|?- friends(X, Y).

Non-ground的variable,再Prolog内部一半标记成_12345这样的形式。你可以暂时理解为这就是一个空指针。所以X和Y,这时标记的就是类似于这样的形式:_10001, _10002。那么如何去处理这个呢:

  \+(_10001 = _10002)

因为它们两个都是不确定的,所以Prolog为了解决_10001 = _10002这个问题,就可以把二者unify,来使得这里为真,从而导致整个\+ /1为否。因此,两个variable都不确定,呃,也在第一步就挂了。

现在你们应该想通了,Prolog在这里去解决的事情并不是X和Y不等价;正相反,它是在括号内,努力得让X和Y等价。这就是为什么我说这里把\+ /1解释为逻辑否不合适的原因。

位置早了

那是不是我不用\+ /1,而使用正儿八经的比较X和Y的predicate,就能防止这个问题呢?那我们就来试试。你要得到X和Y不等价,正确的姿势是\== /2。就比如这样:

  X \== Y

这样的话我们的friends就变成了:

friends(X, Y) :-  
    X \== Y,
    likes(X, Z),
    likes(Y, Z).

你做确定的argument的提问的时候,当然没有问题。然而当使用了不确定的argument提问的时候,问题又来了。

|?- friends(wallace, Y).
Y = wallace ? n  
Y = grommit ? n  
no  

开始那个 \= = /2好像这时候没有用耶!它为什么给出了friends(wallace, wallace)这个答案?

解释这个之前,我们先继续提问两个non-ground argument的情况:

|?- friends(X, Y).
X = wallace,  
Y = wallace ? n  
X = wallace,  
Y = grommit ? n  
X = grommit,  
Y = wallace ? n  
X = grommit,  
Y = grommit ? n  
X = wendolene,  
Y = wendolene ? n  
no  

事情就更加悲催了,它真的完全不考虑X \= = Y了么?我前面讲了Prolog是怎么标记并non-ground variable的,那么这里它其实做的是这样一件事情:

  _10001 \== _10002

当Prolog试图resolve这个结果的时候,发现这事情当然是可以的,因为两个没有ground的variable,是不等价的。而当之后去解决两个likes/2的时候使得两个variable等价了,也是一件无可奈何的事情,因为我们知道,可以找到resolve terms的结果的时候,Prolog是不会去backtracking的,也就是前面X \= = Y虽然当时resolve了,但是对后面的步骤是没有约束力的。

冰雪聪明的各位肯定已经想到,那么我们把它移到最后不就结了么!对,这里正确的写法就是这样的:

friends(X, Y) :-  
    likes(X, Z),
    likes(Y, Z),
    X \== Y.

这样以来,不管是X和Y是ground的,还是不non-ground的,你都可以得到你期望的答案了。

到此为止,王四哥是不是应该闭嘴了?并没有。。。

没朋友了

原书中的例子是为了向小读者们展示基本的确定的argument的query。如果仅仅是以此为目的的话,其实得到的答案也都正确。这就引出了下面我要说的事情,就是:一个Prolog的predicate的argument,你是可以标记它是输入(+)、还是输出(-)、还是双向的(?)。你在文档中应该表明这一点,以防止用户的错误使用。因为根据这样的标记,你可以优化你的程序。你并不用总是满足一个argument是ground(输入)和不non-ground(输出)的情况,而且在一些情况下,这也是做不到的。

上面这段话如果你不知所云的话,没有关系,接下来我们细细来讲。讲完你回溯一下就明白了(逃

首先,我们来说一下在文档中标记predicate。这件事SICStus叫做mode annotations,而SWI里面叫做instantiation patterns。虽然SWI的标记方式更复杂,但是基本的想法是一样的。就是让使用这个predicate的用户清楚,在使用这个(或者这组)predicate的时候,他们能期望所有的argument是怎样的表现。

对于灰常简单的Prolog predicates,你要满足你所有的arguments在不做特殊的处理情况下都是同时可以输入和输出并不难,但是你如果加了性能都必须是最优的这个条件的话,事情就不一定那么容易了。

比如原书中的这个例子,在我们把它改得能够同时满足输入和输出之后,如果输入的两个argument是ground的同时相同的话,那么只有到了最后一步X \= = Y的时候才会fail,白白做了两次找朋友的unification。而且,如果我们给likes增加一个fact的话:

likes(wallace, sheeps).  

这个时候就不仅仅是白找朋友的问题了,同时会导致回溯。这时候一些“学有余力”的同学会说:防止回溯还不容易,cut我还不会用么?于是咔嚓一下:

friends(X, Y) :-  
    likes(X, Z),
    likes(Y, Z), !,
    X \== Y.

然而这样看上去不回溯了,但是这个程序却错了。你这时候如果做一个non-ground的query,事情就乱套了。。。

|?- friends(wallace, Y).
no  

没朋友了!你看,仅仅是这么小一个predicate,你同时追求输入和输出,还对性能和正确性都有要求的话,就会出乱子,当你搞起来Real World Prolog的时候,分分钟到处都是坑啊!

那么是不是原书中的例子在仅考虑输入情况下就是正确的呢?是,也不是。说不是,是从两点来讲的。

首先\+ /1算是一个误用。虽然看上去没有问题,但是一旦其他人改变这段程序的用途,随时可能是个大坑。

其次,这里也有更像一个prologer的写法:

friends(X, X) :- !, fail.  
friends(X, Y) :-  
        likes(X, Z),
        likes(Y, Z).

现代的Prolog,因为有了predicate argument的各种indexing,使得这么写并不会慢,而且逻辑也更像prolog程序的思考过程。这么写也会死在non-ground argument上,但是,呃,起码死得一目了然(

所以,原书中的这个例子,即使不能说是错的,也是用一个有点蹩脚的写法,呃,举了一个不恰当的例子。