list - 如何避免 SWI-Prolog 中的 "out of global stack"错误？

Question

我有一个 (SWI-) Prolog 程序，它以非常庞大的方式 (²) 使用 CLP(FD) 变量。我正在将 CLP(FD) 项列表移入和移出几个谓词 (¹)，并且它们的约束呈指数增长。我的代码适用于小列表，但是当我尝试将它用于长元素列表(其中每个元素的约束量变得巨大)时，我最终得到了 超出全局堆栈 错误。

我的观点是我是否可以使用不同的方法在不使用堆栈的情况下传递如此巨大的参数。我的第一个想法是使用 asserta将中间结果存储在动态数据库中，但我不确定是否能够以这种方式存储未实例化的变量或 CLP(FD) 约束。而且我也不知道这是否是最佳解决方案......

¹ 更多详情:我需要的是 N 个长度为 L 的列表的重叠，其中第一个元素被偏移。但是，偏移量不受限制，而是 CLP(FD) 变量。

² 更多详情:基本上，我有许多列表，其中每个元素都有数千个约束。每个元素约束基本上都保存有关其值的信息，这些信息与“主变量”值相关联。根据主变量的值，每个列表项都有一个或另一个值。

由于我已经在实现此类列表生成器时遇到了问题，因此我在这里征求了一些建议，因此您可以看到实际的列表生成器谓词 overlap_at/5 , here .
overlap_lists/4是发出错误的谓词(它 是否 工作正常 Rs 的长度小于 140 个元素且小于 10 Cs 个元素):

% Cs -> lists that have to be overlapped. Their items are integers.
% Ss -> Offsets per each list. They are CLP(FD) variables.
% Rs -> (not important here)
% Os -> List of overlapped elements.

overlap_lists(Cs,Ss,Rs,Os) :-
    length(Rs,L),
    zeros(Zs,L), % The initial list to overlap with is a list filled with zeros.
    overlap(Cs,Ss,Zs,Os),
    list_limit(Os,Rs). % Constrains the consumptions

overlap([],[],Fs,Fs) :- !.
overlap([C|Cs],[S|Ss],Os,Fs) :-
    fd_inf(S,Inf),
    overlap_at(Os,C,S,Inf,Os2),!,
    overlap(Cs,Ss,Os2,Fs).

overlap_at([], _, _, _, []).
overlap_at([A|As], Bs, S, N0, [AB|ABs]) :-
    overlap_here(Bs, [A|As], [AB|ABs], Conj),
    S #= N0 #==> Conj,
    S #> N0 #==> AB #= A,
    N1 #= N0 + 1,
    overlap_at(As, Bs, S, N1, ABs).

overlap_here(_, [], _, 1) :- !.
overlap_here([], [A|As], [AB|ABs], (AB #= A #/\ Rest)) :-
    overlap_here([], As, ABs, Rest).    
overlap_here([B|Bs], [A|As], [AB|ABs], (AB #= A + B #/\ Rest)) :-
    overlap_here(Bs, As, ABs, Rest).

Answer 1

想到的第一件事:增加SWI-​​Prolog通过的全局堆栈分配
swipl -G128M ...
它可能会帮助您阅读有关 Prolog 堆栈的更多信息:例如，不要将全局堆栈与本地堆栈混淆。以不同的方式传递参数通常不会帮助您减少全局堆栈的使用。 Richard O'Keefes Prolog 的工艺包含一个关于空间去向的很好的讨论。

在 64 位处理器上，使用 SWI-Prolog 的全局堆栈可能大于 128MB，因此对于严重的计算，您可能需要一台具有大量 RAM 的 64 位机器。

话虽如此，我发布的代码仅使用多项式而非指数内存量。如果您以需要指数空间的方式来表述问题，您可能首先尝试找到更(内存)效率更高的公式。这个问题本质上似乎并不需要指数空间。

如果您需要保留对 assertz/1 的约束, 使用 copy_term/3获取作为剩余目标的约束，并将这些剩余目标与变量一起声明，以便您稍后可以通过 maplist(call, Gs) 恢复目标.