CPSC 312 — Functional and Logic Programming
Assignment 4 is due Tomorrow.
“Bad reasoning as well as good reasoning is possible; and this fact is the foundation of the practical side of logic.”
Charles Sanders Peirce, 1877
CPSC 312 — Lecture 21 1 / 23
©D. Poole 2021
Plan
Done:
Syntax and semantics of propositional definite clauses Model a simple domain using propositional definite clauses Soundness and completeness of a proof procedure Bottom-up proof procedure: soundness and completeness Top-down proof procedure
Today:
Procedural definition (box model) Prolog debugger
Datalog
CPSC 312 — Lecture 21
2 / 23
©D. Poole 2021
Top-down Definite Clause Proof Procedure
Idea: search backward from a query to determine if it is a logical consequence of KB.
An answer clause is of the form: yes:-a1,a2, …,am
The (SLD) resolution of this answer clause on leftmost atom a1 with the clause in the knowledge base with head a1:
a1 :- b1, …, bp is the answer clause
yes :- b1, ···, bp, a2, ···, am.
A fact in the knowledge base is considered as a clause where p = 0.
CPSC 312 — Lecture 21 3 / 23
©D. Poole 2021
Clicker Question
Given the answer clause
yes :- gimble, gyre, mimsy.
Which clause in a KB could this be resolved with (i) mimsy :- gimble.
(ii) gimble.
(iii) gyre :- mimsy.
(iv) gimble :- nice, mimsy.
(v) gyre, mimsy Click on:
A (i), (ii) and (iv) only B (ii) and (iv) only
C (ii) only
D (iii) and (v) only
E none of the above
©D. Poole 2021
CPSC 312 — Lecture 21 4 / 23
Clicker Question
Given the answer clause
yes :- gimble, gyre, mimsy.
What is the result of resolving this with the clause
gimble :- rath, mimsy.
A yes :- gimble, rath, mimsy, gyre, mimsy B gimble :- gyre, mimsy
C yes :- gyre, mimsy
D yes :- rath, mimsy, gyre, mimsy
E yes :- rath, mimsy, gimble, gyre, mimsy
©D. Poole 2021
CPSC 312 — Lecture 21 5 / 23
Clicker Question
Given the answer clause
yes :- gyre, mimsy, gimble.
What is the result of resolving this with the clause
gyre .
A yes :- gimble, rath, mimsy, gyre, mimsy B gyre :- mimsy, gimble
C yes :- gyre, mimsy
D yes :- gyre, mimsy, gimble
E yes :- mimsy, gimble
©D. Poole 2021
CPSC 312 — Lecture 21 6 / 23
Search Graph for SLD Resolution
yes :- a, d yes:-b, c, d yes:-g, d
yes:-j, c, d yes:-m, d yes:-k, c, d
yes:-h, d yes:-m, d
yes:- f, d yes:-p, d
yes :- d yes:-m yes:-p
yes :-
1
a:-b, a:-h. b:-k. d:-p. f:-p. g:-f. h :- m. ?a, d.
c.
a:-g. yes:-m, c, d b:-j.
d:-m.
f:-m.
g:-m. k:-m. p.
yes:-m, d
©D. Poole 2021
CPSC 312 — Lecture 21 7 / 23
Procedural View of Propositional Prolog
Informally:
The clauses with same atom as head define a procedure.
Each procedure either succeeds or fails.
To call a procedure, call each body in turn until one succeeds.
To call a body, call each atom in the body.
A body succeeds if all atoms in the body succeed.
The procedure fails if no bodies succeed.
CPSC 312 — Lecture 21 8 / 23
©D. Poole 2021
Box Model of Propositional Prolog
Call Exit Fail Retry
©D. Poole 2021
CPSC 312 — Lecture 21 9 / 23
Example: backeg.pl
:- dynamic f/0.
a :- b, c, d.
a :- e.
b.
c :- s.
c :- t.
d :- f.
e :- t.
e :- s.
s.
t.
©D. Poole 2021
CPSC 312 — Lecture 21 10 / 23
Wiring Boxes
Fact (some atom a is just a fact).
Atom not defined
CPSC 312 — Lecture 21 11 / 23
©D. Poole 2021
Wiring Boxes
conjunction c1, c2, c3
c1 c2 c3
Rules:
b1
b2 b3
redo
a :- b1 a :- b2 a :- b3
It redoes whichever body exited. (It remembers this on “local stack”).
CPSC 312 — Lecture 21 12 / 23
©D. Poole 2021
Prolog Debugging
If there are no clauses for an atom, Prolog assumes there is an error. Add a declaration
:- dynamic atom.
for an atom that has no clauses on purpose.
To start a trace Prolog do:
?- trace.
Prolog displays call and exit following the box model.
It does not diplay retry/fail unless there is another clause to try, where it displays a redo.
Prolog gives one answer for each proof. Type ; to find another proof.
CPSC 312 — Lecture 21 13 / 23
©D. Poole 2021
Example (simpeg.pl)
a :- b, c.
a :- e, f.
b :- f, k.
c :- e.
d :- k.
e.
f :- j, e.
f :- c.
j :- c.
©D. Poole 2021
CPSC 312 — Lecture 21 14 / 23
Box examples
a :- b,c. a :- e,f.
b :- f,k.
e.
no clauses for k
a
bc ef
b
e
fk
k
©D. Poole 2021
CPSC 312 — Lecture 21 15 / 23
Today
Relations and individuals, logical variables, Datalog
CPSC 312 — Lecture 21 16 / 23
©D. Poole 2021
Relations
Table: Course
CPSC 312 CPSC 322 CPSC 322
Year Section Days Time 2021 101 MWF 12:00 2021 101 TR 17:00 2021 201 TR 9:30
Room DMP 310 MCML 166 DMP 310
can be represented in Prolog as:
scheduled(cpsc312, 2021, 101, mwf, 12, dmp310).
scheduled(cpsc322, 2021, 101, tr, 17, mcml166).
scheduled(cpsc322, 2021, 201, tr, 9.50, dmp310).
©D. Poole 2021
CPSC 312 — Lecture 21 17 / 23
From propositions to relations
Consider the atoms: ok_l1, live_l1, live_w0 separate properties/relations from individuals:
ok(l1), live(l1), live(w0)
instead of writing specific rules such as
live_l1 :- live_w0.
live_w0 :- live_w1, up_s2.
live_w0 :- live_w2, down_s2.
write general rules
live(X) :- connected(X,Y), live(Y).
CPSC 312 — Lecture 21
18 / 23
©D. Poole 2021
Role of Semantics in Automated Reasoning
in(kim,r123). part_of(r123,cs_building). in(X,Y) ←
kim r123 r023
part_of(Z,Y) ∧ in(X,Z).
cs_building
in( , ) part_of( , ) person( )
in(kim,cs_building) ©D. Poole 2021
CPSC 312 — Lecture 21 19 / 23
Features of Automated Reasoning
Users can have meanings for symbols in their head.
The computer doesn’t need to know these meanings to derive logical consequence.
Users can interpret any answers according to their meaning.
CPSC 312 — Lecture 21 20 / 23
©D. Poole 2021
Syntax of Datalog
A variable starts with upper-case letter or with underscore (’ ’)
A constant is a sequence of letters, digits or underscore (’ ’) and starts with lower-case letter
or is a sequence of digits (numeral)
or is any sequence of characters between single quotes.
A predicate symbol starts with lower-case letter. A term is either a variable or a constant.
An atomic symbol (atom) is of the form p or p(t1, . . . , tn) where p is a predicate symbol and ti are terms.
CPSC 312 — Lecture 21 21 / 23
©D. Poole 2021
Syntax of Datalog (cont)
A definite clause is either
— an atomic symbol (a fact) or — a rule of the form:
a :-b1,···,bm
head body
where a and bi are atomic symbols.
[A fact is treated as a rule with an empty body (m=0).]
A knowledge base is a set of definite clauses. A query is of the form ?b1, ···, bm.
CPSC 312 — Lecture 21 22 / 23
©D. Poole 2021
Example Knowledge Base
in(kim,R) :-
teaches (kim, cs 322), in(cs 322, R ).
grandfather(william,X) :- father (william, Y ), parent(Y,X).
slithy(toves) :-
mimsy, borogroves, outgrabe(mome, Raths).
The variables are: R, X, Y, Raths.
The constants are: kim, cs322, william, toves, mome. The predicate symbols are: in, teaches, grandfather, father, parent, slithy, mimsy, borogroves, outgrabe.
©D. Poole 2021
CPSC 312 — Lecture 21 23 / 23