Transcript Logic Programming

Logic Programming
Lecture 1:
Course orientation;
Getting started with Prolog
Assoc. Prof. Zeki Bayram
Based on slides by James Cheney
•
•
What is Logic
Programming?
Logic Programming is a programming
paradigm
•
•
cf. object-oriented or functional programming
Not a particular language (like Java or Haskell)
Declarative philosophy
•
specify problem, let computer search for
answer
Logic Programming
The declarative
dream
• Slogan: "Algorithm = Logic + Control"
• Would like to write a program that
describes the solutions to the problem
• Computer then finds answers
• Programmer shouldn't have to think
about how the system works
Logic Programming
The reality
• Purely declarative programming can
only get you so far
• I/O, interaction with outside world, seem
inherently "imperative"
• For efficiency/termination, sometimes
need finer-grained control over search
Logic Programming
Prolog
• Prolog is the best-known LP language
•
•
Core based on first-order (predicate) logic
Algorithmic realization via unification,
search
• Many implementations that make it into
a full-fledged programming language
•
I/O, primitive ops, efficiency issues
complicate declarative story
Logic Programming
Why learn LP?
•
•
•
LP often great for rapidly prototyping
algorithms/search strategies
"Declarative" ideas arise in many areas of CS
•
•
•
LP concepts very important in AI, databases, PL
SAT solvers, model-checking, constraint
programming
Becoming important in program analysis,
Semantic Web
Learning a very different "way to think about
problems" makes you a better programmer
Logic Programming
Course objectives
• Theory
•
•
first-order logic, semantics of LP
unification, resolution proof search
• Programming
•
•
•
basic LP techniques in Prolog
how to use LP to solve interesting problems
AI, parsing, search, symbolic processing
Logic Programming
Atoms
•An atom is
•
•
a sequence of alphanumeric characters
•
usually starting with lower case letter
or, a string enclosed in single quotes
•Examples:
•homer marge lisa
•‘Mr. Burns’ ’Principal
Logic Programming
bart
Skinner’
Variables
•A variable is a sequence of
alphanumeric characters
•
usually starting with an uppercase letter
•Examples:
•X Y Z
Parent Child Foo
Logic Programming
Predicates
• A predicate has the form
• p(t ,...,t )
• where p is an atom and t ...t are terms
• (For now a term is just an atom or variable)
1
n
1
• Examples:
• father(homer,
• mother(marge,
bart)
bart)
Logic Programming
n
Predicates (2)
•
•
•
•
A predicate has a name
•
= atom p in p(t1,...,tn)
and an arity
•
= number of arguments (n)
Predicates with same name but different
arity are different
We write foo/1, foo/2, ... to refer to these
different predicates
Logic Programming
Facts
•A fact is an assertion thatPunctuation
a predicate is
is
true:
important!
•father(homer, bart).
•mother(marge, bart).
•A collection of facts is sometimes called
a knowledge base (or database).
Logic Programming
Goals
• A goal is a sequence of predicates
•p(t ,...,t ),
1
n
..., q(t1',...,tn').
• We interpret “,” as conjunction
• Logically, read as "p holds of t ...t
1
and ... and q holds of t1'...tm'"
• Predicates can be 0-ary
•Some built-ins: true, false, fail
Logic Programming
n
Answers
• Given a goal, Prolog searches for
answers
•
•
“yes” (possibly with answer substitution)
“no”
• Substitutions are bindings of variables
that make goal true
• Use “;” to see more answers
Logic Programming
Examples
•
•
•
•
•
•
•
•
?- father(X,bart).
X = homer ;
no
?- father(X,Z), mother(Y,Z).
X = homer, Y = marge, Z = bart ;
X = homer, Y = marge, Z = lisa ;
X = homer, Y = marge, Z = maggie ;
no
Logic Programming
Rules
•
•
A rule is an assertion of the form
p(ts) :- q(ts’), ..., r(ts’’).
•
where ts, ts’, ts’’ are sequences of terms
•
“p(ts) holds if q(ts’) holds and ... and
r(ts’’) holds”
•
Example:
•
•
sibling(X,Y) :- parent(Z,X),
parent(Z,Y).
Logic Programming
Miscellaneous
•Comments
•% single line
•/* multiple
• line
• comment */
comment
Logic Programming
Consulting
•A Prolog program is a collection of facts
and rules, or clauses
•
stored in one or more files
•The predicate consult/1 loads the
facts/rules in a file
•?-
consult(‘simpsons.pro’).
Logic Programming
Consulting (2)
•If the file name ends with '.pl', can just
write:
•?- consult(simpsons).
•Also, can just write
•?- [simpsons].
Logic Programming
A complete program
•
•
•
•
•
/* hello.pl
* James Cheney
* Sept. 20, 2010
*/
main :- write('hello world').
Logic Programming
Tracing
• trace/0 turns on tracing
• notrace/0 turns tracing off
• debugging/0 shows tracing status
• But: better to use Amzi Prolog’s built-in
debugger
Logic Programming
Further reading
•Quick Start Prolog notes (Dave
Robertson)
• http://www.inf.ed.ac.uk/teaching/courses/lp/prolognotes.pdf
•Learn Prolog Now! (Blackburn, Bos,
Striegnitz)
•
online, free
• http://www.learnprolognow.org/
•Programming in Prolog (Clocksin &
Mellish)
Logic Programming
Exercises
• Using simpsons.pro, write goal bodies
for:
• classmate(X,Y)
• employer(X)
• parent(X,Y)
• grandparent(X,Y)
Logic Programming
Next time
• Compound terms
• Equality and unification
• How Prolog searches for answers
Logic Programming