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.
Announcement
•Office hours for comprehensive assignment(assignment 1)
• 5 | more office hours • check brightSpace for
information
• Assignment 1 – late
submission ends Feb 9th
Announcement
• Quiz 1 is due Thursday Feb 3rd • Quiz 2 is posted due next
Thursday Feb 10th
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
• SWI Prolog
• Swish Online interpereter
• Prolog Programming
• Learn Prolog Now!
Logic Programming in Prolog
• LogicProgramming • Prolog
– facts and rules
– atoms and variables • Queries
– Variable instantiation – Unification
• FirstExamples
Prolog History
• Paradigm:declarative,logicprogramming
• 1972:A.ColmerauerandP.Roussel,Marseille,created the language
– Envisioned application was natural language processing
• 1977:FirstcompilerbyD.H.Warren,Edinburgh
• 1980:BorlandTurboProlog
• 1995:ISOProlog
Applications
• Applications of declarative, logic programming: – symbolic computation (i.e. non-numeric)
• Symbolic computation applications include:
– Many areas of artificial intelligence (property of declarative)
– Understanding natural language (specific to logic programming)
– Relational databases
– Mathematical logic
– Abstract problem solving
– Design automation
– Symbolic equation solving
– Biochemical structure analysis
Programming in is descriptive (as opposed to prescriptive)
• descriptive:describingknownfactsandrelationships(or
rules) about a
– specific problem
• as opposed to
– prescriptive: prescribing the sequence of steps taken by a computer to solve a specific problem
Programming Steps in Prolog
• SpecifyFacts
– which are true in a problem domain. Will remain true forever.
• Definerules
– which when applied establish new facts.
• Startqueries
– and the prolog interpreter answers
• Prologusesfirstorderlogictoproveanswers
– It answers Yes following a successfully proven
– It answers No otherwise
• A no answer means it could not prove a positive answer
First Order Logic
• Consistsof
– predicate symbols
– equality
– negation
– logic binary connections
– quantifiers ‘for all …’ and ‘there exists … such that’
• Moreonthislater…
Computation in Prolog
Specified by
• partlybythelogicaldeclarativesemanticsofProlog (more on this later),
• partlybywhatnewfactsPrologcaninferfromthegiven ones, and
• partlybyexplicitcontrolinformationsuppliedbythe programmer.
– In other words Prolog has/requires some imperative, or prescriptive features.
Example: “Dogs like cats” with individuals “dogs”, “cats” and relationship “like”
In Prolog: like(dogs,cats).
• lowercaseforbothindividualsandrelationships
• relationship(orpredicate)iswrittenfirst
• individuals(orarguments)arewritteninparenthesis, separated by commas
• endswithadot“.”
• orderofargumentsisimportantbutitisuptousto define, in this case “liker” is first, “liked” is second, i.e., like(cats,dogs). is a different fact.
More facts
Other examples:
domestic(cows). faster(horses,cows). take(cats,milk,cows). isYellow(hay). eat(cows,hay).
% cows are domestic animals. % horses run faster than cows % cats take milk from cows
% hay is yellow.
% Cows eat hay.
– Example: cows, horses, hay, cats, milk
• ConstantsorAtoms
– Symbolic: small caps letter followed by letters and numbers
– Numbers : integer and float
Interpretation of Facts
Is “cats” an individual?
Yes, but there is more than one way to interpret it.
• aparticulartypeofcat,e.g.,housecats
• afamilyofanimalsencompassingtigers,leopards,etc.
Either interpretation is fine. The program context will need to define which one is meant.
• Ifaprogramneedsmorethanoneinterpretationthen the names of the individuals have to be different, e.g.,
– houseCats and catsFamily
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)
Queries or Questions
Questions are about individuals and their relationships
Example: ?-eat(cats,mice).
• Means”Docatseatmice?”or”Isitafactthatcatseat
• Noteasbefore,catsareinterpretedasaspecificspecies (house cats) and mice are all type of mice.
• Notethatthesyntaxisthesameasforfacts,exceptfor the special symbol ?- (printed by the interpreter) to
distinguish from a fact.
A Database
like(horses,fish).
like(dogs,cats).
like(cats,mice).
like(dogs,mice).
like(horses,racing).
like(cats,horses).
like(tigers,cats).
like(cats,hay).
like(cows,grass).
like(cows,hay).
like(horses,hay).
Simple Queries
?- like(dogs,bones).
?- like(cats,dogs).
?- like(cats,hay).
?- enjoy(horses,racing).
More interesting questions of the type: “Do cats like X?”
– We want Prolog to tell us what X could stand for.
– Prolog searches through all the facts to find things cats like.
• In Prolog ?- like(cats,X).
– Variables start with uppercase letters.
How Prolog Answers
• WhenPrologisfirstaskedthisquestion,variableXis initially not instantiated.
• Prologsearchesthroughthedatabase,lookingforafact that unifies with the question (or query or goal).
• If there is an uninstantiated variable as argument, Prolog searches for any fact where the predicate is “like” and the first argument is “cats”.
• Whensuchafactisfound,Xbecomesinstantiatedwith the second argument of the fact.
• Prologsearchesthefactsinorder(toptobottom).
• Xisfirstinstantiatedto“mice”.
• Prologmarkstheplaceinthedatabasewherethe unifier is found.
Multiple Answers
• Whenentering;weaskPrologtore-satisfythegoal – or to search for another solution
• Prologresumesitssearch,startingfromwhereitleft the place-marker.
• WeareaskingPrologtore-satisfythequestion,and resume search with X uninstantiated again.
• Aftera;falsemeans“nomoreanswers”
Conjunctions
“Do cats and dogs like each other?”
?- like(cats,dogs), like(dogs,cats).
• , represents “and”
• canhaveanynumberofquestionsseparatedby, (comma) and ending with . (dot)
Example with Variables
“Is there anything that horses and cows both like?” 2 steps:
1. Find out if there is some X that cows like. 2. Then find out if horses like whatever X is.
?- like(cows,X), like(horses,X).
• After finding the first answer for X (hay), Prolog marks the place in the database.
• Prolog attempts to satisfy the second goal (with X instantiated).
• If it succeeds, Prolog marks (separately) that goal’s place in the database.
• Each goal keeps its own place-marker.
• Aruleisageneralstatementaboutobjectsandtheir relationships.
– “Horses like any type of animal who likes hay.” or, in other words
– “Horses like X if X like hay.”
likes(horses,X) :- like(X,hay).
• APrologrulehasaheadandbody,separatedby”:-” pronounced “if”.
• Theheadisontheleft;thebodyisontheright.
• Aruleendsin”.”
• Theheadoftheruledescribeswhatfacttheruleis intended to define.
• Thebodycanbeaconjunctionofgoals. – “Horses like X if X like hay and mice.”
like(horses,X) :- like(X,hay), like(X,mice).
• Thereare3occurrencesofX. WheneverXbecomes instantiated, all X’s are instantiated to the same thing.
• LogicProgramming • Prolog
– facts and rules
– atoms and variables • Queries
– Variable instantiation – Unification
• FirstExamples
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com