ok@quintus.UUCP (Richard A. O'Keefe) (04/26/88)
HP Prolog has a declaration ":- deterministic". The entire description
in the manual reads thus:
" The deterministic predicate specifies predicates having at most
one solutions.
@b<deterministic> @i<Pred1>, @i<Pred2>, ...
Predn : a predicate specification.
The specified predicates are deterministic, i.e. they can never
have more than one solution. This information is used by the
compiler and interpreter to increase efficiency. A determinstic
declaration must stand before all clauses of the predicate in the
source file. "
Now plagiarism is the sincerest form of flattery, and I don't see why
Quintus shouldn't flatter any good ideas that are going around, but it
is hard to steal an idea you don't understand. My problem is that I
can't figure out what :- deterministic @i<means>. (Somewhere at the
bottom of about 20 feet of reports and papers I have a copy of something
by Kamran Parsaye, I think in 1982 or 1983, where he proposed a
:-determinate declaration, or was it :-function pred(<mode>), but I
don't remember grasping that either.)
There is an obvious kludge, namely interpreting this as "add a cut at
the end of every clause of the indicated predicate", but that is clearly
not what is intended, because it would be a sure-fire recipe for making
non-steadfast predicates. What I'm getting at is that if you do e.g.
:- deterministic fac/2.
fac(0, 1).
fac(1, 1).
fac(N, F) :- M is N-1, fac(M, G), F is G*N.
then it should be translated as
fac(0, X) :- !, X = 1.
fac(1, X) :- !, X = 1.
fac(N, F) :- M is N-1, fac(M, G), F is G*N.
not as
fac(0, 1) :- !.
and so on. So presumably the :-deterministic directive must take the
declared :-mode into account, but how exactly does it do this? Anyone know?ok@quintus.UUCP (Richard A. O'Keefe) (04/26/88)
The HP Prolog manual says a little bit more about :-deterministic:
" HP Prolog features a mechanism called declarative determinism.
By declaring a predicate which is known to only succeed once
determinstic, efficiency can be gained in interpreted and
compiled code. This is preferable to cluttering a predicate
definition with cuts. "
which is tantalising, but not explicit.fritz@hpfclp.SDE.HP.COM (Gary Fritz) (04/26/88)
Caveat: I am not one of the designers/implementors of HP Prolog, and therefore do not pretend to understand all the subtleties of the design. Until I get one of the designers to respond, though, allow me to make a few remarks: The deterministic declaration does result in behavior rather like that achieved by inserting a cut at the end of the predicate. There is, however, a more useful effect. Since the compiler knows that predicate X is deterministic, and cannot possibly backtrack, it can emit more efficient efficient code to call it. Since HP Prolog is implemented in Common Lisp, nested closures were used to implement success continuations. This happens to be very efficient in HP's Common Lisp, but obviously it's more efficient if you don't have to do this. The deterministic declarations allow the compiler to just call the predicate without pushing a level of closures. You could garner the same information by examining the definition of predicate X, but the declaration has a more global effect (just like compiler declarations in other languages). It can be made available in other source files, etc. Is this what you were looking for, or am I just stating the obvious? I'm afraid I don't understand what you mean by a "non-steadfast" predicate, so I can't address that. Care to enlighten me? Gary
voda@ubc-cs (Paul Voda) (04/27/88)
I do not know how the deterministic predicates are implemented in HP-Prolog,
but I do know what they are in Trilogy. Maybe this will help.
When you declare a Trilogy predicate as a 'proc' rather than a 'pred'
then the Trilogy system uses the mode information about the arguments
extensively in order to check that the predicate can never backtrack.
Consequently, a call to a deterministic predicate, i.e. to a procedure,
can return at most one set of results. The compiler generates a code
of Pascal-like quality in such a case.
Generally, the system checks that all calls to 'preds', i.e. to the
true backtracking predicates are enclosed in an all (min, one) solution
construct, that there are no values returned through an "or" and
that there are no symbolic (logic) variables with constraints used
(except enclosed in all,min one constructs).
For instance the declaration
proc P(x:>I) iff x = 1 | x = 2
with the output argument "x" is rejected because in order
to satisfy the goal P(2) which is compiled as P(z) & z = 2 we need
backtracking.
Incidentally, the version 1.3 of Trilogy now contains a one-solution
construct of the form
one x,y..,z A(x,y,z)
where one (the first solution found) satisfying the formula A is
communicated to the outside through the variables x,y,z. The one
solution construct can also contain non-local parameters.
The one-solution construct in Trilogy is a tame version of the
cut of Prolog. I have included it in the version 1.3 and not in
the previous versions because until now I could not explain it
logically, and obviously I do not want any hacks in Trilogy.
I have written a paper on the one solution construct which I will
mail to all interested parties on request. The title is:
The Logical Reconstruction of Cuts as One Solution Operators.ok@quintus.UUCP (Richard A. O'Keefe) (04/28/88)
In article <2217@ubc-cs.UUCP>, voda@ubc-cs (Paul Voda) writes: > I do not know how the deterministic predicates are implemented in HP-Prolog, > but I do know what they are in Trilogy. Maybe this will help. Not really. Trilogy is a logic programming language which makes no pretence of being Prolog. (In some ways it resembles ALEPH, except that it is a lot purer.) Trilogy is allowed to reject programs as invalid based on a data flow analysis; Prolog systems are not. The HP-Prolog manual I have a (partial) copy of does not mention any restriction on :-deterministic predicates at all, and as it is an incremental system, I doubt that it is doing much data-flow analysis. > I have written a paper on the one solution construct which I will > mail to all interested parties on request. The title is: > > The Logical Reconstruction of Cuts as One Solution Operators. I have received a copy of this. It's a nice paper, but it makes me even more unhappy with cuts than ever. There is a question: how often do we really need the _control_ component to say "commit to the first solution" rather than "commit to any solution"? Consider the contrast between member(X, [H|T]) <-> X = H | member(X, T) member1(X, L) <-> first member(X, L) -vs- member1(X, [H|T]) <-> X = H | X ~= H & member1(X, T) -or- member1(X, [H|T]) <-> if X = H then true else member1(X, T) [if-then-else being sound as in NU Prolog]. It would be really interesting to see some sketches of how people are using once(Goal), [! Goal !], or (Goal->true) {all the same thing}.
fiorentino@cup.portal.com (05/01/88)
Paul I purchased Trilogy. I would like to be updated and nee to know when you have the linker ready to make stand-alone applications
bd@zyx.SE (Bjorn Danielsson) (05/12/88)
Gary Fritz is right: The deterministic declaration has the same effect as inserting a cut at the end of each clause, or the same effect as wrapping 'PROVE-ONCE' around every call to such a predicate. The main reason for this is to help the compiler produce better LISP code when block-compiling a Prolog program. In particular, a conjunction of goals that have been declared deterministic can be compiled to something like: (and (pred1) (pred2) (pred3) (funcall cont)) instead of the general case, where an explicit success continuation is needed as an extra argument to all three predicates: (pred1 #'(lambda () (pred2 #'(lambda () (pred3 cont))))) Also, deterministic-declarations can be (mis-)used in the same way as cut. In some situations it is easier just to say "only the first solution to this predicate is ever needed" rather than inserting cuts at the right places. Today I consider the deterministic-declaration to be useful only as a "pragma" for the compiler. As a programming device it is less precise than cut, and it hardly gives any advantage in a WAM implementation. I think a convenient "cases" or "cond" macro based on a backtrackable if-then-else is a better way to make programs deterministic, since that's often what people *mean* when they misuse cut. -- Bjorn Danielsson, ZYX Sweden AB, +46 (8) 665 32 05, bd@zyx.SE
ok@quintus.UUCP (Richard A. O'Keefe) (05/15/88)
In article <2525@zyx.SE>, bd@zyx.SE (Bjorn Danielsson) explains the :-deterministic declaration. HP Prolog sounds a *lot* like PopLog. > I think a convenient > "cases" or "cond" macro based on a backtrackable if-then-else is a better > way to make programs deterministic, since that's often what people *mean* > when they misuse cut. I put a "cases" construct into the *.edai versions of C Prolog, but could never think of anything to do with it. (I got the idea from LM-Prolog.) I would very much like to learn how to use this construct. [I very much doubt that most people *do* mean anything when they use cuts, but judging from comp.lang.c there are a lot of C programmers who aren't too clear on assignment statements or procedure calls.]