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]]).
No comments:
Post a Comment