Transcript Declarative programming

CHAPTER NINE
Logic Programming
Programming Languages – Principles and Paradigms
by Allen Tucker, Robert Noonan
Background:
• Declarative programming was created in the
1970s.
• The programmer declares goals of the program,
not how to perform the computation.
• Declarative programming is used primarily in
database management systems (DBMS) and
artificial intelligence (AI).
• An example in the DBMS realm is the
structured query language (SQL).
• In AI the most wide spread language is Prolog,
which we will look at in greater detail.
Terminology:
• Goals are expressed as a collection of
assertions or rules.
• For this reason declarative programming is also
called rule-based programming.
• In AI declarative programming is used to express
specifications for problem solutions in the form of
mathematical logic.
• This style of programming is called logic
programming.
• The resulting programs are often referred to as
expert systems since they contain a knowledge
database that can be asked questions.
Terminology:
• Prolog is based on two principles: resolution
and unification.
• Knowledge is stated as propositions composed
of boolean constants, variables, and logical
operators.
• Predicate logic expressions, or predicates,
include all propositions plus propositions where
variables may be replaced by functions and
quantified expressions.
• Boolean valued functions are functions with
one or more boolean variable that delivers a true
or false result.
Terminology:
• A Horn clause has a head h, which is a
predicate, and a body, which is a list of predicates.
h  p1, p2, …,pn
• Resolution is making a single inference from a
pare of Horn clauses.
• Unification is a pattern matching that
determines what instantiations can be made to
variables during the process of making a series of
simultaneous resolutions.
• Logic programming also features
nondeterminism and backtracking.
Example:
• Consider the following Prolog program:
speaks(allen, russian).
speaks(bob, english).
speaks(mary, russian).
speaks(mary, english).
talkswith(Person1, Person2) :speaks(Person1,L),
speaks(Person2,L),
Person1 \= Person2.
Example:
• Queries can be asked of the program after is has
been loaded:
?- consult(speaks)
speaks compiled…
?- speaks(Who, russian).
Who = allen ;
Who = mary ;
No
? – talkswith(bob, allen).
No
? – talkswith(Who, allen).
Attempting to Satisfy the Query talkswith (bob, allen)
Figure 9.1
First Attempt to Satisfy the Query talkswith(Who, allen)
Figure 9.2
A Partial Family Tree
Figure 9.3
A Small Family “Tree”
Figure 9.4
Next time…
More Logic
Programming