Prolog，置换代码理解 [英] Prolog, permutation code understanding

问题描述

我试图了解这程序有效.

Daniel Lyons解决方案中的代码(来自上面的链接)

Code from Daniel Lyons' solution(from the link above)

takeout(X,[X|R],R).  
takeout(X,[F |R],[F|S]) :- takeout(X,R,S).

perm([X|Y],Z) :- perm(Y,W), takeout(X,Z,W).  
perm([],[]).

我正在尝试了解此列表如何工作[1,2,3] 所以，我有perm([1,2,3],X).

I'm trying ti understand how it works with this list [1,2,3] So, I have perm([1,2,3],X).

首先很容易理解，先Y = [2,3]然后Y = [3]然后Y = []

It's easy to understand at first, Y = [2,3] then Y = [3] and then Y = []

在调用perm([],[]).之后，它给了我们W = []

After that perm([],[]). is called and it gives us W = []

现在，第一次调用takeout-takeout(3, Z, []). 它返回Z = [3]

Now, takeout is called for the first time - takeout(3, Z, []). It returns Z = [3]

现在，我们要回过头来，其中perm([],[]).给我们W = [3]，(因为此时Y为[3])

Now, we are going back, where perm([],[]). gives us W = [3], (because Y was [3] at this point)

与上述takeout(2, Z, [3])和Z = [2, 3]相同.

再次perm([], []).和W = [2, 3].

和takeout(1, Z, [2, 3])，这为我们提供了第一个答案Z = [1, 2, 3]

And takeout(1, Z, [2, 3]), which gives us first answer Z = [1, 2, 3]

在这里，我不知道为什么程序没有结束，递归完成了，那么为什么takeout和perm又能正常工作?

Here I don't know why program don't end , recursion is done, so why takeout and perm are working again ?

此后，将takeout称为takeout(1, [2,3]).

现在可以使用takeout(X,[F |R],[F|S])而不是takeout(X,[X|R],R).了，这是我的第二个问题，为什么?

Which now works with takeout(X,[F |R],[F|S]) and not with takeout(X,[X|R],R). and that's my second question, why?

推荐答案

在Prolog中，谓词的行为与程序语言中的函数完全不同.调用 function 来执行任务，然后执行它，然后返回并返回一些值或执行了某些副作用，或者同时执行这两种操作.

In Prolog, a predicate's behavior is quite unlike that of a function in procedural languages. A function is called to perform a task, it executes, and then comes back returning some values or having performed some side effects, or both.

谓词定义了一种关系和/或一组事实，从而在其参数之间建立了逻辑联系.当在Prolog中对谓词进行查询时，Prolog会尝试查找参数变量的每个实例，以使该谓词成功(正确).

A predicate defines a relation and/or set of facts that establish a logical connection between it's arguments. When a query is made to a predicate in Prolog, Prolog will attempt to find every instantiation of the argument variables that will make that predicate succeed (be true).

在一个非常简单的情况下，我可能有以下事实:

In a very simple case, I might have the following facts:

likes(tom, mary).    % Tom likes Mary
likes(fred, mary).   % Fred likes Mary

在这里，我有一个谓词或事实likes，它定义了两个人之间的关系.我们将上述事实称为事实"，因为它们各自指定了具有完全实例化参数的精确，具体的关系.我可以进行如下查询以确定谁喜欢玛丽?:

Here I have one predicate or fact, likes, which defines a relation between two people. We call the above facts because they each specify a precise, concrete relation with fully instantiated arguments. I can make a query to determine Who likes Mary? as follows:

| ?- likes(Person, mary).

Person = tom ? ;

Person = fred

yes

该查询首先返回Person = tom，但表示一旦发现Person = tom满足查询，它便有更多选项可供检查.输入;告诉Prolog继续下一个解决方案(如果有)，并找到它:Person = fred.

The query first comes back with Person = tom but indicates it has more options to check once it has found that Person = tom satisfies the query. Entering ; tells Prolog to continue with the next solution (if there is one), and it finds it: Person = fred.

现在让我们考虑takeout/3.这是一个谓词，它定义了一组变量之间的关系.

Now let's consider takeout/3. This is a predicate which defines a relation between a set of variables.

1. takeout(X,[X|R],R).
2. takeout(X,[F|R],[F|S]) :- takeout(X,R,S).

1. takeout(X,[X|R],R).
2. takeout(X,[F|R],[F|S]) :- takeout(X,R,S).

takeout/3谓词具有两个用于该关系的谓词子句或规则.尝试阅读它们会很有帮助:

The takeout/3 predicate has two predicate clauses or rules for the relation. It's helpful to try to read them:

如果从[X|R]中取出X，就会得到
1. R.
如果从[F|R]中取出X，则得到
2. [F|S].如果从R中取出X，则得到S. li>

1. R is what you get if you take X out of [X|R].
2. [F|S] is what you get if you take X out of [F|R] if S is what you get when you take X out of R.

Prolog以析取方式查看多个子句.也就是说，如果任何一个规则都成立，则对谓词的查询或调用将成功.当对takeout/3进行查询时，Prolog将在查询中查找给定变量的实例化，这将使它成为真，并且它将尝试找到每个做到这一点的 实例化.换句话说，如果满足条件的方法不止一种，它将回溯，并尝试找到满足条件的变量实例.

Prolog looks at multiple clauses in a disjunctive way. That is, a query or call to the predicate will succeed if any one of the rules can hold true. When a query on takeout/3 is made, Prolog will look for instantiations of the given variables in the query which will make it true, and it will attempt to find every such instantiation that does so. In other words, if there's more than one way to satisfy the condition, it will backtrack and attempt to find those variables instantiations that do so.

考虑查询:

?- takeout(X, [1,2,3], R).

Prolog可以通过实例化X = 1和R = [2,3]将其与第一个谓词子句takeout(X, [X|R], R)匹配为takeout(1, [1,2,3], [2,3]).因此，此查询将成功，并显示以下结果:

Prolog is able to match this to the first predicate clause: takeout(X, [X|R], R) as takeout(1, [1,2,3], [2,3]) by instantiating X = 1 and R = [2,3]. So this query will succeed with the following result:

R = [2,3]
X = 1 ?

但是我们看到Prolog表示还有更多可供选择的选择.这是因为还有另一个子句:takeout(X,[F|R],[F|S])与查询takeout(X, [1,2,3], R)匹配.因此，Prolog 回溯并尝试匹配以下子句的第二个子句:

But we see that Prolog is indicating there are more options to explore. That's because there's another clause: takeout(X,[F|R],[F|S]) which matches the query, takeout(X, [1,2,3], R). Prolog therefore backtracks and attempts the second clause, which matches:

takeout(X, [1|[2,3]], [1|S]) :-    % F = 1, R = [2,3]
    takeout(X, [2,3], S).

然后，Prolog将遵循递归调用takeout(X, [2,3], S)，并且再次从第一个子句开始，并尝试将takeout(X, [2,3], S)与takeout(X, [X|R], R)匹配，该匹配以X = 2和S = [3]( takeout(2, [2|[3]], [3])..递归展开或返回(就像在任何语言中一样)，然后上一个调用头takeout(X, [1|[2,3]], [1|S])最终实例化为:takeout(1, [1|[2,3]], [1|[3]]).这样我们得到:

Prolog will then follow the recursive call takeout(X, [2,3], S) and start from the first clause again and attemp to match takeout(X, [2,3], S) with takeout(X, [X|R], R), which succeeds with X = 2 and S = [3] (takeout(2, [2|[3]], [3]).. The recursion unwinds or returns (as it would in any language), and the previous call head, takeout(X, [1|[2,3]], [1|S]) then ends up instantiating as: takeout(1, [1|[2,3]], [1|[3]]). So we get:

R = [2,3]
X = 1 ? ;

R = [1,3]    % that is, [1|[3]]
X = 2 ? 

以此类推.类似的行为适用于perm.在查询perm的上下文中，对takeout backtrack的调用会产生其他结果，因此perm会产生其他结果(因为它对takeout backtrack的调用，就像在查询takeout时所做的一样手).

---

如@false所示，谓词takeout/3在Prolog中作为标准谓词实现为select/3.

And so on. Similar behavior applies to perm. In the context of the query perm, the calls to takeout backtrack to produce additional results, so perm produces additional results (since its calls to takeout backtrack, just like they do when you query takeout by hand).

---

As noted by @false, the predicate takeout/3 is implemented as a standard predicate in Prolog as select/3.

这篇关于Prolog，置换代码理解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！