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

[Andrew Bromage]

G'day all.

Peter Schachte wrote:

> > Determinism analysis currently has the benefit of being a nice, simple
> > bottom-up analysis.  I'd much prefer to keep it like that, if only to
> > make it easier on the next Mercury implementation.
> 
> 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.

> > I think the case above is a Prolog syntax bug.  Conjunctions should nest
> > as the programmer stated they'd nest rather than as Prolog parses them.
> 
> I thought conjunction was supposed to be commutative and associative?

And so it is.  By nesting conjunctions as the programmer writes them,
the _inferred_ determinism changes, though the _actual_ determinism
(to which the inferred determinism is a "safe" approximation) stays the
same.

And, indeed, you'd just inline the conjunctions if it turned out that
the extra scopes didn't make a difference.

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

> > Of course, it could be argued that the programmer should be obliged to
> > write it as some [Z] (q, r) if they want a better determinism.
> 
> So you want to throw out the rule that variables are quantified in
> their closest enclosing scope?  I find that quite a natural and
> convenient rule.

Actually I'm trying to support that rule by giving the programmer a
more natural way to declare a scope, simply by adding parentheses.
"Making the determinism analysis smarter" would involve the compiler
introducing new scopes, thus making it unclear what a scope actually
is.

> Personally, if I wrote
> 
> 	:- mode t(in, out).
> 	t(X, O) :-
> 		p(X, Y),		% outputs `Y'
> 		q(Y, Z),		% outputs `Z'
> 		r(Z),			% texts `Z'
> 		s(O).			% outputs `O'.
[...]
> You'd have to write:
> 
> 	t(X, O) :-
> 		( p(X, Y), ( q(Y, Z), r(Z) )),
> 		s(O).			% outputs `O'.

You wouldn't have to.  You could also write:

	t(X, O) :-
		( p(X, Y), q(Y, Z), r(Z) ),
		s(O).

Which is really a shorthand for:

	t(X, O) :-
		some [Y, Z] ( p(X, Y), q(Y, Z), r(Z) ),
		s(O).

Cheers,
Andrew Bromage