title: Recursive addition in Prolog
body: <p><strong>Knowledge Base</strong></p>
  
  <pre><code>add(0,Y,Y). // clause 1
  add(succ(X),Y,succ(Z)) :- add(X,Y,Z). // clause 2
  </code></pre>
  
  <p><strong>Query</strong></p>
  
  <pre><code>add(succ(succ(succ(0))), succ(succ(0)), R)
  </code></pre>
  
  <p><strong>Trace</strong></p>
  
  <pre><code>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))))))
  </code></pre>
  
  <p><strong>My Question</strong></p>
  
  <ul>
  <li>I see how the recursive call in clause 2 strips the outermost succ()
  at each call for argument 1.</li>
  <li>I see how it adds an outer succ() to argument 3 at each call.</li>
  <li>I see when the 1st argument as a result of these recursive calls
  reaches 0.  At that point, I see how the 1st clause copies the 2nd
  argument to the 3rd argument.</li>
  </ul>
  
  <p><em>This is where I get confused.</em></p>
  
  <ol>
  <li><p>Once the 1st clause is executed, does the 2nd clause automatically
  get executed as well, then adding succ() to the first argument?</p></li>
  <li><p>Also, how does the program terminate, and why doesn't it just keep
  adding succ() to the first and 3rd arguments infinitely?</p></li>
  </ol>
  
  <blockquote>
    <p><strong>Explanation from LearnPrologNow.com (which I don't understand)</strong></p>
    
    <p>Let’s go step by step through the way Prolog processes this query. The
    trace and search tree for the query are given below.</p>
    
    <p>The first argument is not 0 , which means that only the second clause
    for add/3 can be used. This leads to a recursive call of add/3 . The
    outermost succ functor is stripped off the first argument of the
    original query, and the result becomes the first argument of the
    recursive query. The second argument is passed on unchanged to the
    recursive query, and the third argument of the recursive query is a
    variable, the internal variable _G648 in the trace given below. Note
    that _G648 is not instantiated yet. However it shares values with R
    (the variable that we used as the third argument in the original
    query) because R was instantiated to succ(_G648) when the query was
    unified with the head of the second clause. But that means that R is
    not a completely uninstantiated variable anymore. It is now a complex
    term, that has a (uninstantiated) variable as its argument.</p>
    
    <p>The next two steps are essentially the same. With every step the first
    argument becomes one layer of succ smaller; both the trace and the
    search tree given below show this nicely. At the same time, a succ
    functor is added to R at every step, but always leaving the innermost
    variable uninstantiated. After the first recursive call R is
    succ(_G648) . After the second recursive call, _G648 is instantiated
    with succ(_G650) , so that R is succ(succ(_G650) . After the third
    recursive call, _G650 is instantiated with succ(_G652) and R therefore
    becomes succ(succ(succ(_G652))) . The search tree shows this step by
    step instantiation.</p>
    
    <p>At this stage all succ functors have been stripped off the first
    argument and we can apply the base clause. The third argument is
    equated with the second argument, so the ‘hole’ (the uninstantiated
    variable) in the complex term R is finally filled, and we are through.</p>
  </blockquote>