This chapter describes how to write clean programs that will execute efficiently. To some extent, writing efficient code in any language requires basic knowledge of its compiler, and we will mention some important properties of the SICStus Prolog compiler. A number of simple examples of Prolog programming are also given.
A lot of clarity and efficiency is gained by sticking to a few basic rules. This list is necessarily very incomplete. The reader is referred to textbooks such as [O'Keefe 90] for a thorough exposition of the elements of Prolog programming style and techniques.
[...]), "round lists" ((...)), or
braces ({...}) to represent compound terms, or "tuples", of
some fixed arity. The name of a compound term comes for free.
The clauses of any predicate are indexed according to the principal functor of the first argument in the head of the clause. This means that the subset of clauses which match a given goal, as far as the first step of unification is concerned, is found very quickly, in practically constant time. This can be very important where there is a large number of clauses for a predicate. Indexing also improves the Prolog system's ability to detect determinacy--important for conserving working storage, and strongly related to last call optimization (see below).
Indexing applies to interpreted clauses as well as to compiled clauses.
The compiler incorporates last call optimization to improve the speed and space efficiency of determinate predicates.
When execution reaches the last goal in a clause belonging to some predicate, and provided there are no remaining backtrack points in the execution so far of that predicate, all of the predicate's local working storage is reclaimed before the final call, and any structures it has created become eligible for garbage collection. This means that programs can now recurse to arbitrary depths without necessarily exceeding core limits. For example:
cycle(State) :- transform(State, State1), cycle(State1).
where transform/2 is a determinate predicate, can continue
executing indefinitely, provided each individual structure, State,
is not too large. The predicate cycle is equivalent to an iterative
loop in a conventional language.
To take advantage of last call optimization one must ensure that the Prolog system can recognize that the predicate is determinate at the point where the recursive call takes place. That is, the system must be able to detect that there are no other solutions to the current goal to be found by subsequent backtracking. In general this involves reliance on the Prolog compiler's indexing and/or use of cut; see section The Cut Symbol.
Ordinary disjunction, (P;Q), is treated by the
compiler as an anonymous predicate with two clauses, and the execution
of a disjunction relies on backtracking to explore the two disjuncts.
If-then-else statements of the form:
(If -> Then; Else)
are recognized by the compiler and are under certain conditions compiled to code that is much more efficient than the corresponding disjunction, essentially turning the If test to a conditional jump and often avoiding costly backtracking altogether.
For this optimization to be effective, the test must be a conjunction of a restricted set of built-in predicates (roughly, arithmetic tests, type tests and term comparisons).
This optimization is actually somewhat more general than what is described above. A sequence of guarded clauses:
Head1 :- Guard1, !, Body1. ... Headm :- Guardm, !, Bodym. Headn :- Bodym.
is eligible for the same optimization, provided that the arguments of the clause heads are all unique variables and that the "guards" are simple tests as described above.
The rest of this chapter contains a number of simple examples of Prolog programming, illustrating some of the techniques described above.
The goal concatenate(L1,L2,L3) is true if list
L3 consists of the elements of list L1 concatenated with the
elements of list L2. The goal member(X,L) is
true if X is one of the elements of list L. The goal
reverse(L1,L2) is true if list L2 consists of
the elements of list L1 in reverse order.
concatenate([], L, L).
concatenate([X|L1], L2, [X|L3]) :- concatenate(L1, L2, L3).
member(X, [X|_]).
member(X, [_|L]) :- member(X, L).
reverse(L, L1) :- reverse_concatenate(L, [], L1).
reverse_concatenate([], L, L).
reverse_concatenate([X|L1], L2, L3) :-
reverse_concatenate(L1, [X|L2], L3).
The goal descendant(X,Y) is true if Y is a
descendant of X.
descendant(X, Y) :- offspring(X, Y). descendant(X, Z) :- offspring(X, Y), descendant(Y, Z). offspring(abraham, ishmael). offspring(abraham, isaac). offspring(isaac, esau). offspring(isaac, jacob).
If for example the query
| ?- descendant(abraham, X).
is executed, Prolog's backtracking results in different descendants of Abraham being returned as successive instances of the variable X, i.e.
X = ishmael X = isaac X = esau X = jacob
These predicates implement "association list" primitives. They use a
binary tree representation. Thus the time complexity for these
predicates is O(lg N), where N is the number of keys. These
predicates also illustrate the use of compare/3 (see section Comparison of Terms) for case analysis.
The goal get_assoc(Key, Assoc, Value) is true
when Key is identical to one of the keys in Assoc, and
Value unifies with the associated value.
get_assoc(Key, t(K,V,L,R), Val) :-
compare(Rel, Key, K),
get_assoc(Rel, Key, V, L, R, Val).
get_assoc(=, _, Val, _, _, Val).
get_assoc(<, Key, _, Tree, _, Val) :-
get_assoc(Key, Tree, Val).
get_assoc(>, Key, _, _, Tree, Val) :-
get_assoc(Key, Tree, Val).
The goal put_assoc(Key, OldAssoc, Val,
NewAssoc) is true when OldAssoc and NewAssoc define
the same mapping for all keys other than Key, and
get_assoc(Key, NewAssoc, Val) is true.
put_assoc(Key, t, Val, Tree) :- !, Tree = t(Key,Val,t,t).
put_assoc(Key, t(K,V,L,R), Val, New) :-
compare(Rel, Key, K),
put_assoc(Rel, Key, K, V, L, R, Val, New).
put_assoc(=, Key, _, _, L, R, Val, t(Key,Val,L,R)).
put_assoc(<, Key, K, V, L, R, Val, t(K,V,Tree,R)) :-
put_assoc(Key, L, Val, Tree).
put_assoc(>, Key, K, V, L, R, Val, t(K,V,L,Tree)) :-
put_assoc(Key, R, Val, Tree).
The goal d(E1, X, E2) is true if expression
E2 is a possible form for the derivative of expression E1
with respect to X.
:- op(300, xfy, **). /* binds tighter than * */ d(X, X, D) :- atomic(X), !, D = 1. d(C, X, D) :- atomic(C), !, D = 0. d(U+V, X, DU+DV) :- d(U, X, DU), d(V, X, DV). d(U-V, X, DU-DV) :- d(U, X, DU), d(V, X, DV). d(U*V, X, DU*V+U*DV) :- d(U, X, DU), d(V, X, DV). d(U**N, X, N*U**N1*DU) :- integer(N), N1 is N-1, d(U, X, DU). d(-U, X, -DU) :- d(U, X, DU).
This example illustrates the use of the meta-logical predicates
var/1, arg/3, and functor/3 (see section Meta-Logic).
The procedure call variables(Term, L, [])
instantiates variable L to a list of all the variable occurrences
in the term Term. e.g.
| ?- variables(d(U*V, X, DU*V+U*DV), L, []). L = [U,V,X,DU,V,U,DV]
variables(X, [X|L0], L) :- var(X), !, L = L0.
variables(T, L0, L) :-
% nonvar(T),
functor(T, _, A),
variables(0, A, T, L0, L).
variables(A, A, _, L0, L) :- !, L = L0.
variables(A0, A, T, L0, L) :-
% A0<A,
A1 is A0+1,
arg(A1, T, X),
variables(X, L0, L1),
variables(A1, A, T, L1, L).
This example illustrates the use of user:term_expansion/(2,4) to
augment the built-in predicate expand_term/2 which works as a
filter on the input to compile and consult. The code below will allow
the declaration `:- wait f/3' as an alias for `:- block
f(-,?,?)'. Wait declarations were used in previous versions of SICStus
Prolog.
Note the multifile declaration, which prevents this
user:term_expansion/(2,4) clause from erasing any other clauses for
the same predicate that might have been loaded.
:- op(1150, fx, [wait]).
:- multifile user:term_expansion/2.
user:term_expansion((:- wait F/N), (:- block Head)) :-
functor(Head, F, N),
wb_args(N, Head).
wb_args(1, Head) :- !, arg(1, Head, -).
wb_args(N, Head) :-
% N>1,
arg(N, Head, ?),
N1 is N-1,
wb_args(N1, Head).
This example shows how simple it is to write a Prolog interpreter in
Prolog, and illustrates the use of a variable goal. In this
mini-interpreter, goals and clauses are represented as ordinary Prolog
data structures (i.e. terms). Terms representing clauses are specified
using the predicate my_clause/1, e.g.
my_clause( (grandparent(X, Z) :- parent(X, Y), parent(Y, Z)) ).
A unit clause will be represented by a term such as
my_clause( (parent(john, mary) :- true) ).
The mini-interpreter consists of three clauses:
execute((P,Q)) :- !, execute(P), execute(Q). execute(P) :- predicate_property(P, built_in), !, P. execute(P) :- my_clause((P :- Q)), execute(Q).
The second clause enables the mini-interpreter to cope with calls to
ordinary Prolog predicates, e.g. built-in predicates. The
mini-interpreter needs to be extended to cope with the other control
structures, i.e. !, (P;Q), (P->Q),
(P->Q;R), (\+ P), and if(P,Q,R).
The following example of a definite clause grammar defines in a formal way the traditional mapping of simple English sentences into formulae of classical logic. By way of illustration, if the sentence
Every man that lives loves a woman.
is parsed as a sentence by the call
| ?- phrase(sentence(P), [every,man,that,lives,loves,a,woman]).
then P will get instantiated to
all(X):(man(X)&lives(X) => exists(Y):(woman(Y)&loves(X,Y)))
where :, & and => are infix operators defined by
:- op(900, xfx, =>). :- op(800, xfy, &). :- op(300, xfx, :).
The grammar follows:
sentence(P) --> noun_phrase(X, P1, P), verb_phrase(X, P1).
noun_phrase(X, P1, P) -->
determiner(X, P2, P1, P), noun(X, P3), rel_clause(X, P3, P2).
noun_phrase(X, P, P) --> name(X).
verb_phrase(X, P) --> trans_verb(X, Y, P1), noun_phrase(Y, P1, P).
verb_phrase(X, P) --> intrans_verb(X, P).
rel_clause(X, P1, P1&P2) --> [that], verb_phrase(X, P2).
rel_clause(_, P, P) --> [].
determiner(X, P1, P2, all(X):(P1=>P2)) --> [every].
determiner(X, P1, P2, exists(X):(P1&P2)) --> [a].
noun(X, man(X)) --> [man].
noun(X, woman(X)) --> [woman].
name(john) --> [john].
trans_verb(X, Y, loves(X,Y)) --> [loves].
intrans_verb(X, lives(X)) --> [lives].
This example illustrates the techniques used in foreign language interface programming in Muse.
Let us assume we want to count the number of solutions of some problem, as well as the number of solutions produced by each worker. The following C file, `count.c', defines some procedures that can be used for this purpose.
#include <sicstus/sicstus.h>
static int *overall_counter_lock;
static int *worker_counters, *overall_counter;
void allocate_counters()
{
overall_counter_lock = (int *)SP_malloc(sizeof(int));
overall_counter = (int *)SP_malloc(sizeof(int));
worker_counters = (int *)SP_malloc(muse_max_workers()*sizeof(int));
}
void init_counters()
{
int i;
muse_init_lock(overall_counter_lock);
*overall_counter = 0;
for (i=0; i<muse_num_workers(); i++)
worker_counters[i]=0;
}
long get_counter(c)
long c;
{
if (c >= 0) return worker_counters[c];
else return *overall_counter;
}
long incr_counter()
{
int i;
muse_lock(overall_counter_lock);
i = ++(*overall_counter);
muse_un_lock(overall_counter_lock);
++(worker_counters[muse_worker_id()]);
return i;
}
We have defined here an overall_counter and an array of
worker_counters. There is a lock, overall_counter_lock,
ensuring the atomicity of incrementing the overall_counter. The
code allocate_counter allocates the counters in shared memory.
The init_counter procedure initializes all counters, while
get_counters retrieves the current value of a counter associated
with a worker (non-negative argument), or the value of the
overall_counter (negative argument). The incr_counter
procedure increments the counter for the worker, as well as the overall
counter.
The following Muse code, `count.pl', makes use of the above C routines to accomplish the task of counting the solutions of some goal.
foreign_resource(count, [allocate_counters,init_counters,
incr_counter,get_counter]).
foreign(allocate_counters, c, allocate_counters).
foreign(init_counters, c, init_counters).
foreign(incr_counter, c, incr_counter([-integer])).
foreign(get_counter, c, get_counter(+integer, [-integer])).
:- load_foreign_resource(count).
:- allocate_counters.
count(Goal) :-
statistics(walltime, [Start,_]),
count_solutions(Goal),
statistics(walltime, [End,_]),
display_counts(N),
Time is End - Start,
format('Total ~d solutions in ~3d seconds.~n', [N,Time]).
count_solutions(Goal) :-
init_counters,
Goal,
incr_counter(_),
fail.
count_solutions(_).
display_counts(N) :-
get_counter(-1, N),
muse_num_workers(M),
display_worker_counts(0, M).
display_worker_counts(M, M) :- !.
display_worker_counts(W, M) :-
get_counter(W, C),
( C==0 -> true ;
format('Solutions by worker ~d: ~d ~n', [W,C])
),
W1 is W+1, display_worker_counts(W1, M).
This example is compiled and executed as follows to count the number of solutions to the 8 queens problem (see section Running a Parallel Example):
% gcc -c count.c % sicstus -P | ?- compile([count,queens]). | ?- muse_flag(num_workers,_,3). | ?- count(queens(8,_)). Solutions by worker 0: 39 Solutions by worker 1: 31 Solutions by worker 2: 22 Total 92 solutions in 0.070 seconds. yes | ?-
Go to the first, previous, next, last section, table of contents.