Quintus Prolog Manual Quintus Prolog Manual
This chapter gives an informal description of the semantics of Quintus Prolog.
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 which 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 which 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.
G-2-2: Types of Predicates Supplied with Quintus Prolog
Certain predicates are predefined by the Prolog system. Most of these cannot be changed or retracted. Such predicates are called built-in predicates.
Certain ones, however, can be modified or totally redefined. These are the hook predicates and the redefined predicates used in embedding.
G-2-2-1: Hook Predicates
Hook predicates are called by the system. They enable you to modify Quintus Prolog's behavior. They are either undefined by default (like portray/1 and message_hook/3) or else they have a simple default definition which is dynamic and/or multifile (like file_search_path/1 and library_directory/1, which are multifile by default).
If they do have a default definition, a definition provided by the user overrides it within the module where it is redefined. The idea of a hook predicate is that its clauses are independent of each other, and it makes sense to spread their definitions over several files (which may be written by different people).
G-2-2-2: Redefinable Predicates
Redefinable predicates exist to enable you to embed Prolog code within a program in another language. They have default definitions which are fairly complex. Source is provided for them. They are all in modules beginning with 'QU'. Sophisticated users may wish to provide alternative definitions of these modules. You can redefine embeddable predicates at run-time too, by simply compiling new versions of the QU_ module-file (see section I-2).
The key distinction is that it only makes sense to redefine embeddable predicates totally and globally. Hook predicates, on the other hand, can be extended piecemeal, and need not have any definition at all.
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 (A) which can be read as (B).
grandfather(X, Z) :-
(mother(X, Y)
| father(X, Y)),
father(Y, Z). (A)
"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." (B)
Such uses of disjunction can usually be eliminated by defining an extra predicate. For instance, (A) is equivalent to (C)
grandfather(X, Z) :- parent(X, Y), father(Y, Z).
parent(X, Y) :- mother(X, Y).
parent(X, Y) :- father(X, Y). (C)
Therefore, disjunction will not be mentioned further in the following more formal description of the semantics of clauses.
For historical reasons, the token '|', when used outside a list, is actually an alias for ';'. The aliasing is performed when terms are read in, so that (D) is read as if it were (E) thus you can use ';' instead of '|' for disjunction if you like.
a :- b | c. (D)
a :- b ; c. (E)
Note the double use of the '.' character. Here it is used as a sentence terminator, while in other instances it may be used in a string of symbols which make up an atom (for example, the list functor '.'). The rule used to disambiguate terms is that a '.' followed by a layout-character is regarded as the sentence terminator "full-stop", where a layout-character is defined to be any character less than or equal to ASCII 32 (this includes space, tab, newline, and all control characters).
G-2-4: Declarative and Procedural Semantics
The semantics of definite clauses should be fairly clear from the informal interpretations already given. However, it is useful to have a precise definition. The declarative semantics of definite clauses tells us which goals can be considered true according to a given program, and is defined recursively as follows:
A goal is true if it is the head of some clause instance and each of the goals (if any) in the body of that clause instance is true, where an instance of a clause (or term) is obtained by substituting, for each of zero or more of its variables, a new term for all occurrences of the variable.
For example, if a program contains the procedure for concatenate/3, declared in section G-2-1, then the declarative semantics tells us that (A) is true, because this goal is the head of a certain instance of the second clause ((K)
) for concatenate/3, namely (B), and we know that the only goal in the body of this clause instance is true, because it is an instance of the unit clause which is the first clause for concatenate/3.
concatenate([a], [b], [a,b])
concatenate([a], [b], [a,b]):-
concatenate([], [b], [b]).
Note that the declarative semantics makes no reference to the sequencing of goals within the body of a clause, nor to the sequencing of clauses within a program. This sequencing information is, however, very relevant for the procedural semantics which Prolog gives to definite clauses. The procedural semantics defines exactly how the Prolog system will execute a goal, and the sequencing information is the means by which the Prolog programmer directs the system to execute his program in a sensible way. The effect of executing a goal is to enumerate, one by one, its true instances. Here is an informal definition of the procedural semantics.
To execute a goal, the system searches forwards from the beginning of the program for the first clause whose head matches or unifies with the goal. The unification process (see "A Machine-Oriented Logic Based on the Resolution Principle" by J.A. Robinson, Journal of the ACM 12:23-44, January 1965) finds the most general common instance of the two terms, which is unique if it exists. If a match is found, the matching clause instance is then activated by executing in turn, from left to right, each of the goals (if any) in its body. If at any time the system fails to find a match for a goal, it backtracks; that is, it rejects the most recently activated clause, undoing any substitutions made by the match with the head of the clause. Next it reconsiders the original goal which activated the rejected clause, and tries to find a subsequent clause which also matches the goal.
For example, if we execute the goal expressed by the query (A) we find that it matches the head of the second clause for concatenate/3, with X instantiated to [a|X1]. The new variable X1 is constrained by the new goal produced, which is the recursive procedure call (B) and this goal matches the second clause, instantiating X1 to [b|X2], and yielding the new goal (C).
| ?- concatenate(X, Y, [a,b]). (A)
concatenate(X1, Y, [b]) (B)
concatenate(X2, Y, []) (C)
Now this goal will only match the first clause, instantiating both X2 and Y to []. Since there are no further goals to be executed, we have a solution
X = [a,b]
Y = []
That is, the following is a true instance of the original goal:
concatenate([a,b], [], [a,b])
If this solution is rejected, backtracking will generate the further solutions
X = [a]
Y = [b]
X = []
Y = [a,b]
in that order, by re-matching goals already solved once using the first clause of concatenate/3, against the second clause.
Besides the sequencing of goals and clauses, Prolog provides one other very important facility for specifying control information. This is the cut, written '!'. It is inserted in the program just like a goal, but is not to be regarded as part of the logic of the program and should be ignored as far as the declarative semantics is concerned.
The effect of the cut is as follows. When first encountered as a goal, cut succeeds immediately. If backtracking should later return to the cut, the effect is to fail the parent goal, that goal which matched the head of the clause containing the cut, and caused the clause to be activated. In other words, the cut operation commits the system to all choices made since the parent goal was invoked, and causes other alternatives to be discarded. The goals thus rendered determinate are the parent goal itself, any goals occurring before the cut in the clause containing the cut, and any subgoals which were executed during the execution of those preceding goals.
For example, the procedure
member(X, [X|L]).
member(X, [Y|L]) :-
member(X, L).
can be used to test whether a given term is in a list:
| ?- member(b, [a,b,c]).
returns the answer 'yes'. The procedure can also be used to extract elements from a list, as in
| ?- member(X, [d,e,f]).
With backtracking this will successively return each element of the list. Now suppose that the first clause had been written instead:
member(X, [X|L]) :- !.
In this case, the second call above would extract only the first element of the list ('d'). On backtracking, the cut would immediately fail the entire procedure.
Another example:
x :- p, !, q.
x :- r.
This is analogous to "if p then q else r" in an Algol-like language.
Note that a cut discards all the alternatives subsequent to the parent goal, even when the cut appears within a disjunction. This means that the normal method for eliminating a disjunction -- by defining an extra predicate -- cannot be applied to a disjunction containing a cut.
Prolog's unification does not have an occur check; that is, when unifying a variable against a term, the system does not check to see if the variable occurs in the term. When the variable occurs in the term, unification should fail, but the absence of the check means that the unification succeeds, producing a circular term. Trying to print a circular term, or trying to unify circular terms, will cause a loop. (You can always get out of a loop by typing Control-Parm(text) followed by an 'a' for abort.)
The absence of the occur check is not a bug or a design oversight, but a conscious design decision. The reason for this decision is that unification with the occur check is at best linear on the sum of the sizes of the terms being unified, whereas unification without the occur check is linear on the size of the smallest of the terms being unified. For any programming language to be practical, basic operations should take constant time. Unification against a variable may be thought of as the basic operation of Prolog, and this can take constant time only if the occur check is omitted. Thus the absence of an occur check is essential to Prolog's practicality as a programming language. The inconvenience caused by this restriction is, in practice, very slight. Furthermore, the functionality is available as library(occurs).
contact:
product support
sales information