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

[Peter Schachte]

On Mon, Sep 14, 1998 at 01:07:13PM +1000, Andrew Bromage wrote:
> > No reason you can't keep it reasonably simple and bottom-up and still
> > make it smarter.
> 
> I'm not convinced that you can avoid the O(n^2) hit for each conjunction
> of length n.

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.  You also keep a list of
the output variables of nondet/multidet goals scheduled so far, 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.

> > Anyway, this parenthses-are-significant approach means that you can
> > take a semidet clause body and make it nondet just by adding a semidet
> > goal at the end.  That doesn't seem like a good outcome.
> 
> Example please?

	t(X) :-
		p(X, Y),		% nondeterministically outputs `Y'
		q(Y, Z),		% outputs `Z'
		r(Z).			% texts `Z'

Using the usual operator precedence for `,', this is equivalent to

	t(X) :-
		(p(X, Y),		% nondeterministically outputs `Y'
		 (q(Y, Z),		% outputs `Z'
		  r(Z))).		% texts `Z'

so the parentheses-are-significant school of determism analysis
determines that this is semidet.  Now you notice that you always
follow calls to t(X) (which is semidet) with a call to s(X,O), which
is also semidet, so you edit the clause for t/1 just adding an output
argument and a semidet goal at the end:

	t(X,O) :-
		p(X, Y),		% nondeterministically outputs `Y'
		q(Y, Z),		% outputs `Z'
		r(Z),			% tests `Z'
		s(X,O).			% outputs O

which, sadly, is equivalent to

	t(X) :-
		(p(X, Y),		% nondeterministically outputs `Y'
		 (q(Y, Z),		% outputs `Z'
		  (r(Z),		% texts `Z'
		   s(X,O)))).		% outputs O

(which is nondet) rather than

	t(X) :-
		((p(X, Y),		% nondeterministically outputs `Y'
		  (q(Y, Z),		% outputs `Z'
		   r(Z)))		% texts `Z'
		 s(X,O)).		% outputs O

(which is semidet).

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


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