Amzi! Corporation offers a number of Prolog products. For purposes of this course, I downloaded Amzi! Logic Explorer (http://www.amzi.com/download/amzi_logic_explorer.htm) which provides a basic Prolog language processor for the Wintel platform. It is free for individual use.

They also provide an online Prolog tutorial called Adventure in Prolog.

SOME FACTS AND DEFINITIONS

• Prolog means "Programming in Logic"
• Originally designed for natural language processing and theorem proving
• This is a declarative rather than a procedural style of programming
• BNF grammar for prolog shown in text Figure 11.4 (p. 431). Total of 5 grammar rules!
• All programs are really databases, blurring the distinction between program and data
• "logic" is expressed as a set of facts and rules.
• Rules, in logic programming, are expressed as Horn clauses.
• Horn clause has the format: P if Q1 and Q2 and . . . and Qk.
• This is read as "To deduce P, deduce Q1; deduce Q2; . . . deduce Qk."
• Rules are expressed in Prolog using relations (a.k.a. predicates) -- evaluates true or false.
• A fact is a special case of a rule (Horn clause for which k=0, e.g. P.) -- it is trivially true.
• The P's and Qi's are called terms in Prolog.
• After facts and rules are established, computation is triggered by queries (a.k.a. goals)
• Queries are entered interactively at command line having prompt "?-"
• Prolog attempts to satisfy the query based on facts and rules. Process is called unification.

Enough already! Let's look at an example.

EXAMPLE: FAMILY RELATIONSHIPS

Here are some Prolog facts, based on my family and my wife Nancy's family:

mother(iva, pete).
mother(iva, ed).
mother(iva, becky).
mother(kay, nancy).
mother(kay, bob).
mother(kay, diane).
mother(becky, katie).
husband(dwight, iva).
husband(robert, kay).
husband(pete, nancy).

The line "mother(X,Y)." is read" "X is the mother of Y." (as an aside, it is possible in Prolog to use natural language specifications of facts and rules).

Now, introduce a rule.

This corresponds to the Horn clause with P = wife(X,Y) and Q1 = husband(Y,X).

Read it as "wife(X,Y) is true if husband(Y,X) is true." Or, "X is the wife of Y if Y is the husband of X". X and Y are variables, which begin with upper-case letters in Prolog.

Here is a second rule.

Read it as "X is the father of Y if, for some Z, X is the husband of Z and Z is the mother of Y." We'll skip the social implications of this rule.

In Amzi Prolog, the facts and rules would be typed into a text editor and stored in a file. Note that all facts and rules end with a period (.).

Given these facts and rules, we can now issue some queries. In Amzi Prolog, queries are entered by starting up a listener (window with interactive command line interpreter). The query prompt is: ?-

In the interactions below, Prolog responses will be in italics.

We start by telling it to consult our set of facts and rules. Assume they were stored under the file name: FAMILY.PRO.

Note that query syntax is similar to fact/rule syntax. Also, it must end with a period.

If our query can be matched to a fact, it is trivially true. For example:

Queries can also be matched to a number of facts. Consider the query: mother(kay, Who).

D is a variable. Prolog will attempt to find all possible values of D for which the query succeeds.

If no matches are found, the system responds "no" If at least one match is found, it responds with the first match, as shown above. It then waits for you to respond. If you press the ENTER key, it will abandon the search and issue another query prompt (it will also respond "yes" because there were additional matches -- bob and diane -- that you did not see).

?- mother(kay, Who).
Who = nancy <-- you press ENTER here
yes
?-

If you press the SEMICOLON key (;) instead, it will continue the search and present the next match.

?- mother(kay, Who).
Who = nancy ; <-- you press SEMICOLON here
Who = bob

If you continue to press SEMICOLON, eventually the list will be exhausted and it responds with "no" then issues the next query prompt.

The unification process really kicks in when you issue a prompt like:

What would you expect the response to be?

Suppose you wanted to add a new rule to define the "parent" relationship? Logically, I'd express this as "X is a parent of Y if X is the mother of Y or X is the father of Y." I was unable to find any explanation for how to express the "or" relationship, so I split it up into two rules and it worked fine.

(text section 11.5)

Pseudo-code given in Figure 11.12, p 450

start with a query as the current goal;
while the current goal is nonempty do
	choose the leftmost subgoal;
	if a rule applies to the subgoal then
		select the first applicable rule;
		form a new current goal
	else
		backtrack
	end if;
end while;
succeed

Trace the example of the query: mother(X,Y), mother(Y,Z).
Several backtracks required.

Related Home Pages: notes | CSC 326 | Peter Sanderson | Computer Science | SMSU

Peter Sanderson ( PeteSanderson@mail.smsu.edu )