如何修复这种递归乘法？ [英] How to fix this recursive multiplication?

问题描述

我是逻辑编程和PROLOG的新手。以下PROLOG程序定义了一个谓词mul/3，用于将第一个参数与第二个参数相乘，从而产生第三个参数，该谓词的基础是等效于(x−1)*y+y=z：

mul(0, _, 0).
mul(X, Y, Z) :-
  ground(X),
  succ(U, X),
  add(V, Y, Z),
  mul(U, Y, V).
mul(X, Y, Z) :-
  var(X),
  add(V, Y, Z),
  mul(U, Y, V),
  succ(U, X).

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

但此参数模式下的查询会耗尽资源：

?- mul(X, Y, 2).
   X = 1, Y = 2
;  X = 2, Y = 1
;
Stack limit (0.2Gb) exceeded
  Stack sizes: local: 0.2Gb, global: 20.8Mb, trail: 10.4Mb
  Stack depth: 452,739, last-call: 0%, Choice points: 452,716
  In:
    [452,739] add(_1326, 0, 0)
    [452,738] add(_1354, 0, 1)
    [452,737] add(_1382, 0, 2)
    [452,736] mul(_1410, 0, 2)
    [452,735] mul(_1438, 0, 2)

如何修复此递归乘法？

推荐答案

该程序工作正常，因为它提供了两个解决方案：X = 1, Y = 2和X = 2, Y = 1。然后，它会无限搜索其他解决方案。

此规则有问题：

mul(X, Y, Z) :-
  var(X),
  add(V, Y, Z),
  mul(U, Y, V),
  succ(U, X).

heremul(U, Y, V)递归的方式是第一个参数不是基础的，但前面的规则假定它是基础的(当V不是零时)。只需交换前两个参数即可解决问题。

但仍不尽如人意，请考虑

?- mul(2, 3, X).
   false.

这里的问题在前面的规则中：

mul(X, Y, Z) :-
  ground(X),
  succ(U, X),
  add(V, Y, Z),
  mul(U, Y, V).

对add(V, Y, Z)的调用变为add(V, 3, Z)，未定义。将其与下一个mul互换可解决此问题：

mul(X, Y, Z) :-
  ground(X),
  succ(U, X),
  mul(U, Y, V),
  add(V, Y, Z).

那么现在可以了吗？不完全是，例如

?- mul(X, 3, 6).
   false.

尝试使用

?- trace, mul(X,3,6).

并找出问题所在。

-编辑-

好的，让我们从头开始尝试。

为简化起见，首先看看前两个参数不是变量的情况：

% add1(+X, +Y, ?Z) [semidet]
add1(0, Y, Y) :-
  !.
add1(X, Y, Z) :-
  succ(X1, X),
  add1(X1, Y, Z1),
  succ(Z1, Z).

% mul1(+X, +Y, ?Z) [semidet]
mul1(0, _, 0) :-
  !.
mul1(X, Y, Z) :-
  succ(X1, X),
  mul1(X1, Y, Z1),
  add1(Z1, Y, Z).

然后是另一种情况，当总和/乘积已知时：

% add2(?X, ?Y, +Z) [nondet]
add2(0, Y, Y).
add2(X, Y, Z) :-
  succ(Z1, Z),
  add2(X1, Y, Z1),
  succ(X1, X).

% mul2(?X, ?Y, +Z) [nondet]
mul2(X, Y, 0) :-
  !,
  (X = 0; Y = 0).
mul2(X, Y, Z) :-
  nonvar(Y),
  !,
  succ(Y1, Y),
  add2(Z1, X, Z),
  mul2(X, Y1, Z1).
mul2(X, Y, Z) :-
  add2(Z1, Y, Z),
  mul2(X1, Y, Z1),
  succ(X1, X).

请注意，当mul2中的第三个规则递归时，它的第二个参数将是已知的，并由第二个规则使用。这与您最初编写的内容非常相似。

最后，您可以创建一个规则来选择您需要的规则：

add(X, Y, Z) :-
  nonvar(Z) -> add2(X, Y, Z); add1(X, Y, Z).

mul(X, Y, Z) :-
  nonvar(Z) -> mul2(X, Y, Z); mul1(X, Y, Z).

(当然，您可以使用var(X)等来统一这些规则，但我认为这样会清楚得多。)

这篇关于如何修复这种递归乘法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！