序言中的递归引用
Recursive reference in prolog
我在尝试实施时遇到了一些问题
friends(mia, ellen).
friends(mia, lucy).
friends(X,Y) :-
friends(X,Z),
friends(Y,Z).
当我询问 ?- friends(mia, X). 时，它 运行 超出了本地堆栈。
然后我添加
friends(ellen, mia) friends(lucy, mia)
我问?- friends(mia, X).，一直回复X = mia。
看不懂，为什么是递归的？
friends/2的这个条款有缺陷：
friends(X,Y) :- friends(X,Z),friends(Y,Z).
将其翻译成英文："If X and Y have a mutual friend Z, then X and Y are friends."
或者，让我们专门化，让X成为"me"，让Y成为我的邻居"FooBert"，让Z成为"you"：那么，如果我是你的朋友，而 FooBert 是你的朋友……这会让我和 FooBert 成为朋友吗？我不这么认为，我讨厌那个人——他回家后总是砰的一声关门。 :)
我建议您考虑关系 friends/2 应该 具有的代数性质，它 可能 具有的那些，以及不应该的那些。自反性、对称性、反对称性、传递性呢？
首先，两个假设：
您实际要编写的代码如下，带有适当的点：
friends(mia,ellen).
friends(mia,lucy).
friends(X,Y) :-
friends(X,Z),
friends(Z,Y).
传递性成立：朋友的朋友也是我的朋友（我宁愿将友谊建模为距离："A is near B" 和 "B is near C" 并不一定意味着 "A is near C" ). 是正确的关于首先弄清楚你想要建模什么。
现在，让我们看看为什么要进入无限递归。
循序渐进
那么，当我们问：friends(mia,X) ?
时会发生什么？
- 第一个子句给出
Y=ellen（你要求更多的解决方案）
- 第二条给出
Y=lucy（你再问更多的解法）
- 堆栈溢出！
让我们详细说明第三个条款：
- 我想知道
friends(mia,Y) 是否适用于某些变量 Y。
是否存在满足 friends(mia,Z) 的变量 Z？
请注意，除了从 Y 重命名为 Z 之外，我们问的问题与上述步骤 1 相同？ 这听起来像无限递归，但让我们看看...
- 我们尝试了
friends的前两个子句，但是后来我们失败了，因为没有friends(ellen,Y)也没有friends(lucy,Y)，所以...
- 我们调用第三个子句以查找是否存在可传递的友谊，并且我们没有进一步进行就返回到步骤 1 => 无限递归。
这个问题类似于上下文无关文法中的无限Left recursion。
修复
有两个谓词：
known_friends/2，给出直接关系。friends/2，也对传递性进行编码
known_friends(mia,ellen).
known_friends(mia,lucy).
friends(X,Y) :- known_friends(X,Y).
friends(X,Y) :- known_friends(X,Z), friends(Z,Y).
现在，当我们询问friends(mia,X)时，friends/2给出了与known_friends/2的两个子句相同的答案，但没有找到任何传递子句的答案：这里的区别是 known_friends 会取得一点进展，即找到 mia 的已知朋友（不递归），并尝试（递归）查找该朋友是否是其他人的朋友。
朋友的朋友
如果我们添加 known_friends(ellen, bishop) :-) 那么 friends 也会找到 Y=bishop, 因为:
known_friends(mia,ellen) 成立，friends(ellen,bishop)是递归找到的。
圆度
如果你在友谊图中添加循环依赖（在known_friends），那么你将无限遍历这个图friends。在解决这个问题之前，您必须考虑以下问题：
friends(X,Y) <=> friends(Y,X) 对所有 (X,Y) 都成立吗？- 对于所有
X，friends(X,X) 呢？
然后，你应该在评估 friends 时保留一组所有见过的人，以便检测你何时循环 known_friends，同时考虑到上述属性。这个实现起来应该也不会太难，如果你想试试。
我在尝试实施时遇到了一些问题
friends(mia, ellen).
friends(mia, lucy).
friends(X,Y) :-
friends(X,Z),
friends(Y,Z).
当我询问 ?- friends(mia, X). 时，它 运行 超出了本地堆栈。
然后我添加
friends(ellen, mia) friends(lucy, mia)
我问?- friends(mia, X).，一直回复X = mia。
看不懂，为什么是递归的？
friends/2的这个条款有缺陷：
friends(X,Y) :- friends(X,Z),friends(Y,Z).
将其翻译成英文："If X and Y have a mutual friend Z, then X and Y are friends."
或者，让我们专门化，让X成为"me"，让Y成为我的邻居"FooBert"，让Z成为"you"：那么，如果我是你的朋友，而 FooBert 是你的朋友……这会让我和 FooBert 成为朋友吗？我不这么认为，我讨厌那个人——他回家后总是砰的一声关门。 :)
我建议您考虑关系 friends/2 应该 具有的代数性质，它 可能 具有的那些，以及不应该的那些。自反性、对称性、反对称性、传递性呢？
首先，两个假设：
您实际要编写的代码如下，带有适当的点：
friends(mia,ellen). friends(mia,lucy). friends(X,Y) :- friends(X,Z), friends(Z,Y).传递性成立：朋友的朋友也是我的朋友（我宁愿将友谊建模为距离："A is near B" 和 "B is near C" 并不一定意味着 "A is near C" ).
现在，让我们看看为什么要进入无限递归。
循序渐进
那么，当我们问：friends(mia,X) ?
- 第一个子句给出
Y=ellen（你要求更多的解决方案） - 第二条给出
Y=lucy（你再问更多的解法） - 堆栈溢出！
让我们详细说明第三个条款：
- 我想知道
friends(mia,Y)是否适用于某些变量Y。 是否存在满足
friends(mia,Z)的变量Z？请注意，除了从
Y重命名为Z之外，我们问的问题与上述步骤 1 相同？ 这听起来像无限递归，但让我们看看...- 我们尝试了
friends的前两个子句，但是后来我们失败了，因为没有friends(ellen,Y)也没有friends(lucy,Y)，所以... - 我们调用第三个子句以查找是否存在可传递的友谊，并且我们没有进一步进行就返回到步骤 1 => 无限递归。
这个问题类似于上下文无关文法中的无限Left recursion。
修复
有两个谓词：
known_friends/2，给出直接关系。friends/2，也对传递性进行编码known_friends(mia,ellen). known_friends(mia,lucy). friends(X,Y) :- known_friends(X,Y). friends(X,Y) :- known_friends(X,Z), friends(Z,Y).
现在，当我们询问friends(mia,X)时，friends/2给出了与known_friends/2的两个子句相同的答案，但没有找到任何传递子句的答案：这里的区别是 known_friends 会取得一点进展，即找到 mia 的已知朋友（不递归），并尝试（递归）查找该朋友是否是其他人的朋友。
朋友的朋友
如果我们添加 known_friends(ellen, bishop) :-) 那么 friends 也会找到 Y=bishop, 因为:
known_friends(mia,ellen)成立，friends(ellen,bishop)是递归找到的。
圆度
如果你在友谊图中添加循环依赖（在known_friends），那么你将无限遍历这个图friends。在解决这个问题之前，您必须考虑以下问题：
friends(X,Y) <=> friends(Y,X)对所有(X,Y)都成立吗？- 对于所有
X，friends(X,X)呢？
然后，你应该在评估 friends 时保留一组所有见过的人，以便检测你何时循环 known_friends，同时考虑到上述属性。这个实现起来应该也不会太难，如果你想试试。