Logic Programming and Prolog
Finish reading: Scott, Chapter 12
1
Lecture Outline
n Prolog
n Imperative control flow
n Negation by failure
n Generate and test paradigm
Programming Languages CSCI 4430, A. Milanova 2
Imperative Control Flow
n Programmer has explicit control on backtracking process
cut (!)
n ! is a subgoal
n As a goal it succeeds, but with a side effect:
n Commits interpreter to all bindings made since unifying left-hand side of current rule with parent goal
3
Cut (!) Example
rainy(seattle).
rainy(rochester).
cold(rochester).
snowy(X) :- rainy(X), !, cold(X).
?- snowy(C).
Programming Languages CSCI 4430, A. Milanova 4
Cut (!) Example
rainy(seattle).
rainy(rochester).
cold(rochester).
snowy(X) :- rainy(X), !, cold(X).
snowy(C)
snowy(X)
cold(seattle)
fails; no
backtracking to
rainy(X).
GOAL FAILS.
cold(X)
cold(rochester)
_C = _X
AND X = seattle OR
!
rainy(X)
rainy(seattle) rainy(rochester)
Programming Languages CSCI 4430, A. Milanova
5
Cut (!) Example 2
rainy(seattle).
rainy(rochester).
cold(rochester).
snowy(X) :- rainy(X), !, cold(X).
snowy(troy).
?- snowy(C).
Programming Languages CSCI 4430, A. Milanova 6
Cut (!) Example 2
rainy(seattle).
rainy(rochester).
cold(rochester).
snowy(X) :- rainy(X), !, cold(X). snowy(C) snowy(troy).
OR
_C = _X
snowy(X) snowy(troy)
2 committed OR
bindings:
_C = _X
and X = seattle
GOAL FAILS.
AND OR
!
X = seattlerainy(X)
rainy(seattle) rainy(rochester)
cold(X)
cold(rochester)
How about query ?- snowy(troy)?
Programming Languages CSCI 4430, A. Milanova
7
Cut (!) Example 3
rainy(seattle) :- !.
rainy(rochester).
cold(rochester).
snowy(X) :- rainy(X), cold(X).
snowy(troy).
?- snowy(C).
Programming Languages CSCI 4430, A. Milanova 8
Cut (!) Example 3
rainy(seattle) :- !.
rainy(rochester).
cold(rochester).
snowy(X) :- rainy(X), cold(X).
snowy(troy).
_C = _X
snowy(C)
OR
C = troy
SUCCEEDS
Only rainy(X) is
committed to
bindings (X =
seattle).
C = troy
snowy(troy)
cold(X)
cold(rochester)
snowy(X)
AND
rainy(X)
X = seattle OR
rainy(seattle) rainy(rochester)
How about query ? – snowy(rochester)?
!
9
Cut (!) Example 4
rainy(seattle).
rainy(rochester).
cold(rochester).
snowy(X) :- !, rainy(X), cold(X).
?- snowy(C).
Programming Languages CSCI 4430, A. Milanova 10
Cut (!) Example 4
rainy(seattle).
rainy(rochester).
cold(rochester).
snowy(X) :- !, rainy(X), cold(X).
snowy(C)
_C = _X success snowy(X)
AND
X = seattle OR X =rochester rainy(seattle) rainy(rochester)
cold(seattle)
fails;
backtrack.
cold(X)
cold(rochester)
! rainy(X)
Programming Languages CSCI 4430, A. Milanova 11
Cut (!) Example 5
rainy(seattle).
rainy(rochester).
cold(rochester).
snowy(X) :- rainy(X), cold(X), !.
?- snowy(C).
Programming Languages CSCI 4430, A. Milanova 12
Cut (!) Example 5
rainy(seattle).
rainy(rochester).
cold(rochester).
snowy(X) :- rainy(X), cold(X), !.
snowy(C)
success
snowy(X)
AND
X = rochester
X = seattle
_C = _X
rainy(X)
OR
! cold(X)
cold(rochester)
rainy(seattle) rainy(rochester)
Programming Languages CSCI 4430, A. Milanova 13
Negation by Failure: not(X), \+(X) n not(C) succeeds when C fails
n Called negation by failure, defined: not(X) :- X,!,fail.
not(_).
n Not the same as negation in logic ¬X!
n In Prolog, we can assert that something is
true, but we cannot assert that something is
false
Programming Languages CSCI 4430, A. Milanova 14
Programming Languages CSCI 4430, A. Milanova 15
Exercise
takes(jane, his).
takes(jane, cs).
takes(ajit, art).
takes(ajit, cs).
classmates(X,Y) :- takes(X,Z),takes(Y,Z).
?- classmates(jane,Y). What are the bindings of Y?
How can we change rule classmates(X,Y) to prevent binding Y = jane?
16
Exercise
n p(X) :- q(X), not(r(X)). r(X) :- w(X), not(s(X)). q(a). q(b). q(c).
s(a). s(c).
w(a). w(b).
n Evaluate:
n ?- p(a). n ?- p(b). n ?- p(c).
Programming Languages CSCI 4430, A. Milanova 17
Lecture Outline
n Prolog
n Imperative control flow
n Negation by failure
n Generate and test paradigm
Programming Languages CSCI 4430, A. Milanova 18
Generate and Test Paradigm
n Search in space
n Prolog rules to generate potential solutions
n Prolog rules to test potential solutions for desired properties
n Easy prototyping of search
solve(P) :- generate(P), test(P).
Programming Languages CSCI 4430, A. Milanova 19
A Classical Example: n Queens
n Given an n by n chessboard, place each of n queens on the board so that no queen can attack another in one move
n Queens can move either vertically, n horizontally, or
n diagonally.
n A classical generate and test problem
Programming Languages CSCI 4430, A. Milanova 20
n Queens
my_not(X):- X, !, fail. %same as not my_not(_).
in(H,[H|_]). %same as member in(H,[_|T]):- in(H,T).
nums(H,H,[H]).
nums(L,H,[L|R]):- L