3

我正在写一些 Peano 算术来更好地学习 Prolog。以下是我提出的代码，它似乎与我在网上其他地方看到的相同：

add(X,z,X).
add(X,s(Y),s(Z)) :- add(X,Y,Z).
mult(_,z,z).
mult(X,s(Y),W) :- mult(X,Y,Z), add(X,Z,W).

但是，如果我尝试进行简单的查询，例如 的除数对0，我会遇到问题：

| ?- mult(X,Y,z).

Y = z ? ;

X = z
Y = s(z) ? ;

X = z
Y = s(s(z)) ? ;

X = z
Y = s(s(s(z))) ? ;

Fatal Error: global stack overflow (size: 32768 Kb, reached: 32765 Kb, environment variable used: GLOBALSZ)

这真的让我很烦恼，至于它怎么能一直到Y = 3，但不是Y = 4呢？

4

2 回答 2

3

发生堆栈溢出是因为，对于您的查询，add/3最终调用谓词时使用一个变量作为中间参数。当你回溯到它时，你会得到一个导致堆栈溢出的循环。考虑电话add(X,Y,Z)。第一个子句为您提供了第一个解决方案，add(X,z,X). 但是，在回溯时，当您使用第二个子句时，您将查询与add(X,s(Y),s(Z))递归调用统一起来add(X,Y,Z)，回到您开始的位置（请记住，中间参数没有被实例化，所以Yins(Y)也不会在调用时被实例化。你是能够得到前四个解决方案，如上所示，这要归功于两个谓词的基本情况。当这些基本子句（在回溯时）的使用用尽时，你就会进入我刚刚解释过的循环。

尝试添加以下子句作为add/3谓词的第一个子句：

add(X,Y,Z) :-
    write('Called: '), writeq(add(X,Y,Z)), nl, fail.

重试你会得到的查询（希望你能很快Control-C）：

| ?- mult(X,Y,z).

Y = z ? ;
Called: add(_279,z,z)

X = z
Y = s(z) ? ;
Called: add(_279,z,_307)
Called: add(_279,_279,z)

X = z
Y = s(s(z)) ? ;
Called: add(_279,z,_309)
Called: add(_279,_279,_309)
Called: add(z,z,z)

X = z
Y = s(s(s(z))) ? ;
Called: add(s(_307),_307,_309)
Called: add(s(z),s(s(z)),z)
Called: add(s(s(_311)),_311,_313)
Called: add(s(s(z)),s(s(s(s(z)))),z)
Called: add(s(s(s(_315))),_315,_317)
Called: add(s(s(s(z))),s(s(s(s(s(s(z)))))),z)
Called: add(s(s(s(s(_319)))),_319,_321)
Called: add(s(s(s(s(z)))),s(s(s(s(s(s(s(s(z)))))))),z)
Called: add(s(s(s(s(s(_323))))),_323,_325)
...

希望这可以帮助。

于 2013-09-27T16:58:19.050 回答
1

我知道这是一篇很老的帖子，但我刚刚开始学习 Prolog，发现这个问题很有趣。所以这是我的两分钱。

我注意到如果你改变你的规则

mult(X,s(Y),W) :- mult(X,Y,Z), add(X,Z,W).

到析取

mult(X,s(Y),W) :- mult(X,Y,Z); add(X,Z,W).

并运行相同的查询

?- mult(X,Y,z).

你会得到一些结果，但是你可以看到 SWI Prolog 解释器在一个点之后没有显示太多细节：

?- mult(X,Y,z).
Y = z ;
Y = s(z) ;
Y = s(s(z)) ;
Y = s(s(s(z))) ;
Y = s(s(s(s(z)))) ;
Y = s(s(s(s(s(z))))) ;
Y = s(s(s(s(s(s(z)))))) ;
Y = s(s(s(s(s(s(s(z))))))) ;
Y = s(s(s(s(s(s(s(s(z)))))))) ;
Y = s(s(s(s(s(s(s(s(s(z))))))))) ;
Y = s(s(s(s(s(s(s(s(s(s(...)))))))))) ;
Y = s(s(s(s(s(s(s(s(s(s(...)))))))))) ;
Y = s(s(s(s(s(s(s(s(s(s(...)))))))))) ;
Y = s(s(s(s(s(s(s(s(s(s(...)))))))))) ;
Y = s(s(s(s(s(s(s(s(s(s(...)))))))))) ;
Y = s(s(s(s(s(s(s(s(s(s(...)))))))))) ;
Y = s(s(s(s(s(s(s(s(s(s(...)))))))))) ;
Y = s(s(s(s(s(s(s(s(s(s(...)))))))))) .

在 Gnu Prolog 中做同样的事情看起来好多了，委婉地说：

| ?- mult(X,Y,z).

Y = z ? ;

Y = s(z) ? ;

Y = s(s(z)) ? ;

Y = s(s(s(z))) ? ;

Y = s(s(s(s(z)))) ? ;

Y = s(s(s(s(s(z))))) ? ;

Y = s(s(s(s(s(s(z)))))) ? ;

Y = s(s(s(s(s(s(s(z))))))) ? ;

Y = s(s(s(s(s(s(s(s(z)))))))) ? ;

Y = s(s(s(s(s(s(s(s(s(z))))))))) ? ;

Y = s(s(s(s(s(s(s(s(s(s(z)))))))))) ? ;

Y = s(s(s(s(s(s(s(s(s(s(s(z))))))))))) ? ;

Y = s(s(s(s(s(s(s(s(s(s(s(s(z)))))))))))) ? ;

Y = s(s(s(s(s(s(s(s(s(s(s(s(s(z))))))))))))) ? ;

Y = s(s(s(s(s(s(s(s(s(s(s(s(s(s(z)))))))))))))) ? ;

Y = s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(z))))))))))))))) ? ;

Y = s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(s(z)))))))))))))))) ? ;   
...

在 SWI Prolog（和 GNU Prolog）中，您可以调用调试器，它更多地说明了 Paulo Moura 关于原始问题的出色理论分析：

 ?- trace, mult(X,Y,z).

正如您将看到的，它似乎永远在运行，因此可以解释堆栈溢出。在这里查看跟踪的结果，在它的所有荣耀中。您也可以通过运行上述跟踪来跟踪浏览器上的无限循环。

于 2017-01-29T15:07:13.617 回答