voda@ubc-cs (Paul Voda) (05/01/88)
There is a lively discussion going on the subject Richard raised: Deterministic predicates, and also on my subject of cuts as one solution operators. Let me start with the cuts. I have introduced if-the-else formulas into Trilogy in order to escape the need for the most of cuts. Until about a month ago I have thought that this is all you need. I thought that the few cases where one needs 'a solution' can be dealt with the sound 'all solutions' construct of Trilogy. Unfortunately, this was not the case as we have quite a few rather big applications written in Trilogy where only one solution to a formula is sought and processed by the program. Since there were no cuts in Trilogy, one had to spend a lot of time searching for all solutions only to pick the first (the smallest) one. My guess is that in Prolog you do not perceive the urgency of a one solution because a programmer writing such an application includes a cut and does not think about it. The problem became urgent in Trilogy where no cuts could be used. Lee Naish mentioned a few examples (a sort, the sum of a list) where you know that there cannot be more solutions (deterministic parsing is also such) yet the choice points remain set. In addition to this, there are cases where you need one answer and do not care about the other answers which may be differ only in an order of a list. Both Richard and Lee have said that they want 'an answer' and not 'the first answer found'. Classical logic can cope with 'an answer' only by the use of Hilbert's epsilon operator. However, the logic of equivalence and identity requires that 'one x ( x = 1 | x = 2 )' and 'one x ( x = 2 | x = 1 )' be the same. The Hilbert's epsilon elimination theorems rely on this. Thus the epsilon operator is 'indeterminate' but not 'non-deterministic': the same answer for the same set. To implement epsilon operator is impossible without ordering all solutions and picking one, say the minimal, or the second minimal or so. This is clearly too expensive. Parallelism does not speed up the things very much, we still have to generate all solutions. These considerations lead me to the explication of the one solution as the first solution found (if at all) in the sequential order of the search. Lee Naish says that this is procedural. He does not know (as Richard does, having seen my paper on One Solution operator) that the whole idea of the paper is to turn the 'procedural' or proof-theoretic notion of the search order which is meta-logical into an object-theoretic concept. I achieve this by the trick of Goedel, by arithmetizing the concept of the search path and expressing it in the semantics of the one-formula. As it happens this explanation is quite a simple one, no heavy goedel numbering is needed. A search path is represented as a list consisting of atoms L(eft) and R(ight) selecting the path in an or node of the search tree. Starting from the version 1.3 Trilogy contains the one solution construct. In the mentioned paper I discuss the restrictions on the variables which are free in the one solution operator and thus act as parameters on which the solution depends. As it turns out the one solution operator can be implemented in a sound way in Trilogy only because Trilogy contains modes of variables and the system makes an extensive use of them. This brings us to the subject of deterministic predicates. Richard posted a question about HP-Prolog's deterministic predicate declaration. I offered a solution in Trilogy hoping that this will help. Richard answers: > 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. As Gary Fritz observes the HP-Prolog's deterministic declaration is a hack without a logic: include a cut at the end of each clause. I cannot see how one can have a deterministic declaration without rejecting some predicates as non-deterministic. For instance q(0). q(1). deterministic q must be rejected by a sound Prolog because the query 'q(x), x = 2' clearly requires backtracking. I think that sound Prologs simply must start rejecting non-logical constructs not accepting them as extra-logical. In my brief explanation of deterministic predicates of Trilogy (procs) I said that the modes play a vital role. This is what Richard has suspected anyway and it was also confirmed by Zoltan Somogyi, Saumya Debray, and Lee Naish. We all agree on this. Now, as Saumya pointed out, there are many theoretical papers on the subject, there are no doubt some master-thesis implementations on top of Prologs and Lisps. The reason I have offered Trilogy is because Trilogy is a professionaly implemented system (as a native code compiler). I do not think that it has to be your favourite programming language but it cannot be ignored by the implementors of various Prologs. In the course of my professional career I have implemented five real life compilers and I can tell you that I have never faced a more difficult compiler problem than doing the type and mode checking of Trilogy. This is because of the great number of mode combinations possible requiring a very extensive data-flow analysis.
ok@quintus.UUCP (Richard A. O'Keefe) (05/01/88)
In article <2316@ubc-cs.UUCP>, voda@ubc-cs (Paul Voda) writes: > There is a lively discussion going on the subject Richard raised: > Deterministic predicates, and also on my subject of cuts as one > solution operators. > Both Richard and Lee have said that they want 'an answer' and not > 'the first answer found'. Classical logic can cope with 'an answer' > only by the use of Hilbert's epsilon operator. > These considerations lead me to the explication of the one solution > as the first solution found (if at all) in the sequential order > of the search. Lee Naish says that this is procedural. He does not > know (as Richard does, having seen my paper on One Solution operator) > that the whole idea of the paper is to turn the 'procedural' or > proof-theoretic notion of the search order which is meta-logical > into an object-theoretic concept. It's a very nice paper, and Voda's definition of 'one' _does_ give you a logical construct, so I agree with Voda. But it does this at the price of building the top-down left-to-right search into the semantics, so I agree with Naish too. It is comforting to know that 'one' _has_ a logical reading, but that doesn't really help me to understand it. I understand 'one' procedurally. (It is not clear to me how the formal definition of 'one' interacts with constraints, for example.) Lee Naish suggested that building determinacy into the code is in general the way to go. It can in fact be _grossly_ more efficient than adding cuts at the end of things. I have a simple example example (testing whether a list is a subset of the union of two other lists) where putting the cuts early gives you an algorithm with O(N**2) worst case cost, but putting the cuts at the end of the clauses gives you an algorithm with O(2**N) worst case cost. A method of automatically adding cuts in the wrong place (:-deterministic) doesn't seem like such a wonderful idea. [We still haven't heard from the implementors of HP-Prolog, so there is still some hope that this isn't what :-deterministic means.] It's not quite right to say that I "said that [I] want 'an answer' and not 'the first answer found'". The thing is that "an answer" _feels_ like logic (and should be not too hard to reason about), and "the first answer" doesn't _feel_ like logic (and it seems to me that reasoning about it is not that different from reasoning about the search procedure). If what we really need is "the first answer", then Voda's definition is a lovely way to define it. My question is, how often do we _need_ "the first answer", and how often will "any answer" do. As Voda points out, "any answer to p(X) or q(X)" is not necessarily equal to "any answer to p(X) or q(X)", or, for that matter, to "any answer to p(X) or q(X)". Perhaps there is some restriction on logic programs which ensures that it doesn't matter?
fritz@hpfclp.SDE.HP.COM (Gary Fritz) (05/13/88)
Responding to Paul Voda: > As Gary Fritz observes the HP-Prolog's deterministic declaration is a hack > without a logic: include a cut at the end of each clause. Um, I don't recall ever making *quite* that statement! Please, don't put words in my mouth; I get myself in quite enough trouble without any help, thank you! :-) I gave my (fuzzy) understanding of the mechanism to keep the discussion rolling until the engineers at ZYX could respond more authoritatively. They have been disconnected from the net for the past few weeks, and have been unable to contribute. If, by "without a logic", you mean there is no purely logical derivation of the deterministic declaration, that may be true. I don't pretend to have the theoretical background to debate the point. The deterministic declaration, however, *is* useful to make a program run more efficiently. I could compare it to the speed/safety declarations in Common Lisp; while they may result in generated code which does not strictly conform to the CL definition (not checking tag bits, not checking for a valid list, etc.), they can result in a more efficient program when applied sensibly. > I cannot see how one can have a deterministic declaration without > rejecting some predicates as non-deterministic. For instance > > q(0). q(1). > deterministic q > > must be rejected by a sound Prolog because the query > 'q(x), x = 2' clearly requires backtracking. Hm. Certainly 'q(X), X = 2' requires backtracking, and would fail. However, 'q(2)' is a perfectly reasonable query, and *would* succeed. Therefore, is it necessary for a sound Prolog to reject the definition of 'q'? Mind you, I don't necessarily think this is a "correct" application of deterministic, but it does seem to make some sense. A "correct" use of deterministic would not include a predicate with multiple correct answers. However, if the chief concern here was that 'q' be called efficiently, the deterministic declaration would have some value. If the chief concern is to have a purely logical program, then I suspect the deterministic declaration should *never* be used. Of course, the same thing could be said for cut, no? Responding to Richard: > Lee Naish suggested that building determinacy into the code is in general > the way to go. It can in fact be _grossly_ more efficient than adding > cuts at the end of things. I have a simple example example (testing > whether a list is a subset of the union of two other lists) where putting > the cuts early gives you an algorithm with O(N**2) worst case cost, but > putting the cuts at the end of the clauses gives you an algorithm with > O(2**N) worst case cost. A method of automatically adding cuts in the > wrong place (:-deterministic) doesn't seem like such a wonderful idea. Obviously, if you know early in a predicate that a cut will be required, THAT is the place to insert the cut. Such a predicate is not necessarily a good candidate for a deterministic declaration, if you use that as a substitute for the earlier cut. If, however, you know that the predicate can only generate one solution, it may make sense to declare it deterministic _in addition to_ the earlier cut, so that OTHER predicates may call it more efficiently. Gary
ok@quintus.UUCP (Richard A. O'Keefe) (05/16/88)
In article <6960007@hpfclp.SDE.HP.COM>, fritz@hpfclp.SDE.HP.COM (Gary Fritz) writes: > Obviously, if you know early in a predicate that a cut will be required, > THAT is the place to insert the cut. Such a predicate is not necessarily > a good candidate for a deterministic declaration, if you use that as a > substitute for the earlier cut. If, however, you know that the predicate > can only generate one solution, it may make sense to declare it deterministic > _in addition to_ the earlier cut, so that OTHER predicates may call it > more efficiently. > > Gary Agreed, it _may_ make sense. It's highly implementation dependent. On a WAM-based system like Quintus Prolog, SICStus Prolog, or SB-Prolog, it would not be a good idea. If the compiler were smart enough to figure out that the additional cuts weren't necessary, then it would be a good idea, but then you wouldn't _need_ the :- deterministic declaration (though it would remain as a valuable declaration of intent). (Functional dependencies such as Kamran Parsaye suggested years ago would be even better.)
voda@ubc-cs (Paul Voda) (05/16/88)
I guess I have to apologize to Gary Fritz, he indeed did not say that
HP Prolog's deterministic construct is a hack without a logic. This is what
I have concluded from what he has said about the deterministic construct
in the HP-Prolog. In the meantime it has been confirmed that the deterministic
construct is indeed implemented by inserting a cut at the end of each clause.
So hack it is!
I have been very careful in the design and implementation of Trilogy
to provide for the deterministic predicates in a sound way.
Such predicates are called procedures in Trilogy and they can be compiled
by tests and jumps without any choice points because Trilogy makes
sure they cannot backtrack.
So we have both an efficient implementation and logic!
But then the predicate
q(0).
q(1).
deterministic q
must be rejected by a sound Prolog and Trilogy indeed rejects:
proc Q(x:>I) iff x = 0 | x = 1 {x is OUTPUT}
although it accepts
proc Q(x:<I) iff x = 0 | x = 1 {x is INPUT}
The reason why q must be rejected is because in the output situations
it does not behave soundly. The logically true 'q(X),X=1' fails
whereas the equivalent 'q(1)' succeeds.
Gary writes:
>Hm. Certainly 'q(X), X = 2' requires backtracking, and would fail.
>However, 'q(2)' is a perfectly reasonable query, and *would* succeed.
>Therefore, is it necessary for a sound Prolog to reject the definition
>of 'q'?
Unfortunately a sound Prolog has to reject the definition because
both queries mean the same.
Paul Voda