Prolog在寻求另一个解决方案时得到无限循环

Question

我用的是SWI Prolog，下面的代码是我作业中用到的（代码不是作业，但需要写课程要求的方法）：

nat(0).
nat(s(X)) :-
    nat(X).

plus(0,N,N) :- 
    nat(N).
plus(s(M),N,s(Z)) :-
    plus(M,N,Z).

times(0,N,0) :-
    nat(N).
times(s(M),N,Z) :-
    times(M,N,W),
    plus(W,N,Z).

exp(s(M),0,0) :-
    nat(M).
exp(0,s(M),s(0)) :-
    nat(M).
exp(s(N),X,Z) :-
    exp(N,X,Y),
    times(X,Y,Z).

exp(a,b,c) 表示 c=b^a.

直接从书上抄来的："The Art of Prolog: Advanced Programming Techniques".

当我运行以下查询时：

exp(s(s(0)),L,s(s(s(s(0))))).

我得到一个答案：

L = s(s(0))

但是当我通过输入 ; 询问另一个答案时

L = s(s(0)) ;

我得到一个无限循环（以堆栈外错误结束），我期望得到 false。

代码中有什么问题？是否有代码执行相同的操作（具有相同的自然数表示形式）但行为与我描述的方式相同？如果是这样，一些指示或建议将有很大帮助。

提前致谢。

Answer 1

给定程序进入无限循环是正常的：如果您调用 exp/3，在第二个元素未实例化的情况下，它开始分支遍历 L 的所有可能值。换句话说，如果你查询：

exp(s(s(0)),L,s(s(s(s(0))))).

它的作用是：

I instantiate L to s(0), is s(0) (thus 1) correct?
No! I instantiate L to s(s(0)) is 2 correct?
Yes return 2. Hold on, the user asks for more answers....
Is 3 correct? No
Is 4 correct? No
Is ... correct? (you get the idea)

每次尝试时，堆栈都会上升一层（因为它需要多一层来构建 s(X) over X...

您可以尝试使用另一种方式：有一个逻辑上限：结果（第三个参数），因此您可以先将第二个参数实例化为第三个参数并进行测试，然后递减第二个参数，直到找到正确的结果。

Prolog在寻求另一个解决方案时得到无限循环

Prolog getting inifinite loop when asking for another solution

prolog

infinite-loop

exponentiation

successor-arithmetics