How to structure data in prolog : backtracking ?
Prolog provides ways to structure data as well as ways to structure the order in which attempts are made to satisfy goals. Understanding and learning prolog might seem like a challenge to some students but devoting time to the language helps ease the process of learning. One can take programming assignment help and solve prolog assignments to learn the language better. Structuring data in prolog involves knowing the syntax by which we can denote data. Structuring the order in which goals are solved involves knowing about backtracking.
Syntax for Structuring Data
The syntax of a language describes how we are allowed to fit words together. In English, the syntax of the sentence "I see a zebra" is correct, but the syntax of "zebra see 1 a" is not correct.
Prolog programs are built from terms. A term is either a constant, variable, or a structure. We saw each of these terms in the previous chapter, but we did not know them by these names. Each term is written as a sequence of characters. Characters are divided into four categories as follows:
A B C D E F G H I J K L M N G P Q R S T U V W X Y Z
abcdefghijklmnopqr tuvwxyz
0 1 2 3 4 5 6 7 8 9
+ - * / \^ < > ~ : . ? @ # $ &
The first row consists of upper-case letters. The second row consists of lower-case letters. The third row consists of digits. The fourth row consists of sign characters. There are actually more sign characters than those shown in the fourth row, but others have special uses discussed below. Each kind of term, whether it is a constant, variable, or structure, has different rules for how characters are put together to form its name. Now we shall summarise each kind of term.
Constants are thought of a naming specific objects or specific relationships. There are two kinds of constants: atoms, and integers. Examples of atoms are the names that were given in the last chapter:
likes mary john book wine owns jewels can.steal
The special symbols that Prolog uses to denote questions '? and rules :-' are also atoms. There are two kinds of atoms: those made up of letters and digits, and those made up from signs. The first kind must normally begin with a lower-case letter, as did all the ones we saw in the previous chapter. Those atoms made from signs normally are made up from signs only. Sometimes it may be necessary to have an atom beginning with a capital letter or a digit. If an atom is enclosed in single quotes", then the atom may have any characters in its name. Finally, the special underline character ' may be inserted in the middle of an atom to improve legibility. The following are further examples of atoms:
a
void
=
'george-smith'
-->
george.smith
leh2304
The following are not examples of atoms:
2304ieh
george-smith
Void
_alpha
Integers, the other kind of constant, are used to represent numbers, so that arithmetic operations can be carried out. We have not discussed how to do arithmetic in Prolog, but this will be introduced later in this chapter. Integers are whole numbers consisting only of digits and may not contain a decimal point. In this book, only fairly small positive integers will be used, for example:
0 1 999 512 8192 14765 6224
Prolog is available on several different computers, and depending on what computer you use, you may not be able to use large numbers or negative number. However, in this book we will only give examples that will work on any Prolog you are likely to find. It is safe to say that you will be allowed to use any integer ranging from 0 to 16383. Depending on what computer you use, you may be allowed to use larger numbers or negative numbers, but we will not depend on them. here. It is perhaps surprising that the applications for which Prolog is useful tend not to demand the ability to calculate with very large integers, fractions, or negative numbers. However, as Prolog is an extensible language, the resourceful programmer can add predicates to define such features without too much difficulty. For example, some Prolog systems provide library programs that define operations on rational numbers and numbers of arbitrary precision.
The second kind of term used in Prolog is the variable. Variables look like atoms, except they begin with a capital letter or an underline sign A variable should be thought of as standing for some object that we may not be able to name. This corresponds to the use of a pronoun in English. In the example Prolog clauses we have seen so far, we have used variables with names such as X, Y, and Z. However, the names can be as long as you like, for example:
Answer
Input
Gross_ Pay
_3_blind_mice
Sometimes one needs to use a variable, but its name will never be used. For example, if we want to find out if anyone likes John, but we do not need to know just who, we can use the anonymous variable. The anonymous variable is a single underline character. Our example is written in Prolog as:
?- likes( _.John).
Several anonymous variables in the same clause need not be given consistent interpretations. This is a characteristic peculiar to the anonymous variable. It is used to save having to dream up different variable names when they will not be used elsewhere in the clause.
The third kind of term with which Prolog programs are written is the structure. A structure is a single object which consists of a collection of other objects, called components. The components are grouped together into a single structure for convenience in handling them.
One example of a structure in real life is an index card for a library book. The index card will contain several components: the author's name, the title of the book, the date when it was published, the location where it can be found in the library, and so forth. Some of the components can be broken down into further components. For example, the author's name consists of some initials and a surname.
Structures help to organise the data in a program because they permit a group of related information to be treated as a single object (a library card) instead of as separate entities. The way that you decompose data into components depends on what problem you want to solve, and later on we will give advice on how to do this.
Structures are also useful when there is a common kind of object, of which many may exist. Books, for example. In Chapter 1 we discussed the fact
owns (John, book).
to denote that John owns some particular book. If we later said
owns (mary, book).
this means that Mary owns the same object that John owns, because it has the same name. There is no other way of telling objects apart, except by their name. We could say:
owns (John, wuthering heights).
owns (mary, moby dick).
to specify more carefully what books John and Mary own. How ever, in large programs, it may become confusing to have many dif ferent constants with no context to tell what they mean. Someone reading this Prolog program may not know that we meant wuther ing heights to be the name of the book written by the author Emily Bronte who flourished in Yorkshire, England during the 19th Century. Perhaps they will think that John has named his pet rabbit "wuther ing heights", say. Structures can help to provide this context.
A structure is written in Prolog by specifying its functor, and its components. The components are enclosed in round brackets and separated by commas. The functor is written just before the opening round bracket. Consider the following fact, that John owns the book called Wuthering Heights, by Emily Bronte:
owna (jobs,book (wuthering _heights, bronte)).
Inside the owns fact we have a structure by the name of book, which has two components, a title and an author. Since the book structure appears inside the fact as one of the fact's arguments, it is acting as an object, taking part in a relationship. If we like, we can also have another structure for the author's name, because there were three Bronte writers:
owne (john.book(wuthering heights,author (amily.bronte)))
Structures may participate in the process of question-answering using variables. For example, we may ask if John owns any book by the Bronte sisters:
?- ownss (jobs, book (X,author (Y, bronte))).
If this is true, I will then be instantiated to the title that was found, and Y will be instantiated to the first name of the author. Or, we may not need to use the variables, so we can use anonymous ones:
?- owns (jhon, book (_,author(_,bronte))).
Remember that the anonymous variables do not "share" with each other.
We could improve the book structure by adding another argument indicating which copy the book was. For example, a third argument, where we would insert an integer, would provide a way of uniquely identifying a book:
owns (jhon, book (ulysses,author (james, Joyce),3129)).
which we could use to represent John owns the 3,129th copy of Ulysses, by James Joyce.
If you have guessed that the syntax for structures is the same as for Prolog facts, you are correct. A predicate (used in facts and rules) is actually the functor of a structure. The arguments of a fact or rule are actually the components of a structure. There are many advantages to representing Prolog programs themselves as structures.
It is not important to know why just now, but do keep in mind that all parts of Prolog, even Prolog programs themselves, are made up of constants, variables, and structures.
The names of constants and variables are built up from strings of characters. Although each kind of name (atom, integer, variable) has special rules about what characters may make it up, it is helpful to know what all the characters are that Prolog recognises. This is because a character can be treated as an item of data in its own right. Now that we know about integers, it is appropriate to describe how characters are represented as small integers. It is most common to use "input" and "output" operations on characters; this will be discussed in Chapter 5.
Prolog recognises two kinds of characters: printing characters and non-printing characters. Printing characters cause a mark to appear on your computer terminal's display. Non-printing characters do not cause a mark to appear, but cause an action to be carried out. Such actions include printing a blank space, beginning new lines of text, and perhaps ringing a bell. The following are all the printing characters that can be used:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
a b c d e f g h I j k l m n o p q r s t u v w x y z
0 1 2 3 4 5 6 7 8 9
! “ # $ % & ‘ ( ) = - ~ ^ | | { } [ ] _ `@ + ; * : < > , . ? /
You should recognise these as a more complete set than the one given at the beginning of this chapter. Some of the characters have special meanings. For example, the round brackets are used to en close the components of a structure. However, we shall see in later chapters that all the characters may be treated as information by Pro log programs. Characters may be printed, read from the keyboard, compared, and take part in arithmetic operations.
Characters are actually treated as small integers between 0 and 127. Each character has an integer associated with it, called its ASCII code The term "ASCII" means "American Standard Code for Information Interchange", and it is the code which is used by many computers and computer languages in the world. A table of the ASCII code can be found in various computer reference manuals. The letters are arranged in alphabetical order, so comparing alphabetic order of characters means simply
comparing ASCII codes using the relational operators described later in this chapter. The printing characters all have ASCII codes that are greater than 32.
Although the ASCII code may not seem useful at the moment, the next places we mention it are in Section 3.2 and 3.5.
Sometimes it is convenient to write some functors as operators. This is a form of syntax that makes some structures easier to read. For example, arithmetic operations are commonly written as operators. When we write the arithmetic expression "x+y*z", we call the "plus sign" and the "multiply sign" operators. If we had to write the arithmetic expression "x+y*z" in the normal way for structures, it would look like this: +(x,*(y,z)). The operators are sometimes easier to use, however, because we have grown accustomed to using them in arithmetic expressions ever since our schooldays. Also, the structure form requires that round brackets be placed around the functor's arguments, which may seem awkward at times.
It is important to note that the operators do not "cause" any arithmetic to be carried out. So in Prolog, 3+4 does not mean the same thing as 7. The term 3+4 is another way to write the term +(3,4), which is a data structure. Later we shall explain a way in which structures can be interpreted as though they represent arithmetic expressions, and evaluated according to the rules of arithmetic.
First we need to know how to read arithmetic expressions that have operators in them. To do this, we need to know three things about each operator: its position, its precedence, and its associativity. In this section we will describe how to use Prolog operators with these three things in mind, but we will not go into very much detail at this point. Although many different kinds of operators can be made up, we shall deal only with the familiar atoms +, -,* and /.
The syntax of a term with operators depends in part on the position of the operator. Operators like plus (+), hyphen (-), asterisk (*), and slash (/) are written between their arguments, so we call them infix operators. It is also possible to put operators before their arguments, as in "-x+y", where the hyphen before the x is used in arithmetic to denote negation. Operators that come before their arguments are called prefix operators. Finally, some operators may come after their argument. For example, the factorial operator, used by mathematicians, comes after the number you want to find the factorial of. In mathematical notation, the factorial of x is written "!", where the exclamation sign is used to denote factorial. Operators that are written after their arguments are called postfix operators. So, the position of an operator tells where it is written with relationship to its arguments. It turns out that the operators that we will use in the next section are all infix operators.
Now precedence. When we see the term x+y*z, and assume that it can be interpreted as an arithmetic expression, we know that to evaluate it, we must multiply y and z first, then add x. This is because we were taught in school that mutiplications and divisions are done before additions and subtractions, except where brackets are used for grouping. On the other hand, the structure form +(x,*(y,z)) makes explicit the rule that the multiplication is done before the addition. This is because the* structure is an argument of the + structure, so if we actually wanted the computer to carry out the calculation, the *has to be carried out first in order for+ to know what its arguments are. So when using operators, we need rules that tell us the order in which operations are carried out. This is what precedence tells us about.
The precedence of an operator is used to indicate which operation is carried out first. Each operator that is used in Prolog has a precedence class associated with it. The precedence class is an integer which depends on the particular version of Prolog you are using. However, it is always true that an operator with a higher precedence has a precedence class which is closer to 1. If precedence classes range from 1 to 255, then an operator in the first precedence class is carried out first, before operators belonging to the 129th (say) precedence class. In Prolog the multiplication and division operators are in a higher precedence class than addition and subtraction, so the term a-b/c is the same as the term (a./(b,c)). The exact association of operators to precedence classes is not important at the moment, but it is worth remembering the relative order in which operations are carried out.
Finally, consider how different operators associate. How they associate comes to our attention when we have several operators of the same precedence. When we see the expression "8/2/2", does this mean "(8/2)/2" or "8/(2/2)"? In the first case, the expression could be interpreted to mean 2, and in the second case, 8. To be able to distinguish between these two cases, we must be able to tell whether an operator is left associative or right associative. A left associative operator must have the same or lower precedence operations on the left, and lower precedence operations on the right. For example, all the arithmetic operations (add, subtract, multiply, and divide) are left associative. This means that expressions like "8/4/4" are treated as "(8/4)/4". Also, "5+8/2/2" means "5+ ((8/2)/2)".
In practice, people tend to use round brackets for expressions that may be difficult to understand because of the precedence and associativity rules. In this book we will also try to make it as clear as possible by using lots of round brackets, but it is still important to know the syntax rules for operators so your understanding of operators is complete.
Remember that a structure made up of arithmetic operators is like any other structure. No arithmetic is actually carried out until commanded by the 'is' predicate described in Section 2.5.
Equality and Matching
One noteworthy predicate is equality, which is an infix operator writ ten as ''. When an attempt is made to satisfy the goal
? – x = y
(pronounced X equals 1), Prolog attempts to match I and Y, and the goal succeeds if they match. We can think of this act as trying to make X and Y equal. The equality predicate is built-in, which means that it is already defined in the Prolog system. The equality predicate works as though it were defined by the following fact:
X = x .
Within a use of some clause, I always equals X, and we exploit this property when defining the equality predicate in the way shown.
Given a goal of the form X = Y, where X and Y are any two terms which are permitted to contain uninstantiated variables, the rules for deciding whether X and Y are equal are as follows:
- If X is an uninstantiated variable, and if Y is instantiated to any term, then X and Y are equal. Also, X will become instantiated to whatever Y is. For example, the following question succeeds, causing X to be instantiated to the structure rides(clergyman, bicycle):
- Integers and atoms are always equal to themselves. For example, the following goals have the behaviour shown:
- Two structures are equal if they have the same functor and num ber of arguments, and all the corresponding arguments are equal. For example, the following goal succeeds, and causes X to be instantiated to bicycle:
? – rides (clergyman , bicycle ) :
Policeman= policeman /* succeeds */
Paper= pencil / *fails */
1066= 1066 /* succeeds */
1206= 1583 / *fails */
rides (clergyman, bicycle) = rides (clergyman,X)
Structures can be "nested" one inside another to any depth. If such nested structures are tested for equality, the test may take more time to carry out, because there is more structure to test. The following goal
A (b , c , d , (e , f , g , (h , I , j , ))) = a (B , c , d , (E , f , g (H , I , j )))
would succeed, and cause B to be instantiated to b, C to c, E to e, F to f, H to h, and J to j.
What happens when we attempt to make two uninstantiated variables equal? This is just a special case of the first rule above. The goal succeeds, and the two variables share. If two variables share, then whenever one of them becomes instantiated to some term, the other one automatically is instantiated to the same term. So, in the following rule, the second argument will be instantiated to whatever the first argument is:
do nothing (X,Y) :- X=Y.
An X = Y goal will always succeed if either argument is uninstantiated. An easier way to write such a rule is to take advantage of the fact that a variable equals itself, and write:
do nothing (X.X).
Prolog also provides a predicate '\', pronounced not equal. The goal
X \ = Y succeeds if X = Y fails, and it fails if X = Y succeeds. So, X / = Y means X cannot be made equal to Y. Exercise 2.1: Say whether the following goals would succeed, and which variables, if any, would be instantiated to what values:
pilots(A, london) = pilots(londos, paris)
points (X,Y,Z) = points (X1,Y1,Z1)
letter (C) = word (letter)
noun (alpha) = alpha
vicar = vicar
f(X.X) = f(a,b)
f(x.a(b,c)) = f (Z.a(Z.c))
Arithmetic
Many people use computers to do operations on numbers. Arithmetic operations are useful for comparing numbers and for calculating results. In this section we will see examples of each kind.
First, consider comparing numbers. Given two numbers, we can tell whether one number is equal to the other, or less than the other, or greater than the other. Prolog provides certain "built-in" predicates for comparing numbers. The predicates '=' and '\=' as discussed in Section 2.4 can be used for comparing numbers. The arguments could be variables instantiated to integers, or they could be integers written as constants. There are several other predicates for comparing numbers, and we can summarise all of them here. Note that we are allowed to write them as infix operators:
X = Y X and Y stand for the same number
X \ = Y X and Y stand for different numbers
X < Y X is less than Y
X > Y X is greater than Y
X =< Y X is less than or equal to Y
X >= Y X is greater than or equal to Y
Note that the "less than or equal to" symbol is not written as <= as in many programming languages. This is done so that the Prolog programmer is free to use the <= atom, which looks like an arrow, for other purposes of his own devising.
As these comparison operators are predicates, one might think it possible to write a Prolog fact as follows,
2 > 3.
in order to assert that 2 is actually greater than 3. A fact like this one is perfectly well-formed Prolog. However, Prolog will not allow further facts to be added to predicates that are "built in" to Prolog. This prevents you from changing the meaning of built-in predicates in unexpected ways. In Chapter 6 we shall describe all of the built-in predicates, including all those we have met thus far.
As a first example of using numbers, suppose we have a database of the reigns of the Sovereign Princes of Wales in the 9th and 10th Centuries. The predicate reigna (X,Y,Z) is true if the prince named I reigned from year Y to year Z. The list of facts in the database looks like this:
reigns (rhodri,844,878).
reigns (anarawd,878,916).
reigns(lago ad idwal,950,979).