Program control

In order for a program to achieve its purpose, it needs some type of control structure. Conventional programming languages use explicit statements for loops and branches. Flow charts are often used for mapping out the structure of the control.

In Prolog, you control the way in which a program will execute by ordering the clauses within your program and the goals within each clause. Prolog attempts to finish satisfying a subgoal before it continues on to another goal. This is referred to as “depth-first search” and as “backtracking.” But, don't be fooled: Prolog is a powerful general-purpose implementation language that allows you to build serious applications that go far beyond simple search strategies.

Prolog allows you to use techniques known as repeat-fail loops, recursion, and cut to control the execution of your program. A thorough understanding of these techniques is needed to become a fluent Prolog programmer.

The program control operators and predicates used by Arity/Prolog32 are:

,

Referred to as "and", the comma (,) specifies a conjunction of goals. When a clause contains a sequence of conjunctive goals in the body, they must all be satisfied in sequence for the clause to succeed.

;

|

Referred to as "or", the semicolon (;) or vertical bar (|) specifies a disjunction of goals. A disjunction creates a choice point for possible backtracking. The left arm of the disjunction is attempted and if it succeeds the disjunction succeeds. If not, the right arm is attempted. Outside of a list, the vertical bar (|) may be used instead of the semicolon.

!

The cut, specified with an exclamation point (!) is a goal that always succeeds, but if backtracking encounters the cut, then the predicate that contains the cut fails (not just the clause that contains the cut).

Programmers who are new to Prolog tend to use cut too often or too infrequently. Extraneous cuts that do not remove any choice points are (slightly) inefficient. Missing cuts may produce incorrect results or may force unneeded work to be performed. You should think of cuts as not only marking a point of "commitment" to a chosen path of execution, but also as a way of documenting in your program that if the execution reaches this point, a noteworthy set of conditions has been fulfilled.

The cut-fail pattern in Prolog is very common, clear, and efficient. Often writing code that uses the cut-fail pattern is preferable to code that uses not/1.

[! P !]

Snips contain a goal or goals such that if backtracking attempts to resatisfy the snips, then the entire snips fail. It is similar to the cut but the scope of behavior is not the entire predicate but is delimited by the left and right barriers of the snips.

The typical pretty-printed pattern for snips looks like:

goal1 :-
    subgoal1,
    [!
        subgoal2,
        subgoal3
    !],
    subgoal4.

call(+P)

call(+Address, +P)

The term P is interpreted as a goal. If P succeeds, then call(P) succeeds. If P fails, then call(P) fails. The call/2 predicate is used to call code in runtime loaded DLLs; Refer to the section on DLL and Visibility predicates for more information.

not(+P)

\+ P

not P

The term P is interpreted as a goal. If P succeeds, not(P) fails. If P fails, then not(P) succeeds. Not is an operator so not P is equivalent to not(P). In addition, the operator + is equivalent to not.

true

This goal always succeeds.

fail

This goal always fails. This predicate is useful when you want the program to backtrack.

repeat

This goal always succeeds and, when encountered during backtracking, succeeds again.

The repeat/0 predicate is defined very simply:

repeat.
repeat :- repeat.

ifthen(+P, +Q)

If the goal P succeeds, then the term Q is executed. If the goal P fails, the term Q is not executed and the ifthen/2 goal succeeds.

ifthenelse(+P, +Q, +R)

If the goal P succeeds, then the term Q is executed. If the goal P fails, then the term R is executed.

case(+[A1 -> B1, A2 -> B2, ... | C])

case(+[A1 -> B1, A2 -> B2, ...])

The case/1 predicate selects a single execution path from a list of possible execution paths. For example, if A1 succeeds, then B1 is executed. In the first form, if none of the situations are true, then the default, C, is executed. In the second form, if none of the situations are true, then case succeeds. If the left hand side of an arm succeeds, then the case is committed so no other arms will be attempted. Backtracking into a right hand side of a committed case is permitted. There is no limit to the number of cases that can be listed.

bagof(+Term, +Goal, -Bag)

The bagof/3 predicate collects in a list all instances of a term (Term) such that the specified goal (Goal) may be satisfied. Term must contain variables that are not found anywhere but in Goal. Goal is a goal that contains variables that are shared with Term. Other variables in Goal are either free or bound.

A free variable falls into one of the following categories:

  • It is not instantiated when bagof/3 is called.
  • It does not appear in Term.
  • It is not existentially quantified.

The existential quantifier ( ^ ) is used on uninstantiated variables to make them appear to bagof as if they were bound. That is, in X^P, X is existentially bound in P; in X^Y^P, both X and Y are existentially bound. An alternative notation for indicating that a group of variables are existentially bound to a particular variable is to list the group of variables, each separated by a comma, inside parentheses. For example, X^Y^P can be represented as (X,Y)^P.

If bagof/3 is used in a compiled program, then every subgoal appearing in Goal must be made visible.

The list that is returned (Bag) corresponds to each instantiation of all free variables in the goal. That is, for each instantiation of the free variables, bagof/3 returns all instances of Term in an unordered list that may also contain duplicates. If there are no free variables, then only one bag is produced and the predicate fails on backtracking.

For example, suppose you had a database containing the following facts:

likes(frank,bluegrass).
likes(jane,jazz).
likes(joe,classical).
likes(sue,bluegrass).
likes(sue,jazz).

You could call bagof/3 to determine who likes what types of music, as follows:

?- bagof(X, likes(Y,X), L).
X = _045D
Y = frank
L = [bluegrass] -> ;

X = _045D
Y =  jane
L = [jazz] -> ;

X = _045D
Y = joe
L = [classical] -> ;

X = _045D
Y = sue
L = [bluegrass,jazz] ->;
no

The "_045D" returned by the system represents an uninstantiated variable.

In the following example, the existential quantifier states that for any instance of Y in the goal, bagof will return all instances of X. For the likes database, this means that you can collect all instances of X that are liked by any Y, as follows:

?- bagof(X, Y^likes(Y,X),  L).

X = _0589
Y = _0599
L = [bluegrass,jazz,classical,bluegrass,jazz]
yes

setof(+Term, +Goal, -Set)

The setof/3 predicate is the same as bagof/3, except that setof/3 returns a sorted list that contains no duplicates.

If setof/3 is used in a compiled program, then every subgoal appearing in Goal must be made visible.

Using the facts above:

?- setof(X,Y^likes(Y,X),L).
X = _0589
Y = _0599
L = [bluegrass,classical,jazz]
yes

findall(+Term, +Goal, -List)

The findall/3 predicate is the same as bagof/3, except that any free variable is assumed to be existentially quantified. That is, findall/3 searches through the database for all occurrences of the term such that the goal may be satisfied and it returns those instances to an unsorted list containing any duplicates that are found.

The findall/3 predicate runs more efficiently than either the bagof/3 or setof/3 predicates. If findall/3 is used in a compiled program, then every subgoal appearing in Goal must be made visible.

Using the facts above:

?- findall(X, likes(Y,X), L).
X = _0589
Y = _0599
L = [bluegrass,jazz,classical,bluegrass,jazz]
yes