CS 403: Introduction to logic programming
Stefan D. Bruda
Fall 2021
KNOWLEDGE REPRESENTATION
A proposition is a logical statement that can be either false or true
To work with propositions one needs a formal system i.e., a symbolic logic
Predicate calculus or first-order logic is one such a logic
A term is a constant, structure, or variable
An atomic proposition (or predicate) denotes a relation. It is composed of a
functor that names the relation, and an ordered list of terms (parameters):
secure(room), likes(bob, steak), black(crow), capital(ontario, toronto)
Variables can appear only as arguments. They are free:
capital(ontario,X )
unless bounded by one of the quantifiers ∀ and ∃:
∃X : capital(ontario,X ) ∀Y : capital(Y , toronto)
A compound proposition (formula) is composed of atomic propositions,
connected by logical operators: ¬, ∧, ∨,→ (⇒). Variables are bound using
quantifires
∀X .(crow(X )→ black(X ))
∃X .(crow(X ) ∧ white(X ))
∀X .(dog(fido) ∧ (dog(X )→ smelly(X ))→ smelly(fido))
CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 1 / 41
SEMANTICS OF THE PREDICATE CALCULUS
The meaning is in the eye of the beholder
Sentences are true with respect to a model and an interpretation
The model contains objects and relations among them (your view of the
world)
An interpretation is a triple I = (D, φ, π), where
D (the domain) is a nonempty set; elements of D are individuals
φ is a mapping that assigns to each constant an element of D
π is a mapping that assigns to each predicate with n arguments a function
p : Dn → {True,False} and to each function of k arguments a function
f : Dk → D
The interpretation specifies the following correspondences:
constant symbols → objects (individuals)
predicate symbols → relations
function symbols → functional relations
An atomic sentence predicate(term1, . . . , termn) is true iff the objects referred to
by term1, . . . , termn are in the relation referred to by predicate
CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 2 / 41
SEMANTICS OF THE PREDICATE CALCULUS (CONT)
Objects (richard, kingJohn, leg1, leg2), predicates or relations (brother),
functions (leftLegOf)
CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 3 / 41
KNOWLEDGE REPRESENTATION IN PROLOG
Prolog is a logic/descriptive language
Allows the specification of the problem to be solved using
Known facts about the objects in the universe of the problem (unit clauses):
locked(window).
dark(window).
capital(ontario,toronto).
Rules for inferring new facts from the old ones
Queries or goals about objects and their properties
The system answers such queries, based on the existing facts and rules
?- locked(window).
No
?- [’test.pl’].
Yes
?- locked(window).
Yes
?- locked(door).
No
CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 4 / 41
CONSTANTS AND VARIABLES
A variable in Prolog is anything that starts with a capital letter or an
underscore (“ ”)
A constant is a number or atom. An atom is:
Anything that starts with a lower case letter followed by letters, digits, and
underscores
Any number of symbols +,-,*,/,\,~,<,>,=,’,^,:,.,?,@,#,$,$,&
Any of the special atoms [],{},!,;,%
Anything surrounded by single quotes: ’atom surrounded by quotes!.’
Escape sequence: just double the escaped character:
’insert ’’ in an atom’
NB: The predicate calculus is called first-order logic because no
predicate can take as argument another predicate, and no predicate can
be a variable
CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 5 / 41
PROLOG RULES
A Horn clause is a conjunction in which exactly one atomic proposition is
not negated
A ∨ ¬B ∨ ¬C ∨ ¬D
B ∧ C ∧ D → A
A sentence that contain exactly one atomic proposition is also a (degenerate
form of a) Horn clause
Note in passing that not all the FOL formulae can be converted into a set of
Horn clauses
A Prolog program is a set of Horn clauses
CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 6 / 41
RULES
Natural Language:
The window is locked. If the light is off and the door is locked, the
room is secure. The light is off if the window is dark. The window is
dark.
Horn clauses:
locked(window)
dark(window)
off(light) ∧ locked(door)→ secure(room)
dark(window)→ off(light)
The Prolog program:
dark(window).
locked(window).
secure(room) :- off(light), locked(door).
off(light) :- dark(window).
CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 7 / 41
QUERIES
Now, one can ask something:
?- off(light).
Yes
?- secure(room).
No
?- locked(door).
No
?- locked(Something).
Something = window
Yes
?- locked(Something).
Something = window ;
No
Query variables are all existentially quantified
CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 8 / 41
CONJUNCTIVE RULES
A family tree:
parent(ann,bob). parent(ann,calvin).
parent(bob,dave). parent(dave,helen).
parent(ann,bob) parent(ann,calvin) parent(bob,dave) parent(dave,helen)
parent(X,Y)
Other family relations:
grandparent(X,Y) :- parent(X,Z), parent(Z,Y).
siblings(X,Y) :- parent(Z,X), parent(Z,Y) ., not(X = Y).
parent(X,Z)
grandparent(X,Y)
parent(Z,Y) parent(Z,X) parent(Z,Y) not (X = Y)
siblings(X,Y)
All the rule variables are universally quantified
CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 9 / 41
DISJUNCTIVE RULES
Yet another family relation:
ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y).
ancestor(X,Y)
parent(X,Y) parent(X,Z) ancestor(Z,Y)
A person is happy if she is healthy, wealthy, or wise:
happy(Smb) :- person(Smb), healthy(Smb).
happy(Smb) :- person(Smb), wealthy(Smb).
happy(Smb) :- person(Smb), wise(Smb).
happy(Smb)
person(Smb)person(Smb) healthy(Smb) person(Smb) wealthy(Smb) wise(Smb)
CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 10 / 41
PREDICATE CALCULUS PROOFS
Inference rules→ sound generation of new sentences from old
Prolog uses generalized modus ponens as inference rule
α1, . . . , αn α1 ∧ · · · ∧ αn → β
β
(modus ponens)
α1, . . . , αn
α′1 ∧ · · · ∧ α′n → β
∃σ : (α1)σ = (α
′
1)σ ∧ · · · ∧ (αn)σ = (α
′
n)σ
βσ
(generalized
modus ponens)
Proof→ a sequence of applications of inference rules
Generates in effect a logically sound traversal of the proof tree
CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 11 / 41
PROOF BY CONTRADICTION
KB
Bob is a buffalo 1. buffalo(bob)
Pat is a pig 2. pig(pat)
Buffaloes outrun pigs 3. buffalo(X ) ∧ pig(Y )→ faster(X ,Y )
Query
Is something outran
by something else? faster(U,V )
Negated query: 4. faster(U,V )→ �
(1), (2), and (3) with
σ = {X/bob,Y/pat} 5. faster(bob,pat)
(4) and (5) with
σ = {U/bob,V/pat} �
All the substitutions regarding variables appearing in the query are
typically reported (why?)
CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 12 / 41
INFERENCE AND MULTIPLE SOLUTIONS
parent(ann,X) −>
5
1
6
5 5
2
3
{X/bob}
{A/ann, B/X}
{X/bob}
ancestor(ann,B) ancestor(B,X) −>
parent(ann,B) parent(B,X) −>
parent(cecil,X) −>
{X/dave}
{B/cecil}
{X/dave}
{A/ann, C/X}
ancestor(ann,X) −>
(1) parent(ann,bob)
(2) parent(ann, cecil)
(3) parent(cecil ,dave)
(4) parent(cecil ,eric)
(5) parent(A,B)→ ancestor(A,B)
(6) ancestor(A,B) ∧ ancestor(B,C)→ ancestor(A,C)
CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 13 / 41
SEARCHING THE KNOWLEDGE BASE
parent(ann,calvin). 2 ?- trace(parent).
parent(ann,bob). parent/2: call redo exit fail
parent(bob,dave). Yes
parent(dave,helen). [debug] 3 ?- parent(ann,X).
T Call: ( 7) parent(ann, _G365)
T Exit: ( 7) parent(ann, calvin)
X = calvin ;
T Redo: ( 7) parent(ann, _G365)
T Exit: ( 7) parent(ann, bob)
X = bob ;
No
Fail
Call Exit
Redo
parent(ann,X)
X=calvin ;
X=bob ;
(2)
(1)
(1)
(2)
No
?− parent(ann,X).
CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 14 / 41
SEARCHING THE KNOWLEDGE BASE (CONT’D)
parent(ann,calvin). parent(ann,bob).
parent(bob,dave). parent(dave,helen).
grandparent(X,Y) :- parent(X,Z),parent(Z,Y).
[debug] 8 ?- grandparent(X,Y). T Redo: (8) parent(_G382, _L224)
T Call: (7) grandparent(_G382, _G383) T Exit: (8) parent(bob, dave)
T Call: (8) parent(_G382, _L224) T Call: (8) parent(dave, _G383)
T Exit: (8) parent(ann, calvin) T Exit: (8) parent(dave, helen)
T Call: (8) parent(calvin, _G383) T Exit: (7) grandparent(bob, helen)
T Fail: (8) parent(calvin, _G383)
T Redo: (8) parent(_G382, _L224) X = bob
T Exit: (8) parent(ann, bob) Y = helen ;
T Call: (8) parent(bob, _G383) T Redo: (8) parent(_G382, _L224)
T Exit: (8) parent(bob, dave) T Exit: (8) parent(dave, helen)
T Exit: (7) grandparent(ann, dave) T Call: (8) parent(helen, _G383)
T Fail: (8) parent(helen, _G383)
X = ann T Fail: (7) grandparent(_G382, _G383)
Y = dave ;
No
CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 15 / 41
SEARCHING THE KNOWLEDGE BASE (CONT’D)
Fail
Call Exit
Redo
parent(X,Z)
Fail
Call Exit
Redo
parent(Z,Y)
X/ann
Z/bob
callX/ann
Z/bob
exit
X/ann
Z/calvin
grandparent(X,Y)
parent(Z,Y)
X/ann
Z/calvin
call
redo
parent(X,Z)
parent(ann,bob)
call
exit
call
parent(bob,dave)
parent(dave,helen)
fail
X/ann
Z/bob
Z/dave
exit
X/ann
Z/calvin
X/ann
Z/bob
exit
call
exit
parent(ann,calvin)
CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 16 / 41
RECURSIVE PREDICATES
ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,Z),ancestor(Z,Y).
A recursive call is treated as a brand new call, with all the variables
renamed
Fail
Call Exit
Redo
Fail
Call Exit
Redo
Fail
Call Exit
Redo
Fail
Call Exit
Redo
parent(X,Z) ancestor(Z,Y)
ancestor(X,Y)
ancestor(Z,Y)
parent(Z,Z1) ancestor(Z1,Y)
CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 17 / 41
UNIFICATION
There is no explicit assignment in Prolog
Bindings to variables are made through the process of unification, which
is done automatically most of the time
The predicate =/2 is used to request an explicit unification of its two
arguments
?- book(prolog,X) = book(Y,brna).
X = brna
Y = prolog
The binding {X/brna,Y/prolog} is the most general unifier
The most general unifier can contain free variables: the general unifier of
book(prolog,X) = book(Y,Z) is {Y/brna,X/Z}
even if {Y/prolog,X/brna,Z/brna} is also a unifier, it is not the most general
In passing, note that the following predicates are different, even if they
have the same name
tuple(1,2). % tuple/2 ?- tuple(X,Y).
tuple(1,2,3). % tuple/3 X = 1
tuple(a,b,c). % tuple/3 Y = 2 ;
tuple(a,b,c,d). % tuple/4 No
CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 18 / 41
UNIFICATION ALGORITHM
algorithm UNIFY(T1,T2,S) returns substitution or FAILURE:
Input: T1, T2: the structures to unify; S: the substitution representing the
variable bindings that are already in place
Initial call is typically made with an empty substitution: UNIFY(T1,T2, ∅)
Output: A new substitution (including S) or the special value FAILURE
specifying that the unification has failed
1 if T1 and T2 are both atoms, or bound to atoms in S and T1 == T2
then return S
2 if T1 is a free variable then return S ∪ {T1/T2}
3 if T2 is a free variable then return S ∪ {T2/T1}
4 if T1 == p(a1,a2, . . . ,an) and T2 == p(b1,b2, . . . ,bn)
(by themselves or because they are bound in S to such values) then
1 for i = 1 to n do
1 let A = UNIFY(ai , bi ,S), S = S ∪ A
2 if A == FAILURE then return FALURE
2 return S
5 return FAILURE
CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 19 / 41
UNIFICATION (CONT’D)
Unification can be attempted between any two Prolog entities. Unification
succeeds of fails. As a side effect, free variables may become bound
[debug] 10 ?- parent(ann,Y). [debug] 11 ?- parent(X,ann).
T Call: ( 7) parent(ann, _G371) T Call: ( 7) parent(_G370, ann)
T Exit: ( 7) parent(ann, calvin) T Fail: ( 7) parent(_G370, ann)
Y = calvin No
Yes
Once a variable is bound through some unification process, it cannot
become free again
[debug] 15 ?- X=1, X=2.
T Call: ( 7) _G340=1
T Exit: ( 7) 1=1
T Call: ( 7) 1=2
T Fail: ( 7) 1=2
No
Do not confuse =/2 with assignment!
CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 20 / 41
UNIFICATION AND STRUCTURES
What is the result of X = pair(1,2)?
?- X = pair(1,2).
X = pair(1, 2)
A structure has the same syntax as a predicate. The difference is that a
structure appears as a parameter
You do not have to define a structure, you just use it.
This is possible because of the unification process
Example: binary search trees
% if I found the element, then succeed.
member_tree(X,tree(X,L,R)).
% Otherwise, if my element is larger than the current key, then I
% search in the right child.
member_tree(X,tree(Y,L,R)) :- X > Y, member_tree(X,R).
% Eventually (otherwise) search in the left child.
member_tree(X,tree(Y,L,R)) :- X < Y, member_tree(X,L). % An empty tree cannot contain any element, so anything else fails. CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 21 / 41 SEARCH TREES (CONT’D) ?- member_tree(3,nil). No [debug] ?- member_tree(3,tree(2,tree(1,nil,nil),tree(3,nil,nil))). T Call: ( 7) member_tree(3, tree(2, tree(1, nil, nil), tree(3, nil, nil))) T Call: ( 8) member_tree(3, tree(3, nil, nil)) T Exit: ( 8) member_tree(3, tree(3, nil, nil)) T Exit: ( 7) member_tree(3, tree(2, tree(1, nil, nil),tree(3, nil, nil))) Yes [debug] ?- member_tree(5,tree(2,tree(1,nil,nil),tree(3,nil,nil))). T Call: ( 7) member_tree(5, tree(2, tree(1, nil, nil),tree(3, nil, nil))) T Call: ( 8) member_tree(5, tree(3, nil, nil)) T Call: ( 9) member_tree(5, nil) T Fail: ( 9) member_tree(5, nil) T Redo: ( 8) member_tree(5, tree(3, nil, nil)) T Fail: ( 8) member_tree(5, tree(3, nil, nil)) T Redo: ( 7) member_tree(5, tree(2, tree(1, nil, nil),tree(3, nil, nil))) T Fail: ( 7) member_tree(5, tree(2, tree(1, nil, nil),tree(3, nil, nil))) No CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 22 / 41 LISTS Lists are nothing special, just a structure named “.”, and containing two parameters The first one is the elements at the head of the list, The second is a structure “.”, or the empty list “[]” That is, .(X,XS) is equivalent to Haskell’s (x::xs) The difference from Haskell is given by the absence of types in Prolog: A list can contain any kind of elements As in Haskell, there is some syntactic sugar: One can enumerate the elements: [1,[a,4,10],3] The expression [X|Y] is equivalent to .(X,Y) We also have the equivalence between [X,Y,Z|R] and .(X,.(Y,.(Z,R))), and so on ?- [b,a,d] = [d,a,b]. → unification failure ?- [X|Y] = [a,b,c]. → X=a,Y=[b,c] ?- [X|Y] = []. → unification failure ?- [[X1|X2]|X3] = [[1,2,3],4,5]. → X1=1,X2=[2,3],X3=[4,5] The absence of types in Prolog is brought to extremes: the list [1] is the structure .(1,[]). However, the empty list [] is an atom! CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 23 / 41 LIST PROCESSING Membership: member/2 member(X,[X| ]). member(X,[ |Y]) :- member(X,Y). What is the answer to the query ?- member(X,[1,2,3,4]). Both arguments of member/2 may be bound – if so we write member(+E,+L) In fact, member/2 also works as member(-E,+L) (first argument free) The general specification is member(?E,+L) (last argument is bound, but the first is not necessarily bound) There are no functions in Prolog. What if we want that our program to compute a value? We invent a new variable that will be bound to the result by various unification processes A predicate for concatenating (”appending”) two lists: append/3 append([],L,L). append([X|R],L,[X|R1]) :- append(R,L,R1). What is the result of the query ?- append(X,Y,[1,2,3,4]). CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 24 / 41 NUMBERS AND OPERATIONS ON NUMBERS What means “3+4” to Prolog? (as in ?- X = 3 + 4.) In order to actually evaluate an arithmetic expression, one must use the operator is(?Var,+Expr): ?- X is 3+4 X = 7 Yes Example: A Prolog program that receives one number n and computes n! fact(1,1). fact(N,R) :- R is N*fact(N-1,R1). fact(N,R) :- N1 is N-1, fact(N1,R1), R is N*R1. 13 ?- fact(1,X). X = 1 Yes 14 ?- fact(2,X). [WARNING: Arithmetic: ‘fact/2’ is not a function] Exception: ( 8) G185 is 2*fact(2-1, G274) ? [WARNING: Unhandled exception] CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 25 / 41 NUMBERS (CONT’D) All the expected operators on numbers work as expected One (annoying) difference: the operator for ≤ is not <=, but =< instead Given the call fact(5,X), what happens if one requests a new solution after Prolog answers X=120? Why? How to fix? fact(1,1). fact(N,R) :- N1 is N-1, fact(N1,R1), R is N*R1. ?- fact(5,X). X = 120 ; ??? CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 26 / 41 NEGATION AS FAILURE Negation in Prolog: not/1 or \+/1 Prolog assumes the closed world paradigm. The negation is therefore different from logical negation: ?- member(X,[1,2,3]). X = 1 ; X = 2 ; X = 3 ; No ?- not(member(X,[1,2,3])). No ?- not(not(member(X,[1,2,3]))). X = _G332 ; No not/1 fails upon resatisfaction (a goal can fail in only one way) not/1 does not bind variables CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 27 / 41 NEGATION IN CASE SELECTIONS positive(X) :- X > 0.
negative(X) :- X < 0. sign(X,+) :- positive(X). sign(X,-) :- negative(X). sign(X,0). sign1(X,+) :- positive(X). sign1(X,-) :- negative(X). sign1(X,0) :- not(positive(X)), not(negative(X)). ?- sign(1,X). X = + ; X = 0 ; No ?- sign1(1,X). X = + ; No CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 28 / 41 STATE SPACE SEARCH The concept of state space search is widely used in AI Idea: a problem can be solved by examining the steps which might be taken towards its solution Each action takes the solver to a new state The solution to such a problem is a list of steps leading from the initial state to a goal state Classical example: A Farmer who needs to transport a Goat, a Wolf and some Cabbage across a river one at a time. The Wolf will eat the Goat if left unsupervised. Likewise the Goat will eat the Cabbage. How will they all cross the river? A state is described by the positions of the Farmer, Goat, Wolf, and Cabbage The solver can move between states by making a “legal” move (which does not result in something being eaten) General form for a state space search problem: Input: 1 The start state 2 One (or more) goal states or final states 3 The state transition function, or how to get from one state to another Output: a list of moves or state transitions that lead from the initial state to one of the final states CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 29 / 41 STATE SPACE SEARCH IN PROLOG Prolog already does it: search(Final,Final,[]). search(Current,Final,[M|Result]) :- move(Current,SomeState,M), search(SomeState,Final,Result). The only trick is that Prolog does not explain how it reached the goal state; it just states whether a goal state is reachable or not So we also need to provide a way to report the list of moves (hence the third parameter) CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 30 / 41 A SIMPLE STATE SPACE SEARCH PROBLEM Finding a path in a directed, acyclic graph: A state is a vertex of the graph distance(a,f,5). distance(f,g,2). distance(a,b,1). distance(a,d,2). distance(b,c,2). distance(c,d,3). distance(d,e,6). move(A,B,to(A,B)) :- distance(A,B,_). b c d e f a g 2 3 6 2 5 1 2 ?- search(a,e,R). R = [to(a,b),to(b,c),to(c,d),to(d,e)] ; R = [to(a,d),to(d,e)] ; No ?- search(e,a,R). No CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 31 / 41 SEARCHING A STATE SPACE, REVISED Often, the search space contains cycles. Then, Prolog search strategy may fail to produce a solution. move(A,B,to(A,B)) :- distance(A,B,_). move(A,B,to(A,B)) :- distance(B,A,_). ?- search(a,e,R). ERROR: Out of local stack We can use then a generate and test technique: We keep track of the previously visited states Then, we generate a new state (as before), but we also test that we haven’t been in that state already; we proceed forward only if the test succeeds search(Initial,Final,Result) :- ?- search(a,e,R). search(Initial,Final,[Initial],Result). R = [to(a, b), to(b, c), search(Final,Final,_,[]). to(c, d), to(d, e)] ; search(Crt,Final,Visited,[M|Result]) :- R = [to(a, d), to(d, e)] ; move(Crt,AState,M), % generate No not(member(AState,Visited)), % test search(AState,Final,[AState|Visited], Result). CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 32 / 41 THE PROBLEM-DEPENDENT DEFINITIONS Things to do for solving a specific state space search problem: Establish what is a state for your problem and how will you represent it in Prolog Establish your state transition function; that is, define the move/3 predicate Such a predicate should receive a state, and return another state together with the move that generates it Upon resatisfaction, a new state should be returned If no new state is directly accessible from the current one, move/3 should fail CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 33 / 41 LIMITATIONS The predicate search/3 works on any finite search space It exploits the fact that Prolog performs by itself a depth-first search. Since the depth-first search is not guaranteed to terminate on an infinite search space, neither is search/3 It is possible to implement a breadth-first search in Prolog However, this cannot take advantage of the search strategy which is built in the Prolog interpreter (in fact, it sidesteps it altogether) Such an implementation is thus more complicated and exceeds the scope of this course (but if you are really curious, contact me) CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 34 / 41 ON GOATS, WOLVES, AND CABBAGE % A state: [Boat,Cabbage,Goat,Wolf] % Moving around. We use the "generate and test" paradigm: move(A,B,M) :- move_attempt(A,B,M), legal(B). % first, attempt to move the Cabbage, then the Goat, then the Wolf: move_attempt([B,B,G,W],[B1,B1,G,W], moved(cabbage,B,B1)) :- opposite(B,B1). move_attempt([G,B,G,W],[G1,B,G1,W], moved(goat,G,G1)) :- opposite(G,G1). move_attempt([W,B,G,W],[W1,B,G,W1], moved(wolf,W,W1)) :- opposite(W,W1). %... eventually, move the empty boat: move_attempt([X,C,G,W],[Y,C,G,W], moved(nothing,X,Y)) :- opposite(X,Y). opposite(south,north). opposite(north,south). % Make sure that nothing gets eaten: legal(State) :- not(conflict(State)). % we cannot allow the Cabbage and the Goat on the same shore unsupervised conflict([B,C,C,W]) :- opposite(C,B). % ... nor the Goat and the Wolf... conflict([B,C,W,W]) :- opposite(W,B). % ... but anything else is fine. CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 35 / 41 ON GOATS, WOLVES, AND CABBAGE (CONT’D) ?- search([north,north,north,north], [south,south,south,south], R). R = [moved(goat, north, south), moved(nothing, south, north), moved(cabbage, north, south), moved(goat, south, north), moved(wolf, north, south), moved(nothing, south, north), moved(goat, north, south)] ; R = [moved(goat, north, south), moved(nothing, south, north), moved(wolf, north, south), moved(goat, south, north), moved(cabbage, north, south), moved(nothing, south, north), moved(goat, north, south)] ; NoCS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 36 / 41 ON KNIGHTS AND THEIR TOURS % The board size is given by the predicate size/1 size(3). % The position of the Knight is represented by the structure -(X,Y) % (or X-Y), where X and Y are the coordinates of the square where the % Knight is located. We represent a move by the position it generates. % We use, again, the generate and test technique: move(A,B,B) :- move_attempt(A,B), inside(B). % There are 8 possible moves in the middle of the board: move_attempt(I-J, K-L) :- K is I+1, L is J-2. move_attempt(I-J, K-L) :- K is I+1, L is J+2. move_attempt(I-J, K-L) :- K is I+2, L is J+1. move_attempt(I-J, K-L) :- K is I+2, L is J-1. move_attempt(I-J, K-L) :- K is I-1, L is J+2. move_attempt(I-J, K-L) :- K is I-1, L is J-2. move_attempt(I-J, K-L) :- K is I-2, L is J+1. move_attempt(I-J, K-L) :- K is I-2, L is J-1. % However, if the Knight is somwhere close to board’s margins, then % some moves might fall out of the board. inside(A-B) :- size(Max), A > 0, A =< Max, B > 0, B =< Max. CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 37 / 41 ON KNIGHTS AND THEIR TOURS (CONT’D) ?- search(1-1,3-3,R). R = [2-3, 3-1, 1-2, 3-3] ; R = [3-2, 1-3, 2-1, 3-3] ; No 3 1 1 2 3 2 3 1 1 2 3 2 CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 38 / 41 VARIATIONS ON A SEARCH THEME Since our search/3 predicate generates all the possible solutions, we can use it within another generate and test process! On a 4× 4 board, a Knight moves from one square S to another square D. For a given N, find all the paths between S and D in which the Knight does not make more than N moves. search_shorter(S,D,N,Result) :- search(S,D,Result), % generate length(Result,L), L =< N. % test % length([],0). % length([_|T],L) :- length(T,L1), L is L1+1. ?- search_shorter(1-1,4-3,5,R). R = [2-3, 3-1, 4-3] ; R = [3-2, 2-4, 4-3] ; R = [2-3, 3-1, 1-2, 2-4, 4-3] ; R = [3-2, 2-4, 1-2, 3-1, 4-3] ; R = [2-3, 4-4, 3-2, 2-4, 4-3] ; R = [3-2, 1-3, 3-4, 2-2, 4-3] ; R = [2-3, 4-2, 3-4, 2-2, 4-3] ; No R = [3-2, 4-4, 2-3, 3-1, 4-3] ; ?- search_shorter(1-1,4-3,4,R). R = [2-3, 3-1, 4-3] ; R = [3-2, 2-4, 4-3] ; No CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 39 / 41 VARIATIONS ON A SEARCH THEME (CONT’D) Given some integer n and two vertices A and B, is there a path from A to B of weight smaller than n? distance(a,f,5). distance(f,g,2). distance(a,b,1). distance(a,d,2). distance(b,c,2). distance(c,d,3). distance(d,e,6). move(A,B,to(A,B,C)) :- distance(A,B,C). move(A,B,to(A,B,C)) :- distance(B,A,C). weight([],0). weight([to(_,_,C)|P],W) :- weight(P,W1), W is W1+C. smaller(A,B,N,Result) :- search(A,B,Result), weight(Result,W), W =< N. b c d e f a g 2 3 6 2 5 1 2 CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 40 / 41 LOGIC PROGRAMMING Logic programming Ordinary programming 1. Identify problem Identify problem 2. Assemble information Assemble information 3. Coffee break Figure out solution 4. Encode information in KB Program solution 5. Encode problem instance as facts Encode problem instance as data 6. Ask queries Apply program to data 7. Find false facts Debug procedural errors CS 403: Introduction to logic programming (S. D. Bruda) Fall 2021 41 / 41