Say you wish to find the name and age of the youngest person in a list of person records. This is a straightforward O(N) operation in any iterative language and can be implemented by keeping track of the youngest age seen while looping through the list of persons.
In Prolog we can make use the automatic backtracking capability instead of using a loop construct. This won’t be an O(N) operation but for anything less than a few hundred records it shouldn’t be too bad.
|A goal in Prolog is a predicate that always evalutes to true. A Rule in Prolog is a predicate that may evaluate to true depending on the evaluation of its internal clauses. And clauses may be either goals or rules.|
First we create our person records or "goals".
1 2 3 4 5 6 7 8 9 10 11 12 person(andrew, 48). person(bert, 50). person(carl, 34). person(danielle, 33). person(estelle, 45). youngest(Person, Age) :- person(Person, Age), % (1) not (( % (2) person(NewPerson, NewAge), % (3) NewAge < Age )).
|1||First opportunity for backtracking. The outer loop.|
|2||This effectively means "No person having NewAge less than Age"|
|3||Second opportunity for backtracking. The inner loop.|
youngest returns the youngest person from the previously defined
person records. This predicate states; "for all values of Person/Age, return the
Person/Age where no other NewPerson/NewAge is younger."
|It is important when thinking in Prolog to consider predicates as "for all" or "for some" or "for any" because of this capability for automatic backtracking.|
1 2 3 4 ?- youngest(Person, Age). Person = danielle, Age = 33
youngest defines two opportunities for backtracking in lines #8 and #10 which
means that this algorithm will approach O(N^2) performance which is quadratic
complexity and therefore not really suitable for any large number of person
Prolog attempts to find the youngest person as follows;
Person/Ageto the first matching record in line #8, which is
person(Andrew, 48). This is the first opportunity for backtracking and is in effect the outer loop.
notin line #9, Prolog will backtrack (the inner loop) attempting to satisfy the inner clauses to
true, in other words trying to find any
NewPerson/NewAgevalue (line #10) where
Age(line #11). Failures initiate backtrackng until
34respectively (line #10).
34is less than
48and the clauses succeed. However the
notinverts this to
fail, causing Prolog to backtrack in the outer loop and assign
Ageto the next record found (line #8), which is
Prolog then enters the
notand attempts again to find a value of
Ageby backtracking from
danielle/33. The clauses are satisfied but
trueis inverted by
not, causing backtracking in outer loop.
Outer/Inner backtracking continues until
danielle/33. At this point Prolog backtracks within the inner loop and exhausts all persons causing the clauses to
fail— because there exists no person younger than
person(danielle, 33). The
truesatisfing the clauses in
youngestcausing Prolog to immediately return with
Ageassigned the values