Instructors' Guide

Introduction Terminology Expressions Control Objects Inheritance Technology Summary

Control

 The computation mechanism employed by Prolog may be characterized as goal reduction with unification and backtracking. As an example, look at the Prolog program in slide dlp-control-1, consisting of a number of clauses and facts.

Prolog

 
  p(X,Y) :- r(Z), b(X). 
 clauses

  p(X,Y) :- q(Y), b(X).
  b(X) :- a(X).
  b(0).  
 facts

  a(1).
  q(2).
Query 
  ?- p(X,Y). 
 results in (X = 1,Y = 2)

  
 and (X = 0, Y = 2)
slide: DLP -- control (1)
 When we pose our query, it is first attempted to resolve the goal p(X,Y) with the first clause for p (which fails because r(Z) cannot be resolved). Then the second clause is tried, which leads to binding Y to 2 (since q(2) is a fact), and gives us two possible bindings for X, due to the facts a(1) and b(0). (Variables are local to clauses and will be renamed automatically to avoid clashes.) Hence, the evaluation of the goal p(X,Y) leads to two consistent bindings, that may successively be obtained by backtracking.

As an example of somewhat more realistic clauses, look at the list processing predicates member and append in slide dlp-control-2.

List processing -- backtracking

 
  member(X,[X|_]).
  member(X,[_|T]) :- member(X,T).
  
  append([],L,L).
  append([ H | T ],L,[ H | R ]):- append(T,L,R).
slide: DLP -- control (2)
 Both predicates are specified in an inductive manner, taking care of all possible cases. For example, the first clause for member states as a fact that an element is contained in a list when it is the first element. The second clause prescribes the recursive application of member to the tail of the list if this is not the case. Similarly, the clauses for append distiguish between the case of appending a list to an empty list, and the case of appending a list to a non-empty list.

This manner of specification closely adheres to standard practice in mathematical logic and has proven to be a powerful means to develop knowledge-based systems (such as expert systems) that rely on logical reasoning.