Transcript chapter14-prolog - Korea University

Ch 14. An Introduction to Prolog
KU NLP
 an Implementation of logic as a programming
language(PROgramming in LOGig)
 many interesting contributions to AI problem
solving
 declarative semantics
 built-in unification
 high-powered techniques for pattern matching and search
Artificial Intelligence
1
KU NLP
14.1 Syntax for Predicate Calculus
Programming
 14.1.1 Representing Facts and Rules
 14.1.2 Creating, Changing, and Monitoring the
PROLOG Environment
 14.1.3 Lists and Recursion in PROLOG
 14.1.4 Recursive Search in PROLOG
 14.1.5 The Use of Cut
Artificial Intelligence
2
KU NLP
14.1.1 Representing Facts and
Rules(1)
 English
Predicate Calculus
PROLOG




and
or
only if
not
,
;
:not
 “Everyone likes Susie.”
 likes(X, susie).
or
likes(Everyone, susie).
 The set of people that are liked by George AND Susie
 likes(george, Y), likes(susie, Y).
 “George likes Kate OR George likes Susie.”
 likes(george, kate); likes(george, susie).
Artificial Intelligence
3
KU NLP
14.1.1 Representing Facts and
Rules(2)
 “George likes Susie if George likes Kate.”
 likes(george, susie) :- likes(george, kate).
 “Kate does not like Susie.”
 not(likes(kate, susie)).
 A Model for the database
 Database - a set of specifications describing the objects and
relations in a problem domain
 Queries to the database are patterns in the same logical
syntax as the database entries.
 Prolog interpreter uses pattern-directed search to find
whether these queries logically follow from the contents of
the database.
Artificial Intelligence
4
KU NLP
14.1.1 Representing Facts and
Rules(3)
 Prolog exmaple
likes(george, kate).
likes(george, susie).
likes(george, wine).
likes(susie, wine).
likes(kate, gin).
likes(kate, susie).
?- likes(george, kate).
yes
?- likes(kate, susie).
yes
?- likes(george, X).
X = kate
;
X = susie
;
X = wine
;
no
?- likes(george, beer).
no
Artificial Intelligence
5
KU NLP
14.1.1 Representing Facts and
Rules(4)
 Prolog interpertations
 The prompts with (;) forces a backtrack on the most recent
result. Continued prompts force Prolog to find all possible
solutions to the query
 Closed world assumption or Negations as failure

assumes that “anything is false if it is not known to be true.”
 Horn clause logic
 the left hand side(conclusion) of an implication must be a single
positive literal.
 An example of a rule
friends(X, Y) :- likes(X, Z), likes(Y, Z).
?- friends(george, susie).
yes
 Prolog doesn’t have global variables, the scope of X, Y, and Z is
limited to friends rule.
 Values bound to, X, Y, Z are consistent across the entire
expression.
Artificial Intelligence
6
KU NLP
14.1.2 Creating, Changing, and
Monitoring(1)
 assert - add a new predicate to the current DB.
 ?- assert(likes(david, sarah)).
 asserta(p) asserts the predicate P at the beginning.
 assertz(p) adds p at the end.
 retract(p) remove p from the DB
 place the file in the DB
 ?- consult(myfile)
 ?- [myfile]
 read(X) takes the next term from the current input
stream and binds it to X.
 write(X) puts X in the output stream.
Artificial Intelligence
7
KU NLP
14.1.2 Creating, Changing, and
Monitoring(2)
 see(X) opens the file X and defines the current
input stream as originating in X.
 tell(X) opens a file for the output stream.
 seen(X) and told(X) close the files
 listing(predicate_name) - all the clauses with that
predicate name in the DB are returned.
 trace allows the user to monitor the progress of
the Prolog interpreter.
 when a more selective trace is required, the goal
spy is useful.
Artificial Intelligence
8
14.1.3 Lists and Recursion (1)
KU NLP
 Recursion is the primary control mechanism for PROLOG
programming
 Recursion is the natural way to process the list structure
 List is a data structure consisting of ordered sets of elements.
 List elements are enclosed by [] and separated by commas.
[tom,dick,harry,fred]
 Using the vertical bar operator and unification, we can
break a list into its components
 [tom,dick,harry,fred]
[X | Y]
 X=tom and Y=[dick,harry,fred]
 [tom,dick,harry,fred]
[X,Y | Z]
 X=tom, Y=dick, Z=[harry, fred]
Artificial Intelligence
9
14.1.3 Lists and Recursion (2)
KU NLP
 Definition of member
1: member(X, [X|T]).
2: member(X, [Y|T]) :- member(X,T).
?- member(c, [a,b,c]).
call 1. fail, since c  a
call 2. X=c, Y=a, T=[b,c], member(c,[b,c])?
call 1. fail, since c b
call 2. X=c, Y=b, T=[c], member(c,[c])?
call 1. success, c=c
yes (to second call 2.)
yes(to first call 2.)
yes
Artificial Intelligence
10
14.1.3 Lists and Recursion (3)
KU NLP
 Anonymous variables - variables used solely for
pattern-matching process
 member(X,[X|_])
the content of the tail of the list is unimportant.
 Writing one element of the list on each line.
Writelist([]).
writelist([H|T]) :- write(H), nl, writelist(T).
 Writing out a list in reversed order
reverse - writelist([]).
reverse - writelist([H|T]) :- reverse_writelist(T), write(H), nl.
Artificial Intelligence
11
14.1.4 Recursive Search in
PROLOG(1)
KU NLP
 Knight’s tour problem
 a knight can move two squares either horizontally or vertically
followed by one square in an orthogonal direction as long as it
does not move off the board.
 3*3 chessboard with move rules
1
2
3
4
5
6
7
8
9
move(1,6) move(3,4) move(6,7) move(8,3)
move(1,8) move(3,8) move(6,1) move(8,1)
move(2,7) move(4,3) move(7,6) move(9,4)
move(2,9) move(4,9) move(7,2) move(9,2)
 attempt to find a series of legal moves in which the knight
lands on each square of the chessboard exactly once.
Artificial Intelligence
12
14.1.4 Recursive Search in
PROLOG(2)
KU NLP
 Definition of Path using PROLOG
path(Z,Z)
path(X,Y) :- move(X,W), not(been(W)),assert(been(W)),path(W,Y).
 To determine whether the desired goal state is over reached
(termination condition of recursion), path(Z,Z) is needed.
 been predicate is used to record previously visited states and
avoid loops.
Artificial Intelligence
13
KU NLP
14.1.4 Recursive Search in
PROLOG(3)
 Depth-first graph search with backtracking
algorithm of Path.
1. path (Z, Z, L).
2. path (X, Y, L) :- move(X,Z), not(member(Z,L)), path(Z,Y,[Z|L]).
?-path(1,3,[1]).
path(1,3,[1]) attempts to match 1. Fail 13.
path(1,3,[1]) matches 2. X is 1, Y is 3, L is [1]
move(1,Z) matches Z as 6, not(member(6,[1])) is true, call path(6,3[6,1])
path(6,3,[6,1]) attempts to match 1. Fail 63.
path(6,3,[6,1]) matches 2. X is 6, Y is 3, L is [6,1].
move(6,Z) matches Z as 7, not(member(7,[6,1])) is true, path(7,3,[7,6,1])
Artificial Intelligence
14
14.1.4 Recursive Search in
PROLOG(4)
KU NLP
path(7,3,[7,6,1]) attempts to match 1. Fail 73.
path(7,3,[7,6,1]) matches 2. X is 7, Y is 3, L is [7,6,1].
move(7,Z) is Z=6, not(member(6,[7,6,1])) fails, backtrack!
move(7,Z) is Z=2, not(member(2,[7,6,1])) true, path(2,3,[2,7,6,1])
path call attempts 1, fail, 23
path matches 2, X is 2, Y is 3, L is [2,7,6,1]
move matches Z as 7, not(member(…)) fails, backtrack!
move matches Z as 9, not(member(…)) fails, path(9,3,[9,2,7,6,1])
path fails 1, 93
path matches 2, X is 9, Y is 3, L is [9,2,7,6,1]
move is Z=4, not(member(…)) true, path(4,3,[4,9,2,7,6,1])
path fails 1, 43
path matches 2, X is 4, Y is 3, L is [4,9,2,7,6,1]
move Z=3, not(member(…)) true, path(3,3,[3,4,9,2,7,6,1])
path attempts 1, true, 3=3, yes
Artificial Intelligence
15
KU NLP
14.1.5 The use of Cut to Control
Search in PROLOG(1)
 Cut is represented by !
 Side effects
 when originally encountered it always succeeds.
 If it is “failed back to” in the normal course of backtracking, it
comes the entire goal to fail.
 Example
path2(X,Y):- move(X,Z), move(Z,Y).
move(1,6). move(1,8). move(6,7).
move(6,1). move(8,3). move(8,1).
?-path2(1,W).
W=7; W=1; W=3; W=1; no
path3(X,Y):-move(X,Z), !, move(Z,Y).
?-path3(1,W)
W=7; W=1; no
Artificial Intelligence
16
KU NLP
14.1.5 The use of Cut to Control
Search in PROLOG(2)
 Usage of cut in programming
 allows the programmer to control the shape of the search
tree, when further search is not required, the tree can be
explicitly pruned at that point
 Controls recursion
path(Z,Z,L)
path(X,Z,L):- move(X,Y), not(member(Y,L)),
path(Y,Z,[Y|L]),!.
the addition of cut means that at most one solution is
produced.
Artificial Intelligence
17
KU NLP
The farmer, wolf, goat and
cabbage Problem (P 620)
 A farmer with his wolf, goat, and cabbage come to the edge of a
river they wish to cross.
 There is a boat at the river’s edge, but of course, only the farmer
can row.
 The boat also can carry only two things (including the rower) at
a time.
 If the wolf is ever left alone with the goat, the wolf will eat the
goat;
 Similarly, if the goat is left alone with the cabbage, the goat will
eat the cabbage.
 Devise a sequence of crossings of the river so that all four
characters arrive safely on the other side of the river.
Artificial Intelligence
18
Sample crossing for FWGC
problem
KU NLP
Artificial Intelligence
19
KU NLP
State Space Representation of
FWGC problem
Artificial Intelligence
20
FWGC problem in PROLOG
KU NLP
 test:- go(state(w,w,w,w), state(e,e,e,e)).
 go(Start, Goal) :-
empty_stack(Empty_been_stack),
stack(Start, Empty_been_stack, Been_stack)
path(Start, Goal, Been_stack).
 path(State, Goal, Been_stack) :- ……..
 move(state(….), state(….)) :- ……..
 unsafe, opp, empty_stack, stack, member_stack,
reverse_print_stack, write_list, etc.
Artificial Intelligence
21
A parse Tree
KU NLP
Artificial Intelligence
22
A parser in PROLOG
KU NLP
utterance(X) :- sentence(X, [ ]).
sentence(Start, End) :- nounphrase(Start, Rest),
verbphrase(Rest, End).
nounphrase([Noun|End], End) :- noun(Noun).
nounphrase([Article, Noun|End], End) :- article(Article),
noun(Noun).
verbphrase([Verb|End], End) :- verb(Verb).
verbphrase([Verb|End], End) :- verb(Verb), nounphrase(Rest,
End).
article(a). article(the). noun(man). noun(dog).
verb(likes). verb(bites).
Artificial Intelligence
23
ELIZA
KU NLP
Person: Men are all alike.
ELIZA: In what way?
Person: They’re always bugging us about something or other.
ELIZA: Can you think of a specific example?
Person: Well, my boyfriend made me come here.
ELIZA: Your boyfriend made you come here.
Person: He says I’m depressed much of the time.
ELIZA: I am sorry to hear you are depressed.
Person: It’s true. I am unhappy.
ELIZA: Do you think coming here will help you not to be unhappy?
Person: I need some help, that much seems certain.
ELIZA: What would it mean to you if you got some help?
Person: Perhaps I could learn to get along with my mother.
ELIZA: Tell me more about your family.
(X me Y)

(X you Y)
(I remember Y)

(Why do remember X just now?)
(My {family-member} is Y)

(Who else in your family is Y?
(X {family-member} Y)

(Tell me more about your family)
Artificial Intelligence
24
Prolog Homework
KU NLP
 FWCG problem (exercise, p623)
 Eliza (exercise)
 A parser in PROLOG
 Read 14.9.2 (p 667) recursive parser
 Write a grammar for parsing sentences in the own dialog
 Produce a parse tree as follows:
 ?- utterance([The, man, bites, the, dog]).
[sentence, [nounphrase, [article, the],
[noun, man]],
[verbphrase, [verb, bites],
[nounphrase, [article, the],
[noun, dog]]]].
Artificial Intelligence
25