Examples

• Q : test(a, X) = test( Y, b)
  A : X = b, Y = a
  (this is a unifier (substitution of variables)
• Q : test(a, X)
  = test(Y, b)
  A : no
• Q : test(a,X) = test(Y, f(Z))
  A : X = f(Z), Y = a
• Q : X = f(X)
  A : error - term too deep
  a variable being instantiated by a compound term containing its argument

If matching does not succeed, Prolog backtracks, but if successfully done, it produces the most general instantiation of variables

Prolog works by defining the problem in a declarative way - this is easier for us, as it more closely resembles our method of thinking, however, Prolog solves a problem using the procedural style

nice :- 
 warm.
nice :-
 sunny,
 not_windy.

warm :-
 temperature( T),
 T > 20.

not_windy :-
 wind_speed( S),
 S > 5.

sunny.
temperature(15).
wind_speed( 3).

To prove that it is nice, it must first be proved that it is sunny and then that it is not windy
or
To satisfy the goal nice, first satisfy the goal sunny, and then not_windy - Procedural meaning.

• Prolog tries to match - done by instantiating a variable
• Backtracking ensures that if a solution exists to a goal, it is found, and if more than one solution exists then they are all found.
• Consider the hifi example to see how multiple results were obtained

1. The query (question) is a conjunction of atoms or compound terms - also called the goal (if more than one conjunct exists, they are refered to as the subgoals)
2. The subgoals are satisfied (i.e. get a yes or a value solution), from left to right
3. To satisfy a subgoal, look amongst the relations declared in the program for one with same functor name and arity, i.e. the head of the clauses are inspected. If no match is found between the required query and the head, the subgoal fails (i.e. answer no)
4. If a relation with the same functor as the subgoal is found, try to unify the subgoal with the head of the relation. If the unification fails, reject this relation and try looking for a second one, i.e. the declarations for a same functor are inspected in top to bottom order

1. The above four steps are repeated until :
   either no unifiable relation is found, in whcih the subgoal fails answer no.
   or
   a unifiable relation is found; the tne values given (instantiated) to the variables in the unifier are transmitted through to the other subgoals (if any) and to the body (if any) of the relation; once this transmission is completed, the body of the relation replaces the subgoal in the query conjunction
2. BEcause of the other subgoals and/or the body being possibly empty, the query conjunction may eventually be empty : success (answer yes or values for initial variables in query)

This strategy of left to right, top to bottom is know as depth first with backtracking

• Variables are binded (instantiated) to values while the computation is going forward and they retain those values (no possibility to reassign values like in C or Pascal)
• When backtracking takes place because of a failure, the computation (or part of it) is undone and some of the bindings of variables becomes undone.