Prolog Execution

Clauses

A Prolog program is a collection of Prolog structures called clauses. A clause is a structure of the form where head is a Prolog structure and body is optionally a series of Prolog structures separated by commas. The ":-" symbol is called the neck and is often read as "if".

A number of clauses with the same functor and arity are said to define a predicate of that functor and arity, often written in the form "functor/arity". The clauses must be contiguous unless the predicate is mentioned in a 'multifile' or 'discontiguous' directive.

Here, for example, are three clauses defining a predicate called is_ordered/1.

Unification

Prolog proves goals by matching patterns of a query goal with the patterns of the clauses of a Prolog program. It does this by finding a clause whose head matches the query goal and then trying to prove the goals, if any, in the clause's body.

Prolog has to have a method for matching the goal it is currently trying to prove against heads of clauses. When the head of a clause and the current goal match, the clause is chosen and Prolog goes on to try and prove the goals in its body (if any).

The act of matching two Prolog terms is called unification and is described by the following rules:

  1. Two atoms unify if they are the same.
  2. In the case of numbers, both must be integers or both must be real numbers.
  3. Two structures unify if they have the same name and arity, and each pair of respective arguments unify.
  4. Two lists unify if their initial elements unify, and the lists which remain after removing both initial elements unify.
  5. A variable unifies with a non-variable by being replaced by the non-variable. This is known as binding.
  6. Two variables unify by agreeing to "share" bindings. This means that if later on, one or the other unifies with another term, then both unify with the term.
  7. Two strings unify if and only if they have precisely the same characters in them.
  8. A string and an atom will unify if they have precisely the same characters in them.
When a clause is under consideration to match against a goal, space is reserved to hold variable bindings. If the clause is chosen again later on in the proof, then new space is reserved for the variable bindings caused by the new choice.

Backtracking Search

We have seen that Prolog uses unification to match a goal to the head of a clause, but if there are several candidate clauses, which does Prolog choose to try first? The answer is simple : Prolog looks through the clauses in the order in which they are entered in the database. Usually this is the order in which they occur in the file, or the order in which they are typed into the system (under the add or [user] directives).

Prolog's backtracking top-to-bottom, left-to-right search is simple and effective. Backtracking works as follows:

  1. If Prolog cannot prove a sub-goal in the body of a clause, then it looks at the sub-goal immediately to its left. If there are any other clauses which can be used to re-prove this goal, then any variable bindings which resulted from the previous clause selection are discarded, and Prolog continues with the new proof.
  2. If the sub-goal which initially failed was the first goal in the body of the clause, then the whole goal fails, and the backtracking continues in the parent clause (the clause containing the reference to the goal whose proof just failed).
Backtracking is a very powerful tool since it will try and generate a solution by automated search. Unfortunately it can sometimes be too powerfulgenerating solutions that were not wanted, and so we have to have some way of controlling it. This leads us to the next section.

Complex Goals

In addition to simple predicates, Amzi! Prolog may be given compound or complex goals.

Note that call/1, findall/3, bagof/3 and setof/3 access the database, and for this reason, if they are compiled into modules with import and export, the goals they call must be accessible, which means if they are not in the local code they must be listed in an import directive.

X , Y

X , Y succeeds if both X and Y both can be proved; else it fails.

X ; Y

X ; Y succeeds if X can be proved or Y can be proved; else it fails.

Goal1 -> Goal2 ; Goal3

Goal1 -> Goal2 ; Goal3 is an if-then-else construct. If Goal1 can be proved then Prolog tries to prove Goal2. Otherwise if Goal1 fails Prolog tries to prove Goal3. Goal1 is not backtrackable into once it has been proved.

This predicate can also be used in the form Goal1 -> Goal2, which only succeeds once, if at all, and if so executes Goal2.

call(Goal)

call succeeds if Goal can be proved. Goal must be instantiated to a term which could be a valid goal in a clause body. Then call succeeds if and only if that goal can be proved. Note that Goal may be provable using compiled code or dynamic clausesthe call predicate handles both with no need for declarations.

not(Goal)

not succeeds if and only if Goal cannot be proved. Gola is subject to the same restrictions on Goal as in call above.

Note that not(not(Goal)) has the interesting, and sometimes useful, effect of succeeding if Goal can be proved, but not unifying any of its variables and failing on backtracking.

\+ Goal

\+ X is a synonym for not X.

findall(Instance, Goal, List)

findall succeeds if List can be unified with the list of all instances of Instance making Goal provable.

For example, findall(X, a(X), [1, 2, 3]) is true if the database contains precisely the following clauses for a:

If Goal cannot be proved for any values of Instance, then List is unified with the empty list [].

findall is generally used to generate lists from database entries, so for example it might be used as follows (with the database shown above):

For a database containing: Then you can construct arbitrary terms with:

bagof(Instance, Goal, List)

bagof is like findall above except in the way it deals with variables occurring in Goal which are not in Instance. These are known as free variables. In this case, bagof is backtrackable into and produces one list List for each possible binding of the free variables.

It is possible to convert an otherwise free variable to a non-free variable by using the ^ symbol as follows:

So, for example, consider the following database:

get_preds(PredList)

get_preds/1 is called with an unbound variable, PredList, and returns a list with the names and arities of all the predicates in the dynamic database. The predicates are returned in the form: functor/arity. For example, if DUCKY.PRO were loaded in the listener, then:

once(Goal)

The predicate once behaves like call except it is only executed once. This is useful for isolating code that you don't intend to be backtracked into, and makes for more readable code than inserting lots of cuts (!).

Note that like all such predicates, more than one goal can be given as an argument by enclosing them in parenthesis:

setof(Instance, Goal, List)

setof is like bagof/3 above except the list List is sorted according to the standard order and any duplicates are removed.

Flow-of-Control

The top-down, left-to-right search coupled with backtracking will try to ferret out a solution to a problem. Sometimes it can be too industrious. What we need is a way of saying "if you have got this far then there is no backtracking !"

!Cut

There is a Prolog predicate which does just this. It is called cut, and is denoted with a "!".

! is always true, so if a clause containing a cut is read as a statement of truth, it behaves as if there were no cut there. But cut affects the way backtracking is performed as follows:

Once a cut is executed, the choice of the clause which contains it is frozen as a proof step. Also any choices made during the proof of the goals between the head of the clause and the cut are frozen. Thus cut acts like a fence. When backtracking passes over the cut (heading left in a clause), then proof reconsideration continues not with the goal to the left of the !, but the goal to the left of the goal which chose the clause containing the cut.

repeat

repeat is always provable, and can be backtracked into an arbitrary number of times. It behaves as though it had been defined by:

fail

fail always fails.

true

true always succeeds.

for(Index, Start, End, Increment)

for provides a shorthand for implementing repeat/fail loops that execute a prespecified number of times. Bottom, Top and Increment must be bound to integers with Bottom being less than or equal to Top. When first proved Index is unified with Bottom and checked to see whether it is less than or equal to Top. If so, for succeeds otherwise it fails.

On backtracking Increment is added to the current value of Index and Index is bound to this new value. Again a range check is performed.

catch(Goal, Catcher, Recover) and throw(Term)

Two predicates, catch/3 and throw/1, are a general purpose mechanism for handling user-defined exceptions in Prolog code. These predicates are the ISO standard predicates for exception handling, and provide an alternative to the current tag/1 and cut_tag/1 predicates.

The two key predicates' arguments are:

catch(Goal, Catcher, Recover)

Goal
is a normal Prolog goal to be proved
Catcher
is a term used as a pattern to be checked against possible thrown exceptions
Recover
is a goal to be proved if a thrown exception is caught.
throw(Term)
Term
a term that is used in a search for a matching catch term
catch(Goal,Catcher,Recover) is fully equivalent to 'call(Goal)' for the normal case where no exception is thrown during the execution of goal Goal. If a 'throw(Catcher)' is encountered, then the catch/3 Goal is replaced with the goal 'call(Recover)' instead.

Catch statements are subject to the limitations of local predicates. If a catch is used in a module (a file containing :-import or :-export statements) then the goals mentioned in the catch must be global, not local.

The catch/throw pair allow the flow-of-control to skip over all of the intermediate predicates, which is especially useful for dealing with error exceptions.

Throw will only succeed if the term thrown matches an active catch term. After the goal of the catch is satisfied the catch term can no longer be thrown to. An attempt to throw an uncaught term results in a system error.

The following is the example from samples/prolog/misc/catch.pro:
 
main :-

  /* Catch and process all throws not handled by 
     subsequent catches, including throw(quit) 
     used to end the program. */

   catch(doit, X, error_handler(X)).

error_handler(quit) :-
  write($Quitting\n$).
error_handler(X) :-
  write($Unknown Error$ : X), nl.

doit :-
  repeat,
  write($Enter one or done or something else: $),
  read_string(S),
  string_atom(S, A),
  catch(do(A), badcommand(X),
  (write($Bad Command$:X),nl)),
  fail.

do(one) :-
  catch(do_one, except(X), except(X)), !.
do(done) :-
  throw(quit).
do(X) :-
  throw(badcommand(X)).

except(notinteger:X) :-
  write(X), write($ not an integer\n$).
except(toosmall:X) :-
  write(X), write($ is too small\n$).
except(toobig:X) :-
  write(X), write($ is too big\n$).

do_one :-
  repeat,
  write($Enter a number between 10 and 20,\n$),
  write($'q' to quit,
    or anything else to see an   error:\n$),
  read_string(S),
  string_term(S,T),
  check(T),
  fail.

check(q) :- throw(quit).
check(X) :-
  not(integer(X)),
  throw(except(notinteger:X)).
check(X) :-
  X > 10,
  X < 20,
  !, write($Very good\n$).
check(X) :-
  X =< 10,
  throw(except(toosmall:X)).
check(X) :-
  X >= 20,
  throw(except(toobig:X)).
check(X) :-
  throw(badcheck(X)).

Note that multiple goals can be provided to catch/3, such as:

tag(Term) and cut_tag(Term)

Tags are an advanced feature of Amzi! Prolog. See also the ISO standard predicates catch/3 and throw/1.

Cut is very useful to control backtracking behavior in Prolog programs but its effects are confined only to the code of the predicate in which the clause containing the cut is a part. There are occasions in which we would like to modify backtracking behavior beyond the current predicate- an example of which is in handling errors.

To facilitate a form of more general backtracking control Amzi! Prolog has introduced the concept of the tag.

A tag is a marked instance of a choice point in the execution environment of a Prolog program. The choice point is marked by associating it with some term using the predicate tag/1. The predicate cut_tag/1 allows the removal of all choice points back to and including the choice point marked by a given term.

tag associates the most current choice point with Term. This association is only removed when the tagged choice point is removed by backtracking.

cut_tag scans back through the choice points until it comes across the first choice point with a tag which can be unified with Term. All choice points more recent than the tagged choice point are removed.

As an example, consider the use of tags to "fail out of" the infinite loop of a repeat (repeat is a special built in predicate which can always be reproved an unlimited number of times) so

acts like an infinite loop. When the clause for loop is entered it will tag the most recent choice point with label "loop_marker."

Then the repeat will be proved and doit will be tried. As long as want_to_stop is not provable, do_something will be proved and then fail will be tried. fail always fails, so backtracking takes us eventually back to repeat and doit is proved again.

Once we can prove want_to_stop, cut_tag(loop_marker) is proved. This looks back along the proof and finds that the choice point before repeat was marked with loop marker. So every choice point since then (including the choice point for repeat) is removed. Finally fail is proved one more time. But now the repeat has been effectively removed and so backtracking will go all the way back to some point before loop was entered.

halt

When proved, halt returns to the operating system. halt will flush any files to disk and close them so no data will be lost.

Counters

It is often desirable to do the non-logical thing and count things. For this purpose, Amzi! Prolog supports five global registers called counters. A counter is simply a storage space reserved for a Prolog integer. Its value can be easily accessed by all parts of a Prolog program without having to pass its value as an argument through the predicates. The Counters are accessed by Counter, an integer between 0 and 20.

cntr_get(Counter, Value)

cntr_get succeeds if Value can be unified with the contents of register Counter.

cntr_dec(Counter, Value)

cntr_dec/2 unifies Value with the current value of the Counter, and then decrements the counter.

cntr_inc(Counter, Value)

cntr_inc/2 unifies Value with the current value of the Counter, and then increments the counter.

cntr_set(Counter, Value)

cntr_set(Counter, Value) sets the value of Counter to be Value. So Value must be bound to an integer.

 

Copyright ©1987-2000 Amzi! inc. All Rights Reserved.