4.1.2 Programs

A fundamental unit of a logic program is the goal or procedure call. E.g.

     gives(tom, apple, teacher)   reverse([1,2,3], L)   X<Y

A goal is merely a special kind of term, distinguished only by the context in which it appears in the program. The (principal) functor of a goal identifies what predicate the goal is for. It corresponds roughly to a verb in natural language, or to a procedure name in a conventional programming language.

A logic program consists simply of a sequence of statements called sentences, which are analogous to sentences of natural language. A sentence comprises a head and a body. The head either consists of a single goal or is empty. The body consists of a sequence of zero or more goals (i.e. it too may be empty). If the head is not empty, the sentence is called a clause.

If the body of a clause is empty, the clause is called a unit clause, and is written in the form

     P.

where P is the head goal. We interpret this declaratively as

Goals matching P are true.

and procedurally as

Goals matching P are satisfied.

If the body of a clause is non-empty, the clause is called a rule, and is written in the form

     P :- Q, R, S.

where P is the head goal and Q, R and S are the goals that make up the body. We can read such a clause either declaratively as

P is true if Q and R and S are true.

or procedurally as

To satisfy goal P, satisfy goals Q, R and S.

A sentence with an empty head is called a directive (see Directives), and is written in the form

     :- P, Q.

where P and Q are the goals of the body. Such a query is read declaratively as

Are P and Q true?

and procedurally as

Satisfy goals P and Q.

Sentences generally contain variables. Note that variables in different sentences are completely independent, even if they have the same name—i.e. the lexical scope of a variable is limited to a single sentence. Each distinct variable in a sentence should be interpreted as standing for an arbitrary entity, or value. To illustrate this, here are some examples of sentences containing variables, with possible declarative and procedural readings:

  1. employed(X) :- employs(Y,X).

    “Any X is employed if any Y employs X.”

    “To find whether a person X is employed, find whether any Y employs X.”

  2. derivative(X,X,1).

    “For any X, the derivative of X with respect to X is 1.”

    “The goal of finding a derivative for the expression X with respect to X itself is satisfied by the result 1.”

  3. ?- ungulate(X), aquatic(X).

    “Is it true, for any X, that X is an ungulate and X is aquatic?”

    “Find an X that is both an ungulate and aquatic.”

In any program, the predicate for a particular (principal) functor is the sequence of clauses in the program whose head goals have that principal functor. For example, the predicate for a 3-ary functor concatenate/3 might well consist of the two clauses

     concatenate([], L, L).
     concatenate([X|L1], L2, [X|L3]) :- concatenate(L1, L2, L3).

where concatenate(L1,L2,L3) means “the list L1 concatenated with the list L2 is the list L3”. Note that for predicates with clauses corresponding to a base case and a recursive case, the preferred style is to write the base case clause first.

In Prolog, several predicates may have the same name but different arities. Therefore, when it is important to specify a predicate unambiguously, the form name/arity is used; e.g. concatenate/3.

Certain predicates are predefined by the Prolog system. Such predicates are called built-in predicates.

As we have seen, the goals in the body of a sentence are linked by the operator `,', which can be interpreted as conjunction (“and”). It is sometimes convenient to use an additional operator `;', standing for disjunction (“or”). (The precedence of `;' is such that it dominates `,' but is dominated by `:-'.) An example is the clause

     grandfather(X, Z) :-
             (mother(X, Y); father(X, Y)),
             father(Y, Z).

which can be read as

For any X, Y and Z, X has Z as a grandfather if either the mother of X is Y or the father of X is Y, and the father of Y is Z.

Such uses of disjunction can always be eliminated by defining an extra predicate—for instance the previous example is equivalent to

     grandfather(X,Z) :- parent(X,Y), father(Y,Z).
     
     parent(X,Y) :- mother(X,Y).
     parent(X,Y) :- father(X,Y).

—and so disjunction will not be mentioned further in the following, more formal, description of the semantics of clauses.

The token `|', when used outside a list, is an alias for `;'. The aliasing is performed when terms are read in, so that

     a :- b | c.

is read as if it were

     a :- b ; c.

Note the double use of the `.' character. On the one hand it is used as a sentence terminator, while on the other it may be used in a string of symbols making up an atom (e.g. the list functor ./2). The rule used to disambiguate terms is that a `.' followed by layout-text is regarded as a sentence terminator (see Token String).