WIXLIB

CSNB234 Artificial IntelligenceProlog ProgrammingLAB 3: Syntax and SemanticsContents1.2.3.4.Simple data objects (atoms, numbers, variables) and Structured objectsMatching / Unification.Declarative and Procedural meaning of a Program.Lists – unification and searching.1. Data Objects: Constants, Variables, StructuresData objects in Prolog can be classified as follows:Constants Variables They name specific things or predicates.2 types:oAtoms: (likes, a, , --,'Stuf', married man)oNumbersThese are not atomso314a5 (cannot start with a number),ogeorge-smith( cannot contain a hyphen)ooGeorge (cannot start with a capital letter)something (cannot start with underscore)Written in uppercase or starting with uppercase or underscoreExamples: X, Input, something, (anonymous variable)Anonymous variables need not have consistent interpretations (they need not bebound to the same value):?- likes( , john).%does anybody like John?- likes( , ).%does anybody like anybody?-1-

Structures Used to organize the data.Structured objects (or simply structures) are objects that have several components.The components themselves can, in turn, be structuresA structure is specified by its functor (name) and its components.All structured objects can be pictured as trees (see below). The root of the tree is thefunctor, and the offsprings of the root are the components.If a component is also a structure, then it is a subtree of the tree that corresponds tothe whole structured object.Example 1.Date (as a tree)Date (in prolog)example:1. owns(john, book(wuthering heights, bronte)).2. book(wuthering heights, author(emily, bronte)).?- owns(john, book(X, author(Y, bronte))).%does John own a book (X) by Bronte (Y, bronte)?2. Arithmetic Operators Some of the predefined operators : (addition), - (subtraction), * (multiplication), / (division), ** (power),// (integer division), mod (modulo, the remainder of integer division). The following queries demonstrates the use of and is :Query?- X 1 2.AnswerX 1 2?- X is 1 2.X 3CommentsWhy not X 3?The expression 1 2 denotes a Prolog term where is the functor and 1 and 2 are its arguments.There is nothing in the above goal to force Prolog toactually activate the addition operation.The addition was carried out by a special procedurethat is associated with the operator is. We call suchprocedures built-in procedures.?- X is 5/2, Y is 5//2, X 2.5Z is 5 mod 2.Y 2Z 1 Parentheses can be used to indicate different associations.Evaluation is carried out from left to right without parenthesesQuery?- X is 5-2*2.?- X is (5-2)*2AnswerX 1X 6Comments2*2 is evaluated, followed by 5-55-2 is evaluated, followed by 3*2-2-

Arithmetic is also involved when comparing numerical values.Query?- 277*3 10000.?- 277*38 10000. AnswernoyesComments* is evaluated followed by “Suppose that we have in the program a relation born that relates the names of people with their birth years.Then we can retrieve the names of people born between 1980 and 1990 inclusive with the followingquestion:?born(Name,Year),Year 1980,Year 1990.whereRelationsX YX YX YX YX : YX\ YMeaningX is greater than YX is less than YX is greater than or equal to YX is less than or equal to YX and Y are equal XX and Y are not equalExamples:Query?- 1 2 : 2 1.?- 1 2 2 1.?- 1 A B 2.AAnswerYesNoA 2, B 13. Declarative and Procedural meaning of Prolog programs Prolog programs can be understood in two ways: declaratively procedurally. Consider a clause P:- Q,R.where P, Q and R have the syntax of terms. Comparison between declarative and proceduralDeclarative P is true if Q and R are true. From Q and R follows P. determines whether a given goal is true, and if so, for what values of variables it istrue. -3-ProceduralTo solve problem P, first solve the subproblem Qand then the subproblem R.To satisfy P, first satisfy Q and then R.define the logical relations between the head of theclause and the goals in the body.determine the order in which the goals areprocessed.

Uses the concept of instance of a clause. An instance of a clause C is the clauseC with each of its variablessubstituted by some term. A variant of a clause C is such aninstance of the clause C where eachvariable is substituted by anothervariable. For example, consider the clause hasachild( X) :- parent( X, Y). Two variants of this clause are: hasachild( A) :- parent( A, B). hasachild( Xl) :- parent( Xl, X2). Example instances of this clause are: hasachild(peter):-parent(peter, Z). hasachild(barry) :- parent(barry,small(caroline) ).Specifies how Prolog answers questions. To answer a question means to try to satisfya list of goals. They can be satisfied if the variables thatoccur in the goals can be instantiated in sucha way that the goals logically follow fromthe program.A procedure for executing a list of goals withrespect to a given program.To 'execute goals' means: try to satisfy them.4. Matching/Unification Two terms unify if they are the same term or if they contain variables that can be uniformly instantiated with terms in such a way that theresulting terms are equal. This means that: mia and mia unify 42 and 42 unify woman(mia) and woman(mia) unify This also means that: vincent and mia do not unify woman(mia) and woman(jody) do not unify?- mia mia.Yes This tells us that two constants unify if and only if they are exactly the same object. As mia and mia arethe same atom, unification succeeds.?- 2 2.Yes?- mia vincent.no 2 is the same number as 2 , and as mia is not the same atom as vincent , Prolog responds yes to the firstquery and no to the second.? - X mia, X vincent.no Prolog will respond no. This query involves two goals, X mia and X vincent . Taken separately, Prolog would succeed at both of them, instantiating X to mia in the first case andto vincent in the second.-4-

A n d that’s exactly the problem here: once Prolog has worked through the first goal, X isinstantiated to (and therefore equal to) mia , so that it simply can’t unify with vincent anymore.H e n c e the second goal fails. An instantiated variable isn’t really a variable anymore: it has becomewhat it was instantiated with. 5. Lists Lists is one of the simplest and most useful structures in Prolog, widely used in non-numeric programming. List are also trees and can can be empty []. Examples:1. [ a, b, c, d] is a list2. [Head Tail ] where Head is a and Tail is a list [b, c, d]3. Hobbies1 [ tennis, music]Hobbies2 [ skiing, food]L [ann, [tennis, music], tom, [skiing, food]]4. L [a, b, c]Tail [b, c]L [a, Tail] Operations on list Check if an object is an element of a listmember[X, L] where X is an object and L is a list eg: member( b, [a,b,c])sublist( [c,d], [a,b,c,d,e,f ]) checks if a list is part of another list. Gives true or false. Join 2 listsconc[L1, L2, L3] where L1 and L2 are joint to be L3. Eg: conc([a, b], [c, d], R ) Add or delete an object to a listadd( X, L, [X L] ) , del( X, L, Ll) Permutation?- permutation( [a,b,c], P). permute [a, b, c] and put in P. Example usage of list. Lets say we have a list[sofa, tv, radio, table, chair, bed, mirror]. We can represent the locations of things. Rather than having separate location predicates for each thing, we can have one location predicateper container, with a list of things in the container.A list is a sequence of any number of items, such as ann, tennis, tom, skiing. Such a list can be written inProlog as:[ ann, tennis, tom, skiing]First item if list is the head. The rests form the tail. Example: [ann] is the head and [tennis, tom, skiing] isthe tail. The head can be anything but the tail has to be a list.list where([sofa, tv], livingroom). list where([table,chair],kitchen).list where([bed, mirror], bedroom).list where([radio], everywhere). We can ask questions about lists to Prolog:?- [ , ,X] [lesson, work, sleeping].X sleeping?- list where(X, everywhere).X [radio]?- list where(X, livingroom).X [sofa, tv]-5-

6. List Unification[a,b,c] unifies with [Head Tail] resulting in Head a and Tail [b,c]?- [a,b,c] [Head Tail].Head aTail [b, c][a] unifies with [H T] resulting in H a and T []?- [a] [H T].H aT '[]'[a,b,c] unifies with [a T] resulting in T [b,c]?- [a,b,c] [a T].T [b, c][a,b,c] doesn't unify with [b T]?- [a,b,c] [b T].no[] doesn't unify with [H T]?- [] [H T].no[] unifies with []. Two empty lists always match?- [] [].yesLet’s consider the following fact.queries.?- p([a,b,c], X, Y).X aY [b, c]?- p([a], X, Y).X aY '[]'?- p([], X, Y).nop([H T], H, T). Let’s see what happens when we ask some simple7. List Searching We can use lists within facts and rules. In order to search a list, Prolog inspects the first item in a list and then goes on to repeat the same processon the rest of the list.One common way of using lists is to store information within a list and then subsequently search for thisinformation when we run our programs.-6-

This is done by using recursion. The search can either stop when we find a particular item at the start of the list or when we havesearched the whole list, in which case the list to be searched will be the empty list In order to do this, we have to be able to selectively pull the list apart. How to take the head and a tail of a list:[Head Tail]This method constitutes the basis of the searching method. We shall use it to pull apart a list, looking atthe first item each time, recursively looking at the tail, until we reach the empty list [], when we will stop.Example: Consider the following problem. How can I see if a particular item is on a particular list?For example I want to test to see if item apples is on the list[pears, tomatoes, apples, grapes]. One possible method of doing this is by going through the list, an item at a time, to see if wecan find the item we are looking for. The way we do this in Prolog is to say that we could definitely prove an item was on a list if weknew that the target item was the first one on the list. ie.on(Item,[Item Rest]). /* is the target item the head of the list */ Otherwise we could prove something was on a list if we could prove that although it didn'tmatch the existing head of the list, it nonetheless would match another head of the list if wedisregarded the first item and just considered the rest of the list i.e.on(Item,[DisregardHead Tail]):on(Item,Tail). We now have a program consisting of a fact a nd a rule for testing if something is on a rule. Torecap, it sees if something is the first item in the list. If it is we succeed. If it is not, then we throw awaythe first item in the list and look at the rest.on(Item,[Item Rest]).% base case, if the list is nilon(Item,[DisregardHead Tail]):on(Item,Tail).% recursive call Suppose we pose the query:?- on(apples, [pears, tomatoes, apples, grapes]).yes The first clause of on requires the first argument of on to match with the list head. Howeverapples and pears do not match. Thus we must move on to the second clause. This splits the list upas follows:DisregardHead pearsTail [tomatoes,apples,grapes] This now gives us the following goal in the body of our rule:on(apples, [tomatoes, apples, grapes]). Again, we see if apples and tomatoes match using our initial facts. Since they don't, we again use our secondclause to strip off the current list head, giving us the new goal.on(apples,[apples, grapes]). Since apples matches apples, our first clause succeeds as does our query.-7-

CSNB234 Artificial Intelligence Prolog Programming LAB 3: Syntax and Semantics Contents 1. Simple data objects (atoms, numbers, variables) and Structured objects 2. Matching / Unification. 3. Declarative and Procedural meaning of a Program. 4. Lists – unification and sea