誰もがこの再帰的プログラムでプロローグのステップを説明できますか？

Question

私は最近プロローグの学習を始めましたが、再帰的なルールでは苦労しています。私は単純なルールを理解するが、私は、リスト内のすべての要素の合計を与えるプログラムの発見この例で問題を抱えている：私はこれをトレース場合

addup([], 0). 

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

は今、私は次のGET：

[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を作る。それは3番目のTotalOfRest（私はそれを_L3と呼んでいます）を0に等しくします。 しかし今は何ですか？プロローグは、L2が7 + 0に等しいというステップをどのようにしますか？私はプロローグがバックトラックを開始することを理解しますが、その結論に達するものと一致するのは何ですか？合計は今7ですか？または、TotalOfRestのような異なる値を持つ3つの異なる合計がありますか？ RestofListは[]と同じですが、FirstNumberはまだ7ですか？

基本的に：プロローグはL3を最終的な結論までどのようにして得たのでしょうか？

私は非常に新しいので、誰かが私のためにそれを説明することができます本当にゆっくりと、私はそんなに感謝します！あなたの再帰呼び出しは、新しい変数を導入し

Answer 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 is FirstNumber + TotalOfRest.。これらのすべてがローカル変数であることを覚えておいてください（これは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

。