有人能解释一下prolog使用这个递归程序所做的步骤吗？

提问者：小点点

有人能解释一下prolog使用这个递归程序所做的步骤吗？

我最近开始学习prolog，但我很难使用递归规则。我理解简单的规则，但我在这个例子中遇到了麻烦，我发现一个程序给出了列表中所有元素的总和：

addup([], 0).

addup([FirstNumber | RestOfList], Total) :-
    addup(RestOfList, TotalOfRest),   
    Total is FirstNumber + TotalOfRest.

现在，如果我跟踪它，我得到以下内容：

[trace]  ?- addup([3, 5, 7], Total).
   Call: (7) addup([3, 5, 7], _G322)
   Call: (8) addup([5, 7], _L1)
   Call: (9) addup([7], _L2)
   Call: (10) addup([], _L3)
   Exit: (10) addup([], 0)    % I understand what it does till here
^  Call: (10) _L2 is 7+0
^  Exit: (10) 7 is 7+0
   Exit: (9) addup([7], 7)
^  Call: (9) _L1 is 5+7
^  Exit: (9) 12 is 5+7
   Exit: (8) addup([5, 7], 12)
^  Call: (8) _G322 is 3+12
^  Exit: (8) 15 is 3+12
   Exit: (7) addup([3, 5, 7], 15)
Total = 15.

我理解最初的几个步骤；它不断削减并创建新的TotalOfRest，直到原始列表为空并与第一个事实匹配。这使得第三个TotalOfRest（我称之为_L3）等于0。但是现在呢？prolog如何使L2等于7 0的步骤。我知道prolog开始回溯，但是什么与得出这个结论相匹配？Total现在是7吗？或者有三个不同的Total具有不同的值，就像TotalOfRest一样？RestofList仍然等于[]，FirstNumber仍然是7吗？

所以基本上：prolog是如何从弄清楚L3到最终结论的？

我对这个很陌生，所以如果有人能慢慢为我解释，我会非常感激！

共1个答案

匿名用户

请注意，您的递归调用引入了一个新变量：

addup([], 0).
addup([FirstNumber | RestOfList], Total) :-
    addup(RestOfList, TotalOfRest),   
    Total is FirstNumber + TotalOfRest.

在每个递归级别，都会创建一个新的TotalOfRest变量。请注意，上层递归级别的TotalRest与递归中更深的级别不同。

trace使用变量的名称可能更方便：

[trace]  ?- addup([3, 5, 7], Total).
   Call: (7) addup([3, 5, 7], _Total)
   Call: (8) addup([5, 7], _TotalOfRest1)
   Call: (9) addup([7], _TotalOfRest2)
   Call: (10) addup([], _TotalOfRest3)
   Exit: (10) addup([], 0)
^  Call: (10) _TotalOfRest2 is 7+0
^  Exit: (10) 7 is 7+0
   Exit: (9) addup([7], 7)
^  Call: (9) _TotalOfRest1 is 5+7
^  Exit: (9) 12 is 5+7
   Exit: (8) addup([5, 7], 12)
^  Call: (8) _Total is 3+12
^  Exit: (8) 15 is 3+12
   Exit: (7) addup([3, 5, 7], 15)
Total = 15.

因此，如果执行递归调用，则会创建一个新的变量_TotalOfRest1。调用是递归完成的，直到_TotalOfRest3。现在在该级别_TotalOfRest3=0设置为0。但是递归中仍然有命令需要解决：Total是FirstNumber TotalOfRest。。请注意，所有这些Total都是局部变量（这也适用于TotalOfRest和FirstNumber）。所以在每个级别都解决了这个问题。请注意，例如递归级别2的Total实际上是调用者的_TotalOfRest2。

所以递归看起来像：

addup([3, 5, 7], Total) :-
    % FirstNumber = 3
    % RestOfList = [5, 7]
    % Total = Total
    addup([5,7], _TotalOfRest1) :-
         % FirstNumber = 5
         % RestOfList = [7]
         % Total = _TotalOfRest1
         addup([7], _TotalOfRest2) :-
             % FirstNumber = 7
             % RestOfList = []
             % Total = _TotalOfRest2
             addup([],_TotalOfRest3),
             % resolved to _TotalOfRest3 = 0
             Total is 7 + 0.
             % resolved to Total = 7
         % resolved to _TotalOfRest2 = 7
         Total is 5 + 7.
         % resolved to Total = 12
     % resolved to _TotalOfRest1 = 12
     Total is 3 + 12.
     % resolved to Total = 15
% resolved tot Total = 15

代码部分以粗体书写，您会看到在每个级别都有局部变量被接地并传达回外部范围。