1

最近我开始研究 Prolog ，一旦我处理了它，我就有理解它的问题。

我正在研究列表，但我无法理解append/3应该合并两个列表的谓词如何工作。

book_append([], L, L). 
book_append([X|L1], L2, [X|L3]) :-
    book_append(L1, L2, L3).

确切地说，我不明白如何L2附加到主列表。我试着解释一下我到目前为止所理解的：

只有当第一个列表为空并且第二个和第三个将采用相同的值时，边界条件才会统一。这是对的吗？

第一个问题，也许这很愚蠢，当第一个列表为空时，两个列表必须统一，以便它们取相同的值。但它们应该是不同的，所以我会失去它们的价值之一。

在第二行中，第一个列表的头部被附加到第三个列表中并调用相同的函数。

我通常以这种方式使用此功能：book_append([1, 2, 3], [a, b, c], X).

第一行是假的，因为L1它不是空的。
而第二个应该是：

book_append([1|[2, 3], [a, b, c], [1|L3]) :-
    book_append([2, 3], [a, b, c], L3).

L3在第一次通话期间（我已经知道它是第三个列表的尾部）的价值是多少？是空的吗？还是一个未实例化的变量？或者它被实例化为L2？

4

4 回答 4

2

Prolog 的逻辑变量（logvars）本质上是命名指针，它只能被实例化/ “设置”（赋值）一次。每个 logvar 都可以处于“尚未设置”状态，或处于实例化/设置状态。

在没有发生回溯的情况下，永远无法更改绑定（在回溯时，可以撤消这种“指针设置” ，并且日志变量可以恢复到以前的未实例化状态，以后可能会再次实例化为其他一些值）。

当“设置”时，它可以指向一个原子值，如数字（5）、符号（'a'）等。或者它可以指向另一个 logvar（意思是，两者变得等价）。

或者它可以指向一个复合（类似struct或命名为 record的）值，就像f(a,B,c)其子实体本身可以完全实例化（“ground”）值一样，或者它们可以是/包含尚未实例化的 logvar 本身.

现在， Prolog 中的列表以复合词的形式出现在（一个点）的名称（即functor）下。'.'列表[A|B]实际上是'.'(A,B)具有两个子实体的复合术语，即“参数”和。AB

因此，当我们“设置”时A = [1|B]，我们将A“指向”计算机内存中的实际真正结构，用名称 ( functor )标记'.'，并带有两个字段。第一个字段包含一个数字1，第二个字段是一个名为 的 logvar B，尚未实例化为任何内容。或者在 C++ 术语中，它是一个未初始化的指针。

并且该指针是（通过引用）传递给嵌套递归调用的内容book_append。正是那个指针被设置在那里。这就是“指向”的“列表节点”的第二个字段A现在指向的内容。

所以递归调用不需要将任何东西“返回”给 Prolog 中的“调用者”。它们只是实例化在它们之上设置的结构的一部分，越来越充分地“充实”这些结构。

但是如果我们在列表的顶部节点上有一个句柄，我们就可以访问它的所有子实体，因为它们已经完全实例化了。

所有这些冗长的文本在 C++ 术语中意味着，它append/3通过沿着它的第一个列表进行操作，同时将列表节点复制到一边，当它到达第一个列表的末尾时，它设置最后复制的列表节点的下一个指针- 指向调用它的第二个列表的开头。这意味着它是尾递归模 cons。

于 2012-08-08T08:41:15.607 回答
2

首先，请参阅@Will Ness的这个答案和这个答案（我的）。它应该已经回答了你的问题。

然后让我们（快速）解决您的具体问题：

第一个问题，也许这很愚蠢，当第一个列表为空时，两个列表必须统一，以便它们取相同的值。但它们应该是不同的，所以我会失去它们的价值之一。

您必须考虑 Prolog 中的值如何变化。

基本上价值观通过统一而改变。并且只改变一次。这意味着它A可以成为[5|B]然后将完成改变，并且将适用于您的所有程序。B最终可能会改变，因此A也会以某种方式改变，但绑定只发生一次，如前所述。

所以在这里，你不能“失去”价值，因为你不能重新绑定任何东西。统一将尽最大努力匹配List2并将Result自由变量绑定到正确的事物。这样，如果Result在您的示例中是一个自由变量，那么它将被绑定到List2. 如果两个变量都已经绑定，统一可以做的唯一事情就是测试它们是否绑定到相同的值。

对于您的第二个问题，请特别查看我的答案，该答案将详细说明绑定以获得更清晰的想法。

于 2012-08-08T07:45:04.013 回答
0

第一行仅适用于第一个列表为空且第二个和第三个列表相同（或者一个是变量等，然后可以采用另一个的值）的情况。所以你不会丢失信息。

为了理解第二行，请记住（您演示使用它的方式）第三个参数是结果（同样，这只是一种可能的用法）。因此，当以这种方式使用时，第二行表示它将返回 [X|L3]，并且正文中提到了 L3（我实际上不知道正确的术语）——在哪里？作为新 book_append 调用的结果。所以 L3 将是第一个列表没有头的结果附加到第二个列表。

于 2012-08-08T04:29:53.777 回答
0

数据库：

book_append([], L, L).
book_append([X|L1], L2, [X|L3]) :- book_append(L1, L2, L3).

调用时：

?- book_append([1, 2, 3], [a, b, c], A).

编译器将查看数据库以找到统一。因为第一行不能统一（[1, 2, 3]不能和[]统一）所以使用第二行，会变成：book_append([1|[2, 3], [a, b, c], [1|L3]) :- book_append([2, 3], [a, b, c], L3)。只有当“:-”右边的条件也有一个统一时，统一才会发生。因此它将再次查看数据库以找到 book_append([2, 3], [a, b, c], L3) 等的统一。

统一应该如下所示（= 是统一的符号）：

book_append([1, 2, 3], [a, b, c], A) = 
    book_append([1|[2,3]], [a,b,c], [1|L3]) =
    book_append([2|[3]],   [a,b,c], [2|L3]) =
    book_append([3|[],     [a,b,c], [3|L3]] =
    book_append([],        [a,b,c], [a,b,c])  % book_append([], L, L).
=> A = 1|2|3|[a,b,c]

如果我错了，请纠正我，我刚开始为一个项目学习这个。

于 2016-05-12T13:56:28.787 回答