UNIT I

Fundamentals of Programming

1
 Unit I Contents (06 Hours)

• Importance of Studying Programming Languages, History of Programming

Languages, Impact of Programming Paradigms, Role of Programming
Languages, Programming Environments. Impact of Machine Architectures:
The operation of a computer, Virtual Computers and Binding Times.
• Programming paradigms- Introduction to programming paradigms,
Introduction to four main Programming paradigms- procedural, object
oriented, functional, and logic and rule based.
Logic and Rule based Programming
Paradigm
 Logic and rule based
• We now examine a radically different paradigm for programming: declarative
programming
– rather than writing control constructs (loops, selection statements,
subroutines)
– you specify knowledge and how that knowledge is to be applied through a
series of rules
– the programming language environment uses one or more built-in methods
to reason over the knowledge and prove things (or answer questions)
• in logic programming, the common approach is to apply the methods of
resolution and unification
• While these languages have numerous flaws, they can build powerful problem
solving systems with little programming expertise
– they have been used extensively in AI research
 Terminology
• Logic Programming is a specific type of a more general class: production systems (also
called rule-based systems)
– a production system is a collection of facts (knowledge), rules (which are another
form of knowledge) and control strategies
– we often refer to the collection of facts (what we know) as working memory
– the rules are simple if-then statements where the condition tests values stored in
working memory and the action (then clause) manipulates working memory (adds
new facts, deletes old facts, modifies facts)
– the control strategies help select among a set of rules that match – that is, if multiple
rules have matching conditions, the control strategies can help decide which rule we
select this time through
– there are other control strategies as well – whether we work from conditions to
conclusions or from conclusions to conditions (forward, backward chaining
respectively)
 Logic Programming
• Also known as declarative programming.
• Mostly synonymous with the Prolog language because it is the only widely used
language for logic programming.
• A declarative program does not have code, instead it defines two pieces of
knowledge
– facts – statements that are true.
– rules – if-then statements that are truth preserving.
• We use the program to prove if a statement is true and/or answer questions.
• The reason this works is that Prolog has built-in problem solving processes
called resolution and unification
– in fact Prolog is not so much a programming language as it is a tool, but it
does have some programming language features that make it mildly
programmable
 Background for Logic
• A proposition is a logical statement that is only made if it is true
– Today is Tuesday
– The Earth is round
• Symbolic logic uses propositions to express ideas, relationships between ideas and to generate new
ideas based on the given propositions
• Two forms of propositions are
– Atomic propositions
– Compound terms (multiple propositions connected through the logical operators of and, or, not,
and implies)
• Propositions will either be true (if stated) or something to prove or disprove (determine if it is true) – we
do not include statements which are false
• For symbolic logic, we use 1st order predicate calculus
– statements include predicates like round(x) where this is true if we can find an x that makes it true
such as round(Earth) or round(x) when x = Earth
– you might think of a predicate as a Boolean function except that rather than returning T or F, it finds
an x that makes it true
 – Equivalence means that both
Logic Operators expressions have identical
truth tables
Name Symbol Example Meaning
– Implication is like an if-then
negation ¬ ¬a not a statement

conjunction ∩ a∩b a and b • if a is true then b is true

• note that this does not
disjunction ∪ a∪b a or b necessarily mean that if a
equivalence ≡ a≡b a is equivalent is false that b must also be
to b false

implication ⊃ a⊃b a implies b – Universal quantifier says that

this is true no matter what x is
⊂ a⊂b b implies a
– Existential quantifier says that
universal ∀ X.P For all X, P is there is an X that fulfills the
true statement

existential ∃ X.P There exists a ∀X.(woman(X) ⊃ human(X))

value of X – if X is a woman, then X is a human
such that P is
true ∃X.(mother(mary, X) ∩ male(X))
– Mary has a son (X)
 Clausal Form
• To use resolution, all statements must be in clausal form
– B1 ∪ B2 ∪ … ∪ Bn ⊂ A1 ∩ A2 ∩ … ∩ Am
• B1 or B2 or … or Bn is true if A1and A2 and … and Am are all true
– the left hand side is the consequent (what we are trying to prove) and the right
hand side is the antecedent (what conditions must hold true)
– notice we have turned the if-then statement around,
– We must modify our knowledge so that:
• existential quantifiers are not required (eliminate all of them)
• universal quantifiers are implied (by replacing each with a specific variable)
• no negations (all negations must be removed)
– We break down our statements to have a single item on the left
• the above statement is broken into multiple statements such as
– B1 ⊂ A1 ∩ A2 ∩ … ∩ Am
– B2 ⊂ A1 ∩ A2 ∩ … ∩ Am …
– Bn ⊂ A1 ∩ A2 ∩ … ∩ Am
• note that propositions and predicates by themselves are already in clausal form, such
as round(Earth) and Sunny
 Resolution and Unification
• Given a collection of knowledge
– we will want to prove certain statements are true or answer questions
• For instance, from the previous example, we might ask
– who is Bob’s grandfather?
– is Sue Barbara’s parent?
• How can this be done? Through backward chaining through rules
• Here is how backward chaining works
– we want to prove that A is true
– find a rule with A on its LHS and whatever is on the rule’s RHS must now be proven
to be true, so we add the items on the RHS to a list of things we are trying to prove
– repeat until
• we match something that we know is true to our list, then remove the item
• we run out of items on our list, then we are done, we have proven A is true
• To complicate matters, predicates (e.g., round(X)) need to be unified, that is, to prove
round(X) is true, we have to find some X where we know it is true, for instance,
round(Earth)
 Complete Logic Example
If we want to find out what would
Assume that we know the following about pets: make a good indoor pet, we ask
poodle(COCOA) indoorpet(?)
setter(BIG)
terrier(SCOTTY) This requires finding pet(X) and small(X)
(find an X to make both predicates true)
dog(X) ⊂ poodle(X) (poodles are dogs) pet(X) is implied by dog(X),
dog(X) is implied by terrier(X),
dog(X) ⊂ setter(X) (setters are dogs) SCOTTY is a terrier so SCOTTY
dog(X) ⊂ terrier(X) (terriers are dogs) is a dog so SCOTTY is a pet
small(X) ⊂ poodle(X) (poodles are small)
small(X) ⊂ terrier(X) (terriers are small) Can we find if SCOTTY is small?
small(SCOTTY) is implied
big(X) ⊂ setter(X) (setters are big) by terrier(SCOTTY) which we
pet(X) ⊂ dog(X) (dogs are pets) already know is true, therefore,
indoorpet(X) ⊂ pet(X) and small(X) since terrier(SCOTTY) is true, small(SCOTTY)
(small pets are indoor pets) and pet(SCOTTY)
are true, so indoorpet(SCOTTY) is
outdoorpet(X) ⊂ pet(X) and big(X)
True
(big pets are outdoor pets)
Continuing with this process
will also prove that indoorpet(COCOA)
is true.
 PROLOG
• PROLOG is a programming language that allows the programmer to specify
declarative statements only
– declarative statements (things you are declaring) fall into 2 categories
• predicates/propositions that are true
• clauses (truth preserving rules in clausal form)
– once specified, the programmer then introduces questions to be answered
• PROLOG uses resolution (backward chaining) and unification to perform
the problem solving automatically
• PROLOG was developed in France and England in the late 70s
– the intent was to provide a language that could accommodate logic
statements and has largely been used in AI but also to a lesser extent as a
database language or to solve database related problems
 Elements of Prolog
• Terms – constant, variable, structure
– constants are atoms or integers (atoms are like those symbols found in Lisp)
– variables are not bound to types, but are bound to values when instantiated (via
unification)
– an instantiation will last as long as it takes to complete a goal
• proving something is true, or reaching a dead end with the current
instantiation
– structures are predicates and are represented as
• functor(parameter list) where functor is the name of the predicate
• All statements in Prolog consist of clauses
– headed clauses are rules
– headless clauses are statements that are always true
• in reality, a headless clause is a rule whose condition is always true
– all clauses must end with a period
 Rules
• All rules are stated in Horn clause form
– the consequence comes first
• the symbol :- is used to separate the consequence from the antecedent
– And is denoted by , and Or is denoted by ; or separating the rule into two
separately rules
– variables in rules are indicated with upper-case letters
– rules end with a .
– examples:
• parent(X, Y) :- mother(X, Y).
• parent(X, Y) :- father(X, Y).
• grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
• sibling(X, Y) :- mother(M, X), mother(M, Y), father(F, X), father(F, Y).
– we can use _ as a wildcard meaning this is true if we can find any clause that fits
• father(X) :- father(X, _), male(X).
– X is a father if X is male and is someone’s father
 Other Language Features
• Assignment statements are available using the is operator
– A is B / 17 + C.
• this works if B and C are instantiated and A is not
• however, is does not work like a true assignment statement
– you can not do x is x + y – this can never be true!
– we might use the assignment operator in a rule such as
• distance(X,Y) :- speed(X,Speed), time(X,Time), Y is Speed * Time

• List structures are also available using [ ] marks

– as in new_list([apple, prune, grape, kumquat]).
– this is not a binding of new_list to the values, but instead new_list is
a predicate with a true instance of the predicate being the parameter
[apple, prune, grape, kumquat]
• lists can also be represented as a head and tail using | to separate the two
parts similar to how Lisp uses CAR and CDR
 More Prolog Examples
predecessor(X,Y) :- parent(X,Y); parent(X,Z), predecessor(Z,Y).
// X is a predecessor of Y if X is Y’s parent or
// if X is parent of someone else whoNotice
is a predecessor of Y
the use of “not” here
– in Prolog, x != y is
Using Not: available but ~foo(x) is not
dog(X) :- poodle(X).
That is, we only declare
dog(X) :- terrier(X).
statements that are true, we
likes(X,Y) :- dog(X), dog(Y), not (X=Y). cannot declare the negation
// can also be written as X =\= Y of statements that are false

Database example: imagine we have a collection of terms:

record(name, yearborn, salary)
Successful person is someone who either makes > $50000 in salary
or was born after 1980 and is making more than $40000.
success(X) :- record(X, Y, Z), Z > 50000;
record(X, Y, Z), Y > 1980, Z > 40000.
 Additional Prolog Examples
Defining Max:
max(X,Y,M) :- X > Y, M is X.
max(X,Y,M) :- Y >= X, M is Y.

Defining GCD:
gcd(X,Y,D) :- X=Y, D is X.
gcd(X,Y,D) :- X<Y, Y1 is Y - X, gcd(X, Y1, D).
gcd(X,Y,D) :- X>Y, gcd(Y, X, D).

Two List examples

Defining Length:
length([ ], 0). // empty list has a length of 0
length([ _ | Tail, N) :- length(Tail, N1), N is 1 + N1. // a list that has an
// item _ and a Tail is length N if the length of Tail is N1 where N = 1 + N1

Sum of the items in a list:

sum([ ], 0). // sum of an empty list is 0
sum([X | Tail], S) :- sum(Tail, S1), S is X + S1.
 Advantages of Prolog
• There are several advantages to using Prolog
– ability to create automated problem solvers merely by listing
knowledge
– a shortcut way to build and query a database
– solving significantly difficult problems with minimal code:
Deriving the permutations of a list List:
perm(List,[H|Perm]):-delete(H,List,Rest),perm(Rest,Perm).
perm([ ],[ ]).
delete(X,[X|T],T).
delete(X,[H|T],[H|NT]):-delete(X,T,NT).
Sorting a list of values stored in List:
insert_sort(List,Sorted):-i_sort(List,[],Sorted).
i_sort([ ],Acc,Acc).
i_sort([H|T],Acc,Sorted):-insert(H,Acc,NAcc),i_sort(T,NAcc,Sorted).
insert(X,[Y|T],[Y|NT]):-X>Y,insert(X,T,NT).
insert(X,[Y|T],[X,Y|T]):-X=<Y.
insert(X,[],[X]).
A naïve sort (inefficient, but simple):
naive_sort(List,Sorted):-perm(List,Sorted),is_sorted(Sorted).
is_sorted([ ]).
is_sorted([ _ ]).
is_sorted([X,Y|T]):-X=<Y,is_sorted([Y|T]).
 Deficiencies of Prolog
• Lack of control structures
– Prolog offers built-in control of resolution and unification
• you often have to force a problem into the resolution mold to solve it with Prolog (most
problems cannot or should not be solved in this way)
• Inefficiencies of resolution
– resolution, as a process, is intractable (O(2n) for n clauses)
• useful heuristics could be applied to reduce the complexity, but there is no way to apply
heuristics in Prolog
– they would just be additional rules that increases the size of n!
• Closed world assumption
– in any form of logic reasoning, if something is not known, it is assumed to be false and
everything is either true or false
• Negation is difficult to represent
– since there is no NOT in Prolog, how do we represent NOT?
• recall that anything explicitly stated must be true so we cannot specify NOT something
as something would then be false
• we can represent A != B, but we cannot represent ~dog(X).
 Rule-based Approaches
• Three of Prolog’s deficiencies can be eliminated (or lessened)
– heuristics can be applied to improve efficiency
• not necessarily reduce the complexity below O(2n) but improve it
– uncertainty can be expressed by adding certainty factors or probabilities to data, rules and
conclusions
– use both forward and backward chaining
• Rule-based systems are less restrictive than the strictly logic-based approach in Prolog
– by moving away from the formal logic approach however, doubts can arise from any results
generated by such a system
• that is, we can not be sure of the truth of something proven when the system contains non-
truth-preserving rules and uncertain data
– is it useful to move away from the strict logic-based approach given this uncertainty?
• since nearly everything in the world has uncertainty, my answer is YES
• The rule-based approach is largely the same as in Prolog:
– declare knowledge, provide rules, and ask questions to be answered, but most rule-based
languages provide mechanisms for control strategies
 Case Study

• A case study: Retail Sales application

 Prof. S. N. Shelke
(Assistant Professor)
Department of Computer Engineering
Sinhgad Academy of Engineering,
Kondhwa, Pune