4.2.1 Programs

A fundamental unit of a logic program is the goal or procedure call for example:

     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 is called a predicate. 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 in 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 (it 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 (A) where P is the head goal. We interpret this declaratively as (B) and procedurally as (C).

     
     P.  (A)

     
     “P is true.”  (B)

     
     “Goal P is satisfied.”  (C)

If the body of a clause is non-empty, the clause is called a non-unit clause, and is written in the form (D) 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 (E) or procedurally as (F).

     
     P :- Q, R, S.  (D)

     
     “P is true if Q and R and S are true.”  (E)

     
     “To satisfy goal P, satisfy goals Q, R, and S.”  (F)

A sentence with an empty head is called a directive, of which the most important kind is called a query and is written in the form (G). Such a query is read declaratively as (H), and procedurally as (I).

     
     ?- P, Q.  (G)

     
     “Are P and Q true?”  (H)

     
     “Satisfy goals P and Q.”  (I)

Sentences generally contain variables. A variable should be thought of as standing for some definite but unidentified object. This is analogous to the use of a pronoun in natural language. Note that a variable is not simply a writable storage location as in most programming languages; rather it is a local name for some data object, like the variable of pure Lisp. Note that variables in different sentences are completely independent, even if they have the same name—the lexical scope of a variable is limited to a single sentence. To illustrate this, here are some examples of sentences containing variables, with possible declarative and procedural readings:

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

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

?- 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 procedure for a particular predicate is the sequence of clauses in the program whose head goals have that predicate as principal functor. For example, the procedure for a predicate concatenate of three arguments might well consist of the two clauses shown in (J) where concatenate(L1, L2, L3) means “the list L1 concatenated with the list L2 is the list L3”.

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

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, for example concatenate/3.