2

我正在学习如何在 Prolog 中编程，我找到了下一个定义自然数及其总和的程序：

sum( succ( X ), Y, succ( Z )) :- sum( X, Y, Z ).
sum( 0, X, X ).
?- sum( succ( succ(0)), succ( succ( succ(0))), Answer ).
Answer = succ( succ( succ( succ( succ(0)))))

（在这里找到）

问题是我正在努力解决这个程序的执行流程。说实话我不知道它是做什么的。Prolog 如何计算出答案的价值？Prolog 遵循哪些步骤来找到答案的值？

提前致谢。

4

3 回答 3

2

它有助于理解 Prolog 在找出现有谓词或设计新谓词时的操作方式。当您进行如下查询时：

sum( succ(succ(0)), succ(succ(succ(0))), Answer ).

Prolog 将查找匹配的事实和规则sum(_, _, _)( sum/3) 并选择第一个匹配的。现行规则如下：

(1) sum( succ(X), Y, succ(Z) ) :- sum( X, Y, Z ).
(2) sum( 0, X, X ).

如果您查看查询，它显然与规则 #1 的模式相匹配。请记住，在 Prolog 中，变量可以实例化为任何类型的术语，并且同名的变量是统一的（实例化为相同的值）。当 Prolog 将规则 #1 的“头部”与查询统一时，它通过统一变量来实现，如下所示：

    X = succ(0)
    Y = succ(succ(succ(0)))
(A) Answer = succ(Z)

请注意，即使尚未绑定（分配具体值） ，它Answer也具有该值。现在我们遵循将查询的规则，这将是查询：succ(Z)Zsum(X, Y, Z)

sum( succ(0), succ(succ(succ(0))), Z )
       |        |                  |
       X        Y                  Z

Prolog 现在将再次从顶部开始，因为这是对sum/3. 就像第一次一样，它使用以下统一匹配规则 #1：

    X = 0
    Y = succ(succ(succ(0)))
(B) Z = succ(Z')

我在Z'上面使用它来将它与 中的其他变量区分开来Z，sum(succ(0), succ(succ(succ(0))), Z)因为它Z与头部中使用的变量不同sum(..., succ(Z))。这就像如果您在 C 中声明了一个函数，int f(x) { return 2*x; }并且您从某个地方使用另一个局部变量调用它x，该名称x在两个不同的地方使用并代表两个不同的变量）。

然后我们可以再次遵循下一个递归查询sum(X, Y, Z')，它变成：

sum( 0, succ(succ(succ(0))), Z' )
     |    |                  |
     X    Y                  Z'

此递归查询与规则 #1 不匹配，因为第一个参数0不匹配succ(X)。但是，它符合规则 #2：

    0 = 0
    X = succ(succ(succ(0)))
(C) X = Z'

现在X = succ(succ(succ(0)))如此Z' = succ(succ(succ(0)))。由于此规则中没有更多查询，因此它最终成功返回到查询的位置。回到上面的（B）：

Z = succ(Z') = succ(succ(succ(succ(0))))

并将其返回到（A）：

Answer = succ(Z) = succ(succ(succ(succ(succ(0)))))

你有它。使用trace@CapelliC 提到的工具，您可以看到这些连续步骤发生在 Prolog 解释器中并遵循变量的实例化。

于 2014-04-22T11:09:33.987 回答
2

Prolog 的“评估”通过将给定的查询与程序规则的头匹配，并在匹配替换下继续匹配规则的主体。当一个规则被选中时，它的变量会被统一重命名，以保证唯一性：

(1) sum( succ( X ), Y, succ( Z )) :- sum( X, Y, Z )。
（2）总和（0，X，X）。

    ?- sum( succ( succ(0)), succ( succ( succ(0))), 答案)。
(1) -> sum( succ( X1 ), Y1 , succ( Z1 )) :- sum( X1, Y1, Z1 )。

        %% X1 = succ(0), Y1 = succ( succ( succ(0))), succ(Z1) = 答案。%%

    -？总和（X1，Y1，Z1）。
    -？总和（成功（0），Y1，Z1）。
(1) -> sum( succ( X2 ), Y2, succ( Z2 )) :- sum( X2, Y2, Z2 )。

        %% X2 = 0，Y2 = Y1，成功（Z2）= Z1。%%

    -？总和（X2，Y2，Z2）。
    -？总和（0，Y2，Z2）。
(2) -> 总和(0, X3, X3)。     ％％ 完毕。%%

        %% X3 = Y2，X3 = Z2。%%

从这里，Answer = succ(Z1) = succ( succ(Z2)) = succ( succ(X3)) = succ( succ( Y2)) = succ( succ (Y1)) = succ( succ( succ( succ( succ(0)))))。

于 2014-04-23T00:23:03.350 回答
1

对于这样一个简单的程序，trace/0 是要走的路。leash /1 （这对新手来说并不完全明显）允许控制调试器接口：

21 ?- leash(-all),trace.
true.

[trace] 22 ?- sum( succ( succ(0)), succ( succ( succ(0))), Answer ).
   Call: (6) sum(succ(succ(0)), succ(succ(succ(0))), _G710)
   Call: (7) sum(succ(0), succ(succ(succ(0))), _G789)
   Call: (8) sum(0, succ(succ(succ(0))), _G791)
   Exit: (8) sum(0, succ(succ(succ(0))), succ(succ(succ(0))))
   Exit: (7) sum(succ(0), succ(succ(succ(0))), succ(succ(succ(succ(0)))))
   Exit: (6) sum(succ(succ(0)), succ(succ(succ(0))), succ(succ(succ(succ(succ(0))))))
Answer = succ(succ(succ(succ(succ(0))))).

您可以看到您的程序对第一个参数进行有界递归搜索，将其与第一个子句（标记为 6,7 的调用）或第二个子句（标记为 8 的调用）统一起来。

于 2014-04-22T08:57:44.507 回答