11.3 PROLOG

PROLOG was invented in early seventies by Alain Colmerauer in France and Robert Kowalski in Britain. Prolog = Programming in Logic. Prolog is a declarative programming language unlike most common programming languages like C, C++, Java, which are imperative and procedural. Being a declarative language, the PROLOG programmer specifies a goal to be achieved and the PROLOG system works out how to achieve it. PROLOG can also be used to build a relational database. Some applications of PROLOG are:

• intelligent database retrieval,
• natural language understanding,
• expert systems,
• specification language,
• machine learning,
• robot planning,
• automated reasoning,
• problem solving.

11.3.1 A Short Introduction to PROLOG

PROLOG programs specify relationships among objects and properties of objects. When we say “Ramesh owns the book”, we are declaring the ownership relationship between two objects: Ramesh and the book. We are declaring a fact. When we ask “Does Ramesh own the book?”, we are trying to find out about a relationship. The relationships can also be given as rules such as Two persons are sisters if they are both female and they have the same parents. Thus, a rule allows us to find out about a relationship even if the relationship is not explicitly stated as a fact.

We have to be slightly more specific:

A and B are sisters if
  A and B are both female and
  A and B have the same father and
  A and B have the same mother and
  A is not the same as B

Thus programming in PROLOG involves declaring facts and defining rules by which further relationships can be found out. You can then ask questions to the PROLOG system regarding the objects. The facts are written in PROLOG as follows:

teaches(phd, ″Compilers″).
teaches(hbd, ″Data Structures″).
teaches(phd, ″Operating Systems″).

Note that names of properties or relationships begin with lowercase letters. The relationship name appears as the first term. The objects appear as comma-separated arguments within parentheses. A period “.” must end a fact. The objects can also begin with lowercase letters or with digits and can be strings of characters enclosed in quotes. A fact is also called a predicate.

teaches(X, Y)

means that person X teaches a course Y. We define another set of facts:

studies(ramesh, ″Compilers″).
studies(suresh, ″Compilers″).
studies(mina, ″Data Structures″).
studies(gita, ″Operating Systems″).
studies(bhavesh, ″Data Structures″).

and one more:

semester(ramesh, 6).
semester(suresh, 6).
semester(mina, 4).
semester(gita, 8).
semester(bhavesh, 4).

We say that these facts together form PROLOG's database. After we have input this database, we can query the PROLOG system, and it will reply with an answer, for example,

teaches(phd, ″Compilers″).   <––– our query
true.	                     <––– PROLOG's answer

To answer the query, PROLOG consults its database to see if this is a known fact. We say the query succeeded if the answer was “true”. On the other hand, if the query were,

teaches(hbd, ″Compilers″).   <––– our query
false.	                     <––– PROLOG's answer

the PROLOG system cannot find a matching entry in its database and replies accordingly. The query failed.

If our query were “what does hbd teach?”, then our query would be written as:

teaches(hbd, Course).        <––– our query
Course = ″Data Structures″   <––– PROLOG's answer

Note the word “Course” with the capital first letter. It indicates a variable in PROLOG. A variable is assigned values extracted from the database. If the query were,

teaches(phd, Course).        <––– our query
Course = ″Compilers″         <––– PROLOG's answer
Course = ″Operating Systems″ <––– PROLOG's answer

Suppose the query was “Does phd teach ramesh?”, the query in PROLOG would be

teaches(phd, Course), studies(ramesh, Course).

Now PROLOG has to find if this conjunction can be satisfied by the available data in the database, with the comma being interpreted as AND operation. The answer will be “true”.

As a final example, we want to give a query “Whom does phd teach?”, expressed in PROLOG as

teaches(phd, Course), studies(Student, Course). <––– our query

and the answers are:

Course = ″Compilers″
Student = ramesh

Course = ″Compilers″
Student = suresh

Course = ″Operating Systems″ 
Student = gita

PROLOG solves this problem by proceeding left to right and then backtracking. Out of several “teaches” clauses, two are for phd – “Compilers” and “Operating Systems”. With first answer “Compilers”, PROLOG tries to satisfy the second part of the query and get two successes. As there are no more successes in the second half of the query, PROLOG backtracks and tries to get another answer to the first half of the query. It gets answer “Operating Systems”. It again tries to satisfy the second half and gets the answer “gita”. Based on this answer, we can define a new rule in our PROLOG database:

teacherof(Teacher, Student) :– teaches(Teacher, Course), studies(Student, Course).

Here “:-” means “if” or “is implied by”. The left-hand side is called the head and the right-hand side is called the body of the rule. With such a rule defined, we can give a query:

teacherof(T,S).

and we will get a list similar to the above, but for all the teachers.