Linguistics 482 - Computational Linguistics Prolog Notes A. C. Brett acbrett@uvic.ca
Department of Linguistics
University of Victoria
Clearihue C139
Last updated: 23 October 1999

Rules

Rules are the sentence-like constructs of Prolog that have the following form:
   [head] :- [body] .
where [head] denotes a structure called the head of the rule, the symbol :- is called the neck, and [body] denotes a sequence of structures called goals that comprise the body of the rule. As is the case with all Prolog clauses, rules must end with a period.

The body of a rule may actually be empty, that is, there are no goals between the neck symbol and the period that ends the rule. In this circumstance, the rule is equivalent to a fact. Hence, facts may be written as rules with empty, or null, bodies. It is for this reason that facts are sometimes described as degenerate rules.

The body may consist of just one goal; however, when there is more than one goal in the body of a rule, the goals must be separated from each other by commas. There may also be spaces between the goals, in addition to the commas.

A rule is employed in a proof when the Listener unifies a goal with the head of the rule, where the goal involved in this process might be in the body of another rule, or it might have been typed as a query. The Listener then attempts to prove the goals in the body of the rule according to the same procedure that it employs to prove queries or claims that have been typed. The Listener attempts to prove the goals in the order of their appearance, from left to right, in the body of the rule.

The rule is said to succeed if the Listener has been able to prove all the goals in its body. If the Listener encounters a goal that it cannot prove, then the rule is said to fail. When the Listener fails to prove goal, it will not attempt to prove any of the goals that might come after it in the body of the rule.

Since all the goals in the body of a rule must be proved in order that the rule succeed, the comma between the goals is usually read as the co-ordinating conjunction "and." Since the success of a rule is contingent upon a proof of all of the goals in its body, the neck symbol, :-, is usually read as the subordinating conjunction "if."

In a Prolog program that causes the Listener to function as a recogniser or parser of the sentences of a natural language, rules can be used to encode the rewrite rules of a context-free phrase-structure grammar for the language. For example, the following rules can be translations into Prolog of the rewrite rules in the comments to their right:

   np(X, Y) :- det(X), n(Y).    % NP --> DET N
   np(X, Y) :- a(X), n(Y).      % NP --> A N
The category labels in the Prolog rules are represented with lower case letters because they name structures, and hence, they must be atoms (notwithstanding category labels are normally represented with upper case letters, as shown in the rewrite rules in the comments). Sequences of characters that begin with an upper case letter represent variables in Prolog (which cannot be structure names).

The heads of both of the foregoing Prolog rules are the structure np(X, Y). The bodies of both rules consist of two goals. In the first rule, the goals are the structures det(X) and n(Y). The goals in the body of the second rule are the structures a(X) and n(Y).

If a program has been consulted that includes the foregoing rules, then these rules might be employed in the proof of a claim such as

   np(black, cats).
if this structure is typed at the Listener prompt.

Rules with structures in their heads that have the same name and number of arguments are tested in the order of their appearance in the program. Thus, the Listener will unify the goal np(black, cats) with the head np(X, Y) of the first rule. The atoms black and cats will be instantiated on the variables X and Y, respectively. The Listener will then attempt to prove the first goal in the body of the first rule. Since black has been instantiated on the variable X, the Listener will attempt to prove the goal det(black).

If lexical items have been coded as facts in the program, and determiners have been recorded as the arguments of structures with the name det, the Listener will attempt to unify the goal det(black) with one of these structures. Since there likely is no such structure among the facts, the Listener will fail in this attempt. Consequently, the goal det(black) cannot be proved, and hence, the rule containing it fails. The Listener will not attempt to prove the second goal, n(cats), in the body of the rule, but will instead go on to test the second rule.

Unification of the goal np(black, cats) with the head np(X, Y) of the second rule, together with the consequent variable instantiations, will yield the structure a(black) as the first goal in the body of the rule. If adjectives have been recorded among the facts as arguments of structures with the name a, and a(black) is among them, the Listener will unify the goal with this fact, and hence, will succeed in proving the goal a(black). It will then attempt to prove the second goal, n(cats). If there is a structure n(cats) among the facts in the program, the Listener will be able to prove the second goal. In this case, since both goals in its body can be proved, the rule will succeed. Consequently, the Listener will have obtained a proof of the goal np(black, cats).

The goal np(black, cats) may be translated into English as the claim that "black and cats comprise a noun phrase." The two rules that figure in the proof of this claim, namely,

   np(X, Y) :- det(X), n(Y).    % NP --> DET N
   np(X, Y) :- a(X), n(Y).      % NP --> A N
may themselves be translated into the following English sentence: wherein the variables function as place markers for words.

The two complex English clauses into which the two Prolog rules can be translated have been set off as separate points only for purposes of clarity. Pertinent conjunctions have also been underscored. Translation of the neck symbol, :-, as the subordinating conjunction "if", and translation of the comma separating goals in the body of a rule as the co-ordination conjunction "and", have already been noted above. The co-ordinating conjunction "or," however, has been introduced into the foregoing translation because the bodies of the two Prolog rules represent alternative constructions for noun phrases consisting of two words.

Two or more rules with head structures that have the same name and number of arguments, and facts consisting of structures with the same name and number of arguments, represent alternative proofs of a goal that unifies with the head or fact structure. Hence, the alternative clauses, whether they be facts or rules, may be translated as English clauses that can be conjoined by the conjunction "or" to form one English sentence. The conjunction "or" is sometimes identified as a "disjunctor," and the clauses it connects are described as being "disjoined" alternatives.

The Listener attempts to prove a goal by testing disjoined alternative rules and facts in the order of their appearance in the program. The Listener will obtain a proof of the a goal as soon as one of the alternative rules succeeds, or the goal unifies with one of the alternative facts. It will not test any of the alternative facts or rules in the program that might follow the successful rule or fact. For example, if the rules representing alternative constructions for two-word noun phrases were to appear in the program in the following order:

   np(X, Y) :- a(X), n(Y).      % NP --> A N
   np(X, Y) :- det(X), n(Y).    % NP --> DET N
and the claim np(black, cats) were typed, then the first rule will yield a proof of the claim, and the second alternative will not be tested.

In the foregoing example, the Listener used rules in the program to prove a goal that had been typed. The Listener, however, may also use these rules to prove goals that appear in the bodies of other rules. For example, suppose that a program has been consulted that includes the following rules:

   % S --> NP VP  (V, W, X, Y, and Z comprise a sentence if V and W
   %               comprise a noun phrase, and X, Y, and Z comprise
   %                                           a verb phrase.)

     s(V, W, X, Y, Z) :- np(V, W), vp(X, Y, Z).

   
   % VP --> V NP  (X, Y, and Z comprise a verb phrase if X is a verb,
   %                               and Y and Z comprise a noun phrase.)

     vp(X, Y, Z) :- v(X), np(Y, Z).


   % NP --> DET N | A N  (X and Y comprise a noun phrase if X is a
   %                      determiner and Y is a noun or, if X is an
   %                       adjective and Y is a noun.
   %                      Note that the vertical stroke separates
   %                                alternative right-hand sides.)

     np(X, Y) :- det(X), n(Y).
     np(X, Y) :- a(X), n(Y). 
If the program also includes the following facts:
   % A --> black | good | bad 
     a(black).   a(good).   a(bad).  % More then one clause may be
                                     % typed on a line.
   % DET --> some | those
     det(some).  det(those).

   % N --> cats | luck
     n(cats).    n(luck).

   % V --> bring
     v(bring).
and the following claim is typed as the prompt:
   s(black, cats, bring, good, luck).
then the Listener will unify this goal with the head structure s(V, W, X, Y, Z) of the rule corresponding to the rewrite rule S --> NP VP. The atoms in the arguments of the goal structure will be instantiated on the variables, and the Listener will attempt to prove the goals np(black, cats) and vp(bring, good, luck) in the body of the rule.

The first of these goals will be proved as descibed above where its proof as a claim typed at the Listener prompt was discussed. Since there is a proof of this goal, the Listener will attempt to prove the second goal, vp(bring, good, luck), by unifying it with the head structure vp(X, Y, Z) of the rule corresponding to the VP --> V NP rewrite rule.

The Listener will then prove the first goal, v(bring), in the body of the rule by unifying it with the fact v(bring), and then prove the second goal, np(good, luck), by following the procedure already described. Since it can prove all of the goals, the Listener will have obtained a proof of the claim that "The sequence of words black, cats, bring, good, luck comprises a sentence."

Linguistics 482 Prolog Introductory Notes Top of Page