Backtracking , Structures,Non Deterministic Finite State Automata [Artificial Intelligence Programming in Visual Prologue] --Part II

Backtracking

As has already been seen prolog has built in backtracking mechanism. It tries to prove a goal with all possible instantiations. Automatic backtracking is a useful programming concept because it reveals the programmer of the burden of backtracking explicitly. However in some cases this feature degrades the efficiency of the program.

For example in cases where one solution is sufficient, backtracking to find all the solutions is not a good idea. Similarly, in case of mutually exclusive rules(clauses) when one rule has been proved then it is known in advance that no other rules can succeed. So this backtracking can be controlled by the use of ‘cut’, (“!”).

The disadvantage of using cut is that we tend to move away from the declarative nature of the prolog because when we have used the cut the order of the clauses may make difference in the result we get.

                

Consider the function. The relation between X and Y can be specified by the following three rules.

Rule 1: if X<3 then Y=0

Rule 2: if 3=<X <6 then Y=2

Rule 3: if 6<X then Y=4

This can be programmed as

PREDICATES

f(integer,integer)

CLAUSES

f(X,0):-

                X<3.

f(X,2):-

                3<=X,X<6.

               

f(X,4):-

                6<X.

               

GOAL

f(2,X).

Now modify the program using cut and observe the difference between the two modules. Comment on the difference.

Solution:

Backtracking happens here after the cut operator is added and due to this cut operator the goal returns only one value. Backtracking is like a Tree.

PREDICATES f(integer,integer) CLAUSES f(X,0):-             X<3. f(X,2):-             3<=X,X<6,!. f(X,4):-             6>X.             GOAL f(4,X).

Define the relation min(X,Y,Z) where Z returns the smaller of the two given numbers X and Y. Do it with and without the use of cut and comment on the result.

Ans: Here in this Question the cut operator is used which makes the backtracking stop if solution is found. If 2,3 are passed to the predicate then the compiler tries to find the solution. Backtracking is only effective after a solution is found.

PREDICATES min (Integer, Integer , Integer) Clauses min(X,Y,Y):-X>Y,!. min (X,Y,X):-Y>X. Goal min(2,3,Z). /**/

Structure revisited

            In prolog we can use structures to define data types of our requirement. For example if we want to use date as an structure we can define date as a structure in the domains section as follows

date=d(integer,symbol,integer)

We can then on use date as a data type to contain the date.

DOMAINS date=d(integer,symbol,integer) PREDICATES inquire display(symbol) date_of_birth(symbol,date) CLAUSES date_of_birth(ram,d(12,july,1983)). date_of_birth(shyam,d(15,august,1976)). date_of_birth(hari,d(26,may,1994)). date_of_birth(sita,d(29,september,1991)). display(X):-                 date_of_birth(X,Y),                 write(X),nl,                 write(Y). inquire:-                 write("Enter the name"),                 readln(X),                 display(X).           GOAL inquire.

Here the goal so proceeds as to ask a name from the user and to display the date of birth of the person with that name. With a little modification we can write goals which can find out persons with age below or above certain value, persons born in a month etc as in a relational database.

So the facts of the prolog can be thought of as a database. In fact we use structures to define certain relations and for all purposes of integrity this can be used similar to a table in a relational database. We call it the prolog’s internal database. We can update this database during the execution of the program by using the following keywords.

assert(C)   – this keyword can be used to assert a data in the facts base as

asserta(C) and assertz( C) can be used to control the position of insertion, the two asserts at the beginning and the end respectively.

retract( C) –deletes a clause that matches C.

An example

DOMAINS date=d(integer,symbol,integer) works=w(symbol,integer) FACTS person(symbol,symbol,date,works). PREDICATES start load_name evalans(integer) display search dispname(symbol) delete CLAUSES person(shyam,sharma,d(12,august,1976),w(ntv,18000)). person(ram,sharma,d(12,august,1976),w(ntv,18000)). person(ram,singh,d(13,may,2001),w(utl,12000)). start:-                 write("*************MENU**************"),nl,                 write("Press 1 to add new data"),nl,                 write("Press 2 to show existing data"),nl,                 write("Press 3 to search"),nl,                 write("Press 4 to delete"),nl,                 write("Press 0 to exit"),nl,                 write("*************MENU**************"),nl,                 readint(X),                 evalans(X). evalans(1):-                 load_name,                 start.                 evalans(2):-                 display,                 evalans(2). evalans(3):-                 search,                 evalans(3).                 evalans(4):-                 delete,                 evalans(4).                 evalans(0):-                 write("Thank You").                 delete. /* write clauses delete a fact from the facts base */ search. /*write  clauses to search a fact from the facts base */                 dispname(N):-                 person(N,C,d(D,M,Y),w(O,S)),                 write("Name:",N," ",C),nl,                 write("Date of Birth:",D,"th"," ",M," ",Y),nl,                 write("Organisation:",O),nl,                 write("Salary:",S),nl,nl.                 display:-                 retract(person(N,X,d(D,M,Y),w(O,S))),                 write("Name:",N," ",X),nl,                 write("Date of Birth:",D,"th"," ",M," ",Y),nl,                 write("Organisation:",O),nl,                 write("Salary:",S),nl,nl.                 load_name:-                 write("Enter the name \n"),                 readln(N),                 write("Enter the surname \n"),                 readln(S),                 write("Date of Birth \n Day:"),                 readint(D),nl,                 write("Month:"),                 readln(M),nl,                 write("Year:"),                 readint(Y),nl,                 write("Enter the organisation:"),                 readln(O),                 write("Enter the salary:"),                 readint(Sl),nl,nl,                 asserta(person(N,S,d(D,M,Y),w(O,Sl))).                                 GOAL start.

We may not use prolog to handle databases but the use of prologs internal database makes problem solving with prolog lot more easy.  

Assignment: Observe the above program. Add clauses for search and delete and extend your module as much as you like 3.

Simple application

Let us now see how the features of prolog can be used to simulate a non-deterministic automata which would have been a cumbersome task using other programming languages.

A nondeterministic finite automaton is an abstract machine that reads a string of symbols as input and decides whether to accept or to reject the input string. An automaton has a number of states and it is always in one of the states. The automata can change from one state to another upon encountering some input symbols. In a non deterministic automata the transitions can be non deterministic meaning that the transition may take place with a NULL character or the same character may result in different sitions

A non deterministic automaton decides which of the possible moves to execute, and it chooses a move that leads to the acceptance of the string if such a move is available.

Let us simulate the given automata.

 

DOMAINS Symb_list=symbol* PREDICATES Trans(symbol,symbol,symbol) Silent(symbol,symbol) Final(symbol) CLAUSES final(s3). trans(s1,a,s1). trans(s1,a,s2). trans(s1,b,s1). trans(s2,b,s3). trans(s3,b,s4). silent(s2,s4). silent(s3,s1). accepts(S,[]):-                 final(S). accepts(S,[H|T]):-                 trans(S,H,S1),                 accepts(S1,T). accepts(S,X):-                 silent(S,S1),                 accepts(S1,X). GOAL Accepts(S,[a,b]).

Check the automaton with various input strings and with various initial states. ( The initial state  need not necessarily be s1.) Observe the result and comment on how the simulation works.

            Use the following goals

• accepts(s1,[a,a,b]).
• accepts(s1,[a,b,b]).
• accepts(S,[b,a,b]).
• accepts(s1,[X,Y,Z]).
• accepts(s2,[b]).
• accepts(s1,[_,_,_,_|[a,b]]).

Artificial Intelligence (AI):Programming with VISUAL Prolog

PROLOG (for PROgramming in LOGic) is a very important tool in programming artificial intelligence applications and in the development of expert systems. It allows the programmer to model the logical relationships among objects and processes, complex problems are inherently easier to solve, and the resulting program is easier to maintain through its lifecycle. With Visual Prolog, applications such as customized knowledge bases, expert systems, natural language interfaces, and smart information management systems are easy to develop. Prolog is a declarative language. This means that given the necessary facts and rules, Prolog will use deductive reasoning to solve problems. This is in the contrast to traditional computer languages, such as C, BASIC and Pascal, which are procedural languages. We can also use prolog as any other programming languages in a procedural manner.

Prolog can be viewed as a tool to solve problems in the field of artificial intelligence or it can be very well used a general programming language.  

Prolog enforces the different problem solving paradigm complementary to traditional programming languages so it is believed that a student of computer should learn programming in prolog.

Data types in prolog

There are mainly three data types in prolog which are:

a)      Atoms and numbers

b)      Variables

c)      Structures

a) Atoms and numbers

Atoms can be constructed in three different ways

• Strings of letters, digits, and the underscore character starting with a lower case letter.    For example: man, ram, comp_students, pc_ct_063
• Strings of special characters.                                                                                               For example: < ----- >                                                                                                      Care should be taken not to use the character combination that may some built in meaning.
• Strings of characters enclosed in quotes.                                                                               For example: ‘Hari’    ‘Bird’ etc.                                                                                         Numbers used in prolog are integers and real numbers.     

b) Variables

Variables are strings of letters digits and underscore that start with an underscore or an uppercase letter. The scope of a variable is one clause only. So the same variable used in different clauses mean different thing.             

For example: X, Y, Hari, _load etc.        

Note here that Hari is a variable unlike the earlier use ‘Hari’ where it was a constant, an atom.

An underscore ‘_’ also known as anonymous variable is used in clauses when a variable need not be inferred to more than once.      

c) Structures

 Structures are objects that have different components. The components can be atoms or yet some other structures. A function is used to construct a structure as follows:

family (father, mother, children)

Here family is a structure that has father, mother and children as its elements. The father and mother may de atoms where the children may be yet another structure or a list of atoms. List is a special built in structure in prolog.

A list is a built in structure in prolog. It can be thought of sequence of elements ordered linearly however it is internally represented as a binary tree.

For example: [ albert, john, krish, willium ]

This representation is as follows:

The list as such can be broken down into two parts, the HEAD and the TAIL. The head is the first element of the list and tail is the remaining list. The above list can be broken down as:

[H|T]

Where H = albert

And T = [ john, krish, willium ]

List is one of the most useful structure in prolog.

Writing programs in prolog

All prolog programs start from the goal. It then uses the facts and clauses to break down the goal to sub-goals and tries to prove the sub-goals. A clause is said to have succeeded if there is a combination of facts and clause(s) that holds true.

Prolog has built in backtracking (it will be more clear in next lab) mechanism i. e. whenever three are multiple paths, it chooses one tries to prove it, and comes back to the choices whether the first one succeeds or fails.

Visual Prolog Program to find the bigger of the Two Numbers.

In this program, we have defined a predicate that gives us the larger of atwo given integers. The predicate bigger is defined in the PREDICATES section and the relation is defined in the CLAUSES section. It is customary to put together the predicate definition and clause definition for each predicate but it is not necessary. However, all the clauses for a predicate have to be written together. 

PREDICATES    bigger (integer, integer, integer) CLAUSES   bigger(X,Y,Z):-      X>Y,Z=X.  bigger(X,Y,Z):-      X<Y,Z=Y. GOAL  bigger (4,9,X).

Visual Prolog Program  to find hcf of numbers.

PREDICATES hcf(integer, integer, integer) CLAUSES   hcf(X, Y, X):-        Y mod X = 0.   hcf(X,Y,Z):-        S = Y mod X,S<>0, hcf(S, X, Z). GOAL   hcf(5,10,X).

Visual Prolog program combining facts and rules

Here the predicate mother is used to assert facts. There are four facts in that section. Similarly the predicate husband is used to assert more facts. The predicates son and father are used to define rules. We could have defined rules even with mother and husband but we bet that conciseness for program clarity at this stage.

PREDICATES husband(STRING,STRING) father(STRING,STRING) mother(STRING,STRING) son(STRING,STRING) CLAUSES mother("Kushalya","Ram"). mother("Kaikai","Bharat"). mother("Sumitra","Laxman"). mother("Sumitra","Satrughan"). husband("Dasrath","Kaushalya"). husband("Dasrath","Kaikai"). husband("Dasrath","Sumitra"). son(A,C):- mother(C,A). son(A,C):-husband(C,B), mother(B,A). father(A,B):- husband(A,C), mother(C,B). GOAL son(X, "Kaikai").

Visual Prolog Program to add the contents of an integer list.

Here in this program, the add function is made that adds the contents of list. The first segment ( i.e the Domains section ) defines or declares the space dynamically for integer list. Then the predicate add is defined that takes integer list and a Integer as arguments. The next clause section provides the necessary reasoning and facts to find the solution to the problem. Here the predicate add is called recursively until it gets the last element of the list which is the empty list itself and returns 0 if empty list is encountered. The add predicate else adds the first element to the solution repeatedly to find the solution.

DOMAINS int_list=Integer* PREDICATES             add(int_list, Integer) CLAUSES             add([],0).             add([H|T],Y):- add(T,Y1),Y=Y1+H.                                                 GOAL add([3,2,1,0],X).

                                                                      

Visual Prolog Program to find length of a list.

In this program the predicate length takes integer list and output a integer which is the length of list. Here the predicate length is called repeatedly or recursively until a last empty list is encountered and the 0 value is returned which is then continuously incremented to find the length.

DOMAINS int_list=Integer* PREDICATES length(int_list,integer) CLAUSES length([],0). length([H|T],L):-             length(T,L1),L=L1+1. GOAL length([1,2,3,4,5,6],X).

Visual Prolog Program to find the factorial of a number.

To find the factorial of a number in Visual Prolog, the number is decreased and the predicate “factorial” is continuously until a Zero is encountered when it returns a value 1. Then the predicate multiplies the returned value and the decremented number continuously. Thus, the factorial of a number is found. The visual prologue code to find the factorial of a number is given below:

PREDICATES             factorial(Integer,Integer) Clauses             factorial(0,1).             factorial(X,Y):-                                               X<>0,S=X-1,factorial(S,Y1),Y=X*Y1.                                                             Goal factorial(5,X).

Visual Prolog Program to append two list.

Here the two list are taken by the predicate “append” and returns the appended list. To append two list a list is broken continuously until the last empty list is encountered and finally the other list is appended or joined at the end of first recursively. The code to append is given as follows:

DOMAINS int_list=Integer * PREDICATES append(int_list,int_list,int_list) CLAUSES append([],X,Z):-             Z=X. append([H|T],X,Y):-             append(T,X,Z),Y=[H|Z]. GOAL append([1,2,3,4,5],[6,7,8,9],X).

Visual Prolog Program to delete a given element from the list.

To delete a element from a list the position and the element list is passed to the predicate delete. Then  the delete predicate continuously breaks the list into head (H) and Tail (T) to find that the correct position is reached. On reaching the appropriate position to delete the element the predicate slices the head off the list and finally merges the remaining art with the rest. The prolog code is given as below:

DOMAINS int_list=Integer * PREDICATES delete(integer,int_list,int_list) CLAUSES delete(0,[H|T],T). delete(P,[H|T],[H|Z]):-             P1=P-1,delete(P1,T,Z). GOAL delete(0,[1,2,3,4,5,6,7,8,9],X).