5

下面的 Prolog 程序定义了一个谓词deleted/3，用于从传入第二个参数的列表中删除所有出现在第一个参数中的项目，并导致在第三个参数中传递的列表：

deleted(_, [], []).
deleted(X, [X|Y], Z) :-
  deleted(X, Y, Z).
deleted(U, [V|W], [V|X]) :-
  deleted(U, W, X),
  U \= V.
  1. 它适用于此参数模式下的查询：
?- deleted(a, [a, b, a], [b]).
   true
;  false.
  1. 它也适用于这种参数模式下的查询：
?- deleted(X, [a, b, a], [b]).
   X = a
;  false.
  1. 它也适用于这种参数模式下的查询：
?- deleted(a, [a, b, a], Z).
   Z = [b]
;  false.
  1. 它也适用于这种参数模式下的查询：
?- deleted(X, [a, b, a], Z).
   X = a, Z = [b]
;  X = b, Z = [a, a]
;  false.
  1. 它也适用于这种参数模式下的查询：
?- deleted(a, Y, Z).
   Y = Z, Z = []
;  Y = [a], Z = []
;  Y = [a, a], Z = []
;  Y = [a, a, a], Z = []
;  Y = [a, a, a, a], Z = []
;  …
  1. 它也适用于这种参数模式下的查询：
?- deleted(X, Y, Z).
   Y = Z, Z = []
;  Y = [X], Z = []
;  Y = [X, X], Z = []
;  Y = [X, X, X], Z = []
;  Y = [X, X, X, X], Z = []
;  …
  1. 但它会在这种参数模式下通过查询耗尽资源：
?- deleted(a, Y, [b]).
Stack limit (0.2Gb) exceeded
  Stack sizes: local: 0.2Gb, global: 28.1Mb, trail: 9.3Mb
  Stack depth: 1,225,203, last-call: 0%, Choice points: 1,225,183
  Possible non-terminating recursion:
    [1,225,203] deleted(a, _1542, [length:1])
    [1,225,202] deleted(a, [length:1|_1584], [length:1])
  1. 它还会在此参数模式下通过查询耗尽资源：
?- deleted(X, Y, [b]).
Stack limit (0.2Gb) exceeded
  Stack sizes: local: 0.2Gb, global: 28.1Mb, trail: 9.3Mb
  Stack depth: 1,225,179, last-call: 0%, Choice points: 1,225,159
  Possible non-terminating recursion:
    [1,225,179] deleted(_1562, _1564, [length:1])
    [1,225,178] deleted(_1596, [length:1|_1606], [length:1])

如何为所有参数模式实现列表项删除？

4

1 回答 1

4

介绍

纯 Prolog 连词和析取词实际上是可交换的和结合的。

这允许我们忽略子句和目标顺序，前提是所有答案序列都是有限的。

当查询有无限的解决方案集时，Prolog 可能需要系统地枚举无限的答案序列。

修复

为了帮助 Prolog 找到上述“有问题的”查询的答案，交换两个递归规则：

已删除（_，[]，[]）。
deleted(U,[V|W],[V|X]) :- % 这个子句是最后一个
   差异（U，V），
   删除（U，W，X）。
删除（X，[X|Y]，Z）：-
   删除（X，Y，Z）。

演示

让我们通过上述代码更改再次运行您的查询！

有限的像之前一样工作1：

?- 已删除（a，[a，b，a]，[b]）。% Q1
   真的
; 错误的。

?- 删除（X，[a，b，a]，[b]）。% Q2
   X = 一个
; 错误的。

?- 已删除（a，[a，b，a]，Z）。% Q3
   Z = [b]
; 错误的。

?- 删除（X，[a，b，a]，Z）。% 第四季度
   Z = [a,b,a], dif(X,a), dif(X,b)
; Z = [a, a], X=b
; Z = [ b ]，X = a
; 错误的。

一些无限的以前是好的——它们仍然是：

?- 已删除（a，Y，Z）。% Q5
   Y = Z，Z = []
; Y = Z，Z = [_A]，差异（_A，a）
; Y = Z, Z = [_A,_B], 差异(_A,a), 差异(_B,a)
; Y = Z, Z = [_A,_B,_C], 差异(_A,a), 差异(_B,a), 差异(_C,a)
; …

?- 删除（X，Y，Z）。% Q6
   Y = Z，Z = []
; Y = Z，Z = [_A]，差异（X，_A）
; Y = Z，Z = [_A，_B]，差异（X，_A），差异（X，_B）
; Y = Z，Z = [_A,_B,_C]，差异（X，_A），差异（X，_B），差异（X，_C）
; …

一些无限的曾经是“有问题的”——不再是：

?- 删除（a，Y，[b]）。% Q7
   Y = [b]
; Y = [b,a]
; Y = [b,a,a]
; Y = [b,a,a,a]
; …

?- 删除（X，Y，[b]）。% Q8
   Y = [b]，差异（X，b）
; Y = [b,X], 差异 (X,b)
; Y = [b,X,X], 差异 (X,b)
; Y = [b,X,X,X], 差异 (X,b)
; Y = [b,X,X,X,X], 差异 (X,b)
; …

分析

现在，?- deleted(X,Y,[b]).让 Prolog 给我们答案。

但是为什么我们会耗尽呢？怎么没用？

为了解释这一点，让我们退后一步：许多2 Prolog 系统的默认 / vanilla / out-of-the-box 最初运行每个查询，直到它发现(0)有限故障或( 1)第一个答案3 .

在修复之前，我们没有观察到. 为什么不？

  1. 为什么没有有限失败？

    deleted(a,[a,b,a],[b])成立。

    因此，更一般的 绝不能失败。deleted(X,Y,[b])

  2. 为什么没有（第一个）答案？

    Prolog 进行深度优先、自上而下、从左到右。

    所以当……</p> 

        ?- 删除（X，Y，[b]）。

    ……“遇见”……</p> 

        删除（X，[X|Y]，Z）：-
       删除（X，Y，Z）。

    … 在 Prolog 机器内部，会发生以下情况：

    • 创建一个选择点来保存信息——在回溯时使用——另一个子句可能已经被选中。

    • 接下来，Prolog 继续一个递归目标，就像原来的目标一样：我们离答案更近了，因为第三个参数 -唯一实例化的参数 - 保持完全相同。

    最终，这个循环会耗尽内存——这正是您观察到的行为。

如果我们交换两个递归子句，以下子句将成为我们最顶层的递归子句：

已删除（U，[V|W]，[V|X]）：-
   差异（U，V），
   删除（U，W，X）。

现在，第三个参数发生了一些事情： Prolog 递归地遍历单链表，直到到达[]（或自由逻辑变量）。只有这样，Prolog 才能利用这个事实deleted(_,[],[]).，给我们一个答案。

脚注：

  1. 事实上更好，因为我们通过使用for 表示句法术语不等式来保持dif/2

    更多信息dif/2：

  2. 我曾经使用过的所有基于

  3. 不停留在第一个答案对于代码质量来说要好得多——特别是在通用终止属性方面。

    GUPU是一个专门用于 Prolog 和约束编程课程的优秀环境，它做正确的事——<em>默认情况下！

    “<a href="https://www.complang.tuwien.ac.at/ulrich/gupu/query2" rel="nofollow noreferrer">答案替换以五个为一组显示。”</p>

于 2021-08-27T14:05:58.630 回答