shahaf@taux01.UUCP (Shahaf Moshe) (03/10/88)
Hello,
Can someone help me in the following: In translation from WATERLOO
to Quintus code I need a !/1 predicate which does :
!(P) - A search through the
ancestors exactly as for ancestor and retry. If this
search fails then the predicate fails. If the search
succeeds then certain available choices are eliminated
from an existing portion of the proof. All choice
points are removed in the part of the proof from the
point of selection of the given ancestor literal to the
current point in the proof. Thus a call of the form
/(*) has exactly the same effect as the simple nullary
/ call. Consider the following example:
a:-b,c,d.
b:-e.
c:-f,g.
e.
f.
g:-/(c),h.
:-a.
...
The implication tree has the following form when the
unary cut is called:
goal
|
a
/ | \
/ | \
/ | \
b c d
/ | \
/ | \
e f g
x x | \
| \
/(c) h
All choice points from the selection of c:-f,g onward
are eliminated. Thus if h fails an alternate proof for
e will be attempted (and the subproof of c will be
deleted).
thanks a lot.
shahaf%taux01@nsc.COMok@quintus.UUCP (Richard A. O'Keefe) (03/12/88)
In article <500@taux01.UUCP>, shahaf@taux01.UUCP (Shahaf Moshe) writes: > Can someone help me in the following: In translation from WATERLOO > to Quintus code I need {an ancestral cut}. (1) A predicate which "searches through the ancestors exactly as for ancestor and retry" is a rather hard thing to provide in a system which does last call optimisation, the whole point of which is to ensure that as many ancestors as possible are completely forgotten as soon as possible. Quintus Prolog does not provide 'retry' either. (2) We are currently putting some rather nice things into Quintus Prolog which I don't think we could implement at all if we supported ancestral cuts. (3) Check to see whether your site has a support contract with Quintus. We *may* be able to advise you how to write your program so that it doesn't need ancestral cuts. (4) Could you tell this newsgroup more about your program? It would be very interesting to hear of something that ancestral cuts were needed for. (They _aren't_ needed for interpreting Prolog!)
shahaf@taux01.UUCP (Shahaf Moshe) (03/14/88)
Followup-To: In article <764@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes: > >(4) Could you tell this newsgroup more about your program? It would be > very interesting to hear of something that ancestral cuts were > needed for. (They _aren't_ needed for interpreting Prolog!) The program does Network synthesis from boolean equations for VLSI design. The ancestral cut was used to stop the search of local transformations when the rate of new maping is too low. shahaf%taux01@nsc.COM
lindsay@comp.vuw.ac.nz (Lindsay Groves) (03/17/88)
In article <503@taux01.UUCP> shahaf%taux01@nsc.COM writes: >In article <764@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes: >> >>(4) Could you tell this newsgroup more about your program? It would be >> very interesting to hear of something that ancestral cuts were >> needed for. (They _aren't_ needed for interpreting Prolog!) >The program does Network synthesis from boolean equations for VLSI design. >The ancestral cut was used to stop the search of local transformations >when the rate of new maping is too low. >shahaf%taux01@nsc.COM I'll save Richard saying it -- this doesn't say much about the program, and certainly doesn't explain why ancestral cuts are supposed to be necessary. Could you describe the problem in a bit more detail and illustrate just how the need for ansectral cuts arises? Perhaps a simplified version of the problem could be used to illustrate the point. An example would certainly help. Lindsay Groves Logic programmers' theme song: "The first cut is the deepest"
shahaf@taux01.UUCP (Shahaf Moshe) (03/21/88)
Followup-To: Hdate: 3 Nisan 5748 In article <13364@comp.vuw.ac.nz> lindsay@comp.vuw.ac.nz (Lindsay Groves) writes: >I'll save Richard saying it -- this doesn't say much about the program, and >certainly doesn't explain why ancestral cuts are supposed to be necessary. >Could you describe the problem in a bit more detail and illustrate just >how the need for ansectral cuts arises? Perhaps a simplified version of the >problem could be used to illustrate the point. An example would certainly >help. First I would like to make two comments: * I am a NOVICE (in Prolog). * I do not claim that in my application Ansectral Cut are a MUST. I wrote it on a system were it was a feature and I used it. Since its not available in Quintus Prolog, I asked for help. About the application, The program looks for best mapping of a Boolean function onto a set of logic primitives such as X * Y * Z maps to: 2inputAnd( 2inputAnd( X, Y) , Z) or: 3inputAnd( X, Y, Z) Since the search space is huge I used Ansectral Cut to abort mapping once I get some "STOP CONDITIONS". The program looks like: map(Function,Network) :- generate(Function,Network), test(Network). test(Network) :- lemma(Network,StopCondition), !(map). %this cut aborts the process. I hesitate to post longer description on the net. If anyone would like to get more elaborated data I will mail upon request. shahaf%taux01@nsc.com
ok@quintus.UUCP (Richard A. O'Keefe) (03/23/88)
In article <512@taux01.UUCP>, shahaf@taux01.UUCP (Shahaf Moshe) writes: > The program looks like: > > map(Function,Network) :- > generate(Function,Network), > test(Network). > test(Network) :- > lemma(Network,StopCondition), > !(map). %this cut aborts the process. > In that case, why not just code it as map(Function, Network) :- generate(Function, Network), test(Network), !. test(Network) :- lemma(Network, StopCondition). More generally, suppose that you had several cases: test(Network) :- lemma(Network, ~~~), !(map(_,_)), p(...). ... test(Network) :- lemma(Network, ~~~), !(map(_,_)), q(...). Then you could recast this as map(Function, Network) :- generate(Function, Network), test(Network, Continuation), !, finish(Continuation, ...). finish(p, ...) :- p(...). ... finish(q, ...) :- q(...). test(Network, p) :- lemma(Network, ~~~). ... test(Network, q) :- lemma(Network, ~~~). The basic idea is to redesign your "test" code so that it breaks into three pieces: before-the-cut, the ancestral cut, and after-the-cut, and then unfold the call to it so that the cut is exposed in "map".