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 的串联，因为人们会认为两者不是concatenatable".

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).

因为这里我们检查第二个参数是否是一个列表.然而，缺点是现在我们将在 O(m+n) 中 append/3，其中 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 会推导出 (++) 的类型是 (++)::[一]->[一]->[一].因为它知道每个函数的输入和输出的类型，它可以对其进行演算，因此在 compile 时，如果你给出 (++) 不同于列表的东西.

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屋！