5

有人可以向我解释为什么这个序言查询会这样工作。定义是：

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

鉴于这种：

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

这是查询的跟踪：

Call:  (6)  add(succ(succ(succ(0))),  succ(succ(0)),  R) 

Call:  (7)  add(succ(succ(0)),  succ(succ(0)),  _G648) 

Call:  (8)  add(succ(0),  succ(succ(0)),  _G650) 

Call:  (9)  add(0,  succ(succ(0)),  _G652) 

Exit:  (9)  add(0,  succ(succ(0)),  succ(succ(0))) 

Exit:  (8)  add(succ(0),  succ(succ(0)),  succ(succ(succ(0)))) 

Exit:  (7)  add(succ(succ(0)),  succ(succ(0)), 
                                              succ(succ(succ(succ(0))))) 

Exit:  (6)  add(succ(succ(succ(0))),  succ(succ(0)), 
                                                succ(succ(succ(succ(succ(0))))))

那个教程最让我困惑的部分是，在第一个参数中，成功被剥离了，并且它递归了。虽然在递归时，R 获得了成功......如何？！另外，第一个出口 (9) 处的零是从哪里来的？我是序言的新手，我正在努力理解家庭作业的语言。非常感谢任何帮助。

注意：对于任何感兴趣的人，本教程的链接是http://www.learnprolognow.org/lpnpage.php?pagetype=html&pageid=lpn-htmlse9

4

3 回答 3

4

您看到call并且exit是verbs解释器为解决您提出的查询而采取的操作。然后，跟踪会显示已完成的实际工作的详细信息，并让您从历史角度查看它。

当 Prolog 必须选择一个规则（a call）时，它使用name你给它的（所谓的functor），并尝试对unify规则头部的每个参数。然后我们通常说，Prolog 也考虑了arity，即参数的数量，用于选择。

Unification试图“使等于”两个术语，而值得注意的结果就是所谓bindings的变量。您已经知道变量是那些以Uppercase. 此类名称标识规则中未指定的值，即placeholders用于参数。为了避免混淆，当 Prolog 显示跟踪时，变量被重命名以便我们可以识别它们，因为相关的细节是identities在证明期间建立的或绑定。

然后你会_G648在跟踪中看到这样的符号。它们停留在被调用目标的尚未被实例化的参数上，即R和Z。R 是唯一的（仅在顶级调用中出现），因此此 Prolog 友好地保留用户友好的名称，但 Z 来自程序，可能多次出现，然后被重命名。

回答这个问题

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

Prolog 首次尝试匹配

add(0,Y,Y).

并失败，因为 succ(succ(succ(0)) 不能等于 0。然后尝试

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

因此必须解决这些绑定（在左侧调用者的术语）：

succ(succ(succ(0))) = succ(X)
succ(succ(0)) = Y
R = Z

你可以看到为什么 X 变成succ(succ(0))，我们有一个新的目标要证明，即add(X,Y,Z)带有刚刚建立的绑定的规则体：

添加（成功（成功（0）），成功（成功（0）），_G648）

依此类推...直到 X 变为0并且目标匹配

add(0,Y,Y).

Z那么Y就变成了succ(succ(0))，值得注意的是在调用规则中也给了一个值。

高温高压

于 2012-04-25T06:37:18.723 回答
1

“第一个出口（9）处的零从哪里来？”

该调用add(0, succ(succ(0)), _G652)与第一个子句统一，即如果 的第一个参数add为零，则第二个和第三个相同。在这种特殊情况下，变量_G652变为succ(succ(0))。

“虽然在递归过程中，R 获得了成功……如何？！”

这是应用第二条的结果。该子句（粗略地）表明您首先succ从第一个参数中剥离，然后add递归调用，最后，向succ从该递归调用返回的第三个参数添加另一个“层”。

谓词add只不过是 Peano 算术中加法的直接实现：http ://en.wikipedia.org/wiki/Peano_axioms#Addition

于 2012-04-25T06:14:16.877 回答
0

带有更多注释的（希望）更清晰的跟踪是：

 (6) Call:  add(succ(succ(succ(0))),  succ(succ(0)),  R)          % R     = succ(_G648)
      (7) Call:  add(succ(succ(0)),  succ(succ(0)),  _G648)       % _G648 = succ(_G650) 
           (8) Call:  add(succ(0),  succ(succ(0)),  _G650)        % _G650 = succ(_G652) 
                (9) Call:  add(0,  succ(succ(0)),  _G652)         % _G652 = succ(succ(0))
                (9) Exit:  add(0,  succ(succ(0)),  succ(succ(0)))       
           (8) Exit:  add(succ(0),  succ(succ(0)),  succ(succ(succ(0)))) 
      (7) Exit:  add(succ(succ(0)),  succ(succ(0)), succ(succ(succ(succ(0))))) 
 (6) Exit:  add(succ(succ(succ(0))),  succ(succ(0)), succ(succ(succ(succ(succ(0))))))

如您所见，四个出口是多余的，最终答案在; (9) Exit那时只有一个出口就足够了：

     %     R = succ(_G648)
     %              _G648 = succ(_G650) 
     %                           _G650 = succ(_G652) 
     %                                        _G652 = succ(succ(0))
     % thus,
     %     R = succ(        succ(        succ(        succ(succ(0)) )))

这确实是尾调用优化下发生的情况，因为谓词定义确实是尾递归的，并且结果R是以自上而下的方式构建的，“洞”逐渐被逻辑变量的实例化填充。所以succ( _ )不是在递归调用之后添加的，而是在它之前建立的。这也是尾递归取模 cons 优化的本质。

于 2018-05-31T13:19:48.103 回答