序言中前向链接的实现（SWI-Prolog）
Implementation of forward chaining in prolog (SWI-Prolog)
我想在 Prolog 中实现前向链接推理。我编了一个简单的事实知识库和一些规则，从中我应该可以得到事实green(fritz)。
我试图实现它，但不知何故，当 member 失败时，它就停止了。
/*
meta rules
*/
rule(1, [canary(X)], [sings(X), chips(X)]).
rule(2, [frog(X)], [croaks(X), eats_flies(X)]).
rule(3, [green(X)], [frog(X)]).
rule(4, [yellow(X)], [canary(X)]).
/*
meta facts
*/
fact(1, eats_flies(fritz)).
fact(2, croaks(fritz)).
fact(3, sings(tweety)).
fact(4, chips(tweety)).
fact(5, croaks(kroger)).
fact(6, chips(kroger)).
/*
forward chaining
*/
start_id(100000).
get_id(Y) :-
retract(start_id(X)),
Y is X + 1,
assert(start_id(Y)).
forward(NewFacts) :-
findall(rule(Id, Head, Tail), rule(Id, Head, Tail), Rules),
findall(fact(Id, X), fact(Id, X), Facts),
forward_chaining(Rules, Facts, NewFacts).
forward_chaining(_, [], _).
forward_chaining([], _, _).
forward_chaining([rule(Id, Head, Tail)|Rules], [fact(Id, X)|Facts], NewFactsRec + NewFactsRecRec) :-
forward_rule([rule(Id, Head, Tail)|Rules], fact(Id, X), NewFactsRec, NewRulesRec),
forward_chaining(NewRulesRec + Rules, NewFactsRec + Facts, NewFactsRecRec).
forward_rule([], _, _, _).
forward_rule([rule(Id, Head, Tail)|Rules], fact(Id, X), NewFacts, NewRules) :-
member(X, Tail) ->
(
delete(Tail, X, NewTail),
NewTail = [] ->
get_id(NewId),
NovelFact = [fact(NewId, Head)],
NovelRule = []
;
NovelFact = [],
NovelRule = [rule(Id, Head, NewTail)]
);
NovelRule = [rule(Id, Head, Tail)],
forward_rule(Rules, fact(Id, X), NewFactsRec, NewRulesRec),
append(NewRulesRec, NovelRule, NewRules),
append(NewFactsRec, NovelFact, NewFacts).
关注 forward_rule 实现，我想检查 fact 是否在规则的 tail 中。如果是，则应将其删除。如果不是，我应该继续从所有规则中删除 fact。然后，通过 forward_chaining 实现，应该为每个 fact 完成。
当然，如果tail是空的，那么head应该变成新的fact。如果 tail 不为空，则必须更新 rule。
我是不是漏掉了什么？？
编辑 1：
在 Isabelle Newbie 的回答后，我尝试修复代码。现在 if-then-else 可以正常工作了。
但是，对 forward_rule 的递归调用在开始之前仍然失败。
start_id(100000).
get_id(Y) :-
retract(start_id(X)),
Y is X + 1,
assert(start_id(Y)).
forward(NewFacts) :-
findall(rule(Id, Head, Tail), rule(Id, Head, Tail), Rules),
findall(fact(Id, X), fact(Id, X), Facts),
forward_chaining(Rules, Facts, NewFacts).
forward_chaining(_, [], _).
forward_chaining([], _, _).
forward_chaining([rule(Id, Head, Tail)|Rules], [fact(Id, X)|Facts], NewFacts) :-
forward_rule([rule(Id, Head, Tail)|Rules], fact(Id, X), NewFactsRec, NewRulesRec),
writeln('going on'), % debug
append(Rules, NewRulesRec, ToForwardRules),
append(Facts, NewFactsRec, ToForwardFacts),
forward_chaining(ToForwardRules, ToForwardFacts, NewFacts).
forward_rule([], _Fact, [], []).
forward_rule([rule(Id, Head, Tail)|Rules], fact(Id, X), NewFacts, NewRules) :-
( member(X, Tail)
-> delete(Tail, X, NewTail),
writeln('is member'), % debug
( NewTail = []
-> get_id(NewId),
writeln('newtail is empty'), % debug
NovelFact = [fact(NewId, Head)],
NovelRule = []
;
writeln('newtail is not empty'), % debug
NovelFact = [],
NovelRule = [rule(Id, Head, NewTail)])
;
writeln('is not member'), % debug
NovelRule = [rule(Id, Head, Tail)],
NovelFact = []),
writeln('postlude'), % debug
forward_rule(Rules, fact(Id, X), NewFactsRec, NewRulesRec),
append(NewRulesRec, NovelRule, NewRules),
append(NewFactsRec, NovelFact, NewFacts).
我正在使用 gtrace 来尝试了解代码在哪里失败。所以我看到它没有进入递归调用。似乎有一个统一问题，但我不明白为什么。
这里有几个问题。
问题 1 是您的递归谓词的 non-recursive 子句如下所示：
forward_rule([], _, _, _).
这意味着：“如果规则列表为空，则任意事实对应于任意新事实和任意新规则。”
例如：
?- forward_rule([], apple_pie, [new_fact_1, new_fact_2, new_fact3], [new_rule_1, new_rule_2]).
true.
你的意思几乎可以肯定是：
forward_rule([], _Fact, [], []).
意思是：“如果规则列表是空的，那么无论 _Fact 是什么，都没有新的事实，也没有新的规则可以推导出来。”
问题 2 是这样的行：
forward_chaining(NewRulesRec + Rules, NewFactsRec + Facts, NewFactsRecRec).
这看起来有点像您正在尝试使用 + 作为列表追加函数。 Prolog 中没有函数。您知道如何使用 append，但您也必须为此使用它。
问题 3 与您的 if-then-else 代码有关。您的格式并未反映实际发生的情况。
考虑：
conditional(C) :-
writeln(unconditional_prelude),
C = true ->
(
writeln(true_branch_1),
writeln(true_branch_2)
);
writeln(presumably_false_branch),
writeln(presumably_unconditional_postlude).
这给出：
?- conditional(true).
unconditional_prelude
true_branch_1
true_branch_2
true.
?- conditional(false).
unconditional_prelude
presumably_false_branch
presumably_unconditional_postlude
true.
看到 non-indented 条件“之后”的部分实际上是错误分支的一部分了吗？
通常单独的谓词定义比 if-then-else 结构更清晰。例如，您可以这样写：
x_tail_novelfact_novelrule(X, Tail, NovelFact, NovelRule) :-
member(X, Tail),
... rest of "true" branch ...
x_tail_novelfact_novelrule(X, Tail, NovelFact, NovelRule) :-
\+ member(X, Tail),
... rest of "false" branch ...
如果必须使用 if-then-else 结构，则必须在整个 if-then-else 周围加上括号 。像这样：
... prelude ...
( Condition1,
Condition2
-> TrueBranch1,
TrueBranch2
; FalseBranch1,
FalseBranch2 ),
... postlude ...
只会（最多）执行其中一个分支。不管执行哪个分支，如果执行成功，则执行后序。
您的代码也可能存在其他问题，但我希望这能帮助您暂时开始修复这些问题。
为了正常工作，前向链接算法不能删除，也不能修改，在每次迭代中触发的规则（否则实现不适用于递归规则）。当获得 fixpoint 时算法终止（或者，当导出要证明的 ground fact 时）。
为了更统一的表示，事实可以表示为规则
条件 true。另外，为了区分不同的知识库，
规则可以用知识库标识符来标记。
:- op(1100, xfx, if).
:- op(1000, xfy, and). % <== EDITED
forward(KB, Fact) :-
fixpoint(KB, nil, [true], Facts),
member(Fact, Facts).
fixpoint(_, Base, Base, Base) :- !.
fixpoint(KB, _, Base, Facts) :-
setof(Fact, derived(Fact, KB, Base), NewFacts),
ord_union(NewFacts, Base, NewBase),
fixpoint(KB, Base, NewBase, Facts).
derived(Fact, KB, Base) :-
rule(KB : Fact if Condition),
satisfy(Base, Condition).
satisfy(Base, Condition) :-
( Condition = (A and B)
-> member(A, Base),
satisfy(Base, B)
; member(Condition, Base) ).
% first knowledge base
rule(1 : eats_flies(fritz) if true).
rule(1 : croaks(fritz) if true).
rule(1 : sings(tweety) if true).
rule(1 : chips(tweety) if true).
rule(1 : has_wings(tweety) if true). % <== EDITED
rule(1 : croaks(kroger) if true).
rule(1 : chips(kroger) if true).
rule(1 : frog(X) if croaks(X) and eats_flies(X)).
rule(1 : green(X) if frog(X)).
rule(1 : yellow(X) if canary(X)).
rule(1 : canary(X) if sings(X) and chips(X) and has_wings(X)). % <== EDITED
% second knowledge base (recursive example)
rule(2 : connected(a,b) if true).
rule(2 : connected(b,c) if true).
rule(2 : connected(c,d) if true).
rule(2 : connected(X,Z) if connected(X,Y) and connected(Y,Z)).
示例：
?- forward(1, canary(X)).
X = tweety ;
false.
?- forward(1, green(X)).
X = fritz ;
false.
?- forward(2, connected(a,X)).
X = b ;
X = c ;
X = d ;
false.
Remark 只要知识库是 function-free（即它有一个有限的 Herbrand 模型），就存在一个最小不动点.
我想在 Prolog 中实现前向链接推理。我编了一个简单的事实知识库和一些规则，从中我应该可以得到事实green(fritz)。
我试图实现它，但不知何故，当 member 失败时，它就停止了。
/*
meta rules
*/
rule(1, [canary(X)], [sings(X), chips(X)]).
rule(2, [frog(X)], [croaks(X), eats_flies(X)]).
rule(3, [green(X)], [frog(X)]).
rule(4, [yellow(X)], [canary(X)]).
/*
meta facts
*/
fact(1, eats_flies(fritz)).
fact(2, croaks(fritz)).
fact(3, sings(tweety)).
fact(4, chips(tweety)).
fact(5, croaks(kroger)).
fact(6, chips(kroger)).
/*
forward chaining
*/
start_id(100000).
get_id(Y) :-
retract(start_id(X)),
Y is X + 1,
assert(start_id(Y)).
forward(NewFacts) :-
findall(rule(Id, Head, Tail), rule(Id, Head, Tail), Rules),
findall(fact(Id, X), fact(Id, X), Facts),
forward_chaining(Rules, Facts, NewFacts).
forward_chaining(_, [], _).
forward_chaining([], _, _).
forward_chaining([rule(Id, Head, Tail)|Rules], [fact(Id, X)|Facts], NewFactsRec + NewFactsRecRec) :-
forward_rule([rule(Id, Head, Tail)|Rules], fact(Id, X), NewFactsRec, NewRulesRec),
forward_chaining(NewRulesRec + Rules, NewFactsRec + Facts, NewFactsRecRec).
forward_rule([], _, _, _).
forward_rule([rule(Id, Head, Tail)|Rules], fact(Id, X), NewFacts, NewRules) :-
member(X, Tail) ->
(
delete(Tail, X, NewTail),
NewTail = [] ->
get_id(NewId),
NovelFact = [fact(NewId, Head)],
NovelRule = []
;
NovelFact = [],
NovelRule = [rule(Id, Head, NewTail)]
);
NovelRule = [rule(Id, Head, Tail)],
forward_rule(Rules, fact(Id, X), NewFactsRec, NewRulesRec),
append(NewRulesRec, NovelRule, NewRules),
append(NewFactsRec, NovelFact, NewFacts).
关注 forward_rule 实现，我想检查 fact 是否在规则的 tail 中。如果是，则应将其删除。如果不是，我应该继续从所有规则中删除 fact。然后，通过 forward_chaining 实现，应该为每个 fact 完成。
当然，如果tail是空的，那么head应该变成新的fact。如果 tail 不为空，则必须更新 rule。
我是不是漏掉了什么？？
编辑 1：
在 Isabelle Newbie 的回答后，我尝试修复代码。现在 if-then-else 可以正常工作了。
但是，对 forward_rule 的递归调用在开始之前仍然失败。
start_id(100000).
get_id(Y) :-
retract(start_id(X)),
Y is X + 1,
assert(start_id(Y)).
forward(NewFacts) :-
findall(rule(Id, Head, Tail), rule(Id, Head, Tail), Rules),
findall(fact(Id, X), fact(Id, X), Facts),
forward_chaining(Rules, Facts, NewFacts).
forward_chaining(_, [], _).
forward_chaining([], _, _).
forward_chaining([rule(Id, Head, Tail)|Rules], [fact(Id, X)|Facts], NewFacts) :-
forward_rule([rule(Id, Head, Tail)|Rules], fact(Id, X), NewFactsRec, NewRulesRec),
writeln('going on'), % debug
append(Rules, NewRulesRec, ToForwardRules),
append(Facts, NewFactsRec, ToForwardFacts),
forward_chaining(ToForwardRules, ToForwardFacts, NewFacts).
forward_rule([], _Fact, [], []).
forward_rule([rule(Id, Head, Tail)|Rules], fact(Id, X), NewFacts, NewRules) :-
( member(X, Tail)
-> delete(Tail, X, NewTail),
writeln('is member'), % debug
( NewTail = []
-> get_id(NewId),
writeln('newtail is empty'), % debug
NovelFact = [fact(NewId, Head)],
NovelRule = []
;
writeln('newtail is not empty'), % debug
NovelFact = [],
NovelRule = [rule(Id, Head, NewTail)])
;
writeln('is not member'), % debug
NovelRule = [rule(Id, Head, Tail)],
NovelFact = []),
writeln('postlude'), % debug
forward_rule(Rules, fact(Id, X), NewFactsRec, NewRulesRec),
append(NewRulesRec, NovelRule, NewRules),
append(NewFactsRec, NovelFact, NewFacts).
我正在使用 gtrace 来尝试了解代码在哪里失败。所以我看到它没有进入递归调用。似乎有一个统一问题，但我不明白为什么。
这里有几个问题。
问题 1 是您的递归谓词的 non-recursive 子句如下所示：
forward_rule([], _, _, _).
这意味着：“如果规则列表为空，则任意事实对应于任意新事实和任意新规则。”
例如：
?- forward_rule([], apple_pie, [new_fact_1, new_fact_2, new_fact3], [new_rule_1, new_rule_2]).
true.
你的意思几乎可以肯定是：
forward_rule([], _Fact, [], []).
意思是：“如果规则列表是空的，那么无论 _Fact 是什么，都没有新的事实，也没有新的规则可以推导出来。”
问题 2 是这样的行：
forward_chaining(NewRulesRec + Rules, NewFactsRec + Facts, NewFactsRecRec).
这看起来有点像您正在尝试使用 + 作为列表追加函数。 Prolog 中没有函数。您知道如何使用 append，但您也必须为此使用它。
问题 3 与您的 if-then-else 代码有关。您的格式并未反映实际发生的情况。
考虑：
conditional(C) :-
writeln(unconditional_prelude),
C = true ->
(
writeln(true_branch_1),
writeln(true_branch_2)
);
writeln(presumably_false_branch),
writeln(presumably_unconditional_postlude).
这给出：
?- conditional(true).
unconditional_prelude
true_branch_1
true_branch_2
true.
?- conditional(false).
unconditional_prelude
presumably_false_branch
presumably_unconditional_postlude
true.
看到 non-indented 条件“之后”的部分实际上是错误分支的一部分了吗？
通常单独的谓词定义比 if-then-else 结构更清晰。例如，您可以这样写：
x_tail_novelfact_novelrule(X, Tail, NovelFact, NovelRule) :-
member(X, Tail),
... rest of "true" branch ...
x_tail_novelfact_novelrule(X, Tail, NovelFact, NovelRule) :-
\+ member(X, Tail),
... rest of "false" branch ...
如果必须使用 if-then-else 结构，则必须在整个 if-then-else 周围加上括号 。像这样：
... prelude ...
( Condition1,
Condition2
-> TrueBranch1,
TrueBranch2
; FalseBranch1,
FalseBranch2 ),
... postlude ...
只会（最多）执行其中一个分支。不管执行哪个分支，如果执行成功，则执行后序。
您的代码也可能存在其他问题，但我希望这能帮助您暂时开始修复这些问题。
为了正常工作，前向链接算法不能删除，也不能修改，在每次迭代中触发的规则（否则实现不适用于递归规则）。当获得 fixpoint 时算法终止（或者，当导出要证明的 ground fact 时）。
为了更统一的表示，事实可以表示为规则
条件 true。另外，为了区分不同的知识库，
规则可以用知识库标识符来标记。
:- op(1100, xfx, if).
:- op(1000, xfy, and). % <== EDITED
forward(KB, Fact) :-
fixpoint(KB, nil, [true], Facts),
member(Fact, Facts).
fixpoint(_, Base, Base, Base) :- !.
fixpoint(KB, _, Base, Facts) :-
setof(Fact, derived(Fact, KB, Base), NewFacts),
ord_union(NewFacts, Base, NewBase),
fixpoint(KB, Base, NewBase, Facts).
derived(Fact, KB, Base) :-
rule(KB : Fact if Condition),
satisfy(Base, Condition).
satisfy(Base, Condition) :-
( Condition = (A and B)
-> member(A, Base),
satisfy(Base, B)
; member(Condition, Base) ).
% first knowledge base
rule(1 : eats_flies(fritz) if true).
rule(1 : croaks(fritz) if true).
rule(1 : sings(tweety) if true).
rule(1 : chips(tweety) if true).
rule(1 : has_wings(tweety) if true). % <== EDITED
rule(1 : croaks(kroger) if true).
rule(1 : chips(kroger) if true).
rule(1 : frog(X) if croaks(X) and eats_flies(X)).
rule(1 : green(X) if frog(X)).
rule(1 : yellow(X) if canary(X)).
rule(1 : canary(X) if sings(X) and chips(X) and has_wings(X)). % <== EDITED
% second knowledge base (recursive example)
rule(2 : connected(a,b) if true).
rule(2 : connected(b,c) if true).
rule(2 : connected(c,d) if true).
rule(2 : connected(X,Z) if connected(X,Y) and connected(Y,Z)).
示例：
?- forward(1, canary(X)).
X = tweety ;
false.
?- forward(1, green(X)).
X = fritz ;
false.
?- forward(2, connected(a,X)).
X = b ;
X = c ;
X = d ;
false.
Remark 只要知识库是 function-free（即它有一个有限的 Herbrand 模型），就存在一个最小不动点.