寻找多个答案时如何避免全局堆栈错误？

Question

使用 SWI-Prolog 加载以下程序并输入查询后，例如

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

或者

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

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

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

我的第一个建议：不要使用示踪剂。它不会对你有太大帮助。终止比一步步跟踪器可以向您展示的要复杂得多。首先让我告诉你程序不终止的原因：

细胞（[X | XS]，[Y | YS]）：-
    X=o，
    Y=o，
    长度([X | XS], LX),
    LX >= 3，
    length([Y | YS], LY), false ,
     LY 为 LX + 2 ,
    追加([o, o], [X | XS], W) ,
    追加(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).

有关此技术的更多信息，请参阅故障切片。