[mercury-users] determinism suprises

[Fergus Henderson]

On 07-Dec-2000, William Lee Irwin III <wli at holomorphy.com> wrote:

> Another "catch" I found was the following:
> 
> :- pred color(squareindex, color).
> :- mode color(in, out) is det.
> :- mode color(in, in) is semidet.
> :- mode color(out, in) is multi.
> color({File, Rank}, Color) :-
>    file_parity(File, FileParity),
>    rank_parity(Rank, RankParity),
>    add_parity(FileParity, RankParity, Residue),
>    parity_to_color(Residue, Color).
> 
> Now, file_parity, rank_parity, and parity_to_color have all the
> necessary modes and determinisms to allow all of color's modes and
> determinisms given the appropriate ordering of conjunctions, but I
> still found that the reordering was not done for each mode:
> 
> board.m:018: In `color(out, in)':
> board.m:018:   error: determinism declaration not satisfied.
> board.m:018:   Declared `multi', inferred `nondet'.
> board.m:167:   call to `parity_to_color(in, in)' can fail.
> 
> So I tried to reorder the conjunction as follows:
> 
> color({File, Rank}, Color) :-
>     parity_to_color(Residue, Color),
>     add_parity(FileParity, RankParity, Residue),
>     file_parity(File, FileParity),
>     rank_parity(Rank, RankParity).
> 
> but this runs into the following error:
> board.m:016: In `color(in, out)':
> board.m:016:   error: determinism declaration not satisfied.
> board.m:016:   Declared `det', inferred `nondet'.
> board.m:164:   call to `parity_to_color(out, out)' can succeed more than once.
> board.m:165:   call to `add_parity(out, out, in)' can succeed more than once.
> board.m:166:   call to `file_parity(in, in)' can fail.
> board.m:167:   call to `rank_parity(in, in)' can fail.

and then in a subsequence mail

> :- pred add_parity(parity, parity, parity).
> :- mode add_parity(in, in, out) is det.
> :- mode add_parity(in, out, in) is det.
> :- mode add_parity(out, in, in) is det.
> :- mode add_parity(in, in, in) is semidet.
> :- mode add_parity(out, out, in) is multi.
> :- mode add_parity(out, in, out) is multi.
> :- mode add_parity(in, out, out) is multi.
> :- mode add_parity(out, out, out) is multi.
> add_parity(even, even, even).
> add_parity(even, odd, odd).
> add_parity(odd, even, odd).
> add_parity(odd, odd, even).

The problem here is essentially that you have declared *too many* modes
for the called predicates `add_parity', `file_parity', and `rank_parity'.

In general, you should not declare modes for predicates in which they
produce values for output arguments that are unconstrained, as is the
case for all the modes of `add_parity' that have determinism `multi'.
Instead, you should use the "constrain and then generate" paradigm.
You should omit declarations for those modes, and instead use an
explicit generator predicate, e.g. `gen_parity', to generate
unconstrained values.

	:- pred gen_parity(parity).
	:- mode gen_parity(in) is det.
	:- mode gen_parity(out) is multi.
	gen_parity(even).
	gen_parity(odd).

Code which needs to generate values should first call all the
predicates which impose constraints, and then finally call a generator
to generate values for values which remain unconstrained:

	color({File, Rank}, Color) :-
		% first apply the constraints
		file_parity(File, FilePar),
		rank_parity(Rank, RankPar),
		add_parity(FilePar, RankPar, Res),
		parity_to_color(Res, Color),

		% then generate any values which haven't
		% been determined by the constraints
		gen_parity(FilePar).

I enclose below a patch to your example code which uses this idiom and
which the Mercury compiler will happily accept.

--- old/pathology.m	Sat Dec  9 19:56:40 2000
+++ ./pathology.m	Sat Dec  9 20:12:01 2000
@@ -18,7 +18,6 @@
 :- mode rank_parity(in, in) is semidet.
 :- mode rank_parity(in, out) is det.
 :- mode rank_parity(out, in) is multi.
-:- mode rank_parity(out, out) is multi.
 rank_parity(first, odd). rank_parity(second, even). rank_parity(third, odd).
 rank_parity(fourth, even). rank_parity(fifth, odd). rank_parity(sixth, even).
 rank_parity(seventh, odd). rank_parity(eighth, even).
@@ -27,7 +26,6 @@
 :- mode file_parity(in, in) is semidet.
 :- mode file_parity(in, out) is det.
 :- mode file_parity(out, in) is multi.
-:- mode file_parity(out, out) is multi.
 file_parity(a,odd). file_parity(b,even). file_parity(c,odd).
 file_parity(d,even). file_parity(e,odd).
 file_parity(f,even). file_parity(g,odd). file_parity(h,even).
@@ -36,7 +34,6 @@
 :- mode parity_to_color(in, in) is semidet.
 :- mode parity_to_color(in, out) is det.
 :- mode parity_to_color(out, in) is det.
-:- mode parity_to_color(out, out) is multi.
 parity_to_color(even, black).
 parity_to_color(odd, white).
 
@@ -45,26 +42,25 @@
 :- mode add_parity(in, out, in) is det.
 :- mode add_parity(out, in, in) is det.
 :- mode add_parity(in, in, in) is semidet.
-:- mode add_parity(out, out, in) is multi.
-:- mode add_parity(out, in, out) is multi.
-:- mode add_parity(in, out, out) is multi.
-:- mode add_parity(out, out, out) is multi.
 add_parity(even, even, even).
 add_parity(even, odd, odd).
 add_parity(odd, even, odd).
 add_parity(odd, odd, even).
 
-% What this really should have been was:
-% color({File, Rank}, Color) :-
-%	parity_to_color(Res, Color),
-%	add_parity(FilePar, RankPar, Res),
-%	file_parity(File, FilePar),
-%	rank_parity(Rank, RankPar).
-% but its determinism could not be correctly inferred by the compiler.
 color({File, Rank}, Color) :-
+	% first apply the constraints
 	file_parity(File, FilePar),
 	rank_parity(Rank, RankPar),
 	add_parity(FilePar, RankPar, Res),
-	parity_to_color(Res, Color).
+	parity_to_color(Res, Color),
+	% then generate any values which haven't
+	% been determined by the constraints
+	gen_parity(FilePar).
+
+:- pred gen_parity(parity).
+:- mode gen_parity(in) is det.
+:- mode gen_parity(out) is multi.
+gen_parity(even).
+gen_parity(odd).
 
 :- end_module pathology.
-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------