Discussions related to Visual Prolog
ahmednadi
Active Member
Posts: 37
Joined: 15 Sep 2009 14:06

VP search technique

Unread post by ahmednadi »

Dear Sir;
Could you help me to know the search technique of VP?
Regards;
AHMED
User avatar
Thomas Linder Puls
VIP Member
Posts: 1398
Joined: 28 Feb 2000 0:01

Unread post by Thomas Linder Puls »

What do you mean?
Regards Thomas Linder Puls
PDC
ahmednadi
Active Member
Posts: 37
Joined: 15 Sep 2009 14:06

Unread post by ahmednadi »

Dear Sirs;
Could you help me to solve the following problem?
I create an nondeterm predicate and I want to modify this predicate to be two sequential stage of it.
When I do like this, Visual Prolog gives an overflow error.
How can I overcome this overflow error.
Regards;
AHMED
User avatar
Thomas Linder Puls
VIP Member
Posts: 1398
Joined: 28 Feb 2000 0:01

Unread post by Thomas Linder Puls »

I assume that you mean a stack overflow.

Normally this is caused by an infinite recursion, like in this (silly) code:

Code: Select all

predicates     p : (). clauses     p() :-         p(),         p().
Due to last call optimization there have to be a call after the infinite recursion, if you omit the second call to p() you will get an infinite loop instead (the program will not terminate, but the stack will not be exhausted).

You should read: Memory Management especially the section about the run stack.
Regards Thomas Linder Puls
PDC
ahmednadi
Active Member
Posts: 37
Joined: 15 Sep 2009 14:06

Unread post by ahmednadi »

User avatar
Thomas Linder Puls
VIP Member
Posts: 1398
Joined: 28 Feb 2000 0:01

Unread post by Thomas Linder Puls »

I have to see the code, to be of further help.
Regards Thomas Linder Puls
PDC
ahmednadi
Active Member
Posts: 37
Joined: 15 Sep 2009 14:06

Unread post by ahmednadi »

Code: Select all

pr_Phra:(string,string,pr_Phra,string*) nondeterm(i,o,o,o).

Code: Select all

pr_Phra(Str,Rest,pr_Phra2(P_Phra1,P_Phra2),PrList):- frontToken(Str,W1,_), getW(ID1,W1,_,"pr",_,_,_,_,_,_,_,_,_,_,_,_,_), ID1<>0, pr_ph(Str,Rest1,P_Phra1,PrLst1), frontToken(Rest1,W2,_), getW(ID2,W2,_,"pr",_,_,_,_,_,_,_,_,_,_,_,_,_), ID2<>0, pr_ph(Rest1,Rest,P_Phra2,PrLst2), PrList=list::append(PrLst1,PrLst2). pr_Phra(Str,Rest,pr_Phra1(P_Phra),PrList):- frontToken(Str,W,_), getW(ID,W,_,"pr",_,_,_,_,_,_,_,_,_,_,_,_,_), ID<>0, pr_ph(Str,Rest,P_Phra,PrList).

Code: Select all

pr_ph:(string,string,pr_ph,string*) nondeterm(i,o,o,o).

Code: Select all

pr_ph = pr_ph2(string,string);                          pr_ph1(string).

Code: Select all

pr_ph(Str,Rest,pr_ph2(Pr,Pro),PrList):- frontToken(Str,Pr,Rest1), getW(ID1,Pr,_,"pr",_,_,_,_,_,_,_,_,_,_,_,_,_), ID1<>0, frontToken(Rest1,Pron,Rest), getW(ID2,Pron,_,"pro",_,_,_,_,_,_,_,_,_,_,_,_,_), ID2<>0, PrList=["pr","pro"]. pr_ph(Str,Rest,pr_ph2(Pr,Ad),PrList):- frontToken(Str,Pr,Rest1), getW(ID1,Pr,_,"pr",_,_,_,_,_,_,_,_,_,_,_,_,_), ID1<>0, frontToken(Rest1,Ad,Rest), getW(ID2,Ad,_,"ad",_,_,_,_,_,_,_,_,_,_,_,_,_), ID2<>0, PrList=["pr","ad"]. pr_ph(Str,Rest,pr_ph1(Pr),PrList):- frontToken(Str,Pr,Rest), getW(ID,Pr,_,"pr",_,_,_,_,_,_,_,_,_,_,_,_,_), ID<>0, PrList=["pr"]. pr_ph(Str,Rest,pr_ph1(Ad),PrList):- frontToken(Str,Pr,Rest), getW(ID,Ad,_,"ad",_,_,_,_,_,_,_,_,_,_,_,_,_), ID<>0, PrList=["pr"].
User avatar
Thomas Linder Puls
VIP Member
Posts: 1398
Joined: 28 Feb 2000 0:01

Unread post by Thomas Linder Puls »

Well, there is a lot of copy-paste code here ;-).

There is a few errors with variable names in one place Pro is used instead of Pron. But the last clauses is the worst:

Code: Select all

pr_ph(Str, Rest, pr_ph1(Ad), PrList) :-         frontToken(Str, Pr, Rest),         getW(ID, Ad, _, "ad", _, _, _, _, _, _, _, _, _, _, _, _, _),         ID <> 0,         PrList = ["pr"].
It gives the warning:
w507 Unused variable: 'Pr'
Such warnings should be taken seriously, because very often they are caused by a bug.

I am not sure what you meant, so for now I have simply disregarded the clause.


Before we go any further I will rewrite your program so it becomes clearer.

I have guessed that getW is a fact with word definitions. I have used this dummy declaration:

Code: Select all

class facts     getW : (integer, string, handle, string, handle, handle, handle, handle, handle, handle, handle, handle, handle, handle, handle, handle, handle).
To lessen the copy-paste problem I will define an auxillary predicate for the three lines that you repeat several times.

Given your program this auxillary predicate should look like this:

Code: Select all

class predicates     getWord_nd : (string WordClass, string Input, string Rest [out]) -> string Word nondeterm. clauses     getWord_nd(WordClass, Input, Rest) = Word :-         frontToken(Input, Word, Rest),         getW(ID, Word, _, WordClass, _, _, _, _, _, _, _, _, _, _, _, _, _),         ID <> 0.
I do however guess that a certain word will only appear once in "WordClass". I.e. the fact is only supposed to supply one solution for each invocation:

Code: Select all

class predicates     tryGetWord : (string WordClass, string Input, string Rest [out]) -> string Word determ. clauses     tryGetWord(WordClass, Input, Rest) = Word :-         frontToken(Input, Word, Rest),         getW(ID, Word, _, WordClass, _, _, _, _, _, _, _, _, _, _, _, _, _),         ID <> 0,         !.
The cut (!) in the end removes any backtracking into the getW fact, so that we at most get one solution, thereby making the predicate determ instead of nondeterm.

Rewriting the rest of your clauses using this predicate we get something which is much clearer:

Code: Select all

class predicates     pr_Phra : (string, string, pr_Phra, string*) nondeterm (i,o,o,o). clauses     pr_Phra(Str, Rest, pr_Phra2(P_Phra1, P_Phra2), PrList) :-         _W1 = tryGetWord("pr", Str, _),         pr_ph(Str, Rest1, P_Phra1, PrLst1),         _W2 = tryGetWord("pr", Rest1, _),         pr_ph(Rest1, Rest, P_Phra2, PrLst2),         PrList = list::append(PrLst1, PrLst2).       pr_Phra(Str, Rest, pr_Phra1(P_Phra), PrList) :-         _W = tryGetWord("pr", Str, _),         pr_ph(Str, Rest, P_Phra, PrList).   class predicates     pr_ph : (string, string, pr_ph, string*) nondeterm (i,o,o,o). clauses     pr_ph(Str, Rest, pr_ph2(Pr, Pron), PrList) :-         Pr = tryGetWord("pr", Str, Rest1),         Pron = tryGetWord("pro", Rest1, Rest),         PrList = ["pr", "pro"].       pr_ph(Str, Rest, pr_ph2(Pr, Ad), PrList) :-         Pr = tryGetWord("pr", Str, Rest1),         Ad = tryGetWord("ad", Rest1, Rest),         PrList = ["pr", "ad"].       pr_ph(Str, Rest, pr_ph1(Pr), PrList) :-         Pr = tryGetWord("pr", Str, Rest),         PrList = ["pr"].
The code is clearer for two reasons:
  • First of all because replacing cryptic lines of code with a nice meaning full word (i.e. tryGetWord) ease the understanding.
  • Secondly because the number of strange "noisy" intermediate variables (like ID1) have been dramatically reduced.
Let us first consider the pr_ph predicate with an input sequence <pr> <ad>.

The first clause will fail, because <ad> is not a "pro", but the second clause will succeed. However the third clause will also succeed, consuming only <pr> and leaving <ad> in the "Rest".

When you have received the first solution (the long one) you will still have a backtrack point which will return the shorter solution (leaving more in Rest").

The pr_Phra predicate have a similar behavior, everything that match the first clause will also match the second clause (leaving more in "Rest").

You can prevent such additional solutions by using cut:

Code: Select all

class predicates     pr_ph : (string, string, pr_ph, string*) nondeterm (i,o,o,o). clauses     pr_ph(Str, Rest, pr_ph2(Pr, Pron), PrList) :-         Pr = tryGetWord("pr", Str, Rest1),         Pron = tryGetWord("pro", Rest1, Rest),         !, % if we have found a ["pr", "pro"] solution we will not try ["pr", "ad"] and ["pr"]         PrList = ["pr", "pro"].       pr_ph(Str, Rest, pr_ph2(Pr, Ad), PrList) :-         Pr = tryGetWord("pr", Str, Rest1),         Ad = tryGetWord("ad", Rest1, Rest),         !, % if we have found a ["pr", "ad"] solution we will not try ["pr"]         PrList = ["pr", "ad"].       pr_ph(Str, Rest, pr_ph1(Pr), PrList) :-         Pr = tryGetWord("pr", Str, Rest),         PrList = ["pr"].
But that may not be good if some words can both be a "pro" and a "ad", because the cut in the first clause will mean that the ["pr", "ad"] solution is not found.

And alternative is to cut at a much higher level, but allowing all the lower levels to backtrack.

Code: Select all

clauses     pr(Str, Rest, P, PrList) :-         pr_Phra(Str, Rest, P, PrList),         !. % only consider the first top-level solution
You may want (or need ;-) to read about backtrack in the wiki.


(By the way your code have many inefficiencies, but will have to be another day).
Regards Thomas Linder Puls
PDC
ahmednadi
Active Member
Posts: 37
Joined: 15 Sep 2009 14:06

Unread post by ahmednadi »

Dear Sir;
Thank you very much for your fruitful effort.
I will rearrange my code. but the last case is:

Code: Select all

pr_ph(Str, Rest, pr_ph1(Ad), PrList) :-         frontToken(Str, Ad, Rest),         getW(ID, Ad, _, "ad", _, _, _, _, _, _, _, _, _, _, _, _, _),         ID <> 0,         PrList = ["ad"].
you will find four cases for the predicate pr_ph and we have another predicate named pr_phra which may consist of two pr_ph predicate cases like ["pr","pro"]&["ad"] or one case from pr_ph predicate, such as:["pr"]or["ad"]or["pr","pro"]or["pr","ad"].

If the i/p gives output like ["pr","ad"] the second case of pr_phra1(P_Phra), the predicate behaves pr_Phra2(P_Phra1,P_Phra2) where P_Phra1= ["pr"] and P_Phra2= ["ad"].
the desired result:
fail in the first case but gives the result by the second case meanwhile we don't want to make double processing.

I hope you get my idea.

Regards;
AHMED
User avatar
Thomas Linder Puls
VIP Member
Posts: 1398
Joined: 28 Feb 2000 0:01

Unread post by Thomas Linder Puls »

However, before calling pr_ph you always ensure that the first word is a "pr". So only if the first word is both a "pr" and an "ad" the last clause will succeed.

Also notice that (without the test for "pr") it gives several ways to match for example "<pr> <ad>":
  • first as pr_Pha2(["pr"], ["ad"])
  • the as pr_Pha1(["pr", "ad"])
Regards Thomas Linder Puls
PDC
ahmednadi
Active Member
Posts: 37
Joined: 15 Sep 2009 14:06

Unread post by ahmednadi »

Dear Sir;
Thank you for your recommendations.
I would like to add that the recursive predicate pr_phra which consists of two cases:

Code: Select all

class predicates     pr_phra : (string, string, pr_Phra, string*) nondeterm (i,o,o,o).

Code: Select all

clauses Case (1): pr_phra(Str, Rest, pr_phra2(P_Phra1, P_Phra2), PrList) :-         _W1 = tryGetWord("pr", Str, _),         pr_ph(Str, Rest1, P_Phra1, PrLst1),         _W2 = tryGetWord("pr", Rest1, _),         pr_ph(Rest1, Rest, P_Phra2, PrLst2),         PrList = list::append(PrLst1, PrLst2). Case (2):     pr_phra(Str, Rest, pr_phra1(P_Phra), PrList) :-         _W = tryGetWord("pr", Str, _),         pr_ph(Str, Rest, P_Phra, PrList).
To get my point, For example sequence 1 "<pr> <ad> <pr> <pro>" and sequence 2 "<pr> <ad>".
No problem in processing sequence 1, it meets case (1): first case .
But sequence 2: in case(1) , and the case (2): .
What can I do to avoid the duplicated processing?
I would like to draw your attention that Case(2) is the main case but Case (1) occurs sometimes.
Regards;
AHMED
User avatar
Thomas Linder Puls
VIP Member
Posts: 1398
Joined: 28 Feb 2000 0:01

Unread post by Thomas Linder Puls »

The key to that is thinking a bit different. Instead of:
  • There are two cases two phra's
  • or one phra
You should say:
  • There is one phra
  • and optionally another phra
The key is of course to do the common part once, and then deal with different "tails" afterwards:

Code: Select all

(P and Q1) or (P and Q2) <=> P and (Q1 or Q2)
In your case it could be (I have removed the tests for "pr"):

Code: Select all

clauses     pr_phra(Str, Rest, P_Phra, PrList) :-         pr_ph(Str, Rest1, P_Phra1, PrLst1),         if pr_ph(Rest1, Rest, P_Phra2, PrLst2) then             P_Phra =pr_phra2(P_Phra1, P_Phra2),             PrList = list::append(PrLst1, PrLst2)         else             P_Phra = P_Phra1,             PrList = PrLst1         end if.
I have also used if-then-else instead of or, because I believe that you are not interested in both solutions, if the long solution succeeds the short one is not interesting.
Regards Thomas Linder Puls
PDC
Post Reply