Prolog Learnings: Backtracking

March 23, 2021 3-minute read

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.

The predicate 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 records.

Prolog attempts to find the youngest person as follows;

Prolog assigns Person/Age to 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.
Within the not in line #9, Prolog will backtrack (the inner loop) attempting to satisfy the inner clauses to true, in other words trying to find any NewPerson/NewAge value (line #10) where NewAge less than Age (line #11). Failures initiate backtrackng until NewPerson and NewAge are assigned carl and 34 respectively (line #10). 34 is less than 48 and the clauses succeed. However the not inverts this to fail, causing Prolog to backtrack in the outer loop and assign Person and Age to the next record found (line #8), which is person(bert, 50).
Prolog then enters the not and attempts again to find a value of NewAge less than Age by backtracking from andrew/48 until danielle/33. The clauses are satisfied but true is inverted by not, causing backtracking in outer loop.
Outer/Inner backtracking continues until Person/Age is assigned 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 not inverts the fail to true satisfing the clauses in youngest causing Prolog to immediately return with Person and Age assigned the values danielle and 33 respectively.