4  Backtracking

It is helpful to go into the following evaluation (sec 2.2) in a little detail:

(%which ()
  (%computer-literate 'Penelope))
=> ()true

The starting goal is:

G0 = (%computer-literate Penelope)

(I’ve taken out the quote because Penelope is the result of evaluating 'Penelope.)

Schelog tries to match this with the head of the first clause of %computer‑literate. It succeeds, generating a binding [person Penelope].

But this means it now has two new goals — subgoals — to solve. These are the goals in the body of the matching clause, with the logic variables substituted by their instantiations:

G1 = (%knows Penelope TeX)
G2 = (%knows Penelope Scheme)

For G1, Schelog attempts matches with the clauses of %knows, and succeeds at the fifth try. (There are no subgoals in this case, because the bodies of these “fact” clauses are empty, in contrast to the “rule” clauses of %computer‑literate.) Schelog then tries to solve G2 against the clauses of %knows, and since there is no clause stating that Penelope knows Scheme, it fails.

All is not lost though. Schelog now backtracks to the goal that was solved just before, viz., G1. It retries G1, ie, tries to solve it in a different way. This entails searching down the previously unconsidered %knows clauses for G1, ie, the sixth onwards. Obviously, Schelog fails again, because the fact that Penelope knows TeX occurs only once.

Schelog now backtracks to the goal before G1, ie, G0. We abandon the current successful match with the first clause-head of %computer‑literate, and try the next clause-head. Schelog succeeds, again producing a binding [person Penelope], and two new subgoals:

G3 = (%knows Penelope TeX)
G4 = (%knows Penelope Prolog)

It is now easy to trace that Schelog finds both G3 and G4 to be true. Since both of G0’s subgoals are true, G0 is itself considered true. And this is what Schelog reports. The interested reader can now trace why the following query has a different denouement:

(%which ()
  (%computer-literate 'Telemachus))
=> #f