PART 2    Tutorial Chapters 2 -- 11 :  Learning Prolog

 

This is the first in a sequence of chapters giving a step-by-step tutorial introduction to the Visual Prolog language. We begin this chapter with an introduction to programming in logic. After that we discuss some of Prolog's basic concepts, including clauses, predicates, variables, goals, and matching.

PROgramming in LOGic

In Prolog, you arrive at solutions by logically inferring one thing from something already known. Typically, a Prolog program isn't a sequence of actions--it's a collection of facts together with rules for drawing conclusions from those facts. Prolog is therefore what is known as a declarative language.

Prolog is based on Horn clauses, which are a subset of a formal system called predicate logic. Don't let this name scare you. Predicate logic is simply a way of making it clear how reasoning is done. It's simpler than arithmetic once you get used to it.

Prolog uses a simplified variation of predicate logic syntax because it provides an easy-to-understand syntax very similar to natural language, and because computers are not as fast, large, or as inexpensive as we would like. If Prolog were to accept English statements, the compiler would need to know every possible way something could be worded in English. In many cases, it would take many times longer to translate the program into something the computer understands than it would to run the program. The computer hardware needed to run such a system would be monstrous.

Prolog includes an inference engine, which is a process for reasoning logically about information. The inference engine includes a pattern matcher, which retrieves stored (known) information by matching answers to questions. Prolog tries to infer that a hypothesis is true (in other words, answer a question) by questioning the set of information already known to be true. Prolog's known world is the finite set of facts (and rules) that are given in the program.

One important feature of Prolog is that, in addition to logically finding answers to the questions you pose, it can deal with alternatives and find all possible solutions rather than only one. Instead of just proceeding from the beginning of the program to the end, Prolog can actually back up and look for more than one way of solving each part of the problem.

Predicate logic was developed to easily convey logic-based ideas into a written form. Prolog takes advantage of this syntax to develop a programming language based on logic. In predicate logic, you first eliminate all unnecessary words from your sentences. You then transform the sentence, placing the relationship first and grouping the objects after the relationship. The objects then become arguments that the relationship acts upon. For example, the following sentences are transformed into predicate logic syntax:

1. Sentences: Facts and Rules

A Prolog programmer defines objects and relations, then defines rules about when these relations are true. For example, the sentence

    Bill likes dogs.

shows a relation between the objects Bill and dogs; the relation is likes. Here is a rule that defines when the sentence Bill likes dogs. is true:

    Bill likes dogs if the dogs are nice.

Facts: What Is Known

In Prolog, a relation between objects is called a predicate. In natural language, a relation is symbolized by a sentence. In the predicate logic that Prolog uses, a relation is summarized in a simple phrase--a fact--that consists of the relation name followed by the object or objects (enclosed in parentheses). As with a sentence, the fact ends with a period (.).

Here are some more facts expressing "likes" relations in natural language:

    Bill likes Cindy.
    Cindy likes Bill.
    Bill likes dogs.

Here are the same facts, written in Prolog syntax:

    likes(bill, cindy).
    likes(cindy, bill).
    likes(bill, dogs).

Facts can also express properties of objects as well as relations; in natural language "Kermit is green" and "Caitlin is a girl." Here are some Prolog facts that express these same properties:

    green(kermit).
    girl(caitlin).

Rules: What You Can Infer from Given Facts

Rules enable you to infer facts from other facts. Another way to say this is that a rule, as conclusions is a conclusion that is known to be true if one or more other conclusions or facts are found to be true. Here are some rules concerning a "likes" relation:

    Cindy likes everything that Bill likes.
    Caitlin likes everything that is green.

Given these rules, you can infer from the previous facts some of the things that Cindy and Caitlin like:

    Cindy likes Cindy.
    Caitlin likes Kermit.

To encode these same rules into Prolog, you only need to change the syntax a little, like this:

    likes(cindy, Something):- likes(bill, Something).
    likes(caitlin, Something):- green(Something).

The :- symbol is simply pronounced "if", and serves to separate the two parts of a rule: the head and the body.

You can also think of a rule as a procedure. In other words, these rules

    likes(cindy, Something):- likes(bill, Something)
    likes(caitlin, Something):- green(Something).

also mean "To prove that Cindy likes something, prove that Bill likes that same thing" and "To prove that Caitlin likes something, prove that it is green." In the sameside effects procedural way, a rule can ask Prolog to perform actions other than proving things--such as writing something or creating a file.

2. Queries

In natural language, we ask you:

    Does Bill like Cindy?

In Prolog syntax, we ask Prolog:

    likes(bill, cindy).

Given this query, Prolog would answer

    yes

because Prolog has a fact that says so. As a little more complicated and general question, we could ask you in natural language:

    What does Bill like?

In Prolog syntax, we ask Prolog:

    likes(bill, What).

Notice that Prolog syntax does not change when you ask a question: this query looks very similar to a fact. However, it is important to notice that the second object--What--begins with a capital letter, while the first object--bill--does not. This is because bill is a fixed, constant object--aconstants known value--but What is a variable. Variables always begin with an upper-case letter or an underscore.

Prolog always looks for an answer to a query by starting at the top of the facts. It looks at each fact until it reaches the bottom, where there are no more. Given the query about what Bill likes, Prolog will return

    What=cindy
    What=dogs
    2 Solutions

This is because Prolog knows

    likes(bill, cindy).

We hope that you draw the same conclusion.

If we were to ask you (and Prolog):

    What does Cindy like?
    likes(cindy, What).

Prolog would answer

    What = bill
    What = cindy
    What = dogs
    3 solutions

This is because Prolog knows that Cindy likes Bill, and that Cindy likes what Bill likes, and that Bill likes Cindy and dogs.

We could ask Prolog other questions that we might ask a person; however, a question such as "What girl does Bill like?" will yield no solution because Prolog, in this case, knows no facts about girls, and it can't draw any conclusions based on material not known (supplied to it). In this example, we have not given Prolog any relation or property to determine if any of the objects are girls.

Putting Facts, Rules, and Queries Together

Suppose you have the following facts and rules:

    A fast car is fun.
    A big car is nice.
    A little car is practical.
    Bill likes a car if the car is fun.

When you read these facts, you can deduce that Bill likes a fast car. In much the same way, Prolog will come to the same conclusion. If no fact were given about fast cars, then you would not be able to logically deduce what kind of a car Bill likes. You could take a guess at what kind of a car might be fun, but Prolog only knows what you tell it; Prolog does not guess.

Here's an example demonstrating how Prolog uses rules to answer queries. Look at the facts and rules in this portion of Program 1:

    likes(ellen, tennis).
    likes(john, football).
    likes(tom, baseball).
    likes(eric, swimming).
    likes(mark, tennis).
    likes(bill, Activity):- likes(tom, Activity).

The last line in Program 1 is a rule:

    likes(bill, Activity):- likes(tom, Activity).

This rule corresponds to the natural language statement

    Bill likes an activity if Tom likes that activity.

In this rule, the head is likes(bill, Activity), and the body is likes(tom, Activity). Notice that there is no fact in this example about Bill liking baseball. For Prolog to discover if Bill likes baseball, you can give the query

    likes(bill, baseball).

When attempting to find a solution to this query, Prolog will use the rule:

    likes(bill, Activity):- likes(tom, Activity).

Load Program ch02e01.pro into the Prolog System and run it.

            Dialog window 에서의 출력

It has combined the rule

    likes(bill, Activity):- likes(tom, Activity).

with the fact

    likes(tom, baseball).

to decide that

    likes(bill, baseball).

Try also this query:

    likes(bill, tennis).

The system replies

            no

Visual Prolog replies no to the latest query ("Does Bill like tennis?") because

There is no fact that says Bill likes tennis.

Bill's relationship with tennis can't be inferred using the given rule and the available facts.

Of course, it may be that Bill absolutely adores tennis in real life, but Visual Prolog's response is based only upon the facts and the rules you have given it in the program.

In Prolog, variables enable you to write general facts and rules and ask general questions. In natural language, you use variables in sentences all the time. A typical general statement in English could be

    Bill likes the same thing as Kim.

As we mentioned earlier in this chapter, to represent a variable in Prolog, the first character of the name must be an upper-case letter or an underscore. For example, in the following line, Thing is a variable.

    likes(bill, Thing):- likes(kim, Thing).

In the preceding discussion of rules, you saw this line:

    likes(cindy, Something):- likes(bill, Something).

The object Something begins with a capital letter because it is a variable; it must be able to match anything that Bill likes. It could equally well have been called X or Zorro.

The objects bill and cindy begin with lower-case letters because they are not variables--instead, they are symbols, having a constant value. Visual Prolog can also handle arbitrary text strings, much like we've been handling symbols above, if the text is surrounded by double quotes. Hence, the token bill could have been written as "Bill", if you wanted it to begin with an upper-case letter.

4. Overview

1.  A Prolog program is made up of two types of phrases (also known as clauses): facts and rules.

    Facts are relations or properties that you, the programmer, know to be true.

    Rules are dependent relations; they allow Prolog to infer one piece of information from another. A rule becomes true if a given set of conditions is proven to be true. Each rule depends upon proving its conditions to be true.

2.  In Prolog, all rules have two parts: a head and a body separated by the special :- token.

    The head is the fact that would be true if some number of conditions were true. This is also known as the conclusion or the dependent relation.

    The body is the set of conditions that must be true so that Prolog can prove that the head of the rule is true.

3.  As you may have already guessed, facts and rules are really the same, except that a fact has no explicit body. The fact simply behaves as if it had a body that was always true.

4.  Once you give Prolog a set of facts and/or rules, you can proceed to ask questions concerning these; this is known as querying the Prolog system. Prolog always looks for a solution by starting at the top of the facts and/or rules, and keeps looking until it reaches the bottom.

5.  Prolog's inference engine takes the conditions of a rule (the body of the rule) and looks through its list of known facts and rules, trying to satisfy the conditions. Once all the conditions have been met, the dependent relation (the head of the rule) is found to be true. If all the conditions can't be matched with known facts, the rule doesn't conclude anything.

Exercises

Write natural language sentences that represent what these Prolog facts might convey to a human reader. (Remember that, to the computer, these facts are simple pieces of information that can be used for matching answers to questions.)

    1. likes(jeff, painting).

    2. male(john).

    3. building("Empire State Building", new_york).

    4. person(roslin, jeanie, "1429 East Sutter St.",
      "Scotts Valley", "CA", 95066).

Write Visual Prolog facts that represent the following natural language statements:

Helen likes pizza.

San Francisco is in California.

Amy's telephone number is 476-0299.

Len's father is Alphonso Grenaldi.