4

如果可能的话，我希望有人解释这个过程（来自“现在学习序言”一书）。它需要两个数字并将它们相加。

add(0,Y,Y).  
add(s(X),Y,s(Z)) :- add(X,Y,Z).

原则上我理解，但我有一些问题。假设我发出查询

?- add(s(s(0)), s(0), R).

结果是：

R = s(s(s(0))).

第 1 步是与规则 2 的匹配。现在 X 变为 s(0)，Y 仍然是 s(0)。但是 Z（根据本书）变为 s(_G648)，或 s()，其中包含未实例化的变量。为什么是这样？

在最后一步，匹配第一条规则，结束递归。在这里，Y 的内容以某种方式最终出现在 Z 的未实例化部分中！非常混乱，我需要一个简单的英文解释。

4

3 回答 3

2

第一个前提：

  • 我们已经s(X)定义为Xs(X) = X+1
  • _G### 表示法用于跟踪用于递归的内部变量

让我们首先看一下我觉得更直观的后继加法的另一个定义：

add(0,Y,Y).
add(s(A),B,C) :- add(A,s(B),C).

这基本上是相同的，但递归更容易看到：

我们问

add(s(s(0)),s(0),R).

现在在第一步序言中说这相当于

add(s(0),s(s(0)),R)

因为我们有add(s(A),B,C) :- add(A,s(B),C)，如果我们看问题 A = s(0) 和 B=s(0)。但这仍然没有终止，所以我们必须重新应用 A=0 和 B=s(s(0)) 的等价性，所以它变成

add(0,s(s(s(0))),R)

其中，鉴于add(0,Y,Y).这意味着

R = s(s(s(0)))

您对 add 的定义基本相同，但有两个递归：

首先它将第一个参数运行到 0，所以它归结为 add(0,Y,Y)：

add(s(s(0)),s(0),R)

X=s(0), Y = s(0) 和 s(Z) = R 和 Z = _G001

add(s(0),s(0),_G001)

X = 0，Y=s(0) 和 s(s(Z)) = s(G_001) = R 和 Z = _G002

add(0,s(0),_G002)

所以现在它知道 _G002 是定义 add(0,Y,Y) 的 s(0) 但必须追溯它的步骤所以 _G001 是 s(_G002) 并且 R 是 s(_G001) 是 s(s(_G002) ) 是 s(s(s(0)))。

所以关键是为了得到定义 add(0,Y,Y) 序言必须为第一次递归引入内部变量，然后在第二次递归中评估 R。

于 2013-01-30T07:56:38.930 回答
1

如果您想了解 Prolog 程序的含义，您可能首先关注关系描述的内容。然后你可能想了解它的终止属性。

如果您按照您的问题所暗示的那样深入了解具体执行的细节，您很快就会迷失在众多细节中。毕竟，Prolog 有两种不同的交错控制流程（AND 和 OR 控制），此外它还具有包含参数传递、分配、比较和方程求解的统一性。

简介：虽然计算机可以毫不费力地执行具体的查询以获取无数的推论，但在浏览完这些推论之后你会感到疲倦。你不能在这方面打败电脑。幸运的是，有更好的方法来理解程序。

对于含义，先看规则。上面写着：

add(s(X),Y,s(Z)) :- add(X,Y,Z).

看到:-中间了吗？它是用来象征箭头的。箭头从右到左指向有点不寻常。在非正式写作中，您会从左到右书写。阅读如下：

前提是，add(X,Y,Z)是真的，那么也是add(s(X),Y,s(Z))真的。

所以我们假设我们已经有了一些add(X,Y,Z)意义“X+Y=Z”。鉴于此，我们可以得出结论，“(X+1)+Y=(Z+1)”也成立。

之后，您可能有兴趣了解它的终止属性。让我说得非常简短：要理解它，只要看一下规则就足够了：第二个论点只是进一步阐述。因此：第二个参数不影响终止。第一个和第三个参数看起来都一样。因此：它们都以相同的方式影响终止！事实上， add/3 终止，如果第一个或第三个参数不会与s(_).

的其他答案中找到有关它的更多信息，例如：

Prolog 后继符号产生不完整的结果和无限循环

但现在要回答你的问题，因为add(s(s(0)), s(0), R). 我只看第一个论点：是的！这将终止。而已。

于 2013-01-30T13:32:05.630 回答
0

让我们将问题分为三个部分：关于变量实例化的问题和我在该示例的变体中使用的累加器模式：

add(0,Y,Y).                    
add(s(X),Y,Z):-add(X,s(Y),Z).

以及关于您使用替换组合的示例的评论。

为了查看哪个规则（即 Horn 子句）匹配（其头部统一），Prolog 应用的是统一算法，它特别告诉我，如果我有一个变量，比如说 X 和一个函子，即 f(Y ）这两个术语统一（关于发生检查的一小部分...检查但没关系atm）因此有一个替代项可以让您将一个转换为另一个。

当您的第二条规则被调用时，R 确实统一为 s(Z)。不要被 Prolog 赋予新的、未实例化的变量的内部表示吓到，它只是一个变量名（因为它以 '_' 开头），它代表一个代码（Prolog 必须有一种方法来表示不断新生成的变量和所以 _G648、_G649、_G650 等等）。当您调用 Prolog 过程时，您传递的未实例化的参数（在这种情况下为 R）用于包含过程完成执行时的结果，并且它将包含结果，因为在过程中的某个时刻调用它将被实例化（总是通过统一）。如果在某些时候你有一个 var，即 K 被实例化为 s(H)（或者 s(_G567)，如果你愿意的话），

累加器模式取自函数式编程，简而言之，它是一种拥有变量的方法，即累加器（在我的例子中是 Y 本身），它有责任在某些过程调用之间进行部分计算。该模式依赖于递归，大致具有以下形式：

  • 递归的基本步骤（我的第一条规则，即）总是说，由于您已经到达计算的结尾，您可以将部分结果（现在是总计）从累加器变量复制到输出变量（这是其中的步骤，通过统一你的输出变量被实例化！）
  • 递归步骤告诉如何创建部分结果以及如何将其存储在累加器变量中（在我的情况下，我“增加”Y）。请注意，在递归步骤中，输出变量永远不会改变。

最后，关于您的示例，它遵循另一种模式，即替换的组合，我认为通过统一考虑累加器和实例化，您可以更好地理解。

  • 它的基本步骤与累加器模式相同，但 Y 在递归步骤中永远不会改变，而 Z 会改变
  • 它用于通过在到达基本步骤并且每个过程调用结束后在每个递归调用结束时部分实例化所有计算来将 Z 中的变量与 Y 统一。因此，在第一次调用结束时，Z 中的内部自由 var 已被 Y 中的值多次统一替换。请注意下面的代码，在您到达底部调用后，过程调用堆栈开始弹出并且您的部分vars (S1, S2, S3 for semplicity) 得到统一，直到 R 被完全实例化

这是堆栈跟踪：

add(s(s(s(0))),s(0),S1).          ^ S1=s(S2)=s(s(s(s(0))))
add(  s(s(0)) ,s(0),S2).          | S2=s(S3)=s(s(s(0)))
add(    s(0)  ,s(0),S3).          | S3=s(S4)=s(s(0))
add(      0   ,s(0),S4).          | S4=s(0)
add(      0   ,s(0),s(0)).  ______|
于 2013-01-30T07:57:05.357 回答