Path: utzoo!attcan!uunet!lll-winken!lll-tis!ames!pasteur!ucbvax!decwrl!hplabs!hpda!hp-sde!hpfcdc!hpfclp!fritz
From: fritz@hpfclp.SDE.HP.COM (Gary Fritz)
Newsgroups: comp.lang.prolog
Subject: Re: Re: determinism, once etc, Trilogy
Message-ID: <6960007@hpfclp.SDE.HP.COM>
Date: 13 May 88 16:35:50 GMT
References: <2316@ubc-cs.UUCP>
Organization: HP SDE, Fort Collins, CO
Lines: 64

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