prolog - 在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/2和 sibling/2的定义之间存在相互递归的讨厌情况。尽管您为它们提供的定义看起来不错，但是请考虑在未绑定(bind)所有参数的情况下调用它们时会发生什么情况:
brother(X, Y)↝ sibling(X, Y)↝ brother(X, Y)↝...(无限/恶心)

相反，我们可以做的是定义这些谓词的执行方式，完全了解它们是无限递归的，方法是通过一个单独的谓词来指示它们的执行，我将其称为 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.

请注意，它会在通过所有可能的非递归执行路径找到所有绑定(bind)之后终止，这意味着可能存在很多重复(因此，效率低下的根源)。要查找唯一的绑定(bind)，可以使用 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的任何人，您还应该考虑其他一些事项:

在执行(子)目标时(例如，如果您需要执行相同的子句但具有不同的头部绑定(bind))，也许您可​​能希望或需要多次执行同一子句。例如，考虑一下如何使用元解释器来递归地实现ancestor/2，这可能需要使用不同的头部绑定(bind)(即路径扩展)多次执行相同的子句(本身)。在这种情况下，您不仅可以跟踪子句引用，还可以将子句引用及其特定的头绑定(bind)作为Ref-Head项进行跟踪，并检查它们是否以前已执行过。这可能会带来很多额外的信息，而且价格可能很高!

上面的meta/1和meta/2的定义仅处理诸如事实之类的谓词(以隐式true为主体)。或谓词，其谓词使用结合词(,/2)和析取词(;/2)的任意组合定义。您可以简单地在meta/2中添加更多子句，以处理其他语言结构，例如，如果需要，可以包含蕴含(->/2)，否定(\+/1)，cut(!/0)等。

并非所有此类问题都需要使用元解释器。例如，您可能可以通过简单地精心构造子句并在执行模式之前检查模式(即谓词绑定(bind)为地面/非地面)来摆脱困境，但是这可能会变得棘手，因为程序越复杂。

如果您足够认真地考虑问题，也许有一种方法可以简单地完全避免使用递归:即，不要使用递归定义，而要使用名称互不递归的谓词。