[mercury-users] Confused about "undefined behaviour" of promise_only_solution

Kral Stefan skral at mips.complang.tuwien.ac.at
Sat Nov 27 17:47:07 AEDT 2004

Hi All.

Thanks for all of your answers.

On Fri, 26 Nov 2004, Ralph Becket wrote:  
> Kral Stefan, Thursday, 25 November 2004:  
> > I'd like to commit to one particular solution of a 
> > non-deterministic predicate. I really do not care 
> > which one (first, last, or anything in between). [...]
> promise_only_solution should only be used when there really is only one
> solution, but the compiler can't infer this for itself.  
> If there are multiple solutions and you only want one of them, you 
> should give your predicate a determinism of cc_multi or cc_nondet rather
> than plain multi or nondet.  The `cc' stands for "committed choice" and 
> is a clean version of Prolog's cut. 
Sound like green cuts. However, I want to do something red, just like 
	( member(X, Xs), someTest(X) -> true ).

It's red, but not so bloody red, so I can fold the test into
member, yielding a semi-det predicate that uses higher-order
features, findfirstsuchthat(X,Xs,someTest).

But I am not too happy with that approach, either, because the actual
problem is a lot more complicated. 

Suppose, I want to write a committed-choice term rewriting system
(that does not give actual guarantees about the order in which rules
are tried), can I actually write nondeterministic code and then 
commit at every step or do I have to write a deterministic program
to do the job? (Representing rules as data, instead of being able 
to compile them into actual code.)

> > [...]
> [...]
> Ahh, it sounds as though what you want is user-defined equality.
> User-defined equality is useful where, say, you want to represent sets
> using unordered lists.  In this case you would like Mercury to recognise
> the following identities: [1, 2, 3] = [1, 3, 2] = [1, 1, 3, 1, 2] = ...
> You can do this by supplying your own equality predicate for your set
> type.  The reference manual section on this point is typically terse; if
> you want some help on this aspect of Mercury just ask on the mailing
> list.
That sounds very good, and like a lot of work.

The actual problem is about optimal instruction selection done by
a special purpose compiler. Defining equality over sequences of
instructions would require to consider the binding information of
variables occuring in these sequences. That's a lot of overhead.


Maybe I should reformulate my original question. 
My applications usually look something like this:
   p(S0,S) :-
	( multipart1(S0,S1) -> true ),	% some CC term-writing
	( multipart2(S2,S3) -> true ),	% some DFID for instr. sel.

Do I have to fundamentally restructure my application to do this
in Mercury? I have not yet understood the idea behind the
cc-modes. Does it all boils down to "Do not care that the 
program declaratively describes zillions of solutions, or
indeed does not terminate universally. Just declare 
everything non-deterministic as CC-nondet/CC-multi, 
and think of the program exit as some kind of red cut."?

Best Regards,

Stefan Kral			http://www.complang.tuwien.ac.at/skral/

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

More information about the users mailing list