Prolog，生成无限序列时如何限制 "generate and test"

Question

我正在尝试编写一个“消除列表元素的连续重复项”的谓词。我的谓词如下所示:

compress([], []).
compress([X], [X]).
compress([X, X|Unpacked], [X|Rest]) :-
  % pull an element off Unpacked
  compress([X|Unpacked], [X|Rest]).
compress([X, Y|Unpacked], [X|Rest]) :-
  dif(X, Y), % we've reached the end of this subsequence
  compress([Y|Unpacked], Rest).

而且它对大多数实例化的查询非常有用:

compress([a, b], [a, b]) -> true
compress([a, a, b], [a, b]) -> true
compress([a, b, Z], X) -> Z = b, X = [a, b] OR X = [a, b, Z], dif(Z, b)

我这周才开始学习 Prolog，最后一个很酷!

然而，当以不同的方式使用时，这个谓词会给出不令人满意的结果:

compress(X, [a, b]) -> never terminates

?- compress2(X, Y).
X = Y, Y = [] ;
X = Y, Y = [_904] ;
X = [_904, _904],
Y = [_904] ;
X = [_904, _904, _904],
Y = [_904] ;
X = [_904, _904, _904, _904],
Y = [_904] ;
X = [_904, _904, _904, _904, _904],
Y = [_904] .
(etc)

所以，我围绕它写了一个包装器，它更适合那些类型的查询，它使用“生成和测试”在移动到更大的列表之前详尽地尝试给定列表大小的所有选项:

sizes(Large, Small) :-
  between(0, inf, Large),
  between(0, Large, Small).

compress2(Unpacked, Packed) :-
  sizes(Large, Small),
  length(Unpacked, Large),
  length(Packed, Small),
  compress(Unpacked, Packed).

这个新谓词非常适合一般查询:

?- compress2(X, [a, b]).
X = [a, b] ;
X = [a, a, b] ;
X = [a, b, b] ;
X = [a, a, a, b] ;
X = [a, a, b, b] ;
(etc)

?- compress2(X, Y).
X = Y, Y = [] ;
X = Y, Y = [_658] ;
X = [_658, _658], Y = [_658] ;
X = Y, Y = [_1162, _1168], dif(_1162, _1168) ;
X = [_658, _658, _658], Y = [_658] ;

以上两者最终都会产生所有替代方案。

但是，这个谓词在原始查询上失败了:

compress2([a, b], [a, b]). -> returns true, then loops forever

它永远循环，因为我正在做“生成和测试”，并且 sizes 谓词生成每个尺寸。这在我们找到答案之前效果很好，但是一旦我们找到答案，我们就会回溯，然后生成无限数量的尺寸，这些尺寸肯定永远不会起作用，因为它们太大了。

所以我的问题是，是否有一种纯粹的方法来制作适用于每个查询的 compress 谓词？我尝试的一切都修复了一种类型的查询，同时破坏了其他类型的查询。

Answer 1

这是解决此类问题的一般方法:

1 取关系名

您正在为关系使用命令式名称。尝试使用反射(reflect)关系中最有趣的内容的名称，而不是命令。像 compress(Xs, [a,b]) 这样的查询不会压缩任何东西。那么为什么要这样称呼呢？起初你可能会认为“你可以处理它”，至少我不能。首先，获取每个参数的类型，例如 list_list/2，然后对其进行细化，因为名称不够具体(毕竟两个列表之间有很多关系)。我将使用:list_compressed([a,a,a,b,b,b,b,b],[a,b])。

2 考虑解决方案集

这也称为声明性语义。因此考虑所有真实地面查询的集合。看看那里是否有一些有趣的结构。这里有一些:

2.1 函数依赖

... 在第一个和第二个参数之间。即:对于第一个参数的每个基本术语，(至多)第二个参数有一个基本术语。

然而，这并不适用于其他方向!事实上，对于第二个参数(成立)的每个基本项，第一个参数有无限多个基本项!

这种函数依赖的一个好处是第二个参数的大小总是受第一个参数的限制。因此，无需像您那样盲目枚举第二个参数。

2.2 类型

两个参数都必须是列表。 overgeneralizations 似乎没有任何空间，例如 append([], non_list, non_list)。

2.3 有限性

list_compressed/2 的解决方案集显然是无限的。但是有两个独立的无限源。一个是列表的长度造成的，另一个是参数的随意性造成的。 list_compressed([A,A],[A]) 目标适用于无限多个项。但是那些术语 A 是完全不受约束的。所以从某种意义上说，答案是有限的，而解决方案的集合仍然是无限的。

---

所有这些纯粹的声明性概念已经限制了我们可以编写的过程代码——而无需直接干扰它!

3 了解终止

特别是，您需要了解(通用)终止和寻找答案(有时称为存在性终止)之间的区别。参见 this answer了解更多。

您有点提示 compress(X, [a, b]) 永远不会终止。好吧，X 有一组无限的解决方案，不能像这样紧凑地表达X = [a,a,b] ; X = [a,a,a,b] ... Prolog 尝试枚举该集合，但是，唉，它首先从最大的答案开始!

此外，首先要看的(在您的实际代码中)是以下 failure-slice :

sizes(Large, Small) :-  between(0, inf, Large), false.  % SWI-specific, rather use length(_, Large)  between(0, Large, Small).compress2(Unpacked, Packed) :-  sizes(Large, Small), false,  length(Unpacked, Large),  length(Packed, Small),  compress(Unpacked, Packed).

This alone does not terminate and thus your original program will not terminate. Never, ever! To see this, look at Unpacked and Packed. In this fragment nobody is interested in those at all. Everything that interests those variables is behind false and thus irrelevant. So it is as if you had used _ in their stead.

Since Packed is already constrained by Unpacked but not vice versa, simply add the goal length(Unpacked, _) in front. That's all you can do (with reasonable effort).

So we have:

list_compressed2(List, Compressed) :-
   length(List, _),
   compress(List, Compressed).

这适用于所有有答案/解决方案的情况。对于无解的情况还是可以改进的。喜欢

?- list_compressed2(_, [a,a|_]).
   loops.

应该会失败(并因此终止)，但不会。