寻找多个答案时如何避免Out of global stack ERROR？

Question

使用 SWI-Prolog 加载以下程序并输入

等查询后

cells([o,x,o,x,o], A).

或

cells(A, [o,x,o,x,o]).

第一个结果似乎总是正确的，但在提交分号以查找更多结果后（我不知道在这两种情况下是否应该有额外的结果），我得到一个 PROLOG SYSTEM ERROR 提到垃圾收集和全局堆栈错误。

regla(o,o,o,o).
regla(x,o,o,x).
regla(o,x,o,o).
regla(o,o,x,x).
regla(x,o,x,x).
regla(x,x,o,x).
regla(o,x,x,x).
regla(x,x,x,o).

cells([X | XS], [Y | YS]) :-
    X = o,
    Y = o,
    length([X | XS], LX),
    LX >= 3,
    length([Y | YS], LY),
    LY is LX + 2,
    append([o, o], [X | XS], W),
    append(W, [o, o], Z),
    cellsR(Z, [Y | YS]).

cellsR(_, []).
cellsR([A, B, C | R], [H | T]) :-
    regla(A, B, C, H),
    cellsR([B, C | R], T).

我假设这些错误与我处理递归的方式有关，所以也许有人可以查看代码并告诉我哪里出错了。

Answer 1

我的第一个建议：不要使用示踪剂。它不会帮助你很多。终止比分步跟踪器可以向您展示的要复杂得多。先说说你的程序没有终止的原因：

cells([X | XS], [Y | YS]) :-
    X = o,
    Y = o,
    length([X | XS], LX),
    LX >= 3,
    length([Y | YS], LY), false,
    LY is LX + 2,
    append([o, o], [X | XS], W),
    append(W, [o, o], Z),
    cellsR(Z, [Y | YS]).

这突出显示了程序中您将修改以消除问题的部分。换句话说，只要你保持那部分不变，你的问题就不会消失。

一个最小的变化是添加一个进一步的目标，即在使用 length/2 之前首先建立这两个列表的长度之间的关系：

cells([X | XS], [Y | YS]) :-
    X = o,
    Y = o,
    list_samelength([_,_|XS], YS),
    length([X | XS], LX),
    LX >= 3,
    length([Y | YS], LY),
    LY is LX + 2,
    append([o, o], [X | XS], W),
    append(W, [o, o], Z),
    cellsR(Z, [Y | YS]).

list_samelength([], []).
list_samelength([_|Xs], [_|Ys]) :-
   list_samelength(Xs, Ys).

有关此技术的更多信息，请参阅 failure-slice。

寻找多个答案时如何避免Out of global stack ERROR？

How to avoid Out of global stack ERROR when looking for multiple answers?

prolog

failure-slice