Path: utzoo!mnetor!uunet!seismo!sundc!pitstop!sun!quintus!ok
From: ok@quintus.UUCP (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: determinism, once etc, Trilogy
Message-ID: <923@cresswell.quintus.UUCP>
Date: 1 May 88 09:45:30 GMT
References: <2715@mulga.oz> <2316@ubc-cs.UUCP>
Organization: Quintus Computer Systems, Mountain View, CA
Lines: 47
Keywords: one deterministic logic

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?