Logic Programming
Chapter 12
Logic Programming
Prolog says:
?- 1+1 = 2.
false.
so … keep reading!
2
Logic Programming
§ Algorithm = axioms + control
§ Axioms
§ facts and rules
§ supplied by the programmer
§ Control
§ computation is deduction § supplied by the language
§ Given a set of axioms, the user states a theorem, or goal, and the language attempts to show that the axioms imply the goal
3
Logic Programming
§ Axioms = Horn clauses
Q1 ∧Q2 ∧…∧Qk →P
or
P← Q1∧Q2 ∧…∧Qk
§P isthehead
§Q1 ∧Q2 ∧…∧Qk isthebody
§ k ≥ 1: rule: if Q1 and Q2 and … and Qk, then P § k = 0: fact: P (also: if true, then P)
§ The meaning is that if all Qi’s are true, then we can deduce P
4
Prolog
§ Imperative language:
§ runs in the context of a referencing environment, where various
constants and functions have been defined § Prolog
§ runs in the context of a database where various clauses have been defined
§ Clause composed of terms: § constants:
§ atoms: id that starts with lower case: foo, a , john
§ numbers: 0, 2020
§ variables: id that starts with upper case: Foo, X
§ structures: functor (atom) and argument list (terms)
§ student(john), takes(X, cs3342)
§ arguments can be constants, variables, (nested) structures
5
Prolog
§ structures are interpreted as logical predicates § predicate: functor + list of arguments
§ Syntax:
term → atom | number | variable | struct terms → term | term , terms
struct → atom ( terms )
fact → term.
rule → term :- terms. query → ?- terms.
6
Prolog
§ Rule:
P← Q1∧Q2 ∧…∧Qk
§ in Prolog:
P :- Q1, Q2,…,Qk.
§ Fact (rule without right-hand side): P (P ← true)
§ in Prolog: P.
:-= ← ,=∧
7
Prolog
§ Query (rule without left-hand side)
Q1 ∧ Q2 ∧…∧ Qk (false← Q1 ∧ Q2 ∧…∧ Qk)
§ in Prolog:
?- Q1, Q2,…,Qk.
8
Prolog
§ Rules are implicitly universally quantified (∀)
§ Example:
path(L, M) :- link(L, X), path(X, M).
§ means:
∀L,∀M,∀X (path(L, M) if (link(L, X) and path(X, M)))
∀L,∀M (path(L, M) if (∃X (link(L, X) and path(X, M))))
9
Prolog
§ Queries are implicitly existentially quantified (∃)
§ Example:
?- path(algol60, X), path(X, c).
§ means
∃X (path(algol60, X) and path(X, c))
10
Prolog
§ Setting up working directory § Checking working directory:
?- working_directory(X, X).
X = (//).
§ Changing working directory:
?- working_directory(_,’/Users/Lucian/Documents/
4_myCourses/CS3342b_win2020/lecture_notes/my_programs/’).
true.
?- working_directory(X, X).
X = (_,’/Users/Lucian/Documents/ 4_myCourses/CS3342b_win2020/lecture_notes/my_programs/’).
11
Prolog
§ Reading a file: “my_file.pl” § must be in the working directory
?- consult(my_file).
true.
12
Prolog
§ Example: rainy(seattle).
rainy(rochester).
?- rainy(C).
C = seattle
§ Type ENTER if done
§ Type ‘;’ if you want more solutions
C = seattle ;
C = rochester.
13
Prolog
§ Example:
rainy(seattle).
rainy(rochester).
cold(rochester).
snowy(X) :- rainy(X), cold(X).
?- snowy(C).
C = rochester.
§ only one solution
14
Prolog
§ Example:
link(fortran, algol60).
link(algol60, cpl).
link(cpl, bcpl).
link(bcpl, c).
link(c, cplusplus).
link(algol60, simula67).
link(simula67, cplusplus).
link(simula67, smalltalk80).
path(L, L).
path(L, M) :- link(L, X), path(X, M).
15
Prolog
§ Example:
?- link(simula67, X).
X = cplusplus ;
X = smalltalk80.
?- link(algol60, X), link(X, Y).
X = cpl,
Y = bcpl ;
X = simula67,
Y = cplusplus ;
X = simula67,
Y = smalltalk80.
16
Prolog
§ Example:
?- path(fortran, cplusplus).
true ;
true ;
false.
?- path(X, cpl).
X = cpl ;
X = fortran ;
X = algol60 ;
false.
17
Prolog
§ Example:
?- path(X,Y). X=Y;
X = fortran, Y = algol60 ; X = fortran, Y = cpl ;
X = fortran, Y = bcpl ;
X = fortran, Y=c;
X = fortran,
Y = cplusplus ; % … it finds all paths
18
Lists
§[a, b, c]– list
§ [] – empty list
§ ’.’ is a cons-like predicate:
.(a, .(b, .(c, []))) means [a, b, c]
§ the pretty ’.’ has been repurposed; replaced for lists by ‘[|]’ ‘[|]’(a, ‘[|]’(b, ‘[|]’(c, [])))
§ Head | Tail notation: [H|T]
§ [a, b, c] can be written as: [a | [b, c]]
[a, b | [c]]
[a, b, c | []]
19
Lists
?- [H|T] = [a, b, c].
H = a,
T = [b, c].
?- [H|T] = [[], c | [[a], b, [] | [b]]].
H = [],
T = [c, [a], b, [], b].
?- [H|[X|T]] = [[], c | [[a], b, [] | [b]]].
H = [],
X = c,
T = [[a], b, [], b].
?- [H1,H2|[X|T]] = [[],c | [[a], b, [] | [b]]].
H1 = [],
H2 = c,
X = [a],
T = [b, [], b].
20
List operations
§ Searching an element in a list: member(X, [X|_]).
member(X, [_|T]) :- member(X, T).
§ _ is a placeholder for a variable not needed anywhere else
21
List operations
§ Searching an element in a list: ?- member(a, [b, a, c]).
true
?- member(a, [b, d, c]).
false.
?- member(a, X).
X = [a|_14708] ;
X = [_14706, a|_14714] ;
X = [_14706, _14712, a|_14720] ;
X = [_14706, _14712, _14718, a|_14726] ;
X = [_14706, _14712, _14718, _14724, a|_14732] …
22
List operations
§ Adding an element to a list:
add(X, L, [X|L]).
?- add(a, [b,c], L).
L = [a, b, c].
§ Deleting an element from a list: del(X, [X|T], T).
del(X, [Y|T], [Y|T1]) :- del(X, T, T1).
?- del(a, [a, b, c, a, b, a, d, a], X).
X = [b, c, a, b, a, d, a] ;
X = [a, b, c, b, a, d, a] ;
X = [a, b, c, a, b, d, a] ;
X = [a, b, c, a, b, a, d] ;
false.
23
List operations
§ Appending two lists: append([], Y, Y).
append([H|X], Y, [H|Z]) :- append(X, Y, Z).
§ Sublists:
sublist(S,L) :- append(_,L1,L), append(S,_,L1).
24
List operations
§ Example:
?- append([a, b, c], [d, e], L).
L = [a, b, c, d, e].
?- append(X, [d, e], [a, b, c, d, e]).
X = [a, b, c]
?- append([a, b, c], Y, [a, b, c, d, e]).
Y = [d, e].
§ Very different from imperative programming: input/output
§ In Prolog: no clear notion of input and output § Just search for values that make the goal true
25
List operations
§ Subset subset([], S).
subset([H|T], S) :- member(H, S), subset(T, S).
§ Reversing a list reverse([], []).
reverse([H|T],R) :- reverse(T,R1), append(R1,[H],R).
§ Permutations
permute([], []).
permute([H|T], P) :- permute(T, P1), insert(H, P1, P).
26
Unification
path(L, L).
path(L, M) :- link(L, X), path(X, M).
?- path(fortran, cplusplus).
§ Unification is a type of pattern matching: L unifies with fortran
M unifies with cplusplus
27
Unification
§ Unification rules:
§ a constant unifies with itself
§ two structures unify if and only if:
§ have the same functor
§ have the same arity
§ corresponding arguments unify recursively
§ a variable unifies with anything
§ if the other thing has a value, then the variable is
instantiated
§ if the other thing is an uninstantiated variable, then the two variables are associated so that if either is given a value later, that value will be shared by both
28
Unification
§ Equality (=) is unifiability:
§ The goal =(A,B) succeeds iff A and B can be unified § A = B – syntactic sugar
§ Example:
?- a = a.
true.
?- a = b.
false.
?- foo(a,b) = foo(a,b). true.
29
Unification
§ Example:
?- X = a.
X = a.
?- foo(a,b) = foo(X,b). X = a.
30
Arithmetic
§ arithmetic operators – predicates
§ +(2,3) – syntactic sugar 2+3
§ +(2,3) is a two-argument structure; does not unify with 5
?- 1+1 = 2.
false.
§ is: predicate that unifies first arg. with value of second arg. ?- is(X, 1+1).
X = 2.
?- X is 1+1.
X = 2.
31
More unification
§ Substitution:
§ a function from variables to terms
§ Example: σ = {X → [a,b], Y → [a,b,c]}
§ Tσ – the result of applying the substitution σ to the term T §Xσ=U if X→Uisinσ,Xotherwise
§ (f(T1, T2,…,Tn))σ = f(T1σ, T2σ,…,Tnσ)
§ Example:
σ = {X → [a,b], Y → [a,b,c]}
Yσ = [a,b,c]
Zσ = Z
append([], Y, Y)σ = append([], [a,b,c],[a,b,c])
32
More unification
§ A term U is an instance of T if U=Tσ, for some substit. σ
§ Two terms T1 and T2 unify if T1σ and T2σ are identical, for
some σ; σ is called a unifier of T1 and T2
§ σ is the most general unifier of T1 and T2 if, for any other
unifier δ, Tiδ is an instance of Tiσ
§ Example: L = [a,b | X]
§ Unifiers:
§ σ1 = {L → [a,b | X1], X → X1}
§ σ2 = {L → [a,b,c | X2], X → [c | X2]}
§ σ3 = {L → [a,b,c,d | X3], X → [c, d | X3]}
§ σ1 is the most general unifier
33
Control Algorithm
§ Control algorithm
§ the way Prolog tries to satisfy a query
§ Two decisions:
§ goal order: choose the leftmost subgoal § rule order: use the first applicable rule
34
Control Algorithm
§ Control algorithm
start with a query as the current goal while (the current goal is nonempty) do
choose the leftmost subgoal
if (a rule applies to this subgoal) then
select the first applicable rule not already used
form a new current goal
else
if (at the root) then
false
else backtrack
true
35
Control Algorithm – Example
rainy(seattle).
rainy(rochester).
?- rainy(C).
C = seattle ;
C = rochester.
Prolog search tree:
rainy(C).
C → seattle rainy(seattle).
C = seattle
; (backtrack)
C → rochester rainy(rochester).
C = rochester.
36
Control Algorithm – Example
rainy(seattle).
rainy(rochester).
cold(rochester).
snowy(X) :- rainy(X), cold(X).
?- snowy(C).
C = rochester.
37
Control Algorithm – Example
Prolog search tree:
snowy(C).
X→C
snowy(X) :- rainy(X), cold(X).
C → seattle rainy(seattle).
cold(seattle).
backtrack
C → rochester rainy(rochester).
cold(rochester).
C = rochester
rainy(C), cold(C).
38
Control Algorithm – details
start with a query as the current goal: G1, G2, …, Gk (k ≥ 0) while (k > 0) do // the current goal is nonempty
choose the leftmost subgoal G1 if (a rule applies to G1) then
select first applicable rule (not tried): A :- B1,…, Bj (j ≥ 0) let σ be the most general unifier of G1 and A
the current goal becomes: B1σ,…, Bjσ, G2σ, …, Gkσ
else
if (at the root) then
true
false
else backtrack
// tried all possibilities
// try something else
// all goals have been satisfied
39
Control Algorithm – Example
append([], Y, Y).
append([H|X], Y, [H|Z]) :- append(X, Y, Z).
prefix(P, L) :- append(P, _, L).
suffix(S, L) :- append(_, S, L).
?- suffix([a], L), prefix(L, [a, b, c]). L = [a] // that’s the obvious solution
L = [a] ; // if we ask for more solutions
// we get an infinite computation
// eventually aborting (out of stack)
40
Control Algorithm – Example
?- suffix([a], L), prefix(L, [a, b, c]).
L = [a] ; // infinite computation
§ why the infinite computation? § consider the first subgoal only:
?- suffix([a], L).
L = [a] ;
L = [_944, a] ;
L = [_944, _956, a] ;
L = [_944, _956, _968, a] ; …
§ infinitely many solutions, none (but the first) satisfying the second subgoal
§ control checks an infinite subtree with no solutions
41
Control Algorithm – Example
append([], Y, Y).
append([H|X], Y, [H|Z]) :- append(X, Y, Z).
prefix(P, L) :- append(P, _, L).
suffix(S, L) :- append(_, S, L).
?- suffix([b], L), prefix(L, [a, b, c]).
L = [a, b] // that’s the obvious solution
L = [a, b] ;// if we ask for more solutions
// again, infinite computation
42
Goal order
§ Changing the order of subgoals can change solutions:
?- suffix([a], L), prefix(L, [a, b, c]).
L = [a] ;
// infinite computation
§ if we change the goal order, then no infinite computation:
?- prefix(L, [a, b, c]), suffix([a], L).
L = [a] ;
false.
43
Goal order
§ The explanation is that the first subgoal now has finitely many solutions:
?- prefix(L, [a, b, c]).
L = [] ;
L = [a] ;
L = [a, b] ;
L = [a, b, c] ;
false.
44
Rule order
§ Changing the order of rules can change solutions: append([], Y, Y).
append([H|X], Y, [H|Z]) :- append(X, Y, Z).
?- append(X, [c], Z).
X = [],
Z = [c] ;
X = [_576],
Z = [_576, c] ;
X = [_576, _588],
Z = [_576, _588, c] ;
X = [_576, _588, _600],
Z = [_576, _588, _600, c] ; …
45
Rule order
§ Changing the order of rules can change solutions: append([H|X], Y, [H|Z]) :- append(X, Y, Z).
append([], Y, Y).
?- append(X, [c], Z).
// infinite computation
46
Cuts
§ ! – cut
§ zero-argument predicate
§ prevents backtracking, making computation more efficient § can also implement a form of negation (we’ll see later)
§ General form of a cut:
P :- Q1, Q2,…, Qj-1, !, Qj+1,…,Qk.
§ Meaning: the control backtracks past Qj-1, Qj-2,…, Q1, P
without considering any remaining rules for them
47
Cuts
§ Example: member(X, [X|_]).
member(X, [_|T]) :- member(X, T).
prime_candidate(X) :- member(X,Candidates),prime(X).
§ assume prime(a) is expensive to compute
§ if a is a member of Candidates many times, this is slow § solution:
member1(X, [X|_]) :- !.
member1(X, [_|T]) :- member1(X, T).
48
Cuts
?- member(a, [a,b,c,a,d,a]).
true ;
true ;
true ;
false.
?- member1(a, [a,b,c,a,d,a]).
true.
49
Negation of failure
§not – negation § Definition:
not(X) :- X, !, fail.
not(_).
§ fail always fails
§ the first rule attempts to satisfy X
§ if X succeeds, then ! succeeds as well, then fail fails and ! will prevent backtracking
§ if X fails, then not(X) fails and, because the cut has not been reached, not(_) is tried and immediately succeeds
50
Negation of failure
§ Example:
?- X=2, not(X=1).
X = 2.
?- not(X=1), X=2.
false.
51