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

[Andrew Bromage]

G'day all.

Peter Schachte wrote:

> Here's a scheme for doing determinism analysis at the same time you're
> doing the mode analysis.
> 
> First you compute a sort of "reference count" of each variable in the
> conjunction you're scheduling (a map from variables to the number of
> goals they appear in).  When you schedule a goal, you decrement the
> count for each variable appearing in the scheduled goal, so any
> variable with a zero reference count is dead.

We already currently do this, BTW.  It just happens to be well-hidden.

> 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.

> 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?

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

[Your other example, altered slightly.
	t(X) :- p(X, Y), q(Y, Z), r(Z).		]

> Using the usual operator precedence for `,', this is equivalent to
 
[	t(X) :- (p(X, Y), (q(Y, Z), r(Z))).	]

[...]
> so the parentheses-are-significant school of determism analysis
> determines that this is semidet.

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.  Using a
pseudo-HLDS notation:

	p, q, r => conj([p, q, r])

	p, (q, r) => conj([p, some(conj([q, r]))])

> In the parentheses-are-significant school, conjunction is effectively
> not associative.

It means that (p, q), r might be different from p, (q, r) which might be
different from (p, q, r).  But only for the purpose of analysis and even
then only if it actually makes a difference.

BTW, for the record, I'm not actually pushing this idea as a good
solution.  This is just another option to be thrown into the melting
pot.

Cheers,
Andrew Bromage