Path: utzoo!mnetor!uunet!ncc!alberta!ubc-cs!voda
From: voda@ubc-cs (Paul Voda)
Newsgroups: comp.lang.prolog
Subject: Re: determinism, once etc, Trilogy
Message-ID: <2316@ubc-cs.UUCP>
Date: 30 Apr 88 22:38:13 GMT
References: <2715@mulga.oz>
Sender: nobody@ubc-cs.UUCP
Reply-To: voda@ubc-cs.UUCP (Paul Voda)
Organization: UBC Department of Computer Science, Vancouver, B.C., Canada
Lines: 109
Keywords: one deterministic logic


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.