在Prolog中重构纠结的循环规则

Question

在前面:这不是一个家庭作业.我正在努力学习Prolog,这只是一个需要解决的问题,而Prolog是一个完美的选择.

我有一堆家庭关系,包括我的事实:

male/1
female/1
husband/2
wife/2
father/2
mother/2
grandfather/2
grandmother/2
son/2
daughter/2
brother/2
sister/2
uncle/2
aunt/2
nephew/2
niece/2
cousin/2

我拥有的数据不完整,缺少家庭网格的许多链接.我的事实来自外部来源,我只能提供规则.对于给定的人,我可能有male,brother和表姐,另一个mother和wife.在最糟糕的情况下,我几乎不知道cousin,但有足够的其他事实能够推断谁是,比如说,叔叔,因此这个人可能是其他地方提到的那个兄弟,因此是男性.等等.

我无法影响将会有哪些事实.这就是问题的全部要点:如果事实完整,我就不需要这样做了.我可以手工做猜测,但这就是计算机的用途,如果我能找到表达方式的话.因此,我们的目标是尽可能地填补缺失的环节,尤其是关于叔叔,阿姨,侄子,侄女和特别表兄的"间接"关系,这些关系众所周知是不完整的.

我可以像这样天真地写下我的规则:

male(Who) :-
   brother(Who, _); father(Who, _); uncle(Who, _); …
brother(Who, Whose) :-
   sibling(Who, Ofwhom), male(Who).
sibling(Who, Whose) :-
   brother(Who, Whose) ; brother(Whose, Who).
motherly_cousin(Cousin, Whose) :-
   cousin(Cousin, Whose),
   sibling(Mother, Uncle_or_Aunt),
   parent(Uncle_or_Aunt, Cousin).

我很确定我试图以一种根本错误的方式解决问题,因为我认为无法打破循环推理.在不打破圈子的情况下,我为此设计的任何Prolog程序都将退化为无限的递归.

那么我该怎样做才能将这种纠结分解成可以解决的问题呢？

Answer 1

通常,这是一个棘手的问题.对于这种递归的检查是可能的(类似地对于发生检查在统一),然而大多数实现中省略掉,因为(a)它是通常不清楚要排除的递归路径; (b)计算成本太高; 或者(c)程序员通常有办法规避代码中的问题.

有很多方法可以解决这个问题,有些方法比其他方法更糟糕.我将介绍一种方式:

• 允许你合理地定义你的谓词天真;
• 处理不完整的事实;
• 非常低效;
• 不会无限递归.

我将描述的方式使用元解释器.Prolog中的标准解释器不会检查您的代码是否一遍又一遍地执行相同的条款.例如,你和你的定义之间有一个令人讨厌的相互递归的例子.虽然您为它们提供的定义似乎没问题,但请考虑在调用所有未绑定参数时它们会发生什么:brother/2sibling/2

brother(X, Y)↝ sibling(X, Y)↝ brother(X, Y)↝...(循环往复/ nauseum)

相反,我们可以做的是定义如何完全理解这些谓词的执行,通过将它们的执行指向一个单独的谓词,我可以将其称为无限递归meta/1.这个谓词是元解释器,它将指导Prolog如何以防止无限递归的方式执行你提供的规则和事实.这是一个可能的定义(带注释内联):

meta(Goal) :-
    % defer to meta/2 with a clause reference accumulator 
    meta(Goal, []).

meta(true, _ClauseRefs) :- 
    % the body to execute is true (i.e., a fact); just succeed.
    !,
    true.

meta(meta(X), ClauseRefs) :-
    % the body to execute is a call to the meta interpreter. 
    % interpret the interior goal X, and NOT the interpreter itself.
    !,
    meta(X, ClauseRefs).

meta((G0, G1), ClauseRefs) :- 
    % interpret a conjunct: ,/2. G0 then G1:
    !,
    % interpret the first sub-goal G0
    meta(G0, ClauseRefs),
    % then interpret the second sub-goal G1
    meta(G1, ClauseRefs).

meta((G0 ; G1), ClauseRefs) :- 
    % interpret a disjunct: ;/2. One or the other:
    ( meta(G0, ClauseRefs) 
    ; meta(G1, ClauseRefs) 
    ),
    !.

meta(G0, ClauseRefs) :-
    % G0 is an executable goal: look up a clause to execute 
    clause(G0, Body, Ref),
    % check to see if this clause reference has already been tried 
    \+ memberchk(Ref, ClauseRefs),
    % continue executing the body of this previously unexecuted clause 
    meta(Body, [Ref|ClauseRefs]).

meta/1并且meta/2被设计成使得它们以确保在目标的执行分支中使用的每个子句明确不重复的方式执行提供给它们的目标.为了在您的情况下使用它,请考虑以下事项:

brother_of(a, b).
brother_of(b, c).
brother_of(d, e).
brother_of(X, Y) :- meta((sibling_of(X, Y), male(X))).

male(a).
male(d).
male(b).
male(X) :- meta(brother_of(X, _)).

female(c).
female(e).
female(X) :- meta(sister_of(X, _)).

sister_of(X, Y) :- meta((sibling_of(X, Y), female(X))).

sibling_of(X, Y) :- meta(brother_of(X, Y)).
sibling_of(X, Y) :- meta(brother_of(Y, X)).
sibling_of(X, Y) :- meta(sister_of(X, Y)).
sibling_of(X, Y) :- meta(sister_of(Y, X)).

注意任何递归子句的主体是如何包含在调用中的meta/1,引导Prolog使用元解释器执行它们的定义,这将确保它们的执行(通过解释)不会是递归的.例如,目标:

?- sister_of(X,Y).
X = c,
Y = b ;
X = c,
Y = b ;
X = c,
Y = b ;
... 
X = e,
Y = d ;
false.

请注意,它在通过所有可能的非递归执行路径找到所有绑定后终止,这意味着可能存在大量重复(因此,效率低下的原因).要查找唯一的绑定,您可以使用setof/3如下:

?- setof(sister_of(X,Y), sister_of(X,Y), Set).
Set = [sister_of(c, b), sister_of(e, d)].

这只是您可能觉得有用的一种方法,并且通常是Prolog程序员需要注意的一个很好的(尽管是高级的)工具.您不需要坚持固有的执行策略.

对于任何想要简单使用meta/1和meta/2实践的人来说,还有一些其他的事情需要考虑:

• 也许您可能想要或需要允许在执行(子)目标时多次执行相同的子句(例如,如果您需要执行相同的子句但具有不同的头部绑定).作为一个例子,考虑如何ancestor/2使用元解释器递归实现,元解释器可能需要使用不同的头部绑定(即路径扩展)多次执行相同的子句(本身).在这种情况下,您可以跟踪子句引用及其特定的头部绑定作为Ref-Head项目,而不是简单地跟踪子句引用,并检查它们之前是否已执行.这可能是一大堆额外的信息,可能很昂贵!
• 上面meta/1和meta/2上面的定义只处理诸如事实之类的谓词(隐含true为其主体); 或使用conj(,/2)和disjunction(;/2)的任意组合定义的主体的谓词.如果需要,您可以简单地添加更多子句来meta/2处理其他语言结构,例如implication(->/2),negation(\+/1),cut(!/0)等.
• 并非像这样的所有问题都需要一个元解释器.例如,你可以在执行之前简单地构造你的子句并检查模式(即谓词绑定是地面/非地面),但是这可能会变得棘手,程序越复杂.
• 如果你认真思考这个问题,或许有一种方法可以简单地避免完全使用递归:即,不要使用递归定义,而是使用具有不同名称且不相互递归的谓词.

Answer 2

+ +1通常的"家庭例子".

除了其他人已经说过的内容之外,请考虑使用约束处理规则(CHR).它们似乎非常适合这个问题,需要根据一组事实和规则来计算修复点.

编辑:根据要求,一个小例子.我专注于周围的插图brother_of/2.首先,请注意brother_of/2显然比具体更明确male/1,因为我们知道兄弟总是男性,反之则不然.非正式地,第一个CHR规则因此说:当brother_of(X,_)保持并male(X)保持时,然后放弃male(X)约束,因为它总是可以在以后推断出来.第二规则示出的一个例子推断该brother(X, Y)成立.第三条规则删除了多余的brother_of/2约束.

完整的代码,使用SWI-Prolog测试:

:- use_module(library(chr)).

:- chr_constraint male/1, brother_of/2, child_parent/2.

brother_of(X, Y) \ male(X) <=> brother_of(X, Y).

male(X), child_parent(X, P), child_parent(Y, P) ==> X \== Y | brother_of(X, Y).

brother_of(X, Y) \ brother_of(X, Y) <=> true.

示例查询及其结果:

?- male(john), child_parent(john, mary), child_parent(susan, mary).
brother_of(john,susan)
child_parent(susan,mary)
child_parent(john,mary)
true ;
false.