如何解决这个递归加法?

How to fix this recursive addition?

我是逻辑编程和 Prolog 的新手。下面的 Prolog 程序定义了一个谓词 add/3,用于将第一个参数乘以第二个参数,结果是第三个参数,基于等式 x + y = z 相当于 (x − 1) + y = (z − 1):

add(0, Y, Y) :-
  number(Y).
add(X, Y, Z) :-
  number(X),
  number(Z),
  succ(U, X),
  succ(V, Z),
  add(U, Y, V).

但是这个查询,本应求解方程 1 + 0 = z,却没有 return 预期结果 (1):

?- add(1, 0, Z).
   false.

如何解决这个递归加法问题?

你得到 false 的原因是因为 add/3 的第二个子句调用 number(Z) 它只对地面数字变量成功,但你用 Z 调用它未实例化。 number/1 不能用作生成器。

删除该目标反过来会给您带来另一个错误,现在在 succ(V, Z) 中,因为您最终使用两个未实例化的变量调用它,并且该谓词要求至少实例化其参数之一。

您可以将目标与对 add/3 的递归调用交换,以便 V 在调用 succ/2 之前实例化。由于 succ/2 已经检查了它的参数,我将删除 X 作为数字的检查。

add(0, Y, Y) :-
  number(Y).
add(X, Y, Z) :- 
  succ(U, X),
  add(U, Y, V),
  succ(V, Z).

此程序现在应该适用于 +,+,? 模式。它不适用于其他模式。您可能需要检查 CLP(fd).


为了使其在三个参数中最多使用 1 个未绑定变量,您可以将递归步骤拆分到两个不同的路径上,以确保对 succ/2 的第一次调用有 1 个绑定变量,第二次调用到 succ/2 至少有 1 个绑定变量。

add(0, Y, Y) :-
  number(Y).
add(X, Y, Z) :-
  (var(Z) -> L1-R1/L2-R2 = U-X/V-Z; L2-R2/L1-R1 = U-X/V-Z),
  succ(L1, R1),
  add(U, Y, V),
  succ(L2, R2).

这基本上选择了一个可以用 Prolog 算法计算的方程。