Logic programming in Prolog
• A little background
• A bit of terminology
• A note on semantics
• Prolog warm-up
• SWI Prolog
• A session with Prolog
• Two interpretations
• Arithmetic
• Compound objects
• Lists
• Non-determinism
• Last words
Reading: Chapter 16, these notes, tutorials on the Web.
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 1
A little background
• Prolog was invented in 1970, first implemented in 1972, first implemented efficiently in 1975.
• Excellent commercial-strength implementations have existed since early 1980s.
• After 30 years, Prolog has been unmatched as an unusually powerful language for a fairly wide range of applications (including software prototyping and runnable specifications) but it is amazingly underappreciated.
• People do not even know that Prolog is faster than Java when applied in the right way, and that software production can be an order of magnitude faster in this very high level programming language.
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 2
A bit of terminology
Facts and rules together are called clauses. A group of clauses with the same name and the same number of parameters makes up a predicate. Some predicates we will see in these notes:
alcoholic man
avoid no_hat_at_all
catch_colds no_hat_in_winter
divisor_set non_drinker
drinks
ill
in_range
in_range2
prime
smokes
will_dance
will_talk
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Prolog, page 3
A bit of terminology (2)
Objects in Prolog are called terms. A term can be:
a constant,
a number,
a variable,
a compound object (in particular a list).
Terms are the only data structures in Prolog — and they are quite sufficient!
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 4
A note on semantics
There are no automatic checks in Prolog to ensure the semantic integrity of your program. For example:
healthy_habits( X ) :-
drinks( X, _Y ), smokes( X ).
Formally, this is correct, but the real-world relationship that this
name suggests does not hold!
This is even worse:
likes( jim, mary ) :-
\+ likes( jim, mary ).
Prolog accepts it as a syntactically correct rule, but cannot use it properly: there is an infinite loop.
?- likes( jim, mary ).
ERROR: (user://1:25):
Out of local stack
continued…
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 5
beer( grolsch ).
?- beer( B ).
B = grolsch ;
B = grolsch ;
No
beer( grolsch ).
A note on semantics (2)
If you write
tall( millie ).
short( millie ).
both these (conflicting!) facts will be recorded. tall and short are symbols without any special meaning. Prolog does not know that there is a connection: the programmer must specify it.
Finally, if you give the same fact twice, it will be recorded twice.
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Prolog, page 6
… concluded
Prolog warm-up
(a) People who catch colds should avoid open swimming pools in winter.
(b) Everybody who doesn’t wear a hat in winter catches colds.
(c) Everybody who doesn’t wear a hat at all doesn’t wear a hat in winter.
(d) Jacky never wears a hat.
(e) What should Jacky avoid?
[1] If Jacky catchs colds then Jacky should avoid open swimming pools in winter.
[2] If Jacky doesn’t wear a hat in winter then Jacky catches cold.
[3] If Jacky never wears a hat then Jacky doesn’t wear a hat in winter.
[4] Obviously Jacky never wears a hat.
By [4], [3], [2], [1], Jacky should avoid open swimming pools in winter.
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 7
Prolog warm-up (2)
Let’s translate this into Prolog.
% (a) [text after % is a comment]
avoid( Person, swimming_pools_in_winter ) :-
catch_colds( Person ).
/* (b) [a bracketed comment] */ catch_colds( Person ) :-
no_hat_in_winter( Person ). % (c)
no_hat_in_winter( Person ) :- no_hat_at_all( Person ).
% (d)
no_hat_at_all( jacky ).
Now, we ask Prolog the question:
% (e)
?- avoid( jacky, What ).
What = swimming_pools_in_winter Yes
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 8
Another example
(f) A prime number N is a number whose set of divisors contains only 1 and N.
(g) The set of divisors of a number N is the set of numbers in the range 1 .. N which divide N exactly.
Question
(h) Is 19 a prime number? is 21?
A slightly more efficient algorithm
(i) 2 is a prime number.
(j) A number N greater than 2 is prime if it is odd and its set of
odd divisors contains only 1 and N.
(k) The set of odd divisors of an odd number N is the set of
numbers in the sequence 1, 3, 5, …, N which divide N exactly.
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 9
Prolog warm-up (3)
=:= is a built-in comparison, one of many
Prolog warm-up (4)
Again, let’s translate this into Prolog.
% (f)
prime( N ) :-
divisor_set( N, [1, N] ). % (g)
divisor_set( N, DivSet ) :- setof( K,
( in_range( K, 1, N ), N mod K =:= 0 ),
DivSet ).
setof: built-in
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 10
continued…
Prolog warm-up (5)
Let’s now define a range of values.
% (g’) two cases are possible in_range( K, K, High ) :-
K =< High.
in_range( K, Low, High ) :-
Low < High,
% "is" resembles assignment: Low1 is Low + 1,
in_range( K, Low1, High ).
Now, the question:
% (h)
?- prime( 19 ). Yes
?- prime( 21 ). No
... concluded
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Prolog, page 11
Prolog warm-up (6)
The more efficient version:
% (i)
prime( 2 ).
% (j)
prime( N ) :-
N mod 2 =:= 1,
divisor_set( N, [1, N] ). % (k)
divisor_set( N, DivSet ) :- setof(
K,
( in_range2( K, 1, N ),
N mod K =:= 0 ), DivSet ).
continued...
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 12
Prolog warm-up (7)
% (k')
in_range2( K, K, High ) :-
K =< High.
in_range2( K, Low, High ) :-
Low < High,
Low1 is Low + 2,
in_range2( K, Low1, High ).
And the question:
% (h)
?- prime( 19 ).
Yes
?- prime( 21 ).
No
... concluded
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Prolog, page 13
SWI Prolog
We will work in SWI Prolog, an excellent public- domain implementation for industrial-strength applications. It is installed on site2, SITE’s Linux server. Call ssh to connect to site2.
Feel free to get your own copy—for Windows— but submit work tested in Linux. Note that it is donateware.
{site2}szpak(1)$ alias pl /usr/local/swipl/lib/pl-5.2.8/bin/i686-linux/pl % pl
Welcome to SWI-Prolog (Multi-threaded, Version 5.2.8)
Copyright (c) 1990-2003 University of Amsterdam.
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software, and you are welcome to redistribute it under certain conditions. Please visit http://www.swi-prolog.org for details.
For help, use ?- help(Topic). or ?- apropos(Word).
?- halt. {site2}szpak(2)$
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 14
{site2}szpak(1)$ pl
Welcome to SWI-Prolog [...]
For help, use ?- help(Topic). or ?- apropos(Word).
On-line help
?- apropos(write). put/1
put/2
put_byte/1 put_byte/2 put_char/1 put_char/2 put_code/1 put_code/2 write_term/2 write_term/3 write_canonical/1 write_canonical/2 write/1
write/2 writeq/1 writeq/2 writeln/1 writef/1 writef/2 swritef/3 swritef/2 tty_put/2 Section 4-33 Section 4-33-1 Section 7-6-3-5
Yes
?- help(write). write(+Term)
Write a character
Write a character
Write a byte
Write a byte on a
Write a character
Write a character
Write a character-code
Write a character-code on a stream Write term with options
Write term with options to stream
on a stream stream
on a stream
Write a term with quotes, Write a term with quotes, Write term
Write term to stream Write term, insert quotes Write term, insert quotes Write term, followed by a Formatted write Formatted write Formatted write Formatted write
Write control string to terminal "Formatted Write"
"Writef"
"An example: defining write/1 in C"
Write Term to the current output, using brackets and operators where appropriate. See current_prolog_flag/2 for controlling floating point output format.
write(+Stream, +Term) Write Term to Stream.
Yes ?-
on stream on a string on a string
ignore operators
ignore operators on a stream
on stream newline
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Prolog, page 15
A session with Prolog
{site2}szpak(1)$ cat bad_habits_1 likes( jim, sandra ).
likes( jim, bill ).
likes( peggy, sam ).
likes( bill, sandra ).
drinks( jim, beer ). drinks( peggy, coke ). drinks( bill, juice ). drinks( sam, gin ).
smokes( bill ).
smokes( sandra ).
smokes( sam ).
will_dance( jim, peggy ) :- drinks( peggy, coke ).
will_dance( bill, sandra ) :- likes( bill, sandra ), drinks( sandra, beer ).
will_dance( sam, peggy ) :- likes( peggy, sam ), drinks( sam, gin ),
% does not smoke
\+ smokes( peggy ).
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Prolog, page 16
A session with Prolog (2)
{site2}szpak(2)$ pl
Welcome to SWI-Prolog (Multi-threaded, Version 5.2.8) [...]
?- [bad_habits_1].
% bad_habits_1 compiled 0.00 sec, 2,056 bytes
Yes
?- likes( jim, bill ).
Yes
?- drinks( bill, gin ).
No
?- will_dance( jim, peggy ).
Yes
?- will_dance( bill, sandra ).
No
?- will_dance( sam, peggy ).
Yes
?- smokes( terry ).
No
?- halt.
load file
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Prolog, page 17
A session with Prolog (3)
{site2}szpak(3)$ cat bad_habits_2 likes( jim, sandra ).
likes( jim, bill ).
likes( peggy, sam ).
likes( bill, sandra ).
drinks( jim, beer ). drinks( peggy, coke ). drinks( bill, juice ). drinks( sam, gin ). drinks( sandra, beer ) :-
drinks( jim, beer ).
smokes( bill ).
smokes( sandra ).
smokes( sam ).
will_dance( jim, peggy ) :- drinks( peggy, coke ).
will_dance( bill, sandra ) :- likes( bill, sandra ), drinks( sandra, beer ).
will_dance( sam, peggy ) :- likes( peggy, sam ), drinks( sam, gin ),
% does not smoke
\+ smokes( peggy ).
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Prolog, page 18
A session with Prolog (4) load a file
{site2}szpak(4)$ pl bad_habits_2
% bad_habits_2 compiled 0.00 sec, 2,140 bytes Welcome to SWI-Prolog [...]
?- likes( jim, bill ).
Yes
?- drinks( bill, gin ).
No
?- will_dance( jim, peggy ).
Yes
?- will_dance( bill, sandra ).
Yes
?- will_dance( sam, peggy ).
Yes
?- smokes( terry ).
No
?- halt.
was: No
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Prolog, page 19
A session with Prolog (5)
{site2}szpak(5)$ cat bad_habits_3 likes( jim, sandra ).
likes( jim, peggy ).
likes( peggy, sam ).
likes( bill, sandra ).
drinks( jim, beer ). drinks( peggy, coke ). drinks( bill, juice ). drinks( sam, gin ). drinks( sandra, beer ) :-
drinks( jim, beer ).
smokes( bill ).
smokes( sandra ).
smokes( sam ).
will_dance( jim, peggy ) :- drinks( peggy, coke ).
will_dance( bill, sandra ) :- likes( bill, sandra ), drinks( sandra, beer ).
will_dance( sam, peggy ) :- likes( peggy, sam ), drinks( sam, gin ),
% does not smoke
\+ smokes( peggy ).
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Prolog, page 20
A session with Prolog (6)
{site2}szpak(6)$ pl -f bad_habits_3
% bad_habits_3 compiled 0.00 sec, 2,140 bytes Welcome to SWI-Prolog [...]
?- drinks( Who, gin ).
Who = sam ;
No
?- likes( jim, Whom ).
Whom = sandra ; Whom = peggy ; No
?- will_dance( P1, P2 ).
P1 = jim
P2 = peggy ;
P1 = bill
P2 = sandra ;
P1 = sam
P2 = peggy ;
No
?- ^D
% halt {site2}szpak(7)$
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Prolog, page 21
An interlude
Who, Whom, P1, P2 are variables: unknown objects about which we wish to find out more.
Numbers in Prolog have the usual syntax, for example 23, -99.8, 10e3.
Variables are written as identifiers that start with a capital letter or an underscore. Note: a variable can only get its value once -- this will be explained soon.
Constants are written as identifiers that start with a small letter, for example
sandra, catch_colds, likes.
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 22
continued...
An interlude (2)
Constants can also be symbolic: almost any combination of
+-*/<=>.:@#$%^&?
is valid, for example
> @=< =:=
.:. <==> ::==
Finally, a quoted constant is a sequence of any characters in single quotes, for example
‘Hello, world!’
A single quote must be repeated:
‘Isn”t it nice?’
… concluded
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 23
A session with Prolog (7)
{site2}szpak(7)$ cat bad_habits_4
likes( jim, sandra ). likes( jim, peggy ). likes( peggy, sam ). likes( bill, sandra ).
drinks( jim, beer ). drinks( peggy, coke ). drinks( bill, juice ). drinks( sam, gin ). drinks( sandra, beer ) :-
drinks( jim, beer ).
smokes( bill ).
smokes( sandra ).
smokes( sam ).
will_dance( jim, peggy ) :- drinks( peggy, coke ).
will_dance( bill, sandra ) :-
likes( bill, sandra ),
drinks( sandra, beer ).
will_dance( sam, peggy ) :- likes( peggy, sam ), drinks( sam, gin ),
\+ smokes( peggy ).
ill(X) :- smokes( X ),
drinks( X, Y ), alcoholic( Y ).
alcoholic( beer ).
alcoholic( gin ).
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Prolog, page 24
variables in rules
{site2}szpak(8)$ pl -f bad_habits_4
% bad_habits_4 compiled 0.00 sec, 2,596 bytes Welcome to SWI-Prolog […]
?- ill(Somebody). Somebody = sandra ; Somebody = sam ;
No
?- ^D % halt
A session with Prolog (8)
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Prolog, page 25
{site2}szpak(9)$ cat bad_habits_5 likes( jim, sandra ).
likes( jim, peggy ).
likes( peggy, sam ).
likes( bill, sandra ).
A session with Prolog (9)
ill(X) :- smokes( X ), drinks( X, Y ), alcoholic( Y ).
alcoholic( beer ). alcoholic( gin ).
will_talk( peggy, M ) :- man( M ),
non_drinker( M ).
non_drinker( M ) :- drinks( M, B ), \+ alcoholic( B ).
non_drinker( M ) :- \+ drinks( M, _B ).
man( jim ).
man( bill ).
man( sam ).
drinks( jim, beer ). drinks( peggy, coke drinks( bill, juice drinks( sam, gin ). drinks( sandra, beer
drinks( jim, beer
smokes( bill ). smokes( sandra ). smokes( sam ).
). ).
) :- ).
will_dance( jim, peggy ) :- drinks( peggy, coke ).
will_dance( bill, sandra ) :- likes( bill, sandra ), drinks( sandra, beer ).
will_dance( sam, peggy ) :- likes( peggy, sam ), drinks( sam, gin ),
\+ smokes( peggy ).
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Prolog, page 26
{site2}szpak(10)$ pl -f bad_habits_5 % bad_habits_5 compiled […]
?- will_talk( peggy, ThatGuy ).
ThatGuy = bill ;
No
?- will_talk( peggy, A_man ), | likes( peggy, A_man ).
No
?- drinks( M, D ),
man( M ).
M = jim
D = beer ;
M = bill
D = juice ;
M = sam D = gin ;
No
?- man( M ),
drinks( M, D ).
M = jim
D = beer ;
M = bill
D = juice ;
M = sam D = gin ;
No
A session with Prolog (10)
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Prolog, page 27
continued…
A session with Prolog (11)
?- drinks( M, D ), | \+man(M).
M = peggy
D = coke ;
M = sandra
D = beer ;
No
?- \+ man( M ),
| drinks( M, D ).
No
?- ^D % halt
Variables are local in a fact, rule or query. There are no global variables.
The first occurrence of a variable must not be “under negation”.
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 28
… concluded
{site2}szpak(11)$ cat family father( anthony, james ).
A session with Prolog (12)
father( john, paul ). father( luke, peter ). father( matthew, mark ). father( peter, john ). father( peter, matthew ). father( thomas, anthony ). father( thomas, luke ).
grandfather( X, Y ) :- father( X, Z ), father( Z, Y ).
greatGrandfather( X, Y ) :- father( X, Z ),
grandfather( Z, Y ).
greatGreatGrandfather( X, Y ) :-
father( X, Z ), greatGrandfather( Z, Y ).
ancestor( X, Y ) :-
father( X, Y ).
ancestor( X, Y ) :-
father( X, Z ),
ancestor( Z, Y ).
recursion
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Prolog, page 29
A session with Prolog (13)
{site2}szpak(12)$ pl -f family
% family compiled 0.00 sec, 2,060 bytes Welcome to SWI-Prolog […]
?- ancestor( peter, mark ).
Yes
?- ancestor( X, john ).
X = peter ; X = luke ;
X = thomas ; No
?- ancestor( matthew, X ).
X = mark ;
No
?- ancestor( X, Y ).
… 20 answers
?- ^D % halt
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Prolog, page 30
Two interpretations
The definition of ancestor can be read like this:
Your father is your ancestor, and the father of your ancestor
is your ancestor, too.
This is an example of the declarative (or static, or logical) interpretation of Prolog definitions. Queries, however, are used to find answers, not only to confirm truths recorded in the Prolog database. Finding is necessarily dynamic, so we need another interpretation.
The procedural (or imperative, or control) interpretation of Prolog facts and rules focuses on the process of finding answers:
To find an ancestor of Y, find his father; or else, take his father (call him Z) and find Z’s ancestor.
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 31
Two interpretations (2)
This is the description of a procedure with two variants, one of which is chosen for execution. The procedure’s name is ancestor, and it has
two parameters. The body of the second variant consists of two procedure calls:
first, father with 2 parameters; next, ancestor with 2 parameters.
For consistency, a fact is treated as a procedure with an empty body.
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 32
Another example:
ill(X) :- smokes( X ),
drinks( X, Y ),
alcoholic( Y ).
To find an ill person, find somebody who smokes, then find a drink which he drinks, and finally check whether this drink is alcoholic.
This procedure has only one variant, and its body contains three calls.
Two interpretations (3)
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 33
Two interpretations (4)
Prolog has no conditional statements and no iterations. The only operations allowed in the body of a procedure are other procedure calls—and this is quite sufficient!
Note that the order of conditions is important for the procedural reading:
ill( X ) :-
alcoholic( Y ) , smokes( X ), drinks( X, Y ).
To find an ill person, find an alcoholic drink, then find a smoker, and finally check whether this smoker drinks this drink.
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 34
% data validation:
% A, B, C should be numbers q_EQN( A, B, C, X1, X2 ) :-
number( A ),
number( B ),
number( C ),
q_eqn( A, B, C, X1, X2 ).
a built-in test, one of many
Arithmetics
{site2}szpak(13)$ cat q_eqn % A*X*X + B*X + C = 0,
% A cannot be zero.
q_eqn( A, _B, _C, none, none ) :-
A =:= 0.
q_eqn( A, B, C, X1, X2 ) :-
A =\= 0,
Delta is B*B – 4.0*A*C, q_eqn_( Delta, A, B,
X1, X2 ).
% q_eqn_ are auxiliary rules
q_eqn_( Delta, _A, _B, imag, imag ) :-
Delta < 0.
% two real solutions, may be identical q_eqn_( Delta, A, B, X1, X2 ) :-
Delta >= 0,
SqrtDelta is sqrt( Delta ),
X1 is (-B-SqrtDelta ) / (2.0*A ), X2 is (-B+SqrtDelta ) / (2.0*A ).
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Prolog, page 35
{site2}szpak(14)$ pl -f q_eqn % q_eqn compiled […]
?- q_eqn( 8, -6, -35, X, Y ).
X = -1.75
Y = 2.5
Yes
?- q_eqn( 8, -6, 35,
?- q_eqn( 0, -6, -35, X, Y ).
X = none
Y = none
Yes
?- q_EQN( 8, -6, abc, X, Y ).
No
?- q_eqn( 8, -6, abc, X, Y ).
ERROR: Arithmetic: `abc/0’ is not a function ^ Exception: (8) _G260 is-6* -6-4.0*8*abc ?
X, Y ).
X = imag
Y = imag
?- ^D Yes % halt
Arithmetics (2)
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 36
{site2}szpak(15)$ cat pow
% pow( X, Y, Z ) means X ^ Y = Z
% X^1 = X
pow( X, 1, X ). %forY>1,X^Y =X*X^(Y-1) pow(X,Y,Z) :-
Arithmetics (3)
Y > 1,
Y1 is Y – 1,
pow( X, Y1, Z1 ), Z is X * Z1.
{site2}szpak(16)$ pl -f pow % pow compiled […]
?- pow( 7, 3, P ). P = 343
Yes
?- pow( 7, 3, 345 ).
No
?- ^D % halt
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Prolog, page 37
Compound objects
Constants, including numbers, are simple objects. They have no internal structure. We do not declare constants: we use them whenever we need them.
We also need compound objects: ordered collections of simpler objects that are in some relationship. Examples:
two sides of a rectangle, such as 19 by 24,
the time in hours and minutes, such as 19:24.
Since the pair (19, 24) may represent a rectangle or a time, we distinguish them by naming the relationship:
rectangle( 19, 24 ) time_of_day( 19, 24 )
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 38
Compound objects (2)
We can also represent the time with seconds:
time_of_day( 19, 24, 37 )
This is a different object, but Prolog easily distinguishes these two representations of time. The name is the same, but the arity is not. We have
time_of_day/2 (two components),
time_of_day/3 (three components). Again, we do not need to declare compound objects.
The name of a compound object (and the name of the relationship between components) is called a functor. A component, called an argument, can be any object.
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 39
Example:
customer(
name( jim, white ), address(
street( 17, main ),
city( bytown, ontario ) ))
A compound object is incompletely specified if it contains variables — unknown components. An example:
customer( X,
address(
street( 17, main ),
city( bytown, ontario ) ) )
“Any customer who lives at 17 Main, Bytown, Ontario.”
Compound objects (3)
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 40
Compound objects (4)
customer(
name( X, white ), address(
street( Y, main ), city( Z, ontario ) ) )
“Any customer by the name of White who lives at Main, any town, Ontario.”
A variable may appear more than once. For example,
rectangle( X, X )
represents a square!
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 41
Compound objects (5)
{site2}szpak(17)$ cat empl
% empl( X, Y, Z ) means “employee X works
% for department Y and earns Z dollars”
empl( name( john, smith ),
dept( appliances, 1 ), 350 ).
empl( name( nancy, brown ),
dept( appliances, 2 ), 375 ).
empl( name( peggy, lee ),
dept( cosmetics, 1 ), 410 ).
empl( name( tania, smith ),
dept( shoes, 1 ), 325 ).
empl( name( fran, jones ),
dept( appliances, 2 ), 380 ).
empl( name( carrie, mcrae ),
dept( toys, 1 ), 350 ).
continued…
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 42
_ is a “sink”, a don’t care variable
Compound objects (6)
{site2}szpak(18)$ pl -f empl % empl compiled […]
?- empl( name( _, smith ), X, _ ).
X = dept(appliances, 1) ; X = dept(shoes, 1) ;
No
?- empl( name( First, Last ),
dept( appliances, _ ), _ ).
First = john
Last = smith ;
First = nancy Last = brown ;
First = fran
Last = jones ;
No
?- empl( Name, _, D ), D > 375.
Name = name(peggy, lee) D = 410 ;
Name = name(fran, jones) D=380;
No
?- ^D % halt
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Prolog, page 43
… concluded
Lists in Prolog are normal compound objects. By
convention, we use the functor ./2 (dot with two
arguments) to build lists. We treat the structure
.(p, .(q, .(r, [] ) ) )
as a representation of the 3-element sequence p, q, r. [] is the empty list.
List are so useful that a special notation has been introduced for them. A list is a sequence of objects in square brackets, separated by commas:
[p, q, r]
is the same as
.(p, .(q, .(r, [])))
Lists
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 44
Lists (2)
[1, 3, 8, 16, 23, 34] [[sam,jimmy], [peggy,sally] ] [X, Y]
A list may contain differently shaped objects. This is a correct, even if a bit useless, Prolog list:
[rectangle(78, 78), name(fran, jones), street(17, main ), ‘Hello, world!’]
Finally, the notation
[ Hd | Tl ]
means a list with a head Hd and a tail Tl,
or .(Hd, Tl).
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 45
Lists (3)
Let us define the relation between a list and its length. The length of an empty list is 0:
length_( [], 0 ).
The length of a non-empty list is 1 more than the length of its tail:
length_([_H|T],Len) :- length_( T, Len1 ),
Len is Len1+1.
By the way, length is built into most Prolog systems and need not (cannot in SWI Prolog!) be defined by the user.
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 46
Now, let us pick an element of a list by position. The first element of a non-empty list is its head:
nth( 1, [Hd | _Tl], Hd ).
Element number N > 0 of a non-empty list is element number N-1 of its tail:
nth( N, [_ | Tl], NthElem ) :- N > 1,
N1 is N – 1,
nth( N1, Tl, NthElem ).
Lists (4)
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 47
Trace
The trace is a built-in Prolog structure that displays the set of instantiations at each inference step
– –
Sheds light on how the inference process is conducted and variables are instantiated.
Composed of four events:
– Call (beginning to satisfy a goal)
– Exit (when a goal has been satisfied)
– Redo (when backtrack occurs)
– Fail (when goal fails)
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 48
likes(jake,chocolate). likes(jake, apricots). likes(darcie, licorice). likes(darcie, apricots).
trace.
likes(jake, X), likes(darcie, X). (1) 1 Call: likes(jake, _0)?
(1) 1 Exit: likes(jake, chocolate) (2) 1 Call: likes(darcie, chocolate)? (2) 1 Fail: likes(darcie, chocolate) (1) 1 Redo: likes(jake, _0)?
(1) 1 Exit: likes(jake, apricots)
(3) 1 Call: likes(darcie, apricots)? (3) 1 Exit: likes(darcie, apricots)
X = apricots
Trace (2)
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Prolog, page 49
Non-determinism
Java is a deterministic programming language (as are C and Pascal); at any point in the execution of a Java program there is exactly one next step.
Prolog, however, is nondeterministic. There are points in the execution of a Prolog program when there are multiple legal next steps.
The way this is specified in Prolog is to give multiple definitions of the same procedure. For example, we could write a procedure to find both square roots of a positive real number by:
a_sqrt(X,Y) :- X > 0,
Y is sqrt(X).
a_sqrt(X,Y) :- X > 0,
Y is -sqrt(X).
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 50
Non-determinism (2)
Prolog can produce multiple answers to a query, one by one. When we type a semicolon after getting query results, Prolog looks for another answer. We will now show how this property — called non-determinism — helps program in a very general way.
Let us define the membership relation between a list and its element. The head of a non-empty list is its element:
element( Hd, [Hd | _Tl] ).
The same element can be found further on the list:
element( Elem, [ _Hd | Tl ] ) :-
element( Elem, Tl ).
By the way, member is the built-in version in SWI Prolog and in many other Prolog systems.
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 51
Non-determinism (3)
The procedural interpretation, the base case
To find an element X of a given list, take this list’s head as X.
or
To find a list with a given element X, construct a list with X as its head.
The recursive case
To find an element X of a given list, make X an element of this list’s tail.
or
To find a list with a given element X, construct a list with anything as its head and X somewhere in its tail.
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 52
?- element( 2, [1, 2, 3] ).
Yes
?- element( X, [1, 2] ).
X=1; X=2;
No
?- element( 3, [A, B] ).
A=3
B = _G160 ;
A = _G157 B=3;
No
Non-determinism (4)
?- element( 5, LL ).
LL = [5|_G208] ;
LL = [_G207, 5|_G211] ;
LL = [_G207, _G210, 5|_G214] Yes
The last query has infinitely many answers. We could go on forever.
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Prolog, page 53
Non-determinism (5)
Here is an immortal classic of Prolog teaching:
% list L2 appended to [] is L2 append( [], L2, L2 ).
% list L2 appended to [E | L1] has % E as its head,
% L2 appended to L1 as its tail. append([E|L1],L2,[E|L3]) :-
append( L1, L2, L3 ).
This predicate has an astounding variety of uses! First of all, simple concatenation of lists:
?- append( [a], [b], LL ).
LL = [a, b] ;
No
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 54
Next, find the second list:
?- append( [a], X, [a, b, c] ).
X = [b, c] ;
No
Or the first list:
?- append( Y, [c], [a, b, c] ).
Y = [a, b] ;
No
Non-determinism (6)
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 55
We can even find both lists!
?- append(F, S, [a, b]).
Non-determinism (7)
?- append( F, S, FS ).
F = []
S = _G158
FS = _G158 ;
F = [_G239]
S = _G158
FS = [_G239|_G158] ;
F = [_G239, _G245]
S = _G158
FS = [_G239, _G245|_G158]
Yes
F = []
S = [a, b] ;
F = [a] S = [b] ;
F = [a, b]
S = [] ;
No
Or there can be no information about any lists…
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Prolog, page 56
Finally, this mixed affair:
?- append([X, 55], [Y], [77, Z, 20]).
X = 77
Y = 20
Z = 55 ;
No
It works because Prolog cleverly matches objects. [Y] appended to [X, 55] gives [X, 55, Y].
Now we put together:
[X, 55, Y]
[77, Z, 20]
Non-determinism (8)
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 57
Non-determinism (9)
On the other hand, in this query
?- append([X, 55], [Y], [77, Z]).
we have [X, 55, Y] against [77, Z] — a match
fails because the lists have different lengths!
Other examples of mismatches for lists:
[a,b,c] and [b|Y] different heads
[1, 2, 3, 4] and [1, 3 | T]
different tails, or recursively different heads in
[2,3,4] and [3|T]
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 58
Finally, a most beautiful definition:
intersect( List1, List2 ) :-
element( X, List1 ),
element( X, List2 ).
?- intersect( [a, c, e, g], [b, c, d] ).
Yes
?- intersect( [a, c, e, g], [b, d, f] ).
No
Two lists intersect if they have a common element.
Non-determinism (10)
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 59
Under the surface: Prolog’s inference engine
• The Prolog inference mechanism is driven by a simple yet powerful rule: Resolution
• The Resolution rule was invented in 1965 by Alan Robinson at Syracuse University
– It allows inferred propositions to be computed from given propositions
– Therefore enabling automatic theorem proving!
• To apply resolution, the Knowledge Base must be
converted to Clausal Form
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 60
Under the surface: Prolog’s inference engine (2)
Clausal Form
– Aimed at avoiding redundancy in the KB
𝐵∪𝐵∪⋯∪𝐵⊂𝐴∩𝐴∩⋯∩𝐴 12𝑛12𝑚
– If I have all the A’s, at least one B is true.
– Only disjunction in the left side; only conjunction in the right side.
– All predicate calculus propositions can be converted to clausal form
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 61
Under the surface: Prolog’s inference engine (3)
Back to Resolution…
𝑇⊂𝑃
Example:
2
𝑄⊂𝑇 1
_________
𝑄⊂𝑃 12
older(mary, john) mother(mary, john)
wiser(mary, john) older(mary, john) Then we can infer
wiser(mary, john) mother(mary, john) S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 62
Under the surface: Prolog’s inference engine (4)
• Resolution is more complex than what was shown
– will need to find values for variables
– this process is called unification
– assigning a temporary value to a variable to allow unification is called instantiation.
• Resolution is guaranteed to detect any inconsistency in a given set of propositions
– based on its refutation complete property – given a set of inconsistent propositions,
Resolution can prove them to be inconsistent. S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 63
Under the surface: Prolog’s inference engine (5)
• One way to boost the efficiency of the Resolution rule is by restricting the form of the propositions
– Clausal form ok; not the best option – Better alternative: Horn clauses
– A Horn clause has either:
– a single atomic proposition in the left side (headed)
likes(bob, trout) likes(bob, fish) fish(trout)
– or an empty left side (headless)
father(bob, jake)
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 64
Resolution order control
• In a pure logic programming environment, the order of attempted matches is nondeterministic and all matches would be attempted concurrently
• However, Prolog allows the user, for efficiency reasons, to control the ordering of pattern matching during resolution.
– by altering the order in which clauses are stated in the Knowledge Base
businessman(X), billionaire(X). – by means of the cut (!) operator
max(X,Y,Y) :- X =< Y, !. max(X,Y,X) :- X > Y.
– similar to GOTO in imperative languages; avoid if possible.
Prolog deficiencies
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 65
The closed-world assumption
• The only knowledge is what is in the database
• Query assumed to be false if it cannot be proved true
– But it may not be false at all
The negation problem
• Anything not stated in the database is assumed to be false
– Prolog’s not operator is not equivalent to a logical NOT
– It is satisfied if resolution cannot satisfy the goal.
– Prolog always uninstantiates all variables in all goals that fail.
not(not(some_goal)) is misleading
Prolog deficiencies (2)
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 66
Intrinsic limitations
• It is easy to state a sort process in logic, but difficult to actually do — it doesn’t know how to sort
sorted([]).
sorted([X]).
sorted([X, Y | List]) :- X <= Y,
sorted([Y | List]).
• What is the problem here?
– Terribly inefficient!
– Needs to try all possible permutations (in the worst case) before the list
can be sorted.
– This is an example of a problem for which Prolog was not created.
Prolog deficiencies (3)
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 67
Applications of Logic Programming
Relational database management systems
• SQL is a declarative language too
– The user does not describe how to retrieve the answer; rather, he/she
describes only the characteristics of the answer.
• A relational database management system (RDBMS) in Prolog?
– simple tables can be described by Prolog structures
– Relationships between tables can be enforced by Prolog rules. – only one language required to describe the RDBMS
– instead of data definition language, data manipulation language, etc.
– Prolog’s deductive capability already there; SQL has none. • Disadvantage: efficiency
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 68
Applications of Logic Programming (2)
Expert systems
• Computer systems that emulate human expertise in some particular domain.
• Consist of:
– a database of facts,
– an inferencing process,
– some heuristics about the domain and
– some friendly human interface that makes the system appear much like
an expert human consultant.
• Expert systems learn from their interaction with the users, so their
knowledge bases dynamically grow.
• Needs to interrogate the user when a certain piece of information is missing.
• Logic programming deals with potential inconsistencies in the knowledge
base.
• Logic programming can justify the conclusions it arrived at by means of the
trace mechanism.
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 69
Last words
Prolog has much more to offer. You are ready to explore it on your own:
• Advanced control, including the cut.
• Customizable term syntax.
• Logic grammars.
• Dynamic (on-the-fly) modification of Prolog code. • Programming with trees and graphs.
• Debugging tools.
• Programming in the large (modules).
• Graphics and user interface programming.
Here are some applications where Prolog is a programming language of
choice, for the best of software engineering reasons.
• Rapid software prototyping.
• Deductive databases.
• Language design and development.
• Expert systems.
• Artificial Intelligence:
Games, Planning, Machine Learning, Natural Language Processing.
S. Szpakowicz, N. Japkowicz, R. Falcon CSI 3120, Prolog, page 70