使用带有 `length/2` 的约束变量

Question

问题是：

$ swipl
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.3.6-5-g5aeabd5)
Copyright (c) 1990-2015 University of Amsterdam, VU Amsterdam
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

?- use_module(library(clpfd)).
true.

?- N in 1..3, length(L, N).
N = 1,
L = [_G1580] ;
N = 2,
L = [_G1580, _G1583] ;
N = 3,
L = [_G1580, _G1583, _G1586] ;
ERROR: Out of global stack % after a while

（我可以调换子查询的顺序，结果是一样的）

我想我需要标记N才能使用它，但我想知道问题是什么？我之前一直没能哽咽length/2

Answer 1

让我们从最明显的开始。如果您切换目标，您将获得：

?- length(L, N), N in 1..3.

具有与以下相同的终止属性：

?- length(L, N), false, N in 1..3.

很明显，这个不能以Prolog的执行机制终止。

但是，如果你把N in 1..3放在前面，这个可能会影响终止。为此，必须可以用有限的手段证明从 4 开始不存在 N。你如何在一个没有约束的系统中证明这一点——也就是说，只有语法统一存在？好吧，你不能。 length/2 是 commonly defined 只是没有约束。使用 library(clpfd) 事情是微不足道的，因为 N #>= 4, N in 1..3 完全失败 ¹。另请注意，library(clpfd) 与 library(clpq) 合作不多，library(clpq) 也可能是一个有趣的候选人。

因此，您需要为您感兴趣的每个约束包定义自己的长度。这有点遗憾，但目前还没有通用的方法可以做到这一点。（（也就是说，如果你有兴趣并仔细考虑一下，你可能会想出一个很好的 API，每个约束系统都应该遵守。唉，我怀疑这将需要几十年的时间。目前，分歧太大了。))

所以这是 fd_length/2 的第一个天真的方法：

fd_length([], N) :-
   N #= 0.
fd_length([_|L], N0) :-
   N0 #>= 1,
   N1 #= N0-1,
   fd_length(L, N1).

好的，这可以优化以避免多余的选择点。但是还有一个更根本的问题：如果您要确定长度为 N 的列表的长度，这将创建 N 个约束变量！但我们只需要一个。

fd_length(L, N) :-
   N #>= 0,
   fd_length(L, N, 0).

fd_length([], N, N0) :-
   N #= N0.
fd_length([_|L], N, N0) :-
   N1 is N0+1,
   N #>= N1,
   fd_length(L, N, N1).

同样，由于很多原因，这并不完美：它可以像当前系统一样使用布伦特算法；并将它与所有 fd 属性结合起来。此外，允许使用算术表达式可能不是一个好主意；但我必须在 SWI 中等待 (#)/1...

^{1：严格来说，这个"simply fails"只适用于SICStus、SWI和YAP。因为在这些系统中，不会因当前表示耗尽而导致意外故障。也就是说，他们的失败总是可以被视为诚实的否定。}

Answer 2

下面的baroque work-around based on clpfd and meta-predicate tcount/3怎么样？

:- use_module([library(clpfd), library(lambda)]).

list_FDlen(Xs, N) :-
   tcount(\_^ =(true), Xs, N).

来查询吧！

?- N in 1..3, list_FDlen(Xs, N).
   N = 1, Xs = [_A]
;  N = 2, Xs = [_A,_B]
;  N = 3, Xs = [_A,_B,_C]
;  false.                             % terminates universally

?- N in inf..2, list_FDlen(Xs, N).
   N = 0, Xs = []
;  N = 1, Xs = [_A]
;  N = 2, Xs = [_A,_B]
;  false.                             % terminates universally, too

这个特定的查询呢？

?- N in 2..sup, list_FDlen(Xs, N).
   N = 2, Xs = [_A,_B]
;  N = 3, Xs = [_A,_B,_C]
;  N = 4, Xs = [_A,_B,_C,_D]
...                                   % does not terminate (as expected)

Answer 3

可能比不太确定的 length/2 更有用的是适当的列表长度约束。您可以找到一个名为 len/2 的 ECLiPSe implementation of it here。有了这个你会得到以下行为：

?- N :: 1..3, len(Xs, N).
N = N{1 .. 3}
Xs = [_431|_482]               % note it must contain at least one element!
There is 1 delayed goal.
Yes (0.00s cpu)

然后您可以通过枚举 N:

来枚举有效列表

?- N :: 1..3, len(Xs, N), indomain(N).
N = 1
Xs = [_478]
Yes (0.00s cpu, solution 1, maybe more)
N = 2
Xs = [_478, _557]
Yes (0.02s cpu, solution 2, maybe more)
N = 3
Xs = [_478, _557, _561]
Yes (0.02s cpu, solution 3)

或者通过生成符合良好旧标准的列表 length/2:

?- N :: 1..3, len(Xs, N), length(Xs, _).
N = 1
Xs = [_488]
Yes (0.00s cpu, solution 1, maybe more)
N = 2
Xs = [_488, _555]
Yes (0.02s cpu, solution 2, maybe more)
N = 3
Xs = [_488, _555, _636]
Yes (0.02s cpu, solution 3)

Answer 4

我们展示了的 clpfd-ish 变体 length/2 这是为@mat 的 clpfd 实现量身定制的。

:- use_module(library(clpfd)).
:- use_module(library(dialect/sicstus)).

:- multifile clpfd:run_propagator/2.

"exported"谓词lazy_len/2定义如下：

lazy_len(Es, N) :-
   N in 0..sup,               % lengths are always non-negative integers
   lazylist_acc_len(Es, 0, N),
   create_mutable(Es+0, State),
   clpfd:make_propagator(list_FD_size(State,N), Propagator),
   clpfd:init_propagator(N, Propagator),
   clpfd:trigger_once(Propagator).

全局约束处理程序 list_FD_size/3 在约束传播发生时逐步修改其内部状态。所有修改都被跟踪并且在回溯时 un-done。

clpfd:run_propagator(list_FD_size(State,N), _MState) :- 
   get_mutable(Es0+Min0, State),
   fd_inf(N, Min),
   Diff is Min - Min0,
   length(Delta, Diff),
   append(Delta, Es, Es0),
   (  integer(N)
   -> Es = []
   ;  Delta = []
   -> true                    % unchanged
   ;  update_mutable(Es+Min, State)
   ).

lazy_len/2从两个方面解决问题；它的 clpfd 约束部分如上所示。树端使用 prolog-coroutining 在部分实例化允许的范围内向下遍历列表¹:

lazylist_acc_len(_, _, N) :-
   integer(N),
   !.
lazylist_acc_len(Es, N0, N) :-
   var(Es),
   !,
   when((nonvar(N);nonvar(Es)), lazylist_acc_len(Es,N0,N)).
lazylist_acc_len([], N, N).
lazylist_acc_len([_|Es], N0, N) :-
   N1 is N0+1,
   N  in N1..sup,
   lazylist_acc_len(Es, N1, N).

示例查询：

?- lazy_len(Xs, N).
when((nonvar(N);nonvar(Xs)), lazylist_acc_len(Xs,0,N)),
N in 0..sup,
list_FD_size(Xs+0, N).

?- lazy_len(Xs, 3).
Xs = [_A,_B,_C].

?- lazy_len([_,_], L).
L = 2.

?- lazy_len(Xs, L), L #> 0.
Xs = [_A|_B],
when((nonvar(L);nonvar(_B)), lazylist_acc_len(_B,1,L)),
L in 1..sup,
list_FD_size(_B+1, L).

?- lazy_len(Xs, L), L #> 2.
Xs = [_A,_B,_C|_D],
when((nonvar(L);nonvar(_D)), lazylist_acc_len(_D,3,L)),
L in 3..sup,
list_FD_size(_D+3, L).

?- lazy_len(Xs, L), L #> 0, L #> 2.
Xs = [_A,_B,_C|_D],
when((nonvar(L);nonvar(_D)), lazylist_acc_len(_D,3,L)),
L in 3..sup,
list_FD_size(_D+3, L).

而且，最后还有一个查询...好吧，实际上还有两个：一个在上升，另一个在下降。

?- L in 1..4, lazy_len(Xs, L), labeling([up], [L]).
   L = 1, Xs = [_A]
;  L = 2, Xs = [_A,_B]
;  L = 3, Xs = [_A,_B,_C]
;  L = 4, Xs = [_A,_B,_C,_D].

?- L in 1..4, lazy_len(Xs, L), labeling([down], [L]).
   L = 4, Xs = [_A,_B,_C,_D]
;  L = 3, Xs = [_A,_B,_C]
;  L = 2, Xs = [_A,_B]
;  L = 1, Xs = [_A].

^{脚注 1：
在这里，我们专注于通过使用延迟目标来保持确定性（避免创建 choice-points）。}

使用带有 `length/2` 的约束变量

Using a constrained variable with `length/2`

prolog

clpfd