[mercury-users] cc_multi question

[Fergus Henderson]

On 29-Nov-2002, Peter Ross <peter.ross at miscrit.be> wrote:
> Below is some code abstracted from the RTTI stuff that I am doing.
> (q = deconstruct) and (p = limited_deconstruct).  It was originally coded
> all coded up in C, so no Mercury compiler to make happy.  However with the
> mercury implementation I get the following error.  Can anyone help me on
> what the correct solution is?
> 
> The only thing I can think of is to use promise_only_solution, but that just
> doesn't feel right to me.
> 
> 
> % main.m:018: Error: call to predicate `main:q/2' with determinism `cc_multi'
> % main.m:018:   occurs in a context which requires all solutions.
> % For more information, try recompiling with `-E'.
> :- module main.
> 
> :- interface.
> 
> :- type t
> 	--->	f(int)
> 	;	g(int).
> 
> :- pred p(int::in, int::out) is cc_nondet.
> 
> :- implementation.
> 
> :- import_module int.
> 
> p(A, B) :-
> 	q(f(A), B),
> 	B < 5.
> 
> :- pred q(t::in, int::out) is cc_multi.
> 
> q(f(A), A).
> q(f(A), A+1).
> q(g(B), B).

In this case, there is a simple solution: add another mode for q
which has determinism `multi' rather than `cc_multi':

	:- pred q(t, int).
	:- mode q(in, out) is cc_multi.
	:- mode q(in, out) is multi.

If you want the same semantics as the original code, that's basically
the only solution.

In cases where the procedure q/2 that you are calling cannot feasibly
be implemented in a way that returns all possible solutions
(as is the case e.g. for `deconstruct' in the standard library
when called for a type with user-defined equality),
then there is no way to implement the declarative semantics specified
by the clauses for p/2.  If what you want is something that is
equivalent to what p/2 would do operationally, then you need to
change the interface to p/2 to return a `maybe'.

For example:

	:- pred p(int::in, maybe(int)::out) is cc_multi.
	p(A, R) :-
		q(f(A), B),
		( B < 5 ->
			R = yes(B)
		;
			R = no
		).

The consequence of this with regard to your original problem
(deconstruct and limited_deconstruct) is that there is an
interface design error in the definition of limited_deconstruct
and a few other procedures defined with determinism cc_nondet
in the Mercury standard library.
We will need to change the interface of limited_deconstruct_cc
in std_util.m and drop the cc_nondet modes of limited_deconstruct,
arg, and det_arg in deconstruct.m.  The current implementation
of those procedures in C code does not satisfy referential
transparency -- they will produce different results even for
inputs that are equal (but that have different representations).

In general, code which uses committed choice nondeterminism will
normally need to use `cc_multi' rather than `cc_nondet'.
`cc_nondet' can only be used in cases where the code which might
fail gets called *before* any code which needs committed choice
nondeterminism.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  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
--------------------------------------------------------------------------