WIXLIB

Conjunctii: intrebari mai complexeIConsideram urmatoarele fapte:likeslikeslikeslikesI( mary ,( mary ,( john ,( john ,food ) .wine ) .wine ) .mary ) .Si intrebarea:? l i k e s ( j o h n , mary ) , l i k e s ( mary , j o h n ) .

Conjunctii: intrebari mai complexeIConsideram urmatoarele fapte:likeslikeslikeslikesI( mary ,( mary ,( john ,( john ,food ) .wine ) .wine ) .mary ) .Si intrebarea:? l i k e s ( j o h n , mary ) , l i k e s ( mary , j o h n ) .Icitim “does john like mary and does mary like john?”

Conjunctii: intrebari mai complexeIConsideram urmatoarele fapte:likeslikeslikeslikesI( mary ,( mary ,( john ,( john ,food ) .wine ) .wine ) .mary ) .Si intrebarea:? l i k e s ( j o h n , mary ) , l i k e s ( mary , j o h n ) .IIcitim “does john like mary and does mary like john?”Prolog va raspunde false : cauta pentru fiecare goal (toategoal-urile trebuie sa fie satisfacute, iar daca nu, atunci nu vareusi, deci raspunsul va fi false ).

Conjunctii: intrebari mai complexeILa intrebarea:? l i k e s ( mary , X ) , l i k e s ( j o h n , X ) .

Conjunctii: intrebari mai complexeILa intrebarea:? l i k e s ( mary , X ) , l i k e s ( j o h n , X ) .IProlog: incearca sa satisfaca prima conditie (daca e satisfacuta,atunci marcheaza valoarea), apoi incearca sa satisfaca a douaconditie (daca e satisfacuta, atunci marcheaza valoarea).

Conjunctii: intrebari mai complexeILa intrebarea:? l i k e s ( mary , X ) , l i k e s ( j o h n , X ) .IIProlog: incearca sa satisfaca prima conditie (daca e satisfacuta,atunci marcheaza valoarea), apoi incearca sa satisfaca a douaconditie (daca e satisfacuta, atunci marcheaza valoarea).Daca intr-un punct esueaza, atunci se intoarce la ultimavaloare marcata si incearca alternative.

Exemple: conjunctiii, backtrackingModul in care Prolog calculeaza raspunsul la intrebarea urmatoareeste reprezentat astfel:I In Figura 1, prima conditie e satisfacuta, Prolog urmeaza sagaseasca o potrivire pentru a doua conditie (cu variabilainstantiata).I Daca esueaza sa gaseasca in baza de cunostinte o potrivireatunci incepe procesul de backtracking, in Figura 2.I Noua alternativa incercata reuseste pentru ambele conditii,vezi Figura 3.

Figure: Esecul pentru a doua conditie cauzeaza backtracking.

Figure: Success cu o alternativa instantiata.

ReguliI“John likes all people” se poate reprezenta:

ReguliI“John likes all people” se poate reprezenta:likeslikeslikeslikes.dar doar atat?!!!( john( john( john( john,,,,alfred ).bertrand ).charles ).david ) .

ReguliI“John likes all people” se poate reprezenta:likeslikeslikeslikes.( john( john( john( john,,,,alfred ).bertrand ).charles ).david ) .dar doar atat?!!!l i k e s ( john , X ) .dar ar trebui sa fie doar pentru oameni!!!

ReguliI“John likes all people” se poate reprezenta:likeslikeslikeslikes.( john( john( john( john,,,,alfred ).bertrand ).charles ).david ) .dar doar atat?!!!l i k e s ( john , X ) .dar ar trebui sa fie doar pentru oameni!!!IIntroducem reguli: “John likes any object, but only that whichis a person” este o regula despre ceva (cineva) pe care Johnplace.

ReguliI“John likes all people” se poate reprezenta:likeslikeslikeslikes.( john( john( john( john,,,,alfred ).bertrand ).charles ).david ) .dar doar atat?!!!l i k e s ( john , X ) .dar ar trebui sa fie doar pentru oameni!!!IIntroducem reguli: “John likes any object, but only that whichis a person” este o regula despre ceva (cineva) pe care Johnplace.IRegulile exprima: un fapt depinde de alt fapt.

Reguli ca definitiiIIRegulile pot fi folosite pentru a exprima “definitii”.Exemplu:“X is a bird if X is an animal and X has feathers.”IExemplu:“X is a sister of Y if X is female and X and Y have the sameparents.”IAtentie! Notiunea de “definitie” aici nu e aceeasi cu notiuneade definitie din logica:IIIIasemenea definitii permit detectarea predicatelor in capul uneireguli,dar pot fi si alte modalitati (ex. alte reguli cu acelasi cap)pentru a detecta asemenea predicate,pentru a avea o definitie completa ar trebui sa avem “iff” inloc de “if”.Regulile sunt afirmatii generale despre obiecte si relatiile dintreele (in general variabilele apar in reguli, dar nu intotdeauna).

Reguli in PrologIRegulile in Prolog au head si body.ICorpul (the body) unei reguli descrie conditiile ce trebuie safie satisfacute pentru ca head-ul sa fie true.IExemplu:l i k e s ( j o h n , X) : l i k e s (X , w i n e ) .l i k e s ( j o h n , X) : l i k e s (X , w i n e ) , l i k e s (X , f o o d ) .l i k e s ( j o h n , X) : f e m a l e (X ) , l i k e s (X , w i n e ) .IAtentie! Variabilele in reguli diferite sunt diferite.

Exemplu (royals)IBaza de cunoştinţe:male ( a l b e r t ) .male ( edward ) .female ( a l i c e ) .female ( v i c t o r i a ) .parents ( alice , albert ,p a r e n t s ( edward , a l b e r t ,s i s t e r o f (X , Y): f e m a l e (X ) ,p a r e n t s (X ,p a r e n t s (Y ,Ivictoria ).victoria ).M, F ) .M, F ) .Întrebări:? s i s t e r o f ( a l i c e , edward ) .? s i s t e r o f ( a l i c e , X ) .

Exerciţiu (thieves)ISe consideră următoarele:/ 1 / t h i e f ( j o h n ) ./ 2 / l i k e s ( mary , f o o d ) ./ 3 / l i k e s ( mary , w i n e ) ./ 4 / l i k e s ( j o h n , X): l i k e s (X , w i n e ) ./ 5 / m a y s t e a l (X , Y) : t h i e f (X ) , l i k e s (X , Y ) .IExplicaţi pentru ı̂ntrebarea următoare? m a y s t e a l ( j o h n , X ) .cum e executată ı̂n Prolog.

IIProlog programs are built from terms (written as strings ofcharacters).The following are terms:IIIconstants,variables,structures.

ConstantsIConstants are simple (basic) terms.IThey name specific things or predicates (no functions inProlog).Constants are of 2 types:IIIatoms,numbers: integers, rationals (with special libraries), reals(floating point representation).

Examples of atomsIatoms:IIIIIIIlikes ,a (lowercase letters), , ,’Void’ (anything between single quotes),george smith (constants may contain underscore),not atoms:IIII314a5 (cannot start with a number),george smith (cannot contain a hyphen),George (cannot start with a capital letter),something (cannot start with underscore).

VariablesIVariables are simple (basic) terms,Iwritten in uppercase or starting with underscore ,IExamples: X, Input, something,anonymous variable).IAnonymous variables need not have consistent interpretations(they need not be bound to the same value):(the last one called? l i k e s ( , j o h n ) . % d o e s anybody l i k e John ?% d o e s anybody l i k e anybody ? l i k e s ( , ) .

StructuresIStructure are compound terms, single objects consisting ofcollections of objects (terms),Ithey are used to organize the data.IA structure is specified by its functor (name) and itscomponentsowns ( john , book ( w u t h e r i n g h e i g h t s , b r o n t e ) ) .book ( w u t h e r i n g h e i g h t s , a u t h o r ( e m i l y , b r o n t e ) ) .? owns ( john , book (X , a u t h o r (Y , b r o n t e ) ) ) .% d o e s John own a book (X) by B r o n t e (Y , b r o n t e ) ?

Characters in PrologICharacters:IIIIIA-Za-z0-9 -*/\? @# & ˆ : .ICharacters are ASCII (printing) characters with codes greaterthan 32.IRemark: ’ ’ allows the use of any character.

Arithmetic operatorsIArithmetic operators:IIII , , ,/,I (x, (y , z)) is equivalent with x (y · z)IOperators do not cause evaluation in Prolog.IExample: 3 4 (structure) does not have the same meaningwith 7 (term).IX is 3 4 causes evaluation ( is represents the evaluator inProlog).IThe result of the evaluation is that X is assigned the value 7.

Parsing arithmetic expressionsITo parse an arithmetic expression you need to know:IThe position:IIIIIinfix: x y , x yprefix xpostfix x!Precedence: x y z ?Associativity: What is x y z? x (y z) or (x y ) z?

IEach operator has a precedence class:IIIIII / have higher precedence than 8/2/2 evaluates to:III1 - highest2 - lower.lowest8 (8/(2/2)) - right associative?or 2 ((8/2)/2) - left associative?Arithmetic operators are left associative.

The unification predicate ’ ’I - infix built-in predicate.? X Y .Prolog will try to match(unify) X and Y, and will answer trueif successful.IIn general, we try to unify 2 terms (which can be any ofconstants, variables, structures):? T1 T2 .IRemark on terminology: while in some Prolog sources theterm “matching” is used, note that in the (logic) literaturematching is used for the situation where one of the terms isground (i.e. contains no variables). What does isunification.

The unification procedureSummary of the unification procedure ? T1 T2:IIf T1 and T2 are identical constants, success (Prolog answerstrue);IIf T1 and T2 are uninstantiated variable, success (variablerenaming);IIf T1 is an uninstantiated variable and T2 is a constant or astructure, success, and T1 is instantiated with T2;IIf T1 and T2 are instantiated variables, then decide accordingto their value (they unify - if they have the same value,otherwise not);IIf T1 is a structure: f (X1 , X2 , ., Xn ) and T2 has the samefunctor (name): f (Y1 , Y2 , ., Yn ) and the same number ofarguments, then unify these arguments recursively (X1 Y1 ,X2 Y2 , etc.). If all the arguments unify, then the answer istrue, otherwise the answer is false (unification fails);IIn any other case, unification fails.

Occurs checkIConsider the following unification problem:? X f (X ) .

Occurs checkIConsider the following unification problem:? X f (X ) .IAnswer of Prolog:X f ( ).

Occurs checkIConsider the following unification problem:? X f (X ) .IAnswer of Prolog:X f ( ).X f (X ) .

Occurs checkIConsider the following unification problem:? X f (X ) .IAnswer of Prolog:X f ( ).X f (X ) .IIn fact this is due to the fact that according to the unificationprocedure, the result isX f(X) f(f(X)) . f ( f (.( f (X ).))) - an infiniteloop would be generated.

IUnification should fail in such situations.ITo avoid them, perform an occurs check: If T1 is a variableand T2 a structure, in an expression like T1 T2 make surethat T1 does not occur in T2.IOccurrence check is deactivated by default in most Prologimplementations (is computationally very expensive) - Prologtrades correctness for speed.A predicate complementary to unification:III\ succeeds only when fails,i.e. T1 \ T2 cannot be unified.

Built-in predicates for arithmeticIIProlog has built-in numbers.Built-in predicates on numbers include:XXXXXX Y,\ Y, Y, Y, Y, Y,with the expected behaviour.INote that variables have to be instantiated in most cases(with the exception of the first two above, where unification isperformed in the case of uninstantiation).

The arithmetic evaluator isIProlog also provides arithmetic operators (functions), e.g.: , , , /, mod, rem, abs, max, min, random, floor , ceilingetc, but these cannot be used directly for computation(2 3means 2 3, not 5) - expressions involving operators are notevaluated by default.IThe Prolog evaluator is has the form:X i s Expr .where X is an uninstantiated variable, and Expr is anarithmetic expression, where all variables must be instantiated(Prolog has no equation solver).

Example (with arithmetic(1))r e i g n s ( r h o n d r i , 844 , 8 7 8 ) .r e i g n s ( anarawd , 8 7 8 , 9 1 6 ) .r e i g n s ( hywel dda , 916 , 9 5 0 ) .r e i g n s ( l a g o a p i d w a l , 950 , 9 7 9 ) .r e i g n s ( h y w e l a p i e u a f , 979 , 9 8 5 ) .r e i g n s ( cadwallon , 985 , 9 8 6 ) .r e i g n s ( maredudd , 9 8 6 , 9 9 9 ) .p r i n c e (X , Y): r e i g n s (X , A , B ) ,Y A ,Y B .? p r i n c e ( c a d w a l l o n , 9 8 6 ) .true? p r i n c e (X , 9 7 9 ) .X lago ap idwal ;X hywel ap ieuaf

Example (with arithmetic(2))pop ( p l a c e 1pop ( p l a c e 2pop ( p l a c e 3pop ( p l a c e 4,,,,203).548).800).108).area ( place1 , 3) .area ( place2 , 1) .area ( place3 , 4) .area ( place4 , 3) .d e n s i t y (X , Y): pop (X , P ) ,a r e a (X , A ) ,Y i s P/A .? d e n s i t y ( p l a c e 3 , X ) .X 200true

IIn this lecture the following were discussed:IIIIIIIIIasserting facts about objects,asking questions about facts,using variables, scopes of variables,conjunctions,an introduction to backtracking (in examples),Prolog syntax: terms (constants, variables, structures),Arithmetic in Prolog,Unification procedure,Subtle point: occurs check.

IAll things SWIProlog can be found athttp://www.swi-prolog.org.IInstall SWI-Prolog and try out the examples in the lecture.IRead: Chapter 1 and Chapter 2 (including exercises section)of [Clocksin and Mellish, 2003].

Ben-Ari, M. (2001).Mathematical Logic for Computer Science.Springer Verlag, London, 2nd edition.Clocksin, W. F. and Mellish, C. S. (2003).Programming in Prolog.Springer, Berlin, 5th edition.Nilsson, U. and Maluszynski, J. (2000).Logic, Programming and Prolog.copyright Ulf Nilsson and Jan Maluszynski, 2nd edition.

Rezolvarea problemelor folosind Prolog I Programarea n Prolog: I n loc de a scrie secvent e de pa si pentru a rezolva o problem a, I se descriu fapte si relat ii cunoscute, apoi se pun ntreb ari. I Utilizare Prolog pentru a rezolva probleme care includobiecte sirelat ii ntre obiecte. I Exemple: I Obiecte: \John", \book", \jewel .