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