Transcript Declarative Programming Paradigm Presentation

Programming Paradigms
Declarative Programming
Paradigm
1
Learning Objectives
Describe with the aid of examples, the
characteristics of a variety of programming
paradigms.
Explain the terms declarative and procedural as
applied to high-level languages.
Discuss the concepts and, using examples,
show an understanding of backtracking,
instantiation and satisfying goals.
2
Programming Paradigms
Methods of programming.
3
Procedural Programming Paradigm
Expect the user to write the instructions
in sequence telling the computer exactly
how to solve a problem.


The way you have used Visual Basic up to
know has been in the procedural paradigm
form.
Other examples are C++, FORTRAN,
COBOL, BASIC etc.
4
Declarative Programming
Paradigm
A database of facts / rules is first created.
The user writes programs as queries with criteria (rules)
which are inputted into a search engine which searches
the database for the answers and returns them to the
user.
The user / program specifies what is to be searched for
but does not provide the computer with a procedure,
detailing how to search, for the computer to follow as in
procedural languages e.g. Visual Basic etc....
User /
Program
Search Engine
Database
5
Declarative Programming
Paradigm languages are used:
When solving problems in artificial
intelligence such as medical diagnosis,
fault finding in equipment and oil
exploration.
In robot control.
An example of a declarative language is
Prolog.
6
Example Database
male(X). states that X is male
female(X). states that X is female
parent(X,Y). states that X is a parent of Y
female(jane).
female(anne).
female(sandip).
male(charnjit).
male(jaz).
male(tom).
parent(jane,mary).
parent(jane, rajinder).
parent(charnjit, mary).
parent(charnjit, rajinder).
parent(jaz, atif).
parent(sandip, atif).
Example of Backtracking
Instantiation
A particular variable is assigned a value.

e.g. If male(X) and male(jaz) then jaz is an
instance of X or X is instantiated to jaz
8
A goal
The intention to find all instances that
satisfy a query with criteria (rule/s).

Answer a query with criteria written by the
user by using a search engine to search a
database to find and report items which
satisfy the criteria of the query.
9
Example Goal
Query:


What are the names of all the males?
In prolog: male(X).
Answer:



X = charnjit
X = jaz
X = tom
Note that the user does not have to tell
Prolog how to search for the values of X that
satisfy the query.
10
Backtracking
If a query consists of two or more criteria (rules)
and an item in a database satisfies the first
criteria (rule) but does not satisfy another criteria
(rule), then the search engine must go back
to find another item which satisfies the first
criteria and then try again to see if the other
criteria (rule/s) are also satisfied.

This is repeated until all items have been searched
(note in some searches only one item would be
expected so the search would stop if one is found).
11
Example of Backtracking
Query:


What is the name of the mother of Atif?
mother(X,Y):- parent(X, atif), female(X).
When the query is inputted into the search
engine all parents are searched first until one
satisfies the first criteria (rule).
Example Database
Ignore:




parent(jane,mary).
parent(jane, rajinder).
parent(charnjit, mary).
parent(charnjit, rajinder).
because Y<> atif

Remember that the definition parent(X,Y) states that
X is a parent of Y.
12
Example of Backtracking
The first parent to satisfy the 1st criteria is
parent(jaz, atif) so X = jaz
However, male(jaz) so the 2nd criteria (rule) is not
satisfied so this item (X = jaz) is rejected.
Now the search engine has to go back and search
for another parent of atif (backtracking).
This reveals parent(sandip, atif) so X = sandip
As female(sandip) the 2nd criteria is also satisfied
so report sandip is the mother.
13
Note:
Backtracking can only occur if the query
has two or more criteria and if the answer
is not found the first time.

i.e. The first item which satisfies the first
criteria does not satisfy the other criteria,
otherwise the answer has been found and
backtracking is unnecessary.
14
Plenary
male(X). states that X is male
female(X).states that X is female
parent(X,Y).states that X is a parent of Y
mother(X,Y):- parent(X,Y), female(X). states that
X is mother of Y if X is parent of Y and X is
female.
15
Plenary
Sto, Dis, May, David,
Minah, John are all
members of one family.
The following facts
apply:
female(sto).
female(may).
female(minah).
male(john).
male(dis).
male(david).
parent(john,dis).
parent(john,may).
parent(dis,sto).
parent(dis,david).
parent(minah,dis).
parent(minah,may).
16
Plenary
(a) By using examples from the facts
given, explain what is meant by:



(i) instantiation.
(ii) a goal.
(iii) backtracking.
17
Plenary
(i) -A particular variable is assigned a value

-e.g. if male(X) then dis is an instance of X / X is
instantiated to dis
(ii) -The intention to find all instances that
satisfy a rule/set of facts

-e.g. If rule is male(X) then the goal is to find dis and
david and john
(iii) -If the result of one rule does not apply in a
second rule, then go back to find another result
of the first rule

-e.g. parent (john,dis) is found if we are searching
for mother of dis. This fails the second part of the
rule for mother because john is male, so
backtracking is used to return to the next example
satisfying the first part of the rule.
18
Plenary
(b) A new rule states grandparent (X,Y):parent(X,Z),parent(Z,Y).


(i) Write down a rule to define grandmother.
(ii) Explain how this new rule is used to find
the grandmother of david.
19
Plenary
(i) grandmother (x,y) :- grandparent (x,y), female
(x)
(ii)







Ignores parent (john,dis) parent (john,may) parent
(dis,sto) because Y<> david
finds parent (dis,david)
searches for parent (X,dis), finds X = john
finds male (john), rejects X = john because not female
backtracks to find next occurrence of (X,dis)
finds parent (minah,dis)
finds female (minah), reports minah is grandmother
20