Prolog中的统一算法可以无限递归吗？

Question

我正在使用 swi-prolog 在 Prolog 课程的上下文中为学生制作一些示例。关于统一，我想提请他们注意统一过程中无限递归的危险。然而，像 swi-prolog 这样成熟的 Prolog 实现足够聪明，可以在大多数情况下避免统一过程的无限递归。在所有情况下都是如此，还是可以构建更复杂的示例，其中统一仍然会无限递归？

?- foo(bar(X)) = X.
X = foo(bar(X)).

?- foo(X) = X.
X = foo(X).

?- foo(X) = Y, X = Y.
X = Y, Y = foo(Y).

?- foo(X) = Y, X = foo(Y).
X = Y, Y = foo(foo(Y)).

作为相关的附带问题，为什么（同样，我使用了 swi-prolog）统一在以下示例中将 X 绑定到 Y？没想到。

?- X = f(X), Y = f(Y).
X = Y, Y = f(Y).

Answer 1

Is this true in all cases, or can more intricate examples be constructed where unification would still recurse infinitely?

AFAIK 编号

我不记得在哪里看到 =/2 did not work as expected. Granted my expectations are of how SWI-Prolog does =/2 如下所述。

As a related side-question, why does (again, I used swi-prolog) unification binds X to Y in the following example? I didn't expect that.

请参阅循环项的 SWI-Prolog C 代码中的这些 comments。

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Cyclic term unification. The algorithm has been  described to me by Bart
Demoen. Here it is (translated from dutch):
I created my own variation. You only need it during general unification.
Here is a short description:  suppose  you   unify  2  terms  f(...) and
f(...), which are represented on the heap (=global stack) as:
     +-----+          and     +-----+
     | f/3 |                  | f/3 |
     +-----+                  +-----+
      args                     args'
Before working on args and args', change  this into the structure below,
using a reference pointer pointing from functor  of the one to the other
term.
     +-----+          and      +-----+
     | ----+----------------->| f/3 |
     +-----+                  +-----+
      args                     args'
If, during this unification you  find  a   compound  whose  functor is a
reference to the term at the right hand you know you hit a cycle and the
terms are the same.
Of course functor_t must be different from ref. Overwritten functors are
collected in a stack and  reset   regardless  of whether the unification
succeeded or failed.
Note that we need to  dereference  the   functors  both  left and right.
References at the right are rare, but possible. The trick is to use both
sharing and cycles, where the cycles at the left are shorter:
t :-
    X = s(X),       Y = y(X,X),
    A = s(s(s(A))), B = y(A,A),
    Y = B.
While unifying the first argument of y/2, the left-walker crosses to the
right after the first cycle  and  creates   references  in  A, which are
processed by the right-walker when entering the second argument of y/2.
Initial measurements show a performance degradation for deep unification
of approx. 30%. On the other hand,  if subterms appear multiple times in
a term unification can be much faster. As only a small percentage of the
unifications of a realistic program are   covered by unify() and involve
deep unification the overall impact of performance is small (< 3%).
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

Answer 2

这完全取决于您对 统一算法 和 Prolog.

的理解

您的示例表明您对句法统一感兴趣。这里统一定义好，只要是就终止。所有序言都同意这里。

许多序言提供有理树统一。 SWI 从 2004 年 5.3 开始提供它。而且这个算法正在终止。鉴于这些假设，您问题的答案是 不，它不能无限递归。

然而，有理树对编程的用处相当有限。其主要动机是效率方面的考虑。也就是说，variable-term 与 occurs-check 的统一成本取决于术语的大小，只是有时它们可以是。但对于有理树，它们总是常量。

由于您的兴趣相当集中于教学，请考虑通过像这样更改统一算法来避免创建无限树（SWI 自 5.6.38、Scryer 以来）：

?- set_prolog_flag(occurs_check, error).
true.

?- X = f(X).
ERROR: =/2: Cannot unify _G2368 with f(_G2368): would create an infinite tree

在开发程序的时候，这个标志可以保持启用状态。它会帮助学生定位错误。只要没有这样的错误，程序也会产生与有理树统一完全相同的结果。

语法统一到此为止。通常，在存在约束或协程的情况下，无法保证终止。想到

inf :- inf.

?- freeze(X, inf), X = 1.

对于您的 side-question，这是 SWI 顶级的特殊性，有助于在答案中发现相同的术语。

?- X = 1, Y = 1.
X = Y, Y = 1.

Prolog中的统一算法可以无限递归吗？

Can the unification algorithm in Prolog recurse infinitely?

recursion

prolog

infinite

unification

swi-prolog