Part III: Programming

Introduction

This part gives a general introduction to Prolog. Most of what we say is not specific to Prolog+CG, and can be used in any Prolog environment. We will note, however, when something is specific to Prolog+CG.

An example

Just to whet the appetite, here is an example of a Prolog program written in Prolog+CG. Even though most of Part III is about general Prolog, we will make an exception here and include a CG-parts, which are otherwise only a part of Prolog+CG.

// Type-hierarchy
entity > Person, Act, Haste, Utterance, 
         Proposition, Situation, Manner.
Manner > Loud, Quiet, Wisely, Slow, Fast, Sudden.

// Type-instances
Person = Romeo, FriarLawrence.
Act = Insist, Walk, Run, Stumble.

// CG 1:
// Romeo cries to Friar Lawrence: "I stand on
// sudden haste."
[Utterance]-
         -Agnt->[Person: Romeo],
         -Rcpt->[Person: FriarLawrence],
         -Manr->[Loud],
         -Thme->[Proposition =
                     [Act: Insist]-
                       -Agnt->[Person: I],
                       -Thme->[Situation =
                                  [Haste]-Attr->[Sudden]
                                ]
                  ]
.

//
// CG 2:
// Friar Lawrence says to Romeo: "Wisely and slow,
// they stumble that run fast."
[Utterance]-
         -Agnt->[Person: FriarLawrence],
         -Rcpt->[Person: Romeo],
         -Manr->[Quiet],
         -Thme->[Proposition =
                  [Proposition =
                          [Act: Walk]-
                            -Manr->[Wisely],
                            -Manr->[Slow]
                  ]-Reas->[Proposition =
                              [Act: Stumble]-
                               -Agnt->[Person=  
                                       [Act: Run]-
                                         -Manr->[fast]
                                         -Agnt->[Person]
                                      ]
                          ]
                ]
.

//
// Who talks to whom?
Talk(A,R) :- [r:A]<-Agnt-[Utterance]-Rcpt->[s:R].

This example is available in the AAU directory as "Romeo1.plgCG".

The lines beginning with "//" are comments. The example illustrates the following exchange between Romeo and Friar Lawrence:

Romeo: "I stand on sudden haste!" (I.e., I insist that we haste immediately to proceed with our plans, namely to marry me and Juliet.)

Friar Lawrence: "Wisely and slow. They stumble that run fast."

Difficult things

Now let us say something about the following material. Sometimes, the going may seem to be rough. If this is the case, we advise you to slow down and read slowly, making sure you understand each step in the presentation or explanation. If something is unclear at the moment, perhaps there will be examples later which clarify. Once you have seen these examples, if you still do not understand, it is good to go back and read the presentation again.

Next

Next, we look at the basic datatype in Prolog, namely terms.


Terms

Six kinds of terms

In Prolog, as in many programming languages, a number of different kinds of data are available. For example, numbers and strings are two of the ones available in Prolog. In Prolog, all of the kinds of data are grouped under the general heading of "term". Here is a complete list of all of the different kinds of data available in standard Prolog (Prolog+CG has a few others in addition to these -- we will get back to them later):

For now, we will not go into detail with what these are and what they mean. We will save the details for later. Instead, we will just give an example of what each of the six different kinds of data looks like:


Relationships

Introduction

Before we go into detail with what a structure is, we need to look at what a relationship is.

Three examples

For example, the following are all relationships, expressed in the syntax of Prolog:

  1. father(abraham, isaac)
  2. child(isaac, abraham)
  3. plus(2,3,5)

Meaning of the examples

The first relationship says that Abraham is the father of Isaac. The second relationship says that Isaac is the child of Abraham. The third relationship says that two plus three equals five. We will get to the details of the syntax in due course.

Relationships are central

When describing an application-domain in Prolog, relationships are central. Therefore, it is necessary to learn how to identify relationships, their participants, and their central or main participant (if any).

Primary and secondary participants

For example, in the "father" relationship, there are two participants: The father and the son (or daughter). In this relationship, the father is the central or main participant, since the relationship gets its name after him. It is customary (but not necessary) to write the central or main participant as the first participant in the relationship. That is why the above relationship is written as "father(abraham, isaac)" rather than "father(isaac, abraham)".

In the "plus(2,3,5)" example, the two first participants ("2" and "3") are equally important, but they are both more important than the result ("5"). Therefore, we place the result at the end of the relationship.

We can also say that the two numbers to be added are "primary", whereas the result is "secondary". Likewise, in the "father" relationship, the father is "primary", whereas the son or daughter is "secondary".

Exercise

Exercise: Can you identify the relationship, the three participants, and the primacy of each participant, in the following sentence: "John gave Marty a book"?

Summary

Thus relationships are central in Prolog programming, all relationships have at least one participant, the participants can usually be assigned an importance amongst themselves, and we usually place the more important participants first in the written form of the relationship.


Structures

Introduction

In Prolog, relationships are expressed as "structures". This page defines what a structure is and introduces some vocabulary to describe structures.

Example

An example of a structure could be:

birthday(Albert, 14, March, 1879)

We can interpret this to mean that a person named "Albert" was born on March 14, 1879.

Definition

A structure consists of the following:

  1. A functor (e.g., "birthday")
  2. A list of arguments (e.g., "Albert", "14", etc.) enclosed in parentheses.

The functor

The functor is simply a name we give to the structure. The functor must be an identifier. In Prolog+CG, an identifier is a sequence of letters, underscores, and digits, with the requirement that the first two characters must be letters.

Arguments

Each argument to the structure can be any term.

Arity

The number of arguments is called the arity of the structure. For example, the "birthday" structure has arity 4.

Notation

The following notation is used for the name and arity of a structure:

functor/arity

For example:

birthday/4

Zero arity

A structure can have an arity of zero or more. When the arity us zero, there are no arguments, and consequently, we don't write the parentheses either. For example:

Albert

is really also a structure. We call it an atom. Thus "atom" is a special name we give to structures with arity 0.

Syntax of structures

The syntax of structures is as follows. A structure is either:

There must be no space between the functor and the open-parenthesis.

Summary

Structures consist of a functor and a comma-separated list of arguments enclosed in parentheses. The functor must be an identifier. The arguments must be terms. The arity of a structure is the number of arguments it has. A structure with arity 0 has no list of arguments, and is called an atom. We use the notation "functor/arity" to identify structures, e.g, "birthday/4".

Next

It must be remembered that structures are just one kind of term. There are five other kinds of term, one of which is string constants. We look at string constants next.


String constants

Introduction

Besides structures, another kind of term is the string constant. A string constant is a sequence of characters enclosed in double quotes.

Examples

For example, the following are all string constants:

Double quotes can't be included in a string

The string constant starts and ends with a double quote. That gives rise to a problem: Can one include a double quote in a string? If we include a double quote, Prolog+CG will assume that the string is finished. Unfortunately, there is no way to include a double quote in a string in the present version of Prolog+CG.

Summary

Thus string constants are one kind of term, they are sequences of characters enclosed in double quotes, and there is no way to include a double quote in a string.

Next

We have treated two kinds of terms: Structures and string constants. Next, we treat another kind of term, namely atomic constants. We have already briefly touched upon this when we said that atoms were structures with arity 0. Now we treat them more fully.


Atomic constants

Introduction

Atomic constants is another kind of term. We have already come across atomic constants, because atomic constants are nothing more than structures with an arity of 0. Thus atomic constants are just functors with no arguments in parentheses.

Atomic constants are also called atoms.

A functor is an identifier

Remember that a functor must be an identifier. An identifier is a sequence of letters, digits, and underscores (_), where the first two characters are letters.

Examples

For example, the following are all atomic constants:

What is often the reality behind atomic constants?

Good candidates for atomic constants are single entities with a name. For example, Albert Einstein is a single entity with a name. Therefore, his name is a good candidate for being an atomic constant.

No spaces in atoms

Notice that an identifier (and therefore, an atomic constant), cannot contain spaces. Hence, the following are not atomic constants:

We could instead write these as:

Contracting names with spaces into names without the spaces is common practice in programming.

Another common practice is to place underscores in between the words:

Which we choose doesn't matter, since the identifiers are nothing more than meaningless strings to the computer.

Summary

An atomic constant (or simply, an atom) is a structure with arity 0. So it is just a functor. A functor is an identifier. The reality we wish to describe with atoms is often single entities with a name. Atoms cannot contain spaces, because identifiers cannot contain spaces. The two common solutions to this problem is either to contract the words or to place underscores in between the words.

Next

As we know, there are six kinds of terms. So far, we have treated structures, string constants, and atomic constants. If you want to revise what the others are, you can go back to this page. Next, we treat numeric constants.


Numeric constants

Introduction

Another kind of term is numeric constants. Numeric constants represent specific numbers, either integers or real numbers.

Integers

Integers are whole numbers and look like this:

Real numbers

Reals are numbers with decimal fractions, and look like this:

Summary

Thus numeric constants are numbers, and can be either integers or real numbers. They can be positive or negative.

Next

It is time we have a quiz. The next page will be just that. When the quiz is done, we will go on to a new chapter, leaving the other two kinds of term (lists and variables) for later. The next chapter introduces you to a simple Prolog program.


A simple Prolog program

Students and their semesters

We have looked at what a term is. We have seen four of the six kinds of terms. Now we combine this knowledge into a small, complete program. Consider the following Prolog program:

student(Lisa, 5).
student(Martin, 3).
student(John, 3).
student(Edward, 7).

It is available as the file "Students1.plgCG" in the AAU sample directory.

The program consists of four facts, each of which consists of a structure and a period ("."). Each structure denotes a relationship between a student's name and the semester at which the student is studying. Thus Lisa is in the fifth semester, while Martin is in the third, etc.

We will reprint this sample program on subsequent pages when necessary.


Facts and the program database

Example program

Consider the program from the previous page:

student(Lisa, 5).
student(Martin, 3).
student(John, 3).
student(Edward, 7).

Definition of a fact

As was said, this program consists of four facts. A fact is simply the following:

In the example above, "student(Lisa, 5)" is a structure. Structures are terms. What makes the whole expression a fact is the period that follows it.

The structure can have arity 0

A fact can be any kind of term (except a variable) followed by a period. If the term is a structure, the structure can have arity 0, in which case it is also called an atomic constant. For example, the following is a fact:

it_is_raining.

Of course, the structure can also have an arity greater than 0, just as in the example program above.

The program database

A simple program can consist entirely of facts. Together, these facts make up what we call the program database. The facts are seen as data in a database. And since the facts also simultaneously make up the program, we call them the "program database". This principle is called "program as data," where the program itself is the data. In other programming languages, there is usually a sharp distinction between what is program and what is data, but not in Prolog.

Summary

Thus a fact is a structure followed by a period. The facts of a Prolog program make up the "program database". In Prolog, there is no sharp distinction between what is program and what is data, and this principle is called "program as data".

Next

Next, we look at queries. Queries are questions we ask of the program database.


Queries

Introduction

We saw earlier that the way to interact with the Prolog system is to write queries and get a response. On this page, we look at queries in a little more detail.

Example program

Again, consider the by now familiar example program:

student(Lisa, 5).
student(Martin, 3).
student(John, 3).
student(Edward, 7).

An example query

If we ask the following question of the Prolog+CG system:

?- student(Lisa,5).

we get the following response:

{}

This requires some explanation.

Explanation

The

?-
sequence of symbols means "here starts a query." Prolog+CG prints it for you automatically in the query-area, and you don't need to write it. However, in these notes we will always write it in front of queries to show that we are dealing with a query.

The

{}
sequence of symbols means "yes". The question we asked:

?- student(Lisa, 5).

could be paraphrased as "Does there exist a student named Lisa who is in the fifth semester?", and since there was a fact in the database to match this query, the answer was "yes" or "{}".

A Query is terminated with a period

It will be noticed that the query, like a fact, is terminated with a period. You must always terminate your queries (as well as your facts) with a period.

When a query fails

If we asked the following question:

?- student(Abraham, 3).

the response would be:

no.

The reason is that there is no fact in the program database saying that there is a student named Abraham in the third semester. We say that the query fails.

Summary

Queries start with

?-
, but you don't need to write this -- Prolog+CG writes it for you on the screen. If the answer to a question is "yes", the response will be
{}
. If the answer to a question is "no", the response will be
no.
. Queries must be terminated with a period.

Next

Next, we look at goals and subgoals in queries. This is essential terminology when talking about Prolog queries and programs.


Goals and subgoals

Example program

Again, we reprint the example program:

student(Lisa, 5).
student(Martin, 3).
student(John, 3).
student(Edward, 7).

Goals

Consider the following query:

?- student(Lisa, 5).

In this query, the structure

student(Lisa, 5)

is a goal. Prolog tries to satisfy the goal when answering the query. The process involved when Prolog tries to satisfy a goal will be explained in detail later.

Goals and subgoals

There can be more than one goal in a query. In this case, we talk about the different subgoals of the query. Subgoals must be separated by commas, and again the whole query must be terminated with a period.

Example with two subgoals

For example, the following would be a query with two subgoals:

?- student(Lisa, 5), student(John, 3).

The answer to this query is:

{}

meaning "yes". The answer is "yes" because both of the subgoals can be satisfied.

All subgoals must be satisfied

If even just one subgoal could not be satisfied, the whole of the query would fail. For example, the answer to the following query:

?- student(Lisa, 5), student(Abraham, 3).

would be:

no.

because the second subgoal would fail even though the first would succeed.

Summary

Thus a query is made up of a comma-separated sequence of structures, terminated by a period. Each structure is called a subgoal. When answering a query, Prolog tries to satisfy each subgoal in turn, from left to right. If all of the subgoals can be satisfied, the query succeeds. If just one subgoal fails, the whole query fails.

Next

Now that we know that Prolog tries to satisfy subgoals in a query, we need to look at how this is done. Explaining this will require us to look at a concept called "matching". We look at this next, albeit not in detail yet.


Matching

The process of trying to satisfy a (sub)goal involves the operation called matching. When trying to satisfy the subgoal

student(Lisa, 5).

Prolog tries to find a matching fact in the database. We will get back to the details of how matching occurs later. For now, it is sufficient to note that when trying to satisfy a (sub)goal, Prolog uses a process called "matching" to find the answer to the query.

Next

In order to understand matching, we will also need to know what a variable is. The next page introduces what variables are.


Variables

Example program

Again, we reprint the example program:

student(Lisa, 5).
student(Martin, 3).
student(John, 3).
student(Edward, 7).

Using a variable

Consider the following query:

?- student(Lisa, X).

The answer is:

{X = 5}

What we have just seen is an example of the usage of a variable in a query. The variable "X" was used to ask which semester Lisa was in.

What is a variable?

A variable is a piece of data whose value we do not know. It will be remembered that variables are a kind of term. This means that wherever we can use a term, we can also use a variable.

How did Prolog find the answer?

To answer the query just given, Prolog tried to match the goal with all of the facts of the database. It turned out that only the first fact matched, and X was bound to the value "5". This was reflected in the answer.

The answer was not "no." Therefore, we say that the query succeeded, just as if the answer had been "{}" meaning "yes".

Real meaning of {}

We see now that "{}" means "the query succeeded, but there were no variable bindings."

Another example of variable usage

We could also have asked the following question:

?- student(Y, 3).

The answer would be:

{Y = Martin}
{Y = John}

Now we would get two answers, because two facts in the database matched the goal. In effect, the variable Y would first be bound to the value "Martin", then the binding would be broken, and the variable would be rebound to the value "John". We will get back to how this actually happens later.

Yet another example of variable usage

If we asked the following question:

?- student(Martin, S), student(John, S).

the answer would be:

{S = 3}.

The answer is computed as follows:

  1. Prolog tries to satisfy the first subgoal, "student(Martin, S)". This succeeds, with the variable binding {S = 3}.
  2. Next, Prolog tries to satisfy the subgoal "student(John, 3)". This subgoal can also be satisfied, and the query succeeds.

Free variables and bound variables

Notice how, in the second step, the occurrence of "S" has been substituted with the variable binding already obtained for S. Before the first step, S is a free variable, while in the second step, the variable is a bound variable.

Variable syntax

In Prolog+CG, a variable is any sequence of letters, underscores, and digits that:

  1. starts with a letter or an underscore, and
  2. which does not start with two letters.

For example, "X", "_garble", "r2d2", "c3po", and "f77" are all variables. However, "garble" is not a variable because it starts with two letters. Instead, it is an identifier. In addition, "13r9" is not a variable because it does not start with a letter or an underscore.

Summary

A variable is a placeholder for a piece of data whose value we wish to compute. Variables are terms just like structures and string constants, so you can use a variable anywhere you can use a term. Variables can either be free or bound. A bound variable is a variable that has a value, while a free variable does not yet have a value. Variables have special syntax that you need to learn and learn well.

Next

Next, we look at structures within structures.


Structures within structures

Context

When we defined what a structure is, we gave the following definition:

A structure is either:

Structures can be arguments

Notice that an argument is a term. Since structures are a kind of term, it follows that we can have structures within structures.

Example

For example, the following would be a more telling way of writing the relationship between a student and the semester in which he or she is:

student(name(Lisa), semester(5)).

We see that "name(Lisa)" and "semester(5)" are both structures, and thus we have written two structures inside of a greater structure, namely "student/2".

Rewriting the students program

We can now rewrite the example program so that it becomes a little more readable:

student(name(Lisa), semester(5)).
student(name(Martin), semester(3)).
student(name(John), semester(3)).
student(name(Edward), semester(7)).

This is available as "Students2.plgCG".

Asking queries

If we now ask the query:

?- student(N,S).

we get the following answer:

{N = name(Lisa), S = semester(5)}
{N = name(Martin), S = semester(3)}
{N = name(John), S = semester(3)}
{N = name(Edward), S = semester(7)}

notice how each variable is bound to a structure.

Atoms are structures as well (so we already know this)

Notice also that in the original example, we already had structures within structures: In the fact

student(Lisa, 5).

"Lisa" was an atomic constant. And since atomic constants are a special kind of structure (with arity 0), we already had examples of structures within structures.

Thus, since the arguments of structures are terms, and since a structure is a kind of term, we can have structures within structures. This is often helpful when we need to make programs more readable.

Next

Next, we have a summary.


Summary

Facts

Facts make up the program database of a simple Prolog program. A fact consists of a term and a period. The term can't be a variable.

Queries

Queries are questions written in the syntax of Prolog. A query must be terminated with a period. We don't write the initial "?-" because the Prolog system does this for us. The answer can either be

{}

meaning "Yes", or it can be

no.

meaning "No". (This is a slight simplification, which we will have occasion to correct below.)

Subgoals

A query is made up of one or more subgoals. When Prolog attempts to answer a query, it tries to satisfy the subgoals. All of the subgoals in the query must be satisfied for the query to succeed.

Matching

Matching is the process used when satisfying subgoals. We will get back to matching in detail later.

Variables

Variables are names we give to memory storage locations within the computer. They are used to refer to values which we wish to compute. A variable can be free, meaning it does not have a value, or it can be bound, meaning it has been given a value. When answering queries whose subgoals contain variables, the result is a list of variable bindings, such as the following:

{X = 5}

Structures within structures

Because the arguments of a structure are terms, and since structures are also terms, it follows that we can have structures within structures.


Matching

Introduction

We said earlier that when Prolog tries to satisfy a (sub)goal, one process involved was that of matching. Matching is also called "unification" in the literature, and refers to the process whereby terms are compared with each other while variable bindings are made.

Matching is one of the most important processes to grasp when trying to understand how Prolog works. In the following pages, we will take a detailed look at matching.


Rules of matching

The rules of matching are actually quite simple, though it takes some work to get used to understanding how matching works. On this page, we will list the rules, and on three subsequent pages, we will give three examples of how the rules are used in practice.

The rules of matching are as follows:

Rule 1: Constants

Two constants (string constants, numeric constants, and atomic constants) match if they are the same.

For example, "abc" matches "abc", 12 matches 12, and Lisa matches Lisa.

However, "12" does not match 12, since they are two different kinds of constants (a string constant and a numeric constant). Likewise, "Lisa" does not match with Lisa (a string constant and an atomic constant).

Rule 2: Structures

Two structures match if:

  1. The two functors are the same, and
  2. Their arities are the same, and
  3. All of the arguments match, from left to right.

    It is important that the matching occurs left to right because variables can occur more than once in a structure. If a variable binding occurs at an occurrence to the left in the structure, then the same binding will be used later in the structure.

Rule 3: Variables

Variable binding

When a variable is matched, a variable binding occurs. Thus there is a side-effect to the matching: Not only does the matching occur, but the variable in question is bound to a value (or another variable).

Free variables

A free variable A matches:

  1. Any structure or constant. A is bound to the value of the structure or constant.

    However, A only matches a structure B if A is not also a part of B. For example, X does not match foo(X).

  2. Another variable B. The two variables are bound to each other (this is called "sharing").

    If B is already bound, A is bound to the same value as B.

    If B is a free variable, then A also remains free. However, if either A or B is later bound to a value, then both are bound to the same value, since they are bound to each other.

Bound variables

A bound variable A matches another term B if the term that A is bound to matches the term B. For example, if A has the following variable binding:

{A = name(Nick)}

then A matches the structure

name(Nick)

A also matches the following structure:

name(B)

provided B is a free variable (see above). In this case, B is bound to Nick.

Next

That was a lot of detail in a very short stretch of space. On the following three pages, we will look at three examples explaining the three rules. However, we will not do this so that the first example explains the first rule, the second example explains the second rule, etc. We will not do this. Instead, we will give three examples that will hopefully enable you to understand all of the three rules of matching.


Example I

Introduction

In this and the following two examples, we will try to match two terms. We will spell out the steps taken by the Prolog system in matching, and refer to the rules given on the previous page.

Example

We can try to match the following two terms:

1) person(Nick, G)

with

2) person(Nick, gender(male))

Matching the two structures

The two terms are structures, so we invoke rule 2 and see whether they match:

  1. They have the same functor ("person"), so the first requirement is taken care of.
  2. They have the same arity (2), so the second requirement is taken care of.
  3. But do their arguments match, from left to right?

In order to check 3., we try to match the arguments from left to right.

Matching the first argument

Nick (from term 1) is an atomic constant. According to rule 1, constants match other constants if they are the same. This is the case, since Nick (from term 2) is also an atomic constant and is the same as the Nick from term 1.

So we proceed to the next argument. Does "G" match "gender(male)"?

Matching the second argument

According to rule 3, free variables match any constants and structures, and the variables are bound to the value of the constant or structure. "gender(male)" is a structure, so G matches "gender(male)". In addition, G is bound to the value "gender(male)".

Conclusion

Thus the overall result is that the matching succeeds, and G is bound to "gender(male)".

Next

Next, we proceed with the second example out of three.


Example II

Example

In this example, we match

1. person(Nick, gender(male))

with

2. person(N, gender(male))

Matching the two structures

Again, the top-level term is a structure, so we invoke rule 2. The two structures have the same functor and arity, but do their arguments match?

Matching the first argument

Nick matches N because N is a free variable, and Nick is an atomic constant (rule 3). N is bound to the atomic constant Nick.

Matching the second argument

Does

gender(male) 

(from term 1) match with

gender(male) 

(from term 2)?

Well, they are both structures, so we invoke rule 2. They both have the same functor ("gender") and arity (1), so we try to see whether their arguments match.

male (from term 1) matches male (from term 2) because they are both atomic constants and they are the same (this is rule 1).

Thus the overall result is that the matching succeeds, with the variable N bound to the value Nick.

Next

Next, we look at a third and final example.


Example III

Example

In this example, we try to match the term

1. person(Nick, gender(male))

with the term

2. person(N,N)

Exercise

It is a useful exercise for you to arrive at an answer before reading on. Take a moment to do so now.

Matching the two structures

Again, the top-level term is a structure whose functor (person) and arity (2) are both the same. (Rule 2.) So we try to match the individual arguments, from left to right.

Matching the first argument

Nick matches N because N is a free variable, and "Nick" is an atomic constant. N gets bound to the value "Nick". (Rule 3.)

Matching the second argument

However, when trying to match the next two arguments, N is already bound, to the value "Nick". Thus we try to match the atomic constant "Nick" with the structure "gender(male)". This does not succeed. Although both are structures, they have neither the same functor nor the same arity (rule 2).

The variable binding is undone

The variable binding

{N = Nick}

is undone because the match fails. Thus the result of the match is that the match fails, with no variable bindings.

Summary

Matching is a key process when Prolog tries to satisfy a goal. Matching occurs according to three rules which must be understood and remembered.

Next

Hopefully by now you have a good understanding of how matching works. If not, we suggest you go back and read the chapter again.

Next, we have a quiz.


Rules

Introduction

Prolog has two kinds of programming statements: Facts and rules. So far, we have looked at facts. But Prolog with only facts is only half a Prolog. In order to utilize the power of Prolog, rules are needed. This chapter is on Prolog rules.

Overview of this chapter

We will first give an example of a Prolog rule. Then we will introduce some terminology necessary for talking aboout rules and what is called Prolog clauses (facts is one kind of clause; rules are the other kind of clause). After that, we will say a little about when two occurrences of a variable name refers to the same variable (variable scoping rule). After that, we will present a technique for solving a common programming problem in Prolog: How do we return a value from a rule. Finally, there is a quiz.


Example of a rule

Old students program

We begin our treatment of rules with an example. Consider the familiar program describing students and their semesters:

student(name(Lisa), semester(5)).
student(name(Martin), semester(3)).
student(name(John), semester(3)).
student(name(Edward), semester(7)).

Three interesting problems

One interesting problem would be: Given the names of two students, how can we easily find out whether they are in the same semester?

Another problem would be: Given the name of one student, which students are in the same semester as this student?

And finally, a third problem would be: Which pairs of students are in the same semester?

The solution

The solution to all of these problems turns out to be solvable by means of a rule. Consider the following rule:

same_semester(A,B) :- student(A,S), 
                      student(B,S).

This rule, along with the students database, can be found in "Students3.plgCG".

Meaning of rule

The rule means "A and B are in the same semester IF we can find student A in semester S, AND THEN we can find student B in semester S (the same semester)".

Application of rule

There are three ways this rule can be applied:

We will treat each of these in turn.

Two known students

If we now ask:

?- same_semester(name(Martin), name(John)).

the answer is:

{}

meaning "yes". This is because we can find two students with the names Martin and John in the same semester.

If we ask

?- same_semester(name(Martin), name(Lisa)).

the answer is:

no.

This is because Martin and Lisa are not in the same semester. Thus, while the first subgoal in the rule succeeded with the variable binding

{S = semester(3)}

the second subgoal did not succeed, since S was not bound to

semester(5)

and thus the matching failed.

One unknown student

What happens if we use a variable instead of one of the names? Let's try:

?- same_semester(name(Martin), X).

Perhaps a bit surprisingly, the answer is:

{X = name(Martin)}
{X = name(John)}

We see that John is an answer to the question, but we also see that Martin himself is in the set of answers. But this is just because we haven't included anything in the rule to say that students who are themselves should not be included in the answer. So, in fact, we got what we asked for. Logically, the answer is correct.

Two unknown students

Finally, let us ask which pairs of students are in the same semester.

?- same_semester(X,Y).

The answer is:

{X = name(Lisa), Y = name(Lisa)}
{X = name(Martin), Y = name(Martin)}
{X = name(Martin), Y = name(John)}
{X = name(John), Y = name(Martin)}
{X = name(John), Y = name(John)}
{X = name(Edward), Y = name(Edward)}

It will be noted that all students in the database are listed in the answer as being in the same semester as themselves. This was to be expected, given the answer to the previous question. It will also be noted that both "Martin,John" and "John,Martin" are listed. The reason for all of this will become clear in the next chapter on Prolog's solution strategy.

Next

Now let us turn from this example to some useful terminology.


Terminology

Introduction

In this section, we present some terminology which is both useful and necessary when talking about Prolog programs. The terminology introduced is:

  1. Head
  2. Entails
  3. Body
  4. Subgoal
  5. Fact
  6. Clause
  7. Invocation
  8. Predicate

Head, Entails, Body

The syntax of a rule is as follows:

head :- body.

The symbol ":-" is pronounced "Entails" for reasons that will become clear in a moment.

What precedes the ":-" 'entails' symbol is the head of the rule, while what follows the 'entails' symbol is the body of the rule. The rule is terminated with a period.

Looking at our example rule:

same_semester(A,B) :- student(A,S), 
                      student(B,S).

we see that "same_semester(A,B)" is the head, while "student(A,S),student(B,S)" is the body of the rule.

A rule can be read as "The body entails the head." Put another way, "We have proved the head if we can prove the body." We will get back to this in the chapter on Prolog's solution strategy.

A head can be any Prolog+CG data except variables, lists, and numeric constants.

Subgoal

The body of a rule consists of one or more sub-goals. We have already met the term "subgoal" in connection with queries. For queries, we have seen that a query is made up of one or more subgoal, such as the following query:

?- student(Lisa, 5), student(John, 3).

This query contains two subgoals: "student(Lisa, 5)" and "student(John, 3)". The subgoals are separated by a comma.

Likewise, the body of a rule consists of one or more subgoals. The subgoals are separated by commas. The body of the example rule is:

student(A,S), student(B,S)

with two subgoals.

Fact

Recapitulation

We have already met facts, such as:

student(name(Lisa), semester(5)).

The syntax of facts is as follows:

Head.

Meaning of facts (for the specially interested)

A fact is a head followed by a period.

Facts are really a special kind of rule: There is an invisible 'entails' (":-") symbol, followed by "true". Thus what a fact really means is, for example:

student(name(Lisa), semester(5)) :- true.

which means "We have proved that Lisa is a student in the fifth semester if we can prove true." Since we can always prove "true", we can always prove that Lisa is a student in the fifth semester. Thus it is a "fact" that Lisa is a student in the fifth semester.

Clause

We are now in a position to say what a clause is. The clause is the basic programming unit in Prolog. A clause is simply either a fact or a rule. Thus a fact is a clause, and a rule is a clause. The term "clause" is a higher-level concept than either "fact" or "rule". We can draw the following type-hierarchy:

Invocation

When using a structure as a subgoal in either a query or the body of a rule, that usage is called an "invocation". For example, when asking the following question:

?- same_semester(name(Lisa), X).

we say that we invoke the rule with the functor "same_semester" and arity 2.

The term "invoke" comes from a Latin word which means "call upon". Therefore, we also say that we call a rule when we invoke it.

Predicate

A predicate is a collection of clauses whose heads have the same functor and arity. Thus a predicate is a collection of facts and rules whose heads have the same functor (e.g., student) and arity (e.g., 2). Thus, in the example program, student/2 is a predicate. A predicate can be made up of both facts and rules, so we are not restricted to predicates that consist solely of facts, as in the example program.

Summary

We have introduced the terminology Head, Entails, Body, Subgoal, Fact, Clause, Invocation, and Predicate. All of these terms are useful when talking about Prolog programs.

Next

Now that we have the terminology to talk about Prolog programs, we will look at the rules for when a specific variable name refers to the same variable. We must not assume that just because a variable name occurs more than once, then the variable name refers to the same variable.


Variable scoping rule

Introduction

When we say "variable", we mean one of two things:

  1. We can mean "variable name", e.g., "X". That is, a string of characters that make up a name. This name identifies the variable (in the next sense).

  2. We can mean the memory storage location that holds the value that the variable name stands for.

In Prolog, it is not the case that every occurrence of the same variable name necessarily refers to the same memory storage location.

Example

For example, consider the following example program:

old(Timothy).
old(Elizabeth).

wise(Peter).
wise(Lydia).

happy(X) :- old(X).
happy(X) :- wise(X).

This example program is available in the AAU directory as Old-wise.plgCG.

The program says that Timothy and Elizabeth are old, and that Peter and Lydia are wise, and that you are happy if you are either old or wise.

The program doesn't do anything useful, but it illustrates what we are talking about.

There are four occurrences of the variable name "X". Do they all refer to the same variable memory location? If not, which belong together?

The scoping rule

The scoping rule for variables in Prolog is this:

Two uses of an identical name for a variable only refer to the same memory location if they are within a single clause.

The scoping rule applied

In the example above, there are four uses of the variable name "X". We now know that the two clauses using the variable "X" could have been rewritten as:

happy(X) :- old(X).
happy(Y) :- wise(Y).

without affecting the meaning. We see that the "X" referred to in the following clause:

happy(X) :- old(X).

is not the same as the "X" referred to in the other clause:

happy(X) :- wise(X).

However, within each of these clauses, the "X" does refer to the same memory location.

Summary

When we say "variable", we either refer to a variable name or to the memory location where the variable's value is stored.

Two uses of the same variable name refer to the same memory location only if the uses occur within the same clause.

Next

Next, we present a technique for solving a programming problem which is common when programming in Prolog.


Returning values from rules

The problem

Consider the following query:

?- same_semester(name(Martin), name(John)).

As we saw earlier, the answer is:

{}

This is not very helpful if we wanted to know what semester they were in.

The problem can be formulated in the following general terms: How do we "return" a value from a call to a rule? While executing the body of the rule, we know what semester they are in; it is stored in the variable "S":

same_semester(A,B) :- student(A,S), student(B,S).

"S" is a variable which we use as an intermediate place-holder while executing the body of the rule. How do we return the information contained in S so that it is available even after the body of the rule has been executed?

The solution

The solution is to modify the head of the rule so that it contains a variable which we can use to return the result. In this case, we might as well use the variable which we are using the body of the rule:

same_semester(A,B,S) :- student(A,S), 
                        student(B,S).

The full program so far

The full example program so far looks like this:

student(name(Lisa), semester(5)).
student(name(Martin), semester(3)).
student(name(John), semester(3)).
student(name(Edward), semester(7)).

same_semester(A,B) :- student(A,S), 
                      student(B,S).

same_semester(A,B,S) :- student(A,S), 
                        student(B,S).

It is available in the AAU sample directory as "Students4.plgCG".

Testing the new rule

Let us ask a query:

?- same_semester(name(John), name(Martin), S).

The answer is:

{S = semester(3)}

We have used the variable S to get feedback from the rule. We could equally well have asked:

?- same_semester(name(John), name(Martin), semester(3)).

and the answer would be:

{}

("yes") as we would expect.

The two rules coexist peacefully

Note that the two rules coexist peacefully side by side. They are not in conflict with each other. Why is this?

Recall that two structures match only if:

  1. Their functors are the same
  2. Their arities are the same
  3. Their individual arguments match from left to right.

Here, the functors are the same, so requirement 1. is fulfilled, but their arities are not the same, so requirement 2. is not fulfilled. The first rule has arity 2, while the second rule has arity 3.

Why is it important that the two structures do not match? It is important because, when answering queries (and when executing bodies of rules), matching is the process that drives the sequence of events. For example, the following query:

?- same_semester(name(Lisa), Y).

would not invoke our new rule, since the query uses the structure with arity 2. The new rule has arity 3, and so the subgoal in the query does not match the new rule. Therefore, the new rule is not used to answer the query.

A deeper look at returning values

So the technique for returning values from a rule is to include a variable in the head of the rule which can be used for returning the desired value.

However, there is nothing special about adding an extra variable to the arguments of the head of a rule. As we saw, we can ask questions like:

?- same_semester(name(Martin), name(John), S).

as well as questions like:

?- same_semester(name(Martin), name(John), semester(3)).

The only difference between the two queries is the usage of a variable versus the usage of a value (in this case, a structure) as one of the arguments to the rule.

This is one reason why Prolog is so useful: You can freely decide when to use variables and when to use values as the arguments to rules and facts (collectively called 'clauses', remember?). Prolog will either find the value (if you have used a variable), or use the value (if you supply a value).

Thus there is really nothing new in this technique. There is no fundamental difference between the way the following two questions are answered:

?- student(name(Lisa), S).
?- student(name(Lisa), semester(3)).

and the way following two questions are answered:

?- same_semester(name(Martin), name(John), S).
?- same_semester(name(Martin), name(John), semester(3)).

In both cases, we either use a variable or a value as the input to a rule-invocation. And in both cases, Prolog either finds a value for the variable or uses the value supplied.

Summary

When wanting to return a value from a rule, the technique is to include an extra variable in the arguments to the rule. This variable is then given the desired value in the body of the rule.

There is nothing fundamentally different between:

When asking questions, the user is free to use either variables or values as arguments to the rule invoked.

Next

Next, we have a quiz.


Prolog's solution strategy

The questions

In this chapter, we investigate how Prolog actually works. By the end of the chapter, you should be able to explain how Prolog executes a Prolog program.

We will explain Prolog's solution strategy by answering a number of questions:

  1. How is a subgoal satisfied?
  2. In what order does matching occur?
  3. What is backtracking?
  4. How are all solutions found?

Each of these questions will be treated on a page of its own.

But now we turn to the first question: How is a subgoal satisfied?


How is a subgoal satisfied?

The Question

Remember that the way you get answers from Prolog is by asking queries. A query is made up of one or more subgoals. The whole of the query is satisfied if each of the subgoals can be satisfied in turn. So the first question to answer is:

How is a subgoal satisfied?

The Answer

The answer is this:

A subgoal can be satisfied in two ways:

  1. By matching with a fact. If the matching occurs, the subgoal is satisfied.
  2. By matching with the head of a rule. If matching occurs, the subgoal is only satisfied if all of the subgoals of the body of the rule can also be satisfied.

Matching

Remember that when we say "match", we are referring to the process of matching previously discussed, and that this matching takes place according to some specific rules.

Matching vs. satisfying

Note that there is a difference between 'matching' and 'satisfying'.

'Matching' is a process that applies to terms. It is the process whereby it is decided whether two terms match or not.

'Satisfying', on the other hand, is a higher-level process, and applies to subgoals. Subgoals are satisfied by means of matching, but as we saw, there is something more involved:

A subgoal that matches the head of a rule is satisfied only if all of the subgoals of the body of the rule can be satisfied.

Example

For example, take the familiar example program:

student(name(Lisa), semester(5)).
student(name(Martin), semester(3)).
student(name(John), semester(3)).
student(name(Edward), semester(7)).

same_semester(A,B) :- student(A,S), 
                      student(B,S).

If we ask the query:

?- same_semester(name(Martin), name(John)).

the only subgoal in the query is satisfied by matching with the head of the rule:

same_semester(A,B) :- student(A,S), 
                      student(B,S).

However, it is only satisfied because both of the subgoals in the body of the rule can also be satisfied.

These subgoals, in turn, are satisfied by matching with the heads of facts.

Next

So a goal is satisfied by the process of matching, plus the requirement that the subgoals in the body of a rule must also be satisfied. This leaves us with a number of new questions, one of which is: In what order does matching occur? We treat this question next.


In what order does matching occur?

The question

Now that we know that goals are satisfied by means of the process of matching, another question which we need to answer is:

In what order does matching occur?

Why is this important?

To really see why this is important, we need some information which is only presented later, in the chapter on recursivity. But for now, we can at least note that if we have the following program:

father(Abraham,Isaac).
father(Abraham,Ishmael).

and we ask the following query:

father(Abraham,X).

we get the following two answers, in the following order:

{X = Isaac}
{X = Ishmael}

It might be important to us that we get the answers in this order, and then it will be important to know in what order Prolog is going to give them to us.

So now we are ready for the answer to the question: In what order does matching occur?

The answer

The answer must be given in three stages.

The first stage involves the order in which subgoals are matched against clauses in the program database.

The second stage involves the order in which arguments of a subgoal are matched against the arguments of the head of a clause.

The third stage involves the order in which subgoals in the body of a rule are satisfied.

Subgoals and clauses

When Prolog tries to satisfy a subgoal, it tries to match the subgoal with the first clause (i.e., fact or rule) in the program. If this does not satisfy the subgoal, Prolog goes on to the next clause, and the next, and the next, etc., in the written top-to-bottom order of the program, until either the goal is satisfied or there are no more clauses in the program.

Arguments of subgoals

As already noted in the chapter on matching, when Prolog tries to match the arguments of two structures with the same functor and the same arity, the matching occurs left-to-right. This is important because a variable might get bound to a value in the process of matching. If this variable occurs again in one of the later arguments (i.e., an argument more to the right), then the variable will already be bound to a value, and this value will be used in place of the variable.

For example, when matching the following subgoal:

1) foo(Abraham, N)

with the following subgoal:

2) foo(X,X)

N will be bound to the value "Abraham".

The reason is that when matching the first argument of the subgoals, X gets bound to the value "Abraham". When matching the second argument of the subgoals, N gets bound to X, which already has the value "Abraham", so N also gets the value "Abraham".

Subgoals in the body of a rule

Recall that when matching a subgoal with the head of a fact, the subgoal is satisfied if the matching succeeds. Recall also that when matching a subgoal with the head of a rule, the subgoal is satisfied only if all of the subgoals in the body of the rule are satisfied. Then it is important to know: In what order are the subgoals in the body of the rule satisfied?

The answer is that again, Prolog attempts to satisfy them in the left-to-right, top-to-bottom order in which they are written. If the first subgoal is satisfied, Prolog goes on to the next subgoal, and the next, etc., until all of the subgoals have been satisfied.

This is actually a slightly simplified answer, but we shall mend matters shortly on the next page.

Summary

Matching generally occurs top-to-bottom, left-to-right.

Subgoals are matched against heads of clauses in a top-to-bottom order.

Arguments of subgoals are matched against arguments of the heads of clauses in a left-to-right, top-to-bottom order.

Subgoals in the body of a rule are matched in a left-to-right, top-to-bottom order.

Next

When a subgoal is not satisfied, Prolog starts the process of bactracking. The next page discusses this process. Backtracking, among other useful results, is the reason why we can get more than one answer from a given query.


What is backtracking?

The question

What happens when a subgoal cannot be satisfied? The answer is that Prolog starts the process called backtracking. The questions then becomes:

What is backtracking?

The answer

Backtracking is a process. When a subgoal fails, the Prolog system traces its steps backwards to the previous goal and tries to resatisfy it.

This means that all variables that were bound to a value when that goal was satisfied are now made free again. Then the Prolog system tries to resatisfy that goal by matching with the next clause starting at the clause just after the one that matched the subgoal.

This continues until either the subgoal is satisfied, or until the program database has been exhausted, at which point Prolog backtracks yet again to the subgoal that was before the current subgoal.

All of this probably requires an example, and we will provide such an example right away.

An example

Consider the following program:

son(Ishmael, Abraham, mother_is_slave).
son(Isaac, Abraham, mother_is_free).
patriarch(Abraham).
freeborn(P,S) :- patriarch(P), 
                 son(S,P,F),
                 eq(F,mother_is_free).

It is available in the AAU sample directory as "Abraham1.plgCG".

The eq/2 structure is a primitive goal in Prolog+CG. It attempts to match the two arguments. If the matching succeeds, the eq/2 goal succeeds. If the matching fails, the eq/2 goal fails.

Let us see what happens when we issue the query:

?- freeborn(X,Y).

First, Prolog tries to match this subgoal with the first clause in the program database (which is

son(Ishmael, Abraham, mother_is_slave)

). This does not succeed because the two structures do not have the same functor. Of course, only the fourth clause (the rule) matches. X gets bound to P, and Y to S, but since these are both free variables at the time, none of the four variables are bound to any value.

Then Prolog attempts to satisfy the subgoals in the body of the rule for freeborn/2. The first subgoal is

patriarch(P)

and the only clause that matches is the fact

patriarch(Abraham)

so P gets bound to the value "Abraham", and the subgoal succeeds.

The next subgoal is

son(S,P,F)

Prolog tries to match against the first clause, which happens to be

son(Ishmael,Abraham,mother_is_slave)

Since the two functors are the same, and the arities are the same, Prolog attempts to match the arguments from left to right. S is a free variable at this point, so S matches Ishmael and is bound to this value. P is already bound to "Abraham", and this value matches "Abraham" in the head of the fact. F is a free variable, so F matches "mother_is_slave" and is bound to this value. So the subgoal succeeds, with S having been bound to the value "Ishmael" and F having been bound to "mother_is_slave".

Prolog then goes on to the next subgoal and tries to satisfy this. The subgoal is:

eq(F,mother_is_free)

It will be remembered that this subgoal succeeds if the two arguments can be matched; otherwise it fails. F is now bound to "mother_is_slave", which does not match with "mother_is_free" (see Rule 1 on the list of rules for matching).

So the "eq(F,mother_is_free)" subgoal fails.

Prolog now starts the process of backtracking. It retraces its steps backwards to the previous subgoal, which was

son(S,P,F)

and undoes any variable bindings that were made at this point. This means that S and F are now free variables again.

Since this subgoal was matched against "son(Ishmael, Abraham, mother_is_slave)", Prolog starts at the next clause after this. This happens to be

son(Isaac, Abraham, mother_is_free)

which does match with the subgoal. S gets bound to "Isaac", F gets bound to "mother_is_free", and the subgoal succeeds.

Prolog now goes on to the next subgoal in the rule, which is

eq(F,mother_is_free)

Since F is now bound to "mother_is_free", the subgoal succeeds.

Since this subgoal was the last in the body of the rule:

freeborn(P,S) :- patriarch(P), 
                 son(S,P,F),
                 eq(F,mother_is_free).

the rule succeeds. Recall that the subgoal in the query which we tried to match against this rule was:

freeborn(X,Y)

and that X was bound to P and Y was bound to S. Since P is now bound to "Abraham" and S to "Isaac", we get these variable bindings:

{X = Abraham, Y = Isaac}

Summary

When a subgoal cannot be satisfied, Prolog starts the process of backtracking. It goes back to the previous subgoal, undoes any variable bindings that took place at this point, and tries to resatisfy this subgoal. It does so by attempting to match against the head of the next clause in the program database after the clause that last resulted in a match.

Next

There is actually more to say about backtracking, because at this point, Prolog does some more backtracking, but we will save that for the next page.


How are all solutions found?

The question

We now know what backtracking is. We also know that backtracking occurs when a subgoal fails. But there is one other case in which backtracking occurs. This has to do with the following question:

How are all solutions found?

The answer

The answer is that when all the subgoals in a query have been satisfied, and the query therefore succeeds, Prolog starts the process of backtracking in order to find all solutions. The process continues until all possibilities have been exhausted. We will spell this out in an example.

Example

Consider the following program:

professor(Alfred).
professor(Albert).
student(name(Lisa), course(MA301), prof(Alfred)).
student(name(Martin), course(MA302), prof(Alfred)).
student(name(Lisa), course(PH307), prof(Albert)).
student_of(S,P) :- professor(P),
                   student(name(S), C, prof(P)).

The program links students, courses, and professors with each other. The program is available in the AAU sample directory as "Students5.plgCG".

Let us see what happens if we ask the question

?- student_of(Lisa, X).

The answers are:

{X = Alfred}
{X = Albert}

as expected. But how did Prolog obtain these answers?

Firstly, the only clause that matches the subgoal in the query is the rule:

student_of(S,P) :- professor(P),
                   student(name(S), C, prof(P)).

S gets bound to "Lisa", and X is bound to the free variable P, so it gets no value at this point.

Prolog proceeds with trying to satisfy the subgoals in the body of the rule.

professor(P) first matches professor(Alfred) (the first clause in the program), and P gets bound to "Alfred". The next subgoal to satisfy is "student(name(S), C, prof(P))", and the first matching that succeeds is the third line. C gets bound to the value "course(MA301)", and the subgoal succeeds. (The variable C is not used for anything later, but it needs to be there in order to match against the student/3 facts).

Since this subgoal was the last in the rule, the overall rule succeeds. Since X was bound to P, and since P is now bound to the value "Alfred", X now has the value "Alfred". Since the subgoal

student_of(Lisa, X)

was the last in the query, we now have one answer. Prolog+CG prints the following:

{X = Alfred}

Now the fun begins. Prolog backtracks to the previous goal that succeeded, which is still

student_of(Lisa, X)

The variable X is now made free again, since it was bound at that point, and Prolog starts at the last subgoal that succeeded. This was

student(name(S), C, prof(P))

in the rule:

student_of(S,P) :- professor(P),
                   student(name(S), C, prof(P)).

P still has the value "Alfred", and C is still bound to the value "course(MA301)". Prolog tries to satisfy the subgoal (with values substituted for variables):

student(name(Lisa), course(MA301), prof(Alfred))

Prolog starts at the next clause after the one that matched last time. This means that the subgoal is matched against:

student(name(Martin), course(MA302), prof(Alfred)).

This, of course, fails. So Prolog goes on to match the subgoal against all of rest of the clauses in the program, which fails.

Prolog now backtracks once more. It first undoes the variable binding

{C = course(MA302)}

since the subgoal failed. It goes back to the previous goal, which was

professor(P)

Since P was bound to the value "Alfred" at this point, P is now made free, and Prolog tries to satisfy the subgoal by going on to the next clause after the clause that satisfied the subgoal. This is:

professor(Albert)

which satisfies the subgoal, and P is bound to the value "Albert". Prolog now attempts to satisfy the subgoal

student(name(Lisa), C, prof(Albert))

The process starts at the top of the program, and succeeds with the fifth line of the program:

student(name(Lisa), course(PH307), prof(Albert)).

This of couse satisfies the last goal of the rule. Prolog+CG prints out:

{X = Albert}

Prolog now backtracks. It tries to resatisfy the subgoal

student(name(S), C, prof(P))

with variable bindings

{S = Lisa, C = course(PH307), P = Albert}

Prolog goes on after the clause that matched this, which is the fifth line, but fails all the way to the bottom of the program. Prolog now backtracks again. It undoes the variable binding {C = course(PH307)} and goes back to the previous subgoal that succeeded. This was

professor(P)

with the variable binding

{P = Albert}

this binding gets undone so that P is now a free variable, and Prolog tries to resatisfy the goal. This fails. Since this was the first subgoal of the rule, the overall rule fails.

Prolog now backtracks for the last time. The subgoal that last succeeded was the query-subgoal

student_of(Lisa, X)

Prolog now tries to match this subgoal against the next clause after the clause that satisfied it. But since there is no such clause, the backtracking fails. Since this subgoal was the top-level subgoal in the query (there was no subgoal before it in the query), backtracking stops at this point, and the process is done. Prolog shows the query-prompt again, ready to answer another question.

The answers which we got along the way were:

{X = Alfred}
{X = Albert}

Summary

Backtracking is used to find all solutions.

Next

This was a large and difficult chapter. We end it by giving a summary of the main points.


Summary

We can summarize the main points of this chapter as follows:

  1. A subgoal is satisfied by matching with a clause. If the clause is a fact, and the subgoal matches the head of the fact, the subgoal is satisfied. If the clause is a rule, and the subgoal matches the head of the rule, the subgoal is only satisfied if all of the subgoals in the body of the rule can be satisfied.
  2. Matching occurs top-to-bottom, left-to-right.
  3. Backtracking is the process whereby, when a subgoal fails (or we successfully reach the end of the query), variable bindings are undone and the last subgoal that was satisfied is resatisfied. This starts at the next clause after the clause that satisfied the subgoal.


Recursivity and lists

Introduction

Two notions which are central in Prolog are:

  1. Recursivity, and
  2. Lists

Recursivity is a concept which we find again and again in computer science: In programming problems, in data structures, in definitions of programming constructs, in languages, etc. Also in Prolog do we find several instances of recursivity, one of which is the way lists are defined and used. Some other places in Prolog where we find recursivity include the definition of structures and in recursive rules.

But what is recursivity? To answer this, we will first look at an instance of recursivity, namely the definition of lists. Then afterwards we will give a general definition of when something is recursive.


The definition of a list

Defining what a list is

A list is a datastructure which is central to Prolog. Informally, a list is an ordered sequence of items. For example, the following is a list:

(Peter,Paul,Mary)

The list is a sequence of items, which means that it is a succession of items after each other. The list is ordered, which means that it does matter in which order or sequence the items are. For example, the following list is different from the above list:

(Mary,Paul,Peter)

because the items are in a different order.

Had this been a set rather than a list, the order would not have mattered. But since a list is an ordered sequence, the order does matter.

We usually call the items of a list the elements of a list.

Recursive definition of a list

The notion of 'list' can be defined recursively as follows:

A list is either the empty list (called 'nil'), or it is a head followed by a tail, where the head is an element and the tail is a list.

Unraveling the recursive definition

We see that a list is one of two things. It is:

  1. Either the empty list, called 'nil',
  2. Or a succession consisting of:
    1. The head of the list, which is an element,
    2. The tail of the list, which is a list.

We see that a list is partially defined in terms of itself. The tail of a list is a list. It is this self-reference which gives the predicate "recursive" in the definition.

In order to translate a list such as the following:

(Ishmael, Isaac)

to something that matches the above definition, we could define a structure called cons/2. This structure would look as follows:

cons(H,T)

This structure would be interpreted to mean that:

  1. the head H (which is an element)
  2. is before
  3. the tail T (which is a list).

At the same time, we would define an atomic constant called nil:

nil

which would be interpreted to be an empty list.

We now have all of the ingredients needed to translate our example list:

(Ishmael, Isaac)

to something that matches the definition:

cons(Ishmael, cons(Isaac, nil))

We see that Ishmael is in the place of the head of the outermost cons. In the place of the tail of this outermost cons, we find another cons. This inner cons has Isaac in the place of the head, and the list 'nil' in the place of the tail. Thus the list terminates after Isaac.

Again, the list

(Peter,Paul,Mary)

would be written as:

cons(Peter, cons(Paul, cons(Mary, nil)))

Exercise: Try to unravel this list, identifying each part, and saying whether each part is a head or a tail, an element or a list. Be sure to point out where the brackets for each part begin and end.

Summary

A list is an ordered sequence of elements. A list can be defined recursively as follows:

A list is either the empty list, or it is an element followed by a list. The element is called the head of the list, and the trailing list is called the tail of the list.

It is the element of self-reference that gives rise to the predicate recursive definition.

Next

Next, we take a deeper look at what exactly makes a definition 'recursive'.


Recursive definitions

Introduction

We have looked at an example of a recursive definition, namely the definition of what a list is. Now it is time to take a look at what it means that a definition is recursive.

What makes a definition 'recursive'?

In order for a definition to be recursive, it needs at least two characteristica:

  1. It needs to define the entity being defined partially in terms of itself. There needs to be an element of self-reference, i.e., the entity being defined must be partially defined by reference to itself.
  2. There must be at least one so-called 'base case' which is not defined in terms of the entity being defined. The base case serves as an 'escape hatch' from the definition so that it does not become circular (more on this below).

Thus, in order for a definition to be recursive, the entity being defined needs to be partially defined in terms of itself, and the definition needs at least one 'base case' not involving the entity being defined.

Application to the definition of lists

Recall that a list is defined as follows. A list is:

  1. Either the empty list, called 'nil',
  2. Or a succession consisting of:
    1. The head of the list, which is an element,
    2. The tail of the list, which is a list.

We see that 1. is the base case, while 2b) provides the self-reference. The base case (a list is an empty list, called 'nil') is not defined in terms of what a list is. The recursive part (the tail of a list is a list) is, by contrast, defined in terms of what a list is.

Why there needs to be a base case

What would happen if there were no base case in the definition of what a list is? The answer is that the definition would not be recursive but circular. We would never be finished describing any particular list:

Suppose we only had rules 2a and 2b. Every list would be infinitely long: When we had specified the first element, we would have to specify what the tail was. But the tail was a list. And a list could only be a head (which was an element) and a tail (which was a list). So we would specify the next element, but be left with the same problem again of saying what the tail was, which was a list. And so on ad infinitum.

So we see that it is precisely the requirement that a recursive definition have at least one base case that saves the definition from being circular. With the base case, the definition is not circular. Without the base case, the definition is always circular, since it defines the element being defined in terms of itself.

Summary

In order for a definition to be recursive, it needs at least these two characteristica:

  1. The entity being defined needs to be defined partially in terms of itself.
  2. There needs to be at least one base case definition which is not defined in terms of the element being defined.

Recursive definitions are not circular precisely because they have at least one base case.

Next

There are other things in Prolog than lists that can be recursive. One of them is predicates. We look at recursive predicates next.


Recursive predicates

Introduction

We have seen what a recursive definition is. Predicates, however, can also be recursive. On this page, we take a brief look at what a recursive predicate is. On the next page, we give an example of a recursive predicate.

What is a recursive predicate?

A recursive predicate is a predicate which satisfies these two conditions:

  1. It must have at least one rule whose body does not call the same predicate. Alternatively, this can be a fact. This is the base case.
  2. It must have at least one rule whose body does call the same predicate. This is the recursive part.

Next

On the next page, we will see a recursive predicate in action.


Example of a recursive predicate

Introduction

One every-day phenomenon which involves recursivity is that of ancestors and descendants. For example, your father is your ancestor, but so are his father's father and his father's father's father. All of these people are your ancestors, and the relationships can be described elegantly using recursivity.

Defining 'ancestor' recursively

We will not define fully what an ancestor is. This would involve both fathers and mothers, grandfathers and grandmothers, great-grandfathers and great-grandmothers etc. Instead, we will define what a patrilineal ancestor is, i.e., an ancestor who is either the father, the father's father, or the father's father's father, etc.

The recursive definition of a patrilineal ancestor is:

A person A is an ancestor of a person D if:

  1. A is the father of D, or
  2. Some third person F is the father of D, and A is an ancestor of F.

Here, 1. serves as the base case, whereas 2. serves as the recursive part.

Seeing that it works

To see that it works, imagine the following patrilineal ancestry

   Terah
     |
   Abraham
     |
   Isaac
     |
   Jacob
     |
   Judah

Where Terah is an ancestor of all the others, Abraham is an ancestor of Isaac, Jacob, and Judah, etc. etc.

Suppose we want to know whether Terah is an ancestor of Jacob. So we ask: Is Terah, "A", an ancestor of Jacob, "D"?

Well, we can't use part 1. of the definition, since Jacobs's father is Isaac, not Terah. But can we use part 2.?

Some third person F is the father of D. Here, F would be Isaac, and D would be Jacob. Is Terah an ancestor of Isaac?

Again, we can't use part 1. of the definition. But Part 2. yields Abraham (F) is the father of Isaac (D). Is Terah an ancestor of Abraham?

We apply rule 1. Yes, Terah is an ancestor of Abraham, because Terah is Abraham's father. So all of the other rules also succeeded. So Terah is an ancestor of Judah.

All this in Prolog

Consider the following Prolog program. It is available in the AAU directory as: "Ancestors1.plgCG".

father(Terah, Abraham).
father(Abraham, Isaac).
father(Isaac, Jacob).
father(Jacob, Judah).

ancestor(A,D) :- father(A,D).
ancestor(A,D) :- father(F,D), ancestor(A,F).

We see that there is a close correspondence between our definition of what a patrilineal ancestor is and what the predicate "ancestor" is.

Exercise: Try to match each part of the definition above with each part of the Prolog predicate.

The first parameter to the "ancestor/2" predicate is the ancestor, whereas the second parameter is the descendant.

If you have Prolog+CG available, now would be a good time to load the program and test it. For example, you could ask:

?- ancestor(Terah, Abraham).

and the answer would be:

{}

meaning "yes".

If you asked:

?- ancestor(Judah, Abraham).

the answer would be:

no.

since Judah is not an ancestor of Abraham.

Summary

We have seen an example of a recursive predicate. Recursive predicates have a base case not involving the predicate itself. This can either be a fact or a rule. A recursive predicate also has at least one rule which calls the predicate itself. This is the recursive part.

Next

Next, we have a quiz on recursivity and lists


Prolog+CG

Introduction

Most of what we have said in this part has been generally applicable to most Prolog systems. We haven't said much that was specific to Prolog+CG. Exceptions have been, e.g.:

In most other Prolog systems, strings are enclosed in 'single quotes', lists are enclosed in [square brackets], and variables must start with an upper-case letter, and the two first characters of a variable can both be letters.

In this chapter, we will be looking at some more things that are specific to Prolog+CG. In particular, we will be looking at built-in primitive goals.

A list of primitive goals can be found by clicking the menu-item Windows -> Primitives in Prolog+CG. They are described in the Prolog+CG manual. If you need more help, you can read this.

We start by looking at some relational goals.


Relational goals

Introduction

On this page, we introduce three built-in primitive goals:

  1. eq/2
  2. eqv/2
  3. dif/2

eq/2

This goal tries to match (or unify) the two arguments. It succeeds if the matching succeeds, and fails if the matching fails.

For example, given the following program:

XIsNameY(X,Y) :- eq(X, name(Y)).

we can ask the following query:

?- XIsNameY(name(Martin), Martin).

and we get the answer:

{}

meaning "yes".

The reason is that X, which is bound to name(Martin), matches with name(Y), since Y is bound to Martin.

eqv/2

The eqv goal stands for "equivalent", and is the identity test on numbers. No matching occurs -- both arguments should have values. Thus you cannot make new variable bindings with this goal, since if either argument contains a variable, that variable should already have a value (or "be bound").

For example, if we ask:

?- eqv(X,54).

the answer is:

Error: any variable in an expression should have a value.

This is because X is a free variable here.

However, if we ask:

?- eqv(54,54).

the answer is:

{}

Again, if we ask

?- eq(X,54), eqv(X,54).

The answer is:

{X = 54}

thus the first subgoal (eq(X,54)) succeeded with the variable binding just given, and the second subgoal also succeeded, since X was bound to 54.

dif/2

This goal means "different".

dif(x,y) 

is equivalent to:

not(eq(x,y))

Thus, first matching is attempted between the two arguments. Then the result is negated: If the matching succeeded, the dif goal fails. If the matching failed, the dif goal succeeds.

For example,

?- dif(X,name(Martin)).

yields the answer:

no.

This is because X is a free variable, so X matches with name(Martin). Thus the matching succeeds, and therefore the dif subgoal fails.

On the other hand, if we ask:

?- eq(X,name(Lisa)), dif(X,name(Martin)).

we get the answer:

{X = name(Lisa)}

Thus the first subgoal succeeded with the variable binding just given, and the second subgoal also succeeded, since name(Lisa) does not match with name(Martin).

Next

Next, we look at two logical goals.


Logical goals

Introduction

On this page, we look at two logical goals:

  1. not
  2. fail

not

The not goal is logical negation. Its argument must be a goal. If the argument succeeds, the not goal fails. If the argument fails, the not goal succeeds.

For example,

?- not(eqv(54,47)).

yields

{}

This is because the eqv goal fails.

Note that you cannot use variable bindings that occurred inside the goal-argument after the not goal. For example, if you try to say:

?- not(eq(X,54)), eq(Y,X).

and expect Y to be bound to 54, you will be disappointed to see the answer:

no.

This is because, although X is bound to 54 inside the first eq goal, the second eq goal is never executed. This is because the not goal fails, since the first eq goal succeeds.

Thus you cannot export any variable bindings occurring inside the argument to not after the not goal.

fail

fail is the goal that always fails.

?- fail.
no.

one usage of fail is to stop a computation that you know will not succeed. (However, the cut operator is often better for this).

Next

Next, we look at some list goals.


List goals

Intruduction

On this page, we look at three goals that relate to lists:

  1. | (list constructor)
  2. member
  3. length

| (list constructor)

Remember that a list is defined as:

  1. Either the empty list, called 'nil',
  2. Or a succession consisting of:
    1. The head of the list, which is an element,
    2. The tail of the list, which is a list.

The list constructor (which might also be termed the list destructor, depending on how you look at it) is used as follows:

head((H | T), H).

it must be read as: head has two arguments. The first consists of a list, which is constructed as a head H and a tail T. The second argument is the head H.

Because matching occurs left-to-right, the second argument, H, will have been given the value which is the head of the list in the first argument.

Thus if we say:

?- head((Peter,Paul,Mary), H).

the answer is:

{H = Peter}

Thus the list constructor can be used to separate a list into its head and its tail.

member

The member/2 goal takes two arguments:

member(E,L)

where E must be an element, and L must be a list. It answers the question: Is E somewhere in the list L?

If we ask:

?- member(Paul, (Peter,Paul,Mary)).

we get the answer:

{}

On the other hand, if we ask:

?- member(Bob, (Peter,Paul,Mary)).

we get the answer:

no.

If we ask:

?- member(P, (Peter,Paul,Mary)).

We get the answer:

{P = Peter}
{P = Paul}
{P = Mary}

This is because backtracking occurs even after the query succeeds.

length

The length/2 goal takes one argument:

length(L,X)

where L is a list and X is either an integer or a free variable. It counts the number of elements in the list.

For example,

?- length((Peter,Paul,Mary),X).

yields

{X = 3}

Note that this is an example of using an argument which is a variable to return a value from a rule.

Next

Next, we look at two meta-goals. Meta-goals are goals that have side-effects apart from succeeding or failing.


Meta-goals

Introduction

On this page, we look at two meta-goals. A meta-goal is a goal that has side-effects apart from merely succeeding or failing.

The two goals we treat are:

  1. / (cut)
  2. write

/ (cut)

Definition

The cut/0 goal is a quite important goal in Prolog. It is used to stop backtracking. If the Prolog system meets a cut operator as one of the subgoals of a clause, the effect is the following:

  1. Any attempt to backtrack to the left of the cut operator in the same call to the clause will fail.
  2. Clauses in the same predicate (i.e., with the same functor and arity), which are below the clause with an executed cut operator, cannot be reached. They are not called even if the overall goal of the clause succeeds. Normally, backtracking would have gone on to calling later clauses, but the cut operator entails that they are not called.

Example

For example, consider the following, rather artificial, program:

aa(X) :- ba(X), /, ca(X).
aa(X) :- da(X).

ba(1).
ba(3).

ca(1).
ca(3).

da(2).

It is available in the AAU directory as "Cut1.plgCG".

It says that aa(X) succeeds in two cases:

  1. Either, if ba(X) succeeds, and then ca(X) succeeds (with the cut operator in between, which always succeeds).
  2. Or, if da(X) succeeds.

ba(X) and ca(X) succeed for X=1, and X=3, while da(X) succeeds for X=2.

Now let us see what the effect of the cut is. If we ask:

?- aa(X).

we get the answer:

{X = 1}

Normally, without the cut, we would have expected the following answers:

{X = 1}
{X = 3}
{X = 2}

This is because backtracking would have found all solutions.

Now, however, the cut does two things:

  1. It prevents ba(X) to be resatisfied with

    {X = 3}

    (rule 1 above)

  2. It prevents the clause

    aa(X) :- da(X)

    from being called (rule 2 above).

write

The write/1 goal takes one argument, which can be any kind of term (i.e., any kind of Prolog+CG data). It always succeeds, and it writes the argument to the screen.

For example, consider the following program:

yeehaaa(X) :- eq(X, "Texas"),
              write("Yeehaa!  Howdy y'all.").

If we then ask:

?- yeehaaa("Texas").

the answer will be:

"Yeehaa!  Howdy y'all."
{}

As was mentioned, you can write any kind of Prolog+CG data, including CGs.

You can also use the write/1 goal to debug your programs, by inserting it in important places to see whether Prolog executes the subgoals before it.


Next

We have come to the end of Part III on general Prolog. The advanced material continues with Peirce's rules of inference.