CPSC 312 — Functional and Logic Programming
Assignment 4 is due next Thursday!
No textbook for logic programning; see readings tab. Get SWI Prolog.
“Learn at least a half dozen programming languages. Include one language that emphasizes class abstractions (like Java or C++), one that emphasizes functional abstraction (like Lisp or ML or Haskell), one that supports syntactic abstraction (like Lisp), one that supports declarative specifications (like Prolog or C++ templates), and one that emphasizes parallelism (like Clojure or Go).”
Peter Norvig “Teach Yourself Programming in Ten Years”
http://norvig.com/21-days.html
CPSC 312 — Lecture 18 1 / 11
©D. Poole 2021
Plan
Logic Programming
Propositional logic programs Semantics
Bottom-up and top-down proof procedures Datalog
Logic programs with function symbols
Applications (e.g., natural language processing) Semantic web
Today:
Syntax and semantics of propositional definite clauses
Model a simple domain using propositional definite clauses Bottom-up proof procedure
CPSC 312 — Lecture 18 2 / 11
©D. Poole 2021
What is Logic programming
Functional programming + search + flexible pattern matching + relations
As a simple database language (Datalog) + function symbols (= data constructors)
Statements of a subset of first-order logic, with procedural interpretation
Prolog started as a tool to write natural language understanding systems (and is used today in controlled natural language situations).
CPSC 312 — Lecture 18 3 / 11
©D. Poole 2021
Haskell vs Prolog Example: append (first.pl)
Haskell:
— append [a1,a2,..an] [b1,..,bm] = [a1..an,b1,..,bm]
append [] l2 = l2
append (h:r) l2 = h : append r l2
Prolog
% append([a1,a2,..an], [b1,..,bm], [a1..an,b1,..,bm])
append([], L2, L2).
append([H|R], L2, [H|L3]) :-
append(R,L2,L3).
Some Prolog queries:
append([1,2,3], [7,8,9], R).
append([1,2], X, [1,2,3,4,5]).
append(X,Y,[1,2,3,4,5]).
©D. Poole 2021
CPSC 312 — Lecture 18 4 / 11
Haskell vs Prolog Example: del1
Delete one instance of an element from a list. Haskell:
del1 :: Eq e => e -> [e] -> Maybe [e]
del1 _ [] = Nothing
del1 e (h:t)
| e==h = Just t
| otherwise = fmap (h:) (del1 e t)
Prolog:
% del1(E,L,R) is true if R is the L with one E removed
del1(E,[E|Y],Y).
del1(E,[H|T],[H|Z]) :-
del1(E,T,Z).
Some Prolog queries:
del1(a,[a,v,a,t,a,r],A).
del1(b,[a,v,a,t,a,r],A).
©D. Poole 2021
CPSC 312 — Lecture 18 5 / 11
Datalog program: family relationships (family.pl)
% father(X, Y) means X is the father of Y
father(pierre, justin).
father(pierre, alexandre).
father(pierre, michel).
father(justin, xavier).
father(justin, ella_grace).
% mother(X, Y) means X is the mother of Y
mother(margaret, justin).
mother(margaret, alexandre).
mother(margaret, michel).
mother(sophie, xavier).
mother(sophie, ella_grace).
% Also defined: parent, grandmother, sibling, ancestor
% parent(X,Y) means X is a parent of Y
©D. Poole 2021 CPSC 312 — Lecture 18 6 / 11
parent(X,Y) :- mother(X,Y).
A progression of logical languages
Propositional logic programs: atoms have no arguments. Datalog: allow for logical variables in clauses.
Pure Prolog: Datalog + function symbols
CPSC 312 — Lecture 18 7 / 11
©D. Poole 2021
Propositional Logic Program Syntax
An atom is of the form p, a word that (can contain letters, digits and underscore ) and starts with a lower-case letter. A body is either
an atom or
(b1, b2) where b1 and b2 are bodies. (Parentheses are
optional). A comma in a body means “and”. A definite clause is either
an atomic clause: an atom or
arule: h:-bwherehisanatomandbisabody.
:- means “if”
An atomic clause is treated as a rule with an empty body. All definite clauses ends with a period “.”
A logic program or knowledge base is a set of definite clauses
A query is a body that is asked at the Prolog prompt (ended with a period).
CPSC 312 — Lecture 18 8 / 11
©D. Poole 2021
Electrical Environment
cb1
w5
outside power
circuit breaker
off
on switch
two-way switch
light
power outlet
s1
cb2
s2 w1 w2
s3
w3
w6
p2
p1
w0
w4
l1
l2
©D. Poole 2021
CPSC 312 — Lecture 18 9 / 11
Example Knowledge Base (elect prop.pl)
light l1. light l2. down s1. up s2. up s3. ok l1.
ok l2.
ok cb1.
ok cb2.
live outside.
lit l1 :- live w0, ok l1
live w0 :- live w1, up s2. live w0 :- live w2, down s2. live w1 :- live w3, up s1. live w2 :- live w3, down s1. lit l2 :- live w4, ok l2.
live w4 :- live w3,
live p1 :- live w3.
live w3 :- live w5,
live p2 :- live w6.
live w6 :- live w5,
live w5 :- live outside.
up s3. ok cb1. ok cb2.
©D. Poole 2021
CPSC 312 — Lecture 18 10 / 11
Clicker Question
Which of the following is a clause?
A happy :- Good.
B happy,rich :- good. C happy :- .
D rich;sad :- good.
E None of the above
©D. Poole 2021
CPSC 312 — Lecture 18 11 / 11