程序代写代做代考 C graph interpreter Logic Programming and Prolog

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