Prolog Execution

Clauses
Unification
Backtracking Search
Flow-of-Control
Complex Goals
Counters

Clauses

A Prolog program is a collection of Prolog structures called clauses. A clause is a structure of the form

head :- body.

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 compiler expects clauses to be contiguous unless the predicate is mentioned in a 'multifile' or 'discontiguous' directive, or is dynamic, indexed or sorted.

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:

Two atoms unify if they are the same.
Two numbers unify if they have the same value (non ISO).
Two structures unify if they have the same name and arity, and each pair of respective arguments unify.
Two lists unify if their initial elements unify, and the lists which remain after removing both initial elements unify.
A variable unifies with a non-variable by being replaced by the non-variable. This is known as binding.
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.
Two strings unify if and only if they have precisely the same characters in them.
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.

Occurs Check

It is possible to construct a unification query with terms that refer to impossible nested combinations. These are called cyclic terms. They cause the unification algorithm to go in an infinite loop, thus crashing the system. They can be caught by turning on occurs_check using either Prolog flags or the amzi.cfg file.

It requires the unification of multiple cyclic terms to cause the problem. For example:

?- A = f(A), B = f(B), A = B.

The first two unifications are cyclic, and when the third unification between the cyclic terms is tried, that's when the infinite loop happens. With occurs_check on, the above query will fail at the final A = B.

Clearly occurs_check seems like a good idea, but because these situations are rare, and because occurs_check adds about 10% performance overhead, the ISO standard default for it is off.

Note that only complex situations, like the one above cause the problem. Single cyclic unification doesn't cause a unification problem until it is output, and the output routines automatically detect that situation, whether occurs_check is on or off. A '...' is displayed to indicate the cyclic term after a few iterations.

?- A = f(A).
A = f(f(f(f(...))))

If the Prolog flag occurs_check is turned on, the default is off, then attempts to unify cyclic terms will simply fail, rather than crash. This normally isn't necessary because it is usually an unusual error that causes the problem.

unify_with_occurs_check(X,Y)

unify_with_occurs_check(X,Y) attempts to unify X and Y in the normal way, but also guards against unification of cyclic terms, which could cause a system crash. It is implemented internally by turning on and off the occurs_check flag.

is_cyclic(Term)

is_cyclic(Term) succeeds if Term contains cyclic redundencies. For example,

?- X = [X|Y], is_cyclic(X).
X = [[[[... | H182] | H182] | H182] | H182]
Y = H182
yes

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? In most cases Prolog looks through the clauses in the order in which they are entered in the logicbase. This is not the case for a 'sorted' predicate, which is, as the name implies, stored in sorted order.

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

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.
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 powerful, generating 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. And for each of the predicates below that takes a goal as an argument, that goal can be a complex goal, often requiring parenthesis.

The following example shows the call/1 predicate first calling a simple goal, then calling the 'and' operator ','/2 which joins three goals together.

   call( text(X) ),
   call( (test1(X), test2(Y), test3(Z)) ),
   ...

X , Y

Logical 'and' is represented by the comma operator ','/2. It succeeds if both X and Y both can be proved; else it fails. Note that the comma used to separate goals is an operator, and syntactically very different from the comma used to separate the arguments of a structure, or elements of a list.

X ; Y

Logical 'or' is represented by the semicolon operator, ';'/2. It 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.

call(Goal)

call/1 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 clauses, the call predicate handles both with no need for declarations. call/1 is often used for calling generated goals, for example:

G =.. [PRED, ARG1, ARG2, ARG3],
call(G).

not(Goal)

not/1 succeeds if and only if Goal cannot be proved.

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

\+/1 X is a synonym for not X.

once(Goal)

The predicate once/1 behaves like call/1 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 (!).

findall(Instance, Goal, List)

findall/3 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 logicbase contains the following clauses for a:

a(1).
a(2).
a(3).

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

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

?- findall(X, a(X), L).
L = [1, 2, 3]

Consider these facts in the logicbase:

fact(bird, duck).
fact(sound, quack).
fact(color, white).

The terms in the list take the form of the first argument, as in this example:

?- findall(Name:Value, fact(Name, Value), List).
List = [bird:duck, sound:quack, color:white]

bagof(Instance, Goal, List)

bagof/3 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/3 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:

bagof(W, a(W, X, Y, Z), L).          % Here X, Y and Z are free
bagof(W, X ^ Y ^ a(W, X, Y, Z), L)   % Here only Z is free

So, for example, consider the following logicbase:

likes(fred, beer).
likes(tom, wine).
likes(jane, beer).
likes(jane, coke).

?- bagof(P, likes(X, P), L).   % X is free so we will backtrack 
P = H47
X = fred
L = [beer] ;
P = H47
X = tom
L = [wine] ;
P = H47
X = jane
L = [beer, coke] ;
no
?- bagof(P, X ^ likes(X, P), L).
P = H47
X = H48
L = [beer, wine, beer, coke].

setof(Instance, Goal, List)

setof/3 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 find all solutions to a problem. Sometimes we know there are no more solutions. 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 "!".

!/0 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/0 is always provable, and can be backtracked into an arbitrary number of times. It behaves as though it had been defined by:

repeat.
repeat :- repeat.

fail

fail/0 always fails.

true

true/0 always succeeds.

for(Index, Start, End, Increment)

for/4 provides a shorthand for implementing repeat/fail loops that execute a prespecified number of times. Start, End and Increment must be bound to integers with Start being less than or equal to End. The for/4 goal succeeds on REDO until the end condition is met, in which case 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.

?- for(X, 1, 5, 1), write(X), fail.
12345
no

catch(GOAL, ERROR, HANDLER)

catch/3 catches any errors that unify with ERROR thrown during the execution of GOAL. If an error is caught, control passes to HANDLER. If no errors are caught, catch/3 is the same as call/1.

catch/3 catches errors thrown by the application, using throw/1, or errors thrown by the system. System errors are thrown as error/2 structures:

error(ERROR_CLASS, ATTRIBUTE_VALUE_LIST)

The ATTRIBUTE_VALUE_LIST will vary depending on the type of error. Here's an example of a read error:

?- catch(read(X), E, write(E)).
duck+*(le.
error(syntax_error,
  [type = read,
   rc = 407,
   message = Unexpected operator,
   predicate = read_term$/3,
   callstack = - read_term3;- catch/3;...
   read_buffer = duck+*( **NEAR HERE** le.,
   read_file = user_function,
   line_number = 0])
X = H1
E = % same as above

See below for details on application thrown errors and multiple catch/3 goals. See the Logic Server error handling documentation for more details on system errors.

throw(TERM)

throw/1 throws and error, and the error is TERM. TERM can be any valid Prolog term. If TERM unifies with the ERROR argument of a catch/3 above the throw/1 in the call stack, then that catch/3 HANDLER will handle the error.

If there is no catch/3 to handle the error, then the error is thrown to the calling application, and, if it doesn't handle it, eventually to the operating system. The calling application might include Logic Server exception handling, which can also catch errors thrown from Prolog code, or the runtime.

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:

main :-
     catch(
          (goal1,
           goal2,
           goal3),
     error(X,Y),
     process_error(X,Y)).

halt

When proved, halt/0 returns to the operating system. halt/0 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 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/2 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.