使用 clpfd 时出现小问题 space 超出 SWI-Prolog 堆栈限制

Question

我试着举一个最简单的例子来说明这种行为。这是我加载的代码：

:- use_module(library(clpfd)).

gcd(A, 0, A) :- !.
gcd(0, B, B) :- !.
gcd(A, B, C) :- A #> B, !, A1 #= A mod B, gcd(A1, B, C).
gcd(A, B, C) :- A #=< B, A1 #= B mod A, gcd(A1, A, C).

ncalc(N, X, Y) :-
    Y #=< N,
    X*X #= (Y),
    X #< Y,
    X #> 0,
    gcd(X, Y, 1).

查询 ncalc(9, X, Y). 我得到：

ERROR: Stack limit (1.0Gb) exceeded
ERROR:   Stack sizes: local: 1Kb, global: 0.7Gb, trail: 9Kb
ERROR:   Stack depth: 1,548,057, last-call: 100%, Choice points: 5
ERROR:   In:
ERROR:     [1,548,057] clpfd:pop_queue(_176712142, <compound fast_slow/2>, 1)
ERROR:     [1,548,056] clpfd:pop_queue(_176712170)
ERROR:     [1,548,055] clpfd:fetch_propagator(_176712188)
ERROR:     [1,548,054] clpfd:do_queue
ERROR:     [1,548,052] clpfd:parse_clpfd('<garbage_collected>', _176712222)
ERROR:
ERROR: Use the --stack_limit=size[KMG] command line option or
ERROR: ?- set_prolog_flag(stack_limit, 2_147_483_648). to double the limit.

立即查询 ncalc(8, X, Y). returns false.。查询 ncalc(9, 1, Y). 到 ncalc(9, 8, Y).（X 的所有可能有效范围）。为什么它只适用于更简单的情况？有解决方法吗？谢谢！

PS：我是 prolog 的新手，我打算做的更复杂，但知道一个解决方法，我可能可以调整解决方案。

Answer 1

（让我们忽略编程风格，请参阅@Capelli 的评论。）

不终止的实际来源是由于 SWI 的 CLP(FD) 系统中的弱点。这是真正的罪魁祸首：

?- X in 2..3, Y in 4..9, Y mod X#=X1.
X in 2..3,
Y mod X#=X1,
Y in 4..9.

因此系统无法为X1推断出任何有用的信息。将此与 SICStus 进行对比：

| ?- X in 2..3, Y in 4..9, Y mod X#=X1.
Y mod X#=X1,
X in 2..3,
Y in 4..9,
X1 in 0..2

这里 SICStus 推断 X1 必须在 0..2 之内，因此不是负数。这反过来又避免了下一个推理中有问题的循环。

您可以通过坚持非负数来帮助系统一点，因此模块总是小于操作数。

A1 #>= 0, A1 #=< B, A1 #=< A

同时固定在CLP(Z)。

使用 clpfd 时出现小问题 space 超出 SWI-Prolog 堆栈限制

SWI-Prolog stack limit exceeded with tiny problem space using clpfd

prolog

swi-prolog

clpfd