Go to the first, previous, next, last section, table of contents.


Programming Tips and Examples

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.

Programming Guidelines

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.

Indexing

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.

Last Call Optimization

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.

If-Then-Else Compilation

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.

Programming Examples

The rest of this chapter contains a number of simple examples of Prolog programming, illustrating some of the techniques described above.

Simple List Processing

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).

Family Example (descendants)

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

Association List Primitives

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).

Differentiation

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).

Use of Meta-Logical Predicates

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).

Use of Term Expansion

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).

Prolog in Prolog

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).

Translating English Sentences into Logic Formulae

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].

Muse FLI Example

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.