Programming Paradigms
• Course overview •Introduction to programming
• Review: The object-oriented
Copyright By PowCoder代写 加微信 powcoder
paradigm in Java •Imperative and concurrent
programming paradigm: Go.
• Logic paradigm: Prolog.
• Functional paradigm: Scheme.
• Quiz 2 is posted due Thursday Feb 10th
• Assignment 1 – late submission ends Feb 9th
Announcement
Acknowledgment
The slides posted through the term are based of the slides offered by:
Prof. Jochen Lang
Demo code: https://www.site.uottawa.ca/~jl ang/CSI2120/demoCode.html
Logic Programming in Prolog
• Predicatecalculus – Predicates
– Horn clauses – Unification
– Resolution
• SearchTrees
– Backtracking
• Prolog Programming
• Learn Prolog Now!
Predicates in Prolog
A prolog program consists of a collection of facts and rules.
• A fact is a predicate terminated by a period “.”
• Rules encode ways of deriving or computing a
loves(vincent,mia). loves(marcellus,mia). loves(pumpkin,honey_bunny). loves(honey_bunny,pumpkin).
jealous(X,Y) :- loves(X,Z),loves(Y,Z).
Predicates in Prolog
loves(vincent,mia). loves(marcellus,mia). loves(pumpkin,honey_bunny). loves(honey_bunny,pumpkin).
jealous(X,Y) :- loves(X,Z),loves(Y,Z).
Variables allow us to
Compute more than yes/no answers Compress the program.
More on Facts
Arity of Predicates
Predicates can have an arbitrary number of arguments
domestic/1 isYellow/1 % 1 argument faster/2 like/2 eat/2 % 2 arguments takes/3 % 3 arguments
Facts that are false in the real world can be used. • faster(snails,cheetahs).
• acollectionoffacts(partofaprogram)
Prolog and Horn Clauses
• FactsandrulesareHornClauses.
• IngeneralF:-F1,F2,…,Fn.
– meaning F if F1 and F2 and …and Fn – F is an atomic formula (must be unique) – Fi are terms / literals or their negation
• F is the head of the clause
• F1, F2,…, Fn together are the body of the clause
• ToproveFinProlog,itmustbetrue(proven)thatF1, F2,…, and Fn are true .
• Horn’s clauses are the only formulas allowed in Prolog
Horn Clauses
• Aruleisaclausewherethebodyisnon-emptywhileafactis a clause with an empty body. Most rules contain variables.
• PrologDefinitionwithananonymousvariable,writtenas“_”
salary(X) :- employed(Y,X). % Ok but with % a warning
– Or with an anonymous variable
salary(X) :- employed(_,X).
• Factsandrulesarepredicates.
https://www.swi-prolog.org/pldoc/man?section=singleton
Predicates in Prolog
• 𝒃←𝒂𝟏∧𝒂𝟐∧⋯∧𝒂𝟑
– All terms 𝒂𝟏, 𝒂𝟐, … , 𝒂𝟑 in the body of the predicate havetobetrueforthe headtobetrue.Or,
𝒂𝟏, 𝒂𝟐, … , 𝒂𝟑 being true, implies b is true.
– This is a fact because truth is always implied.
– Without a head, it is goal for which correctness still needs to be proven. This may be considered a question in logic programming in Prolog. Proofing correctness requires deductive reasoning.
Horn Clauses
• Hornclausescanexpressnearlyalllogicexpressions,all mathematical algorithms.
• Itenablesonetoestablishthetruthofahypothesisby establishing the truth of terms but it does not allow one to prove the falsehood of a hypothesis. False in logic programming only means that the goal can not be proven correct.
Prolog programs
• Prologprograms:successionofpredicatedeclarations • Noordertofollow
• Fromaprogram,youcanaskquestions
* Eg: brother (paul, X). To find paul’s brothers.
* That is, determine the values of the variables (X) such that the question is deductible from the facts and predicates of the program.
• Wearetalkingaboutproblemsolvingorfrom problem demonstration.
2021-02-04
Resolution
• Prolog execution is based on the Resolution proof method.
• Resolution is a technique of producing a new clause by resolving two clauses that contain a complimentary literal and Resolution produces proof by contradiction.
Unification
• Example:
* brother (X, Y): – man (X), child (X, Z), child (Y, Z), X \ = Y. where \ = represents the difference predicate.
* brother (paul, Who) : attempt to unify with the head of the clause brother (X, Y)
• Definition:processbywhichwetrytomaketwoformulas identical by giving values to the variables they contain.
• Asloknownasmatching
2021-02-04
Unification
• Definition:processbywhichwetrytomaketwoformulas identical by giving values to the variables they contain.
1. Thepredicatenamemuchmatch.
*Sofoo(X,X) canmatchfoo(2,3),butcannevermatch
2. Oncethepredicatesnamesthearityofthe predicatesmuch match (number of terms).
3. Ifthepredicatenamesandaritiesmatchtheneach ofthek- termsmuchmatch.Soforfoo(t1,t2,t3)to matchfoo(s1, s2,s3)wemusthavethatt1matches s1,t2matchess2, and t3 matches t3.
2021-02-04
Unification
• Result:itisaunifying(orsubstitutionormatching),asetof variable assignments.
* Example: {X = paul, Qui = Y}
• Theresultisnotnecessarilyunique,butrepresentsthemost
general unifier.
• Unificationcansucceedorfail.
* e (X, X) and e (2,3) cannot be unified.
Unification
flies (X): – bird (X). bird (duck).
? – flies (duck) ? – bird (duck)
2021-02-04
Unification
• Unificationpredicate:”=”
* a (B, C) = a (2,3). gives the result:
YES {B = 2, C = 3}
* a (X, Y, L) = a (Y, 2, carole). gives for result :
YES {X = 2, Y = 2, L = carole}
a (X, X, Y) = a (Y, u, v). gives the result:
2021-02-04
Demonstration steps
• Iftheunificationfails:failuresituationontherule considered to demonstrate the formula.
• Iftheunificationsucceeds:substitutionofthevariables present in the tail of the clause by the corresponding values of the variables of the unifier.
2021-02-04
Demonstration steps
• Demonstrationofthissetofformulasintheorderof their quotation to enrich the system with the
values obtained from the variables.
• Attheend,thesetofvalue-variablepairsofthe variables present in the initial question forms the solution displayed by Prolog.
2021-02-04
% of facts in Prolog man (john).
man (peter). man (marc). wife(mary). woman (louise).
% questioning the facts ? – man (john). Yes
? – man (mary). No
? – man (simon). No
? – man (M). M = john; M = peter; M = marc; No
% parent predicate / 2: parent(john, peter). parent(peter, marc). parent(peter, louise). parent(mary, marc). parent(mary, louise).
% Peter’s children? ? – parent(peter, C).
C = marc; C = louise; No
% Louise’s parents? ? – parent (P, louise). P = peter;
% Does John have children? ? – parent (john, _).
% Does Marc have children? ? – parent (marc, _).
% define a Prolog rule hasChildren (P): – parent (P, _).
? – hasChildren (peter). Yes
? – hasChildren (marc). No
Search Trees
• Searchtreesrepresentqueries
– Root of the tree is the question
– Nodes (or vertices) are decisions and show which goals still need to be satisfied
– Transitions (along edges) from one node to the next are the result of an unification between a goal and a fact or the head of a rule.
– The edges are a step in the proof (unifications).
Nodes in Search Tree
– Goals are ordered from left to right following the order in the rules. Goals are stated in a node.
– Leaf nodes which contain one or several goals are failure nodes. The first (left-most) goal caused the failure.
– Empty leaf nodes are success nodes. The path from the root to the leaf node contains the unifications and steps necessary for the proof. These can be found on the edges.
Solution Strategy of Prolog
• Prologbuildsthesearchtreefromthequestionasaroot node. The tree is built in a depth-first fashion.
• Anempty(leaf)nodeisaprooforasolution
– Search can continue for other solutions by backtracking and traversing unexplored branches
• Annon-emptyleafnodeisafailure
– A solution may still be found by backtracking and traversing unexplored branches
Backtracking
• Iftherearenomorenewnodesfound,thereareno more solutions and Prolog answers no.
• Terminationisnotguaranteed.Itiseasytowriterules that cause an infinite recursion.
• Theorderinwhichsolutionsareproduceddependson the order in predicates, in particular:
– the order of the literals in the body of clause – the order of the predicates
A first Example
voter(Y) Y=X
name(X), citizen(X), adult(X)
name(joe).
name(jane).
citizen(jane).
citizen(joe).
adult(jane).
voter(X):-
name(X), citizen(X), adult(X).
?- voter(Y).
X=joe citizen(joe), adult(joe)
X=jane citizen(jane), adult(jane)
adult(jane)
adult(joe)
Another Example
k (X): – f (X), g (X), h (X).
? – k (Y).
Another Example
f(a). f(b).
g(a). g(b).
k(X) :- f(X),g(X),h(X).
http://cs.union.edu/~striegnk/learn-prolog-now/html/node20.html#sec.l2.proofsearch
Another Example
[trace] 2 ?- k(X).
Call: (6) k(_G348) ? Call: (7) f(_G348) ? Exit: (7) f(a) ? Call: (7) g(a) ? Exit: (7) g(a) ? Call: (7) h(a) ? Fail: (7) h(a) ? Fail: (7) g(a) ? Redo: (7) f(_G348) ?
Exit: (7) f(b) ? Call: (7) g(b) ?
Yes notrace.
(7) g(b) ? (7) h(b) ? (7) h(b) ? (6) k(b) ?
http://cs.union.edu/~striegnk/learn-prolog-now/html/node22.html#sec.l2.praxis
Another Example
Building categories:
parent(building,farmbuilding). parent(farmbuilding,barn). parent(farmbuilding,silo). parent(farmbuilding,house). parent(barn,horsebarn). parent(barn,cowbarn).
typeof(X,Y):- parent(Z,X),typeof(Z,Y). typeof(X,Y):- parent(Y,X).
?- typeof(cowbarn,A).
parent(_Z,barn),typeof(_Z,A)
X=cowbarn, Y=A
X=cowbarn,
typeof(cowbarn, A)
parent(Z,cowbarn),typeof(Z,A)
parent(A, cowbarn)
typeof(barn,A)
_X=barn, _Y = A
_Z=farmbuilding
X=farmbuidling,
Z=building
X=building,
parent(A, barn)
A = farmbuilding
typeof(farmbuilding,A)
X=farmbuilding,
A = building
parent( Z,farmbuilding),typeof( Z,A)
parent(A, farmbuilding)
typeof(building,A)
X=building, Y = A
parent(A, building)
parent( Z,building),typeof( Z,A)
Another Example: 3 Versions of
French Nobleman
father(charles,jean). noble(henri). noble(louis). noble(charles). noble(X):- father(Y,X),
father(charles,jean). noble(X):- father(Y,X),
noble(henri).
noble(louis).
noble(charles).
?- noble(jean).
father(charles,jean). noble(henri). noble(louis). noble(charles). noble(X):- noble(Y),
father(Y,X).
Source: R. Laganière
A Last Example
likes(peter,jane).
likes(paul,jane).
conflict(X,Y) :- likes(X,Z),likes(Y,Z).
?- conflict(X,Y).
• Howmanysolutions?…4
http://cs.union.edu/~striegnk/learn-prolog-now/html/node20.html#sec.l2.proofsearch
• Predicatecalculus – Predicates
– Horn clauses
– Resolution • SearchTrees
– Backtracking
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com