Prolog 的追加有什么问题? [英] What's wrong with Prolog's append?

问题描述

根据我所在大学的逻辑课程，对于以下查询，我们可以期待与 Prolog 定义的结果不同的结果:

According to my university's course in logic we could expect a different outcome than defined by Prolog for the following query:

append([], a, X)

(统一为 X=a).

但是我不明白他们的目标是什么?考虑到 append 应该为(在本例中)[] 和 a 的连接统一 X，应该期望什么作为有效响应?

However I don't get what they're aiming at? What should be expected as a valid response, given that append should unify X for (in this example) the concatenation of [] and a?

我假设他们可能期望返回 false 或 [a]；但是我想这应该是连接 a 和 [] 的结果，而不是 [] 和 a (因为[] 是[a]的尾部).

I assume they may be expecting a return of false or [a]; however I suppose that should be the result of concatenating a and [], not [] and a (since [] is the tail of [a]).

推荐答案

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

However I don't get what they're aiming at?

如果不询问他们，当然不可能确切地知道他们的目标是什么.

Knowing exactly what they are aiming at is of course impossible without asking them.

尽管如此，我认为他们的目标是表明 Prolog 是(或多或少)无类型.append/3 已记录如:

Nevertheless I think they aim to show that Prolog is (more or less) untyped. append/3 is documented as:

append(?List1, ?List2, ?List1AndList2)

   List1AndList2 是 List1 和 List2 的串联.

   List1AndList2 is the concatenation of List1 and List2.

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

So clearly one expects that the three arguments are lists and a is not a list. a is not the concatenation of [] and a since one would consider the two not "concatenatable".

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

Now this still succeeds, because append/3 is usually implemented as:

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

所以如果你给它append([],a,X).，它会简单地与第一个子句统一并统一X = a.

So if you give it append([],a,X)., it will simply unify with the first clause and unify X = a.

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

The same "weird" behavior happens with append([14],a,X). Here X = [14|a] which is not a list as well. This is because the Prolog interpreter does not "know" it is working with lists. For Prolog [A|B] is the same like any other functor.

一种更类型安全"的处理方法可能是:

A more "type safe" way to handle this could be:

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.

since here we check whether the second argument is a list. The downside however is that now we will append/3 in O(m+n) with m the length of the first list and n the length of the second list whereas in the original code it would take only O(m) time. Furthermore note that Prolog will not raise a warning/error at parse time. It will only fail to append [] with a at the moment you query these.

不检查类型的结果是，当您将程序提供给解释器时，您对程序编译/不引发错误的保证较少.这可能是一件好事，但问题可能在于您以他们不期望的方式调用某些谓词，这最终可能会引发错误.这就是为什么有时使用静态类型语言:它们保证"(至少在某种程度上)如果您调用问题，则不会发生此类错误.当然，这并不意味着程序不能在其他事情上出错(或者根本没有意义).例如，haskell 是静态类型的，并且有一个像:

Not checking types results in the fact that you have less guarantees if the program compiles/does not raises errors when you feed it to an interpreter. This can be a good thing, but a problem might be that you call some predicates in a way they don't expect which may raise errors eventually later. That is why statically typed languages are sometimes used: they "guarantee" (at least to some extent) that if you call the problem, no such errors will occur. Of course that does not mean that the program cannot error on other things (or simply make no sense). haskell for instance is statically typed and has an append like:

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

定义或多或少"相同，但 Haskell 会推导出 (++) 的类型是 (++) ::[a] ->[a] ->[a].因为它知道每个函数的输入和输出的类型，它可以对其进行微积分，因此在编译时，如果你给 (++) 与列表不同的东西.

The definition is "more or less" the same, but Haskell will derive that the type of (++) is (++) :: [a] -> [a] -> [a]. Because it know the type of the input and output of every function, it can perform calculus on it, and therefore at compile time, it will raise errors if you would give (++) something different than a list.

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

Whether that is a good thing is of course a different question: dynamically typed programming languages are designed that way deliberately since it allows more flexibility.

这篇关于Prolog 的追加有什么问题?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！