如果直接插入Prolog，为什么将变量与失败的结果匹配? [英] Why would Prolog match a variable to a result that fails if plugged in directly?
问题描述
我正在制作一个Prolog程序，该程序查找一组列表的子集.该子集必须匹配某些特定条件，一方面是该子集的列表不能相同.令我感到困惑的是，当我尝试找到变量X的匹配项时，如果我将其插入查询中以代替X，它将生成返回false的结果.例如:
?- containsSet(2, [[3],[7],[7]], X).
X = [[3], [7]] ;
X = [[3], [7]] ;
X = [[7], [7]] ;
false.
?- containsSet(2, [[3],[7],[7]], [[7],[7]]).
false.
如果直接插入X时返回false，怎么可能将X与[[7]，[7]]匹配?
containsSet的想法是找到长度为N(在本例中为2)的列表子集，该子集在匹配位置没有匹配元素(即子集中的两个列表都没有相同的第一元素或相同的第二元素) ， 等等).在上面的示例中，[7]和[7]的第一个(也是唯一一个)元素匹配，因此返回false.
首先，祝贺我初学者在问题中看到的最具说明性和正当性的观察之一！
一方面，合取在逻辑上是可交换的，这是最基本，最著名的属性之一.另一方面，许多Prolog初学者未能意识到，使用像(\+)/1这样的非单调谓词几乎总是 destroys 这样的基本不变式.您注意到这里发生了非常出乎意料的事情，并且您期望Prolog采取更正确的行为是正确的.幸运的是，针对此类问题的声明式解决方案现在在Prolog系统中得到了前所未有的广泛传播.
首先，考虑一下如果在程序中使用(\+)/1会很快出现的一些问题:
?- X = d, \+ member(X, [a,b,c]). X = d.
但是，如果我们只是简单地通过合取性交换目标，我们就会得到不同答案:
?- \+ member(X, [a,b,c]), X = d. false.
这表明(\+)/1不是 单调:尽管更具体的查询会产生解决方案，但它可能导致更通用的查询失败:
?- \+ member(X, [a,b,c]). false. ?- \+ member(d, [a,b,c]). true.
因此，非单调谓词会导致各种杂质并违反声明性语义.声明性地，知道有解决方案后，我们当然希望更通用的查询成功完成，但失败了.
在此具体说明中，要指定一个术语与列表中的所有其他术语不同，请使用 constraint dif/2. dif/2可以全方位运行，并且如果其参数为变量，也会产生正确的答案.例如:
not_member(X, Ls) :- maplist(dif(X), Ls).
这个定义保留了对偶的可交换性，正如我们对纯逻辑关系的深切期望和期望一样:
?- not_member(X, [a,b,c]), X = d. X = d. ?- X = d, not_member(X, [a,b,c]). X = d.
由于not_member/2仅使用纯谓词，因此您已确保—已经在建造中—只能给出声明正确的答案.
为了对您的代码进行声明式推理，我在您的方法中对此表示赞赏，建议您使用Prolog的纯单调子集.请参见逻辑纯度和 prolog-dif 的问题，以获取更多信息. >
I'm making a Prolog program that finds a subset of a set of lists. This subset must match some specific conditions, an aspect of which is that the subset's lists cannot be identical. What's confusing me is that when I try to find a match for a variable, X, it generates results that return false if I plug them into the query in place of X. For example:
?- containsSet(2, [[3],[7],[7]], X).
X = [[3], [7]] ;
X = [[3], [7]] ;
X = [[7], [7]] ;
false.
?- containsSet(2, [[3],[7],[7]], [[7],[7]]).
false.
How could it possibly match X to [[7], [7]] if, when plugged in directly, it returns false?
The idea of containsSet is to find a length-N (in this case 2) subset of lists that has no matching elements in matching positions (i.e. no two lists in the subset have the same first element, or the same second element, etc). In the example above, the first (and only) elements of [7] and [7] match, so it returns false.
First, congratulations for one of the most declarative and justified observations I have seen in questions by beginners!
On the one hand, it is one of the most basic and well-known properties that conjunction is commutative in logic. On the other hand, many Prolog beginners fail to realize that using one of the non-monotonic predicates like (\+)/1 almost invariably destroys such basic invariants. You noticed that something very unexpected is going on here, and you are right to expect more correct behaviour from Prolog. Luckily, declarative solutions for such problems are now more widely spread than ever before among Prolog systems.
First, consider some problems that soon arise if you use (\+)/1 in your programs:
?- X = d, \+ member(X, [a,b,c]). X = d.
yet, if we simply exchange the goals by commutativity of conjunction, we get the different answer:
?- \+ member(X, [a,b,c]), X = d. false.
This shows that (\+)/1 is not monotonic: It can cause a more general query to fail although a more specific query yields solutions:
?- \+ member(X, [a,b,c]). false. ?- \+ member(d, [a,b,c]). true.
Thus, non-monotonic predicates cause all kinds of impurities and violate declarative semantics. Declaratively, knowing that there are solutions, we certainly expect the more general query to succeed, but it fails.
In this concrete, to specify that a term is different from all other terms in a list, use the constraint dif/2. dif/2 works in all directions, and yields correct answers also if its arguments are variables. For example:
not_member(X, Ls) :- maplist(dif(X), Ls).
This definition preserves commutativity of conjunction, as we deeply desire and in fact expect from pure logical relations:
?- not_member(X, [a,b,c]), X = d. X = d. ?- X = d, not_member(X, [a,b,c]). X = d.
Since not_member/2 uses only pure predicates, you have ensured — already by construction — that it gives only declaratively correct answers.
For reasoning declaratively about your code, which I applaud in your approach, I recommend you stay in the pure monotonic subset of Prolog. See logical-purity and prolog-dif for more information.
这篇关于如果直接插入Prolog，为什么将变量与失败的结果匹配?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
