VP search technique
Dear Sir;
Could you help me to know the search technique of VP?
Regards;
AHMED
Could you help me to know the search technique of VP?
Regards;
AHMED
- Thomas Linder Puls
- VIP Member
- Posts: 1424
- Joined: 28 Feb 2000 0:01
- Thomas Linder Puls
- VIP Member
- Posts: 1424
- Joined: 28 Feb 2000 0:01
I assume that you mean a stack overflow.
Normally this is caused by an infinite recursion, like in this (silly) code:
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.
Normally this is caused by an infinite recursion, like in this (silly) code:
Code: Select all
predicates
p : ().
clauses
p() :-
p(),
p().
You should read: Memory Management especially the section about the run stack.
Regards Thomas Linder Puls
PDC
PDC
- Thomas Linder Puls
- VIP Member
- Posts: 1424
- Joined: 28 Feb 2000 0:01
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"].
- Thomas Linder Puls
- VIP Member
- Posts: 1424
- Joined: 28 Feb 2000 0:01
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:
It gives the warning:
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:
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:
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:
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:
The code is clearer for two reasons:
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:
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.
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).
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"].
Such warnings should be taken seriously, because very often they are caused by a bug.w507 Unused variable: 'Pr'
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).
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.
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,
!.
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"].
- 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.
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"].
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
(By the way your code have many inefficiencies, but will have to be another day).
Regards Thomas Linder Puls
PDC
PDC
Dear Sir;
Thank you very much for your fruitful effort.
I will rearrange my code. but the last case is:
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
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"].
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
- Thomas Linder Puls
- VIP Member
- Posts: 1424
- Joined: 28 Feb 2000 0:01
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>":
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
PDC
Dear Sir;
Thank you for your recommendations.
I would like to add that the recursive predicate pr_phra which consists of two cases:
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
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).
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
- Thomas Linder Puls
- VIP Member
- Posts: 1424
- Joined: 28 Feb 2000 0:01
The key to that is thinking a bit different. Instead of:
In your case it could be (I have removed the tests for "pr"):
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.
- There are two cases two phra's
- or one phra
- There is one phra
- and optionally another phra
Code: Select all
(P and Q1) or (P and Q2) <=> P and (Q1 or Q2)
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.
Regards Thomas Linder Puls
PDC
PDC