CSc 372 - Comparative Programming Languages
16 : Prolog -- Introduction

Christian Collberg

Department of Computer Science

University of Arizona

1 What is Prolog?

Prolog is a language which approaches problem-solving in a declarative manner. The idea is to define what the problem is, rather than how it should be solved.
In practice, most Prolog programs have a procedural as well as a declarative component -- the procedural aspects are often necessary in order to make the programs execute efficiently.

2 What is Prolog?


		     Algorithm = Logic + Control 		 Robert A. Kowalski

Prescriptive Languages:

Describe how to solve problem
Pascal, C, Ada,...
Also: Imperative, Procedural

Descriptive Languages:

Describe what should be done
Also: Declarative

Kowalski's equation says that

Logic - is the specification (what the program should do)
Control - what we need to do in order to make our logic execute efficiently. This usually includes imposing an execution order on the rules that make up our program.

3 Objects & Relationships

Prolog programs deal with

objects, and
relationships between objects

English:

``Christian likes the record''

Prolog:
$\begin{gprogram} \x likes(christian, record). \end{gprogram}$

4 Record Database

Here's an excerpt from Christian's record database:

$\begin{gprogram} is\_record(planet\_waves). \\ is\_record(desire). \\ is\_reco... ...ding\_year(desire, 1975). \\ recording\_year(slow\_train, 1979). \end{gprogram}$

5 Record Database...

The data base contains unary facts (is_record) and binary facts (recorded_by, recording_year).
The fact
$\begin{program} is\_record(slow\_train) \end{program}$
can be interpreted as
$\begin{program} slow\_train {\em is-a-record} \end{program}$
The fact recording_year(slow_train, 1979) can be interpreted as the recording year of slow_train was 1979.

6 Conditional Relationships

Prolog programs deal with conditional relationships between objects.

English:

``C. likes Bob Dylan records recorded before 1979''

Prolog:
$\begin{gprogram} likes(christian, X) :- \\ \xx is\_record(X), \\ \xx recorded... ...bob\_dylan),\\ \xx recording\_year(X, Year),\\ \xx Year < 1979. \end{gprogram}$

7 Conditional Relationships...

The rule
$\begin{gprogram} likes(christian, X) :- \\ \xx is\_record(X), \\ \xx recorded... ...bob\_dylan),\\ \xx recording\_year(X, Year),\\ \xx Year < 1979. \end{gprogram}$
can be restated as
``Christian likes X, if X is a record, and X is recorded by Bob Dylan, and the recording year is before 1979.''
Variables start with capital letters.
Comma (``,'') is read as and.

8 Asking Questions

Prolog programs

solve problems by asking questions.

English:

``Does Christian like the albums Planet Waves & Slow Train?'

Prolog:
$\begin{gprogram} \redtt{?- likes(christian, planet\_waves).}\\ yes\\ \redtt{?- likes(christian, slow\_train).}\\ no \end{gprogram}$

9 Asking Questions...

English:

``Was Planet Waves recorded by Bob Dylan?''

``When was Planet Waves recorded?''

``Which album was recorded in 1974?''

Prolog:
$\begin{gprogram} \redtt{?- recorded\_by(planet\_waves, bob\_dylan).} \\ \x yes\... ...\\ \redtt{?- recording\_year(X, 1974).} \\ \x X = planet\_waves \end{gprogram}$

10 Asking Questions...

In Prolog

"," (a comma), means "and'

English:

``Did Bob Dylan record an album in 1974?''

Prolog:
$\begin{gprogram} \redtt{?- is\_record(X),} \\ \xx \redtt{recorded\_by(X, bob\_dylan),} \\ \xx \redtt{recording\_year(X, 1974).} \\ yes \end{gprogram}$

11 Asking Questions...

Sometimes a query has more than one answer:

Use ";" to get all answers.

English:

``What does Christian like?''

Prolog:
$\begin{gprogram} \redtt{?- likes(christian, X).} \\ \x X = planet\_waves ; \\ \\ \x X = desire ; \\ \\ no \end{gprogram}$

12 Asking Questions...

Sometimes answers have more than one part:

English:

``List the albums and their artists!''

Prolog:
$\begin{gprogram} \redtt{?- is\_record(X), recorded\_by(X, Y).}\\ X = planet\_wa... ...\ Y = bob\_dylan ;\\ X = slow\_train,\\ Y = bob\_dylan ;\\ no \end{gprogram}$

13 Recursive Rules

``People are influenced by the music they listen to.

People are influenced by the music listened to by the people they listen to.''

$\begin{gprogram} listens\_to(bob\_dylan, woody\_guthrie). \\ listens\_to(arlo\_... ...nced\_by(X, Y) :- \=listens\_to(X,Z), \\ \> influenced\_by(Z,Y). \end{gprogram}$

14 Asking Questions...

English:

``Is Björk influenced by Bob Dylan?''

``Is Björk influenced by Woody Guthrie?''

``Is Bob Dylan influenced by Bruce Springsteen?''

Prolog:
$\begin{gprogram} \redtt{?- influenced\_by(bjork, bob\_dylan).} \\ yes \\ \redt... ... yes \\ \redtt{?- influenced\_by(bob\_dylan, bruce\_s).} \\ no \end{gprogram}$

15 Visualizing Logic

Comma (,) is read as and in Prolog. Example: The rule
$\begin{program} person(X) :- has\_bellybutton(X), not\_dead(X). \end{program}$
is read as
``X is a person if X has a bellybutton and X is not dead.''
Semicolon (;) is read as or in Prolog. The rule
$\begin{program} person(X) :- X=adam ; X=eve ; \\ \xxxx has\_bellybutton(X). \end{program}$
is read as
``X is a person if X is adam or X is eve or X has a bellybutton.''

16 Visualizing Logic...

To visualize what happens when Prolog executes (and this can often be very complicated!) we use the following two notations:

AND	OR

and	or

For AND, both legs have to succeed.
For OR, one of the legs has to succeed.

17 Visualizing Logic...

Here are two examples:

AND	OR

and-example	or-example

18 Visualizing Logic...

and and or can be combined:
and-or-example
This query asks
``Is there a person X who is adam, eve, or who has a bellybutton, and who is also not dead?''

19 Answering Questions

$\begin{gprogram} (1) \xx scientist(helder). \\ (2) \xx scientist(ron). \\ (3) ... ...:- scientist(X). \\ (6) \xx \redtt{?- logician(X), american(X).} \end{gprogram}$

The rule (5) states that
``Every scientist is a logician''
The question (6) asks
``Which scientist is a logician and an american?''

20 Answering Questions...

logician-3

21 Answering Questions...

logician

$\begin{gprogram} (1) \xx scientist(helder). \\ (2) \xx scientist(ron). \\ (3) ... ...:- scientist(X). \\ (6) \xx \redtt{?- logician(X), american(X).} \end{gprogram}$

22 Answering Questions...

logician-2

23 Answering Questions...

$\begin{gprogram} is\_record(planet\_waves). is\_record(desire). \\ is\_record(s... ..._by(X, bob\_dylan),\\ \xx recording\_year(X, Year), Year < 1979. \end{gprogram}$

24 Answering Questions...

likes

25 Answering Questions...

$\begin{gprogram} listens\_to(bob\_dylan, woody\_guthrie). \\ listens\_to(arlo\_... ...rk, bob\_dylan).} \\ \redtt{?- inf\_by(bjork, woody\_guthrie).} \end{gprogram}$

26 Answering Questions...

bjork1

27 Answering Questions...

bjork2

28 Map Coloring

ColoringMap1

``Color a planar map with at most four colors, so that contiguous regions are colored differently.''

29 Map Coloring...

A coloring is OK iff

The color of Region 1 $\neq$ the color of Region 2, and
The color of Region 1 $\neq$ the color of Region 3,...

$\begin{gprogram} color(R1, R2, R3, R4, R5, R6) :- \\ \x diff(R1, R2), diff(R1, ... ...ow). \\ diff(yellow, red).diff(yellow,blue). diff(yellow,green). \end{gprogram}$

30 Map Coloring...

$\begin{gprogram} \redtt{?- color(R1, R2, R3, R4, R5, R6).} \\ R1 = R4 = red, R2... ... \\ R1 = red, R2 = blue, \\ R3 = R5 = green, R4 = R6 = yellow \end{gprogram}$

ColoringMap2

31 Map Coloring - Backtracking

ColoringMap3

32 Map Coloring - Backtracking

ColoringMap4

33 Working with `gprolog`

gprolog can be downloaded from here: http://gprolog.inria.fr/.
gprolog is installed on lectura (it's also on the Windows machines) and is invoked like this:
$\begin{program} \redtt{> gprolog} \\ GNU Prolog 1.2.16\\ \redtt{\vert ?- [colo... ...ext(A, B), ...\\ \redtt{\vert ?- go(A,B,C,D,E,F).}\\ A = red ... \end{program}$

34 Working with `gprolog`...

The command [color] loads the prolog program in the file color.pl.
You should use the texteditor of your choice (emacs, vi,...) to write your prolog code.
The command listing lists all the prolog predicates you have loaded.

35 Working with `gprolog`...

$\scalebox{0.25}{\includegraphics{PS/gprolog.ps}}$

36 Readings and References

Read Clocksin-Mellish, Chapter 1-2.
http://dmoz.org/Computers/Programming/Languages/Prolog

Prolog by Example	Coelho & Cotta
Prolog: Programming for AI	Bratko
Programming in Prolog	Clocksin & Mellish
The Craft of Prolog	O'Keefe
Prolog for Programmers	Kluzniak & Szpakowicz
Prolog	Alan G. Hamilton
The Art of Prolog	Sterling & Shapiro

37 Readings and References...

Computing with Logic	Maier & Warren
Knowledge Systems Through Prolog	Steven H. Kim
Natural Language Processing in Prolog	Gazdar & Mellish
Language as a Cognitive Process	Winograd
Prolog and Natural Language Analysis	Pereira and Shieber
Computers and Human Language	George W. Smith
Introduction to Logic	Irving M. Copi
Beginning Logic	E.J.Lemmon

38 Prolog So Far

A Prolog program consists of a number of clauses:
Rules
- Have head + body:
```
 :- 

 
```
- Can be recursive
Facts
- Head but no body.
- Always true.

39 Prolog So Far...

A clause consists of

atoms

Start with lower-case letter.

variables

Start with upper-case letter.
Prolog programs have a
- Declarative meaning
  - The relations defined by the program
- Procedural meaning
  - The order in which goals are tried

40 Prolog So Far...

A question consists of one or more goals:
- ?- likes(chris, X), smart(X).
- "," means and
- Use ";" to get all answers
- Questions are either
  - Satisfiable (the goal succeeds)
  - Unsatisfiable (the goal fails)
- Prolog answers questions (satisfies goals) by:
  - instantiating variables
  - searching the database sequentially
  - backtracking when a goal fails

Christian S. Collberg
2005-10-05

CSc 372 - Comparative Programming Languages 16 : Prolog -- Introduction

CSc 372 - Comparative Programming Languages
16 : Prolog -- Introduction