logo标签列表

如何在SWI-Prolog中复制预定义长度/2的行为？

prologclpfd
10

我想复制标准的length/2谓词的行为。特别是，我希望我的谓词能够适用于有界和无界的参数，就像下面的示例一样：

% Case 1
?- length(X, Y).
X = [],
Y = 0 ;
X = [_G4326],
Y = 1 ;
X = [_G4326, _G4329],
Y = 2 ;
X = [_G4326, _G4329, _G4332],
Y = 3 .

% Case 2    
?- length([a,b,c], X).
X = 3.

% Case 3
?- length(X, 4).
X = [_G4314, _G4317, _G4320, _G4323].

% Case 4
?- length([a,b,c,d,e], 5).
true.

简单明了的实现：

my_length([], 0).
my_length([_|T], N) :- my_length(T, X), N is 1+X.

这段代码存在问题。在第三种情况下，程序会输出正确答案后进入无限循环。这个谓词能否被转化为一个确定性的谓词？或者是一个不确定性的谓词，但返回false时停止运行？

可以！但需要使用red cut。详见：https://dev59.com/xGUp5IYBdhLWcg3wrY9p#15123016

经过一段时间的努力，我已经编写出了一组谓词来模仿内置的length/2的行为。我的my_len_tail是确定性的，并且在所有情况1-4中都能正确工作。 有没有更简单的方法？

my_len_tail(List, Len) :- var(Len)->my_len_tailv(List, 0, Len);
                          my_len_tailnv(List, 0, Len).

my_len_tailv([], Acc, Acc).
my_len_tailv([_|T], Acc, Len) :-
    M is Acc+1,
    my_len_tailv(T, M, Len).

my_len_tailnv([], Acc, Acc) :- !. % green!
my_len_tailnv([_|T], Acc, Len) :-
    Acc<Len,
    M is Acc+1,
    my_len_tailnv(T, M, Len).
如评论区的@DanielLyons所建议，可以使用clpfd来推迟小于检查。但是仍然存在一个问题：在Case 3 (my_len_clp(X, 3))中，谓词是非确定性的。如何解决？
:-use_module(library(clpfd)).
my_len_clp(List, Len) :- my_len_clp(List, 0, Len).

my_len_clp([], Acc, Acc).
my_len_clp([_|T], Acc, Len) :-
    Acc#<Len,
    M is Acc+1,
    my_len_clp(T, M, Len).

可以使用CLP(FD)库中的zcompare/3进行修复。参见：https://dev59.com/xGUp5IYBdhLWcg3wrY9p#15123146
如果有人能够提供不使用供应商扩展或clp(fd)的解决方案，那将特别有趣。 - Daniel Lyons
感谢您的建议@DanielLyons。我已经更新了我的帖子。但问题仍然没有解决。 - damisan
2
+1 给 my_len_clp/3，它非常高效！ - false
6个回答
5
在SWI-Prolog中，可以通过使用CLP（FD）的zcompare/3来解决非确定性问题，该函数将不等式反映为一个术语，可用于索引。
:- use_module(library(clpfd)).

my_length(Ls, L) :-
        zcompare(C, 0, L),
        my_length(Ls, C, 0, L).

my_length([], =, L, L).
my_length([_|Ls], <, L0, L) :-
        L1 #= L0 + 1,
        zcompare(C, L1, L),
        my_length(Ls, C, L1, L).

你的例子现在是确定性的（因为最新版本的SWI-Prolog执行即时索引）：

?- my_length(Ls, 3).
Ls = [_G356, _G420, _G484].

所有严肃的Prolog实现都会配备CLP（FD），在这里使用它是非常合理的。如果尚未提供，请向供应商要求实现zcompare/3或更好的替代方案。

在这里使用它是有意义的，但教学上有趣的是知道如何在没有它的情况下解决这种问题。 - Daniel Lyons
我发现这个应用程序比文档条目更易懂。 - CapelliC
CLP(FD) 肯定很有用！我已经对查询 my_length(X,1) 进行了 trace/1。调用树深度约为 30 级，且有许多统一步骤。通常情况下，我们会进行速度与功率的权衡。在这种情况下，L1 #= L0 + 1 是否比 L1 is L0 + 1 更好呢？ - damisan
3
一般说明：当教授涉及整数的谓词时，我认为最好使用有限域约束来进行教学，因为它们是真实关系，可以在所有方向上使用。如果没有约束，你将不得不引入非单调谓词来处理整数。L1 #= L0 + 1 比使用 is/2 更一般化，尝试使用最一般化的查询 my_length(Ls, C, L0, L) 来测试这两个版本。速度差异很容易测量（在严肃应用中通常可以忽略不计），而你会获得很多普遍性。 - mat
1
关于上面的 zcompare(C, 0, L)，需要注意的是它涉及到创建一个冻结目标，该目标将立即执行。正是这样的例子让我认为更喜欢非确定性解决方案。 - false
3

针对一组测试用例，请参考此表格以及Prologue中的当前定义。还有许多奇怪的情况需要考虑。

使用var/nonvar、is/2等来定义length/2并不完全简单，因为(is)/2和算术比较非常有限。也就是说，它们经常会产生instantiation_error而不是相应地成功。仅仅为了说明这一点：使用successor-arithmetics定义length_sx/2非常简单。

length_sx([], 0).
length_sx([_E|Es], s(X)) :-
   length_sx(Es, X).

这个定义非常完美。它甚至对于 length_sx(L, L) 也无法通过。不幸的是，后继算术并没有得到高效支持。也就是说，一个整数 i 需要 O(i) 的空间，而不是像人们期望的那样只需要 O(log i)。

我更喜欢的定义是：

length_fd([],0).
length_fd([_E|Es], L0) :-
   L0 #> 0,
   L1 #= L0-1,
   length_fd(Es, L1).

哪个是最直接的翻译。如果长度已知，它非常高效，但否则，后面的约束开销就会显现出来。此外，还存在这种不对称性：

?- length_fd(L,0+0).
   false.
?- length_fd(L,0+1).
   L = [_A]
;  false.

然而，使用library(clpfd)进行定义的方法尤其优雅和高效，即使在更为复杂的情况下也是如此。它虽然不像内置的length函数快速，但仍然十分有效。

?- time(( length_fd(L,N),N=1000 )).
% 29,171,112 inferences, 4.110 CPU in 4.118 seconds (100% CPU, 7097691 Lips)
   L = [_A,_B,_C,_D,_E,_F,_G,_H,_I|...], N = 1000
;  ... .
?- time(( my_len_clp(L,N),N=10000 )).
% 1,289,977 inferences, 0.288 CPU in 0.288 seconds (100% CPU, 4484310 Lips)
   L = [_A,_B,_C,_D,_E,_F,_G,_H,_I|...], N = 10000
;  ... .
?- time(( length(L,N),N=10000 )).
% 30,003 inferences, 0.006 CPU in 0.006 seconds (100% CPU, 4685643 Lips)
  L = [_A,_B,_C,_D,_E,_F,_G,_H,_I|...], N = 10000
;  ... .

...但是它能够正确处理约束条件：

?- N in 1..2, my_len_clp(L,N).
   N = 1, L = [_A]
;  N = 2, L = [_A, _B]
;  false.
?- N in 1..2, length(L,N).
   N = 1, L = [_A]
;  N = 2, L = [_A, _B]
;  loops.
1

我并不是特别有信心回答这个问题，但我的想法是不行的。你需要做一些额外的工作来让Prolog正确处理length/2，这真是太可惜了，因为它在最简单的形式下是一个很好的“教程”谓词。

我提供证据，SWI-Prolog函数的源代码和GNU Prolog 的源代码。这两者都不是简洁而巧妙的技巧，看起来它们都通过测试参数，然后根据参数实例化情况将处理推迟到不同的内部函数中。

我很希望我是错的。例如，我经常想知道为什么写member/2很容易做到正确，但写length/2却很难。Prolog不擅长算术，但它真的那么糟糕吗？希望有人能给出更好的答案。

关于member/2: 它的实现并不像你所建议的那样容易描述。这是当前的定义。为了涵盖其含义，内置谓词的定义格式必须更改，并且需要一个非常牵强的 列表前缀 的概念。容易吗？我会说不是。 - false
1
基于表达式求值的算术运算，如(is)/2，是Prolog语言中非常特殊的补充。如果您想要纯粹的运算，可以使用s(X)-表示法或约束。 - false
@false 我不确定我是否理解你的意思。member/2 的定义比非 clpfd 版本的 length/2 更少的代码量和更容易理解。即使使用了 clpfd，它也比 member/2 的朴素定义更长且更复杂。你需要什么样的知识才能理解 member/2，而这些知识对于 length/2 也是必需的呢？ - Daniel Lyons
看一下上面 member/2 的定义：你认为 member(a,[a|nonlist]) 很容易理解吗？length/2 根本没有这样奇怪的特性，但这并不意味着它很容易定义。 - false
1
member/2需要奇怪的概念，而length/2根本不需要这样奇怪的概念。因此，length/2更容易定义/说明。但实现起来要困难得多，因为（is/2）太不完整了。 - false
显示剩余2条评论
-1

这个适用于您所有的测试案例（但它有红色删减）：

my_length([], 0).
my_length([_|T], N) :- 
    ( integer(N) ->
        !, 
        N > 0, 
        my_length(T, X), N is 1 + X, !
    ;
        my_length(T, X), N is 1 + X
    ).
不错。看起来，你的解决方案基本上使用了和我的相同的思路 my_len_tail：测试我们是否已经完全实例化了长度，如果是，则在检查点处进行第一次选择后中止。 - damisan
但是在 my_len([1,2,3], X) 的情况下，PROLOG 尝试使用第二个谓词进行三次统一（并且每次都失败）。 为了解决这个问题，我使用了“弹簧”来在第一次统一时选择正确的长度函数类型。 您能否给出一些例子，在这个函数中应该优先选择 ground/1 而不是 nonvar/1？ - damisan
nonvar/1 在这里可能更好，但 integer/1 更好。第二个子句应该加上 N > 0。 - Sergii Dymchenko
错误，是的，这就是为什么我在之前的评论中说“应该将N>0添加到第二个子句”的原因。 - Sergii Dymchenko
my_length(L,N), N = 100000 - false
-1

（我尝试编辑@false的response，但被拒绝了）

my_len_tail/2在生成列表时比buldin length/2快（无论是推理次数还是实际时间），但在N in 1..2约束条件下存在问题。

?- time(( my_len_tail(L,N),N=10000000 )).
% 20,000,002 inferences, 2.839 CPU in 3.093 seconds (92% CPU, 7044193 Lips)
L = [_G67, _G70, _G73, _G76, _G79, _G82, _G85, _G88, _G91|...],
N = 10000000 .

?- time(( length(L,N),N=10000000 )).
% 30,000,004 inferences, 3.557 CPU in 3.809 seconds (93% CPU, 8434495 Lips)
L = [_G67, _G70, _G73, _G76, _G79, _G82, _G85, _G88, _G91|...],
N = 10000000 .
1
你需要在同一台机器上比较东西。 - false
要么你的机器更快，要么你的时钟更粗糙。尝试使用N = 100000来同时测试my_len_tail和length参数。 - false
我所说的“更快”，指的是推理次数（在不同机器上相同），而不是实际时间。我已经编辑了我的帖子。 - damisan
误解：我比较了my_len_clp和length。你比较的是my_len_tail和length！ - false
1
关于“更快”的问题：这里不同的推理次数是由于一个版本使用(is)/2，而另一个版本使用succ/2。succ/2算作一次推理，但(is)/2不算。因此，这相当武断，并与实际执行无关。 - false
很好的观察。在将(is)/2更改为succ/2后，my_len_tail使用相同数量的推理并在大约相同的时间内运行，与内置的length/2相同。 - damisan
-1

实现

goal_expansion((_lhs_ =:= _rhs_),(when(ground(_rhs_),(_lhs_ is _rhs_))))  .

:- op(2'1,'yfx','list')  .

_list_ list [size:_size_] :-
_list_ list [size:_size_,shrink:_shrink_] ,
_list_ list [size:_size_,shrink:_shrink_,size:_SIZE_]  .

_list_ list [size:0,shrink:false]  .

_list_ list [size:_size_,shrink:true] :-
when(ground(_size_),(_size_ > 0))  .

[] list [size:0,shrink:false,size:0] .

[_car_|_cdr_] list [size:_size_,shrink:true,size:_SIZE_] :-
(_SIZE_ =:= _size_ - 1) ,
(_size_ =:= _SIZE_ + 1) ,
_cdr_ list [size:_SIZE_]  .

测试

/*
   ?- L list Z .
L = [],
Z = [size:0] ? ;
L = [_A],
Z = [size:1] ? ;
L = [_A,_B],
Z = [size:2] ? ;
L = [_A,_B,_C],
Z = [size:3] ?
yes

   ?- L list [size:0] .
L = [] ? ;
no
   ?- L list [size:1] .
L = [_A] ? ;
no
   ?- L list [size:2] .
L = [_A,_B] ? ;
no

   ?- [] list [size:S] .
S = 0 ? ;
no
   ?- [a] list [size:S] .
S = 1 ? ;
no
   ?- [a,b] list [size:S] .
S = 2 ? ;
no
   ?- [a,b,c] list [size:S] .
S = 3 ? ;
no
   ?- 
*/
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接