Prolog TypesProlog Typesldots Prolog NumbersProlog Arithmetic ExpressionsProlog AtomsProlog VariablesProlog Variablesldots Prolog ProgramsProlog Programsldots Standard predicatesStandard predicatesldots Unification/MatchingBacktrackingBacktrackingldots Maaori Family RelationshipsMaaori Terms of AddressMaaori Terms of Addressldots Maaori Terms of Addressldots The WhanauThe Whanauldots The Whanauldots The Whanau Program --- Database FactsThe Whanau Program --- Database Factsldots Whanau --- Auxiliary predicatesWhanau --- Family RelationshipsWhanau --- Family Relationshipsldots Whanau --- Family Relationshipsldots The Whanau Program --- CallsThe Whanau Program --- Callsldots Readings and References520 —Spring 2008 — 42CSc 520Principles of ProgrammingLanguages42 : Logic Programming — Prolog BasicChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2008 Christian Collberg[1]520 —Spring 2008 — 42Prolog TypesThe term is Prolog’s basic data structure.Everything is expressed in the form of a term. Thisincludes programs and data.Prolog has four basic types of terms:1.variables start with an uppercase letter;2.compound terms are lists, strings, and structures;3.atoms start with a lower-case letter;4.numbers.[2]520 —Spring 2008 — 42Prolog Types...’Hello’termvaratomnumberXYZHelloatomicnonvarcompound13456.78f(x)[1,2,3]point(x,y)"hello"a bhello[3]520 —Spring 2008 — 42Prolog NumbersMost Prolog implementations support infinite precisionintegers.This is not true of GNU Prolog!The built-in operator is evaluates arithmeticexpressions:| ?- X is 6*7.X = 42| ?- X is 6.0*7.0.X = 42.0| ?- X is 60000000000000*7000000000000000.X = 1[4]520 —Spring 2008 — 42Prolog Arithmetic ExpressionsAn infix expression is just shorthand for a structure:| ?- X = +(1,*(2,3)).X = 1+2*3| ?- X = 1+2*3.X = 1+2*3| ?- X is +(1,*(2,3)).X = 7| ?- X is 1+2*3.X = 7X = 1*2 means “make the variable X and 1*2 thesame”. It looks like an assignment, but it’s what we callunification. More about that later.[5]520 —Spring 2008 — 42Prolog AtomsAtoms are similar to enums in C.Atoms start with a lower-case letter and can containletters, digits, and underscore ( ).| ?- X = hello.X = hello| ?- X = hE l l o99.X = hE l l o99[6]520 —Spring 2008 — 42Prolog VariablesVariables start out uninstantiated, i.e. without a value.Uninstantiated variables are written number:| ?- write(X).16Once a Prolog variable has been instantiated (given avalue), it will keep that value.| ?- X=sally.X = sally| ?- X=sally, X=lisa.no[7]520 —Spring 2008 — 42Prolog Variables...When a program backtracks over a variableinstantiation, the variable again becomesuninstantiated.| ?- (X=sally; X=lisa), write(X), nl.sallyX = sally ? ;lisaX = lisa[8]520 —Spring 2008 — 42Prolog ProgramsA Prolog program consists of a database of facts andrules:likes(lisa,chocolate).likes(lisa,X) :- tastes like chocolate(X).:- is read if.:- is just an operator, like other Prolog operators. Thefollowing are equivalent:likes(lisa,X) :- boy(X),tastes like choc(X).:-(likes(lisa,X),(boy(X),tasteslike chok(X))).[9]520 —Spring 2008 — 42Prolog Programs...Prolog facts/rules can be overloaded, wrt their arity.You can have a both a rule foo() and a rule foo(X):| ?- [user].foo.foo(hello).foo(bar,world).foo(X,Y,Z) :-Z is X + Y.<ctrl-D>| ?- foo.yes| ?- foo(X).X = hello| ?- foo(X,Y).X = barY = world| ?- foo(1,2,Z).Z = 3[10]520 —Spring 2008 — 42Standard predicatesread(X) and write(X) read and write Prolog terms.nl prints a newline character.| ?- write(hello),nl.hello| ?- read(X), write(X), nl.hello.hello[11]520 —Spring 2008 — 42Standard predicates...write can write arbitrary Prolog terms:| ?- write(hello(world)),nl.hello(world)Note that read(X) requires the input to be syntacticallycorrect and to end with a period.| ?- read(X).foo).uncaught exception: error[12]520 —Spring 2008 — 42Unification/MatchingThe =-operator tries to make its left and right-handsides the same.This is called unification or matching.If Prolog can’t make X and Y the same in X = Y,matching will fail.| ?- X=lisa, Y=sally, X = Y.no| ?- X=lisa, Y=lisa, Z = X, Z = Y.X = lisaY = lisaZ = lisaWe will talk about this much more later.[13]520 —Spring 2008 — 42BacktrackingProlog will try every possible way to satisfy a query.Prolog explores the search space by usingbacktracking, which means undoing previouscomputations, and exploring a different search path.[14]520 —Spring 2008 — 42Backtracking...Here’s an example:| ?- [user].girl(sally).girl(lisa).pretty(lisa).blonde(sally).| ?- girl(X),pretty(X).X = lisa| ?- girl(X),pretty(X),blonde(X).no| ?- (X=lisa; X=sally), pretty(X).X = lisaWe will talk about this much more later.[15]520 —Spring 2008 — 42M¯aori Family RelationshipsJohn Foster (in He Whakamaarama – A New Course inM¯aori) writes:Relationship is very important to the M¯aori. Socialseniority is claimed by those able to trace theirwhakapapa or genealogy in the most direct way toillustrious ancestors. Rights to shares in land andentitlement to speak on the marae may also dependon relationship. Because of this, there are specialwords to indicate elder or younger relations, orsenior or younger branches of a family.M¯aori is the indigenous language spoken in NewZealand. It is a polynesian language, and closelyrelated to the language spoken in Hawaii.[16]520 —Spring 2008 — 42M¯aori Terms of AddressM¯aori Englishau Itipuna, tupuna grandfather, grandmother, grandparent, ancestortiipuna grandparentsmatua taane fathermaatua parentspaapaa fatherwhaea, maamaa motherwhaea kee auntkuia grandmother, old ladytuakana older brother of a man, older sister of a womanteina younger brother of a man, younger sister of a woman[17]520 —Spring 2008 — 42M¯aori Terms of Address...M¯aori Englishtungaane woman’s brother (older or younger)tuahine man’s sister (older or younger)kaumaatua elder (male)mokopuna grandchild (male or female)iraamutu niece, nephewtaane husband, manhunaonga daughter-in-law, son-in-lawtamaahine daughtertama sontamaiti child (male or female)tamariki childrenwahine wife, womanmaataamua oldest child[18]520 —Spring 2008 — 42M¯aori Terms of Address...M¯aori Englishpootiki youngest childkoroheke, koro, koroua old manwhaiapo boyfriend, girlfriendakootiro girltamaiti taane boywhanaunga relativesaLiterally: ”What you follow at night”[19]520 —Spring 2008 — 42The WhanauA program to translate between
View Full Document