[m-dev.] from [mercury-users] Re: Question regarding determinism

[Peter Schachte]

On Mon, Sep 14, 1998 at 04:00:19PM +1000, Andrew Bromage wrote:

> > You also keep a list of
> > the output variables of nondet/multidet goals scheduled so far,
> 
> Which is, in general, impossible to tell while you're doing mode
> analysis if you haven't done determinism inference.

Ah, maybe I forgot to mention that I'm suggesting doing determinism
analysis at the same time you're doing mode analysis.  If you're doing
inference, I really think you should do it bottom-up one SCC at a
time, for efficiency, but it's not necessary for correctness.

> > and
> > remove from it any variable whose reference count becomes zero.  When
> > the list of nondet output variables is empty, the determinism is
> > det/semidet.  Furthermore, when you go to schedule a goal that can
> > only be called in a det/semidet context (due to uniqueness) at a point
> > where the clause is not det/semidet, you can delay scheduling it in
> > the usual way, so the scheduler uses both mode and determinism in
> > determining goal order.  This could be quite useful in handling
> > destructive modes for predicates.
> 
> I assume that the output vars of (semi)det goals whose inputs depend on
> nondeterministic outputs are also counted as nondeterminist output vars,
> right?

Oh, yeah, good point.  But this can be done with just the information
I'm talking about.

> OK, this could work, but I still think it needs the extra pass.

Why?  In fact, doing mode and determinism analysis at the same time
*avoids* one pass.  And gives a better determinism analysis.  Each
analysis contributes to the other, so they should be done together.

> Ah, you misunderstood me.
> 
> The parentheses-are-significant school of determinism analysis should
> not be confused with the implicit-parenthesis-that-Prolog-introduces-
> because-it-uses-an-operator-grammar-are-significant school.

The implicit parentheses have nothing to do with operator precedence
parsing.  There aren't really implicit parentheses, anyway; there's
just a nested structure of the terms that are read.  A grammar-based
parser would do the same.

So you're suggesting that parentheses introduce a new unary goal
constructor, like \+, called, say, scope/1, so a goal `a, b' would be
read as ','(a,b), while `(a,b)' would be read as scope(','(a,b))?

Doesn't sound real nice to me.

Anyway, you can still make a semidet predicate nondet just be adding a
semidet goal at the end:

	:- mode t(in) is semidet.
	:- mode p(in, out) is nondet.

	t(X) :- p(X, _).

is ok, but

	:- mode t(in, out) is semidet.
	:- mode p(in, out) is nondet.
	:- mode q(in, out) is semidet.

	t(X, Y) :- p(X, _), q(X, Y).

isn't.

-- 
Peter Schachte                | Apologists for Economic Darwinism seem to
mailto:pets at cs.mu.OZ.AU       | forget that the goal is maximum aggregate
http://www.cs.mu.oz.au/~pets/ | utility -- not just having the fittest
PGP: finger pets at 128.250.37.3 | corporations. -- me