Search trees in Prolog:


You saw some examples in class (and on the webpage).

Some explanations:

- Keeping track of variables from different clauses by giving them a
unique name.  You do this by suffixing the variables with a new number
each time I match a new clause.  All the variables in a clause have
the same suffix.  You can do without subscripting the variables if
there is no danger of confusion.

- Backtracking over links when you either fail or want to generate
more answers.  When you fail (or succeed but then use ";"), you only
backtrack back over the most recent unification and try again.  (Of
course, you might then fail again, or succeed but want more
solutions, so that you keep backtracking over and over.)

- Links are labeled with unifications.  If you say on a link X=Y, it
doesn't really matter which name you use if you have a subgoal in the
next node that uses X or Y -- since the variables are unified, they
have the same value (or future value, if they aren't instantiated
yet).  However, you will see in the example trees that it *does*
matter to us as humans, as it can make it easier or harder to follow
the logic of the program depending on the variable/value used.


++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Tracing:

Using "trace" in Prolog corresponds to the search tree. Generally, the
trace has the following properties:

-- A "Call" action corresponds to creation of a search node (or
   entering the node from its parent) for the goal which is on the top
   of the stack. 

-- A "Redo" action correspond to re-entering the search node from
   its child, redo-ing the match that was made to cross the link from 
   parent to child.

-- An "Exit" action correspond to successfully matching the top
   subgoal at the node and creating a new link in the tree, which is
   annotated with any unifications made in making the match.

-- A "Fail" action correspond to an inability to match the top
   subgoal of the node.

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++