Prolog的附加有什么问题？

Question

根据我大学的逻辑课程,我们可以预期Prolog定义的结果与以下查询不同:

append([], a, X)

(统一为X=a).

但是我不明白他们的目标是什么？应该期望什么作为有效的响应,因为append应该统一X(在这个例子中)[]和a？的串联？

我认为他们可能期待回归false或[a]; 然而,我想应该是级联的结果a和[],而不是[]和a(因为[]是的尾部[a]).

Answer 1

这里的关键是,我们预计append/3持有仅用于名单.

在你展示的查询,a是不是一个名单,但append/3 仍然  成立.

因此,这种关系实际上比我们最初期望的更为普遍:它也适用于其他情况!

之所以如此,可以很快从传统定义的第一个条款append/3:

append([], Bs, Bs).

仅此子句已使查询成功!没有额外的纯子句可以阻止这一点.因此,如果我们希望关系只保留列表,则必须限制此子句.这意味着,我们必须对第二个参数设置一个约束,我们通过在子句的主体中声明它来做:

append([], Bs, Bs) :- ... (left as an exercise)

这显然是有代价的:性能.

因此,这里的权衡取决于性能和精度.在Prolog中,我们经常接受这样的权衡,因为我们只使用预期的术语隐含地使用这些谓词.另一方面,对于许多谓词,如果未使用预期类型调用域错误或类型错误,我们希望受益.

Answer 2

您的课程针对Prolog编程的非常重要的一点。

手册对于append/3谓词和类似谓词的精确定义常常是草率的。实际上，完整的定义是如此复杂，以至于通常只希望定义实际关系的一部分。考虑一下Prolog序言中的第一个定义：

append(Xs, Ys, Zs)如果Zs是列表Xs和的串联，则为true Ys。

注意如果。因此，该定义给出了关系保持但没有明确排除其他情况的情况。为了排除其他情况，应改为iff。提到的情况（我们在谈论列表）是谓词的预期用途。那么，现在可能还包括哪些情况？前提（参数为列表）不成立的情况。

考虑append/3用“ iff”代替“ if”的定义：

append([], Xs, Xs) :-
   list(Xs).
append([X|Xs], Ys, [X|Zs]) :-
   append(Xs, Ys, Zs).

list([]).
list([X|Xs]) :-
   list(Xs).

现在，添加两个列表的费用为| Xs| + | Ys|。与|相比，这是相当大的开销。Xs| 单独。

但是情况更糟。考虑查询：

?- append([1,2], Ys, Zs).
;  Ys = [], Zs = [1,2]
;  Ys = [_A], Zs = [1,2,_A]
;  Ys = [_A,_B], Zs = [1,2,_A,_B]
...

因此，我们可以无限查询此查询。将此与通常的定义进行对比：

?- append([1,2], Ys, Zs).
   Zs = [1,2|Ys].

只有一个答案！它包含所有列表的所有答案以及您观察到的一些奇怪的情况。因此，append的常规定义具有更好的终止属性。实际上，如果第一个或第三个参数是已知长度¹的列表，它将终止。

请注意，答案包含Ys。以这种方式，无数个答案可以分解为一个答案。这实际上就是逻辑变量的力量！我们可以用有限的方法来表示许多解决方案。要付出的代价是一些可能导致编程错误的额外解决方案²。因此需要采取一些预防措施。

1它也终止于某些更晦涩的情况，例如append([a|_],_,[b|_])。

2 append([a], Zs, Zs).（在许多系统中）也会产生一个答案。

Answer 3

但我不明白他们的目的是什么？

如果不问他们，就不可能确切地知道他们的目标。

尽管如此，我认为他们的目的是表明Prolog（或多或少）是非类型化的。append/3记录为：

append(?List1, ?List2, ?List1AndList2)

   List1AndList2List1是和的串联List2。

很明显，人们期望这三个参数是列表而a不是列表。a不是[]和的串联a，因为人们会认为两者不可“串联”。

现在这仍然成功，因为append/3通常实现为：

append([],T,T).
append([H|T],T2,[H|R]) :-
    append(T,T2,R).

因此，如果您给出它append([],a,X).，它将简单地与第一个子句统一并统一X = a。

同样的“奇怪”行为也会发生在append([14],a,X). 这里X = [14|a]也不是一个列表。这是因为 Prolog 解释器不“知道”它正在处理列表。Prolog 与[A|B]任何其他函子一样。

处理此问题的更“类型安全”的方法可能是：

append([],[],[]).
append([H|T],T2,[H|R]) :-
    append(T,T2,R).
append([],[H|T],[H|R]) :-
    append([],T,R).

或者更优雅地：

list([]).
list([_|T]) :-
    list(T).

append([],T,T) :-
    list(T).
append([H|T],T2,[H|R]) :-
    append(T,T2,R).

因为在这里我们检查第二个参数是否是一个列表。然而，缺点是现在我们将append/3在O(m+n)中， m是第一个列表的长度，n是第二个列表的长度，而在原始代码中只需要O(m)时间。此外请注意，Prolog 在解析时不会引发警告/错误。仅当您查询这些时，它才会无法附加[]。a

不检查类型会导致当您将程序提供给解释器时，您对程序是否编译/不引发错误的保证较少。这可能是一件好事，但问题可能是您以他们不期望的方式调用某些谓词，这最终可能会引发错误。这就是有时使用静态类型语言的原因：它们“保证”（至少在某种程度上）如果您调用该问题，则不会发生此类错误。当然，这并不意味着程序不会在其他事情上出错（或者根本没有意义）。例如，haskell是静态类型的，并且有一个附加，例如：

(++) [] t2 = t2
(++) (h:t) t2 = h:((++) t t2)

定义“或多或少”相同，但 Haskell 会推导出 的类型(++)是(++) :: [a] -> [a] -> [a]。因为它知道每个函数的输入和输出的类型，所以它可以对其执行微积分，因此在编译(++)时，如果您给出与列表不同的内容，它将引发错误。

这是否是一件好事当然是一个不同的问题：动态类型编程语言是故意这样设计的，因为它允许更大的灵活性。