Determinism case

Fergus Henderson fjh at cs.mu.OZ.AU
Sat Feb 27 05:46:49 AEDT 1999


On 26-Feb-1999, Gustavo A. Ospina <gos at info.fundp.ac.be> wrote:
> I'm trying to test the behaviour of Mercury translating specifications with
> universal quantifiers. One of these tests is this procedure who computes
> the minimum element of an integer list:
> 
> minlist(L,M) :-
> 	list__member(M,L),
> 	all [X] (list__member(X,L) => M =< X).
> 
> The mode declaration is :- mode minlist(in,out) is nondet. I can't declare
> it 'det' because the compiler rejects this with a mode error (infers
> 'nondet').

Right.  That's because operationally it can return multiple copies
of the same solution.  The compiler is not smart enough to figure out
that the different solutions returned will all be equal.

> Anyway, I checked that this procedure has only one solution using
> 'solutions', and can be used in procedures (like 'main', being declared as
> cc_multi)  with an if-then-else.

An alternative to using `solutions' is to use `promise_only_solution'
(defined in the `builtin' library module), e.g.

:- mode minlist(in, out) is semidet.
minlist(L,M) :-
	M = promise_only_solution(minlist_2(L)).

:- mode minlist_2(in, out) is cc_nondet.
minlist_2(L,M) :-
 	list__member(M,L),
 	all [X] (list__member(X,L) => M =< X).

In general, using `promise_only_solution' may be more efficient than
using `solutions'; on the other hand, using `solutions' does allow you
to check at runtime that there really is only one solution, whereas
with `promise_only_solution' you don't get even runtime checking.

(In this particular case, of course, if efficiency is of concern then
you should be using an O(N) algorithm rather than the above O(N**2)
algorithm.)

The `promise_only_solution' approach is also useful because,
unlike `solutions', this approach also works when the compiler
infers `cc_nondet'.

> This is not a criticism to the Mercury determinism analyzer, I want just to
> show a case (rare) in that fails this analysis. In fact, the compiler help
> me to make work well this example with their error messages.

Thanks for the feedback.

Cheers,
	Fergus.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "Binaries may die
WWW: <http://www.cs.mu.oz.au/~fjh>  |   but source code lives forever"
PGP: finger fjh at 128.250.37.3        |     -- leaked Microsoft memo.



More information about the users mailing list