Tutorial 2

Rules
Lists
exercise 2

Rules

A rule is convenient a way of creating a handle for an often used complex query, just as a subroutine is a handle for a complex set of instructions in a procedural programming language. In exercise 1 we saw how the solutions to the conjoined query

?- sum(P1,P2,Z), sum(Z,P3,6).

solve the distribution problem for P=3 and N=6. Instead of typing in the query in full each time we wanted to use it, we might define the following rule:

dist3(P1,P2,P3) :- sum(P1,P2,Z), sum(Z,P3,6).

Instead of writing the original complex query, we could now write:

?- dist3(X,Y,Z).

and expect to see a set of solutions for X, Y and Z such that X+Y+Z = 6. Notice that query variables need not have the same names as those in the rule. A better way to think of such variables is as "place holders".

In defining rules, we are at liberty to choose the number of parameters, so that a more general rule might parametrize the total sum, i.e.

dist3(P1,P2,P3,N) :- sum(P1,P2,Z), sum(Z,P3,N).

Variable Scope

Variables are local to both rules and queries. Within a rule, multiple occurrences of the same variable (such as the two occurences of N above) refer to the same thing.

However, variables in different rules are disjoint. P1 and P2 in

father(P1,P2) :- parent(P1,P2), male(P1).

have nothing to do with the P1 and P2 in dist_3. We should also note that the names we actually give to variables are conventional. If we substitute for them consistently, we do not change the meaning of the rule. So the above rule can also be expressed:

father(P,Q) :- parent(P,Q), male(P).

In fact, internally, variables are represented as integers, which are underlined to distinguish them from real integers (e.g. _456). These are sometimes seen when debugging using the tracer.

Rule Syntax

Note that the rule above consists of

A left hand side or "head", which has the same shape as a fact.
A right hand side which is identical to the original conjoined query. It comprises a list of queries or subgoals.
The symbol :- which separates the two parts.

Being just another kind of clause, the rule is must be terminated by a period. It is included in a program file along with other clauses, whether they be facts or rules.

Rule Semantics

The semantics of a rule must be seen in the context of what happens when a single query is processed. The first step is to search the database for a set of matching clauses, which might be facts or rules. In tutorial 1 we looked at the process of matching queries against facts. Now we turn to how a query can match a rule.

Matching Rules

A rule matches whenever the head of the rule matches the query in just the sense explained for a fact, i.e.
- matching predicate name (or functor)
- matching arguments
- same number of arguments
The head of a rule contains variables such as P1, P2 and P3 in the rule
```
dist3(P1,P2,P3) :- sum(P1,P2,Z), sum(Z,P3,6).
```
With the matching query
```
?- dist(X,Y,3)
```
certain variable bindings are created (X=P1 Y=P2 and P3=3).
A rule instance is created under those variable bindings. In this case
```
dist3(X,Y,3) :- sum(X,Y,Z), sum(Z,3,6).
```
Unlike a fact, a rule has a right hand side which specifies a list of subgoals that must be achieved for the original query to hold. The above query thus leaves us with the subgoals
```
sum(X,Y,Z), sum(Z,3,6)
```
which are executed in order. Each solution (there may be several or none) yields a complete set of variable bindings for X, Y and Z. However, only some of them, X and Y, are part of the original query, the Z being "internal" to the right hand side of the rule.
The only bindings returned by Prolog are those which are unbound in the original query or goal, i.e. X and Y.

Mike Rosner (mros@cs.um.edu.mt)