[m-dev.] parallel conjunction

[Fergus Henderson]

On 27-Sep-2000, Ralph Becket <rbeck at microsoft.com> wrote:
> >From Fergus Henderson on 27/09/2000 15:08:06
> > 
> > Another alternative would be to document `&' as a standard feature
> > equivalent to `,' with no additional restrictions on modes or
> > determinism -- just a hint to the implementation to try parallelizing
> > things here.  The implementation would then have to issue warnings
> > rather than errors if its implementation-specific restrictions are not
> > met, and to treat such parallel conjunctions which don't meet its
> > restrictions as if they were ordinary conjunctions.
> 
> This one sounds about right to me.
> 
> > The disadvantage of this approach is that it would require changes
> > to the current implementation, and that you'd only get warnings
> > rather than errors.  The advantage is that it would ensure portability
> > of programs using parallel conjunction to implementations (or grades ;-)
> > that don't support real parallelism.
> 
> How much of a change to the current implementation would be required?

Quite a bit more than I first thought.  I though the only change
required would be to change the errors into warnings.  But it turns
out to be more difficult than that.

The problem is with the treatment of unique modes,
which are handled differently for `&' and `,'.
The issue arises when you have code such as

	:- mode p(di).
	:- mode q(ui).
	:- mode r(ui).
	:- mode s(di).

	p(X) :- (q(X) & r(X)), s(X).

This is a unique mode error, since the variable `X'
is marked as shared in the parallel conjunction.
However, if you substitute `,' in place of `&', this code is allowed.
The difficulty is that the mode error only occurs at the call
to s(X), not at the parallel conjunction.  So to
handle cases like this, if we adopt the naive approach,
we'd need to create a choice point (or something equivalent)
when processing each parallel conjunction, and then backtrack
whenever we got a mode error.  This could easily lead to
exponential performance for code involving multiple parallel
conjunctions.

The reason that such variables are marked as shared when using `&' is
to prevent problems with code such as

	p(X) :- (q(X) & s(X)).

If such code was allowed, the variable X might get clobbered
by the call to s(X) before the call to p(X) had finished,
which would be a problem, since p(X) might still be using it.
Marking the variable X as shared at the start of the
parallel disjunction ensures that this code is illegal,
since s(X) requires its argument to be unique.

However, I guess that situation could be handled differently, by
locking the variables in question against destructive update, similar
to the way that we lock non-local variables against being bound when
we're inside a negation, rather than marking them as shared.
The difference is that after `(q(X) & r(X))', X would remain
unique, rather than being marked as shared.

But doing that would be a non-trivial task.
Doing it that way might also complicate reuse analysis.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------