mercury and determinism

[Thomas Charles CONWAY]

Henk, you write:
> Any particular reason for the following:
> 
> 
> :- module little.
> :- interface.
> :- type t.
> :- pred p(t,t).
> :- mode p(in, out) is det.
> :- pred q(t,t).
> :- mode q(in, out) is det.
> :- implementation.
> :- import_module int.
> 
> :- type t ---> a;b(int).
> 
> 
> p(X, Y):-
> 	(X=a, Y=b(0);
> 	 X=b(N), N1 is N +5, Y=b(N1)
> 	).
> 
> q(X, Y):-
> 	( X = a -> Y=b(0);
> 	  X = b(N), N1 is N + 5, Y = b(N1)
> 	).
> 
> %------------------------------------------------------------------------
> 
> 
> $ mc little.m
> little.m:007: In `q(in, out)':
> little.m:007:   error: determinism declaration not satisfied.
> little.m:007:   Declared `det', inferred `semidet'.
> little.m:021:   Unification of `X' and `b(N)' can fail.
> For more information, try recompiling with `-E'.
> $
> 
> Because I'd like to reuse my code in Prolog, I prefer the definition of
> q above the one of p. There could be some serious efficiency-problems
> in some Prolog-implementations  with the first one.
> 

Indeed. This is one of the [many] ways in which Mercury's performance
model is very different to Prolog's.

The reason that q/2 gets the determinism error is that the information
from the failure of the condition (ie X wasn't bound to `a') isn't
propagated to the else. It is something that we've talked about before -
that we don't turn if-then-else's (or more importantly, chains of if-then-
else's) into switches automatically. I'll put it onto the todo list, but
I don't expect anything to happen in the near future.

If it is important that your code have good performance both for Mercury
and Prolog then you could write your code in the way that most Prolog
implementations will index properly:

r(a, b(0).
r(b(N), b(N1)) :-
	N1 is N + 5.

In fact, the Mercury compiler will produce identical code for p/2 and r/2;
the compiler transforms code like r/2 into code like p/2 during compilation.

The situation where things become more annoying is when you write code
like:

:- pred s(list(string), maybe(string)).
:- mode s(in, out) is det.

s([], no).
s([Str], yes(Str)).
s([_|Strs], MaybeStr) :-
	Strs = [_|_],
	s(Strs, MaybeStr).

In Mercury, this becomes a two level switch, so indexing does the right
thing, and the code is deterministic (note though that the unification
of Strs with cons is necessary to make the 2nd and 3rd clauses mutually
exclusive). To make the Prolog version deterministic so that it doesn't
leave a choice-point behind it is usually necessary to introduce an
extra predicate:

s([], no).
s([Str|Strs], MaybeStr) :-
	t(Strs, Str, MaybeStr).

t([], Str, yes(Str)).
t([Str|Strs], _, MaybeStr) :-
	t(Strs, Str, MaybeStr).

In this instance, it is a bit painful writing code that is efficient
in Prolog, but is valid Mercury too, because (unless you have type
and mode inference on) you have to write the extra pred and mode
declarations. <sigh> I guess that's the way it goes.

On the other hand, if you're using Mercury now, it might not be
important to keep the code so it is really efficient in Prolog.

Thomas
-- 
Thomas Conway               				      conway at cs.mu.oz.au
AD DEUM ET VINUM	  			      Every sword has two edges.