Recursive Decision Tree In Problems

Question

So I am trying to draw the decision of tree of 2 Prolog problems, one that uses the accumulator and other that doesn't. Here are my problems and the solutions I did, respectively:

length([H|T],N) :- length(T,N1), N is N1+1.
length([ ],0). 
Goal: ?: length([1,2,3],N) 

Second one with accumulator:

length_acc(L,N) :- len_acc(L,0,N).
len_acc([H|T], A, N) :- A1 is A+1, len_acc(T, A1, N).
len_acc([], A, A). 
Goal: ?-length_acc([1,2], N).

Are the decision trees correctly drawn? Or have I made a mistake? Whats the correct way to draw these kind of recursive decision tree?

Thanks.

Answer 1

The tree you are referring to is usually called a search-tree aka SLD-tree, not to be confused with a proof-tree.

Both the problems you have outlined are the most simple cases of search-trees:

• there is only one solution
• the query does not fail
• each step in the search can only match a single clause (empty list vs non-empty list)

These three characteristics imply that there will only be a single branch in the SLD tree.

You'll get the following search-trees:

Note that for it to be a correct search-tree, at most one goal is resolved in each step, which makes search-trees very large... therefore it's common that people make simplified trees where multiple goals can be resolved in each step, which arguably are not true search-trees but illustrates the search in a more succint way.

Edges in the tree are labeled with substitutions that are applied to the variables as part of the unification algorithm.

Search-trees correspond closely to traces, and you can usually do a straight translation from a trace of your program to a search tree.

I advise you to study search-trees for queries that have multiple answers and branches that can fail, which gives more interesting trees with multiple branches. An example from The Art of Prolog by Sterling, Shapiro:

Program:

father(abraham, isaac).        male(isaac)
father(haran, lot).            male(lot).
father(haran, milcah).         female(milcah).
father(haran, yiscah).         female(yiscah).

son(X,Y):- father(Y,X), male(X).
daughter(X,Y):- father(Y,X), female(X).

Query:

?: son(S, haran) 

Search-tree:

Answer 2

A nice way to understand something is to re-implement it yourself.

It's especially nice to implement Prolog when you already have Prolog to implement it with. :)

program( patriarchs, P ) :- 
  P = [ % [son(S, haran)] ,        % Resolvent
        [father(abraham, isaac)]   % Clauses...
      , [father(haran, lot)]       %   [Head, Body...]
      , [father(haran, milcah)]       
      , [father(haran, yiscah)]
      , [male(isaac)]
      , [male(lot)]
      , [female(milcah)]
      , [female(yiscah)]
      , [son(X,Y), father(Y,X), male(X)]
      , [daughter(X,Y), father(Y,X), female(X)]
      ].

solve( Program ):- 
   Program = [[] | _].   % empty resolvent -- success

solve( [[Goal |                   Res] |      Clauses] ) :-
   member(    Rule,                           Clauses),                      
   copy_term( Rule, [Head | Body]),                 % rename vars
   Goal  =           Head,                          % unify head
   append(                  Body, Res, Res2 ),      % replace goal
   solve(                             [Res2 | Clauses] ).

query( What, Query ):-  % Query is a list of Goals to Solve
    program( What, Program),
    solve( [ Query | Program ] ).

Testing,

23 ?- query( patriarchs, [son(S, haran)] ).
S = lot ;
false.

Now the above solve/1 can be augmented to record the record of successful instantiations of Goal making the unifications Goal = Head possible.