[mercury-users] Emacs mode; a_solution?

[Fergus Henderson]

On 03-Jan-2002, Ralph Becket <rafe at cs.mu.OZ.AU> wrote:
> Douglas Michael Auclair, Thursday,  3 January 2002:
> > * Is there a method to solving a system of equations (m variables over
> > n equations, m <= n)?  Not talking CLP, as there is only one solution
> > over the systems I'm working ... I get unbound errors when I try:
> > 
> > system_of_eqns(A, B) :-  2 * A + B = 5, A - B = 7.
> 
> The Mercury modes for integer addition and subtraction work where any
> two of the three arguments are inputs (this isn't true for
> multiplication or floats).  However, there's no way of reordering your
> goals to satisfy the two-input requirement, which is why Mercury is
> reporting an error.
> 
> You could implement Gaussian elimination, I suppose.

Doing something like that is going to be the most efficient approach.

A less efficient but simpler alternative would be to use a
generate-and-test strategy or a constrain-and-then-generate strategy.
This requires knowing a suitable range for the values of the variables.

For example, if you know that the values of A and B will both be
between -100 and 100, you could write this system_of_eqns/2 as

	:- pred system_of_eqns(int::out, int::out) is nondet.
	system_of_eqns(A, B) :- 
		2 * A + B = 5,
		A - B = 7,
		between(-100, 100, A),
		between(-100, 100, B).

	%
	% between(Min, Max, X):
	% X is between Min and Max inclusive
	%
	:- pred between(int, int, int).
	:- mode between(in, in, in) is semidet.
	:- mode between(in, in, out) is nondet.
	:- pragma promise_pure(between/3).
	between(Min::in, Max::in, X::in) :-
		X >= Min,
		X =< Max.
	between(Min::in, Max::in, X::out) :-
		( Min = Max ->
			X = Min
		;
			Min < Max,
			(
				X = Min
			;
				Min1 is Min + 1,
				between(Min1, Max, X)
			)
		).

This code makes use of mode-specific clauses, which is a new feature in
the latest development versions of Mercury; for Mercury 0.10, you can
write it like this instead:

	:- pred system_of_eqns(int::out, int::out) is nondet.
	system_of_eqns(A, B) :-
		2 * A + B = 5,
		A - B = 7,
		between_generate(-100, 100, A),
		between_check(-100, 100, B).

	:- pred between_check(int, int, int).
	:- mode between_check(in, in, in) is semidet.
	between_check(Min, Max, X) :-
		X >= Min,
		X =< Max.

	:- pred between_generate(int, int, int).
	:- mode between_generate(in, in, out) is nondet.
	between_generate(Min, Max, X) :-
		( Min = Max ->
			X = Min
		;
			Min < Max,
			(
				X = Min
			;
				Min1 is Min + 1,
				between_generate(Min1, Max, X)
			)
		).

> > * Writing of CLP ... is constraints.m available for hacking on (I saw
> > mention of it in an archive)?

I'm not sure what you're referring to here.  There is a module
`compiler/constraint.m' which is included in the Mercury compiler
source distribution, but I don't think that is what you're after.

The source code for the Mercury modules which implement the CLP(R) interface is
available -- they are in the files clpr/*.m in the mercury-extras distribution.

> > I saw the CLP(R) implementation in the
> > extras package with the associated warnings.  I was wondering if there
> > was an open-source, freely-usable implementation to work on and to
> > use.

I believe there are open-source, freely-usable constraint packages
written in C (for a list, try asking on the comp.constraints newsgroup),
and it would be possible to write a Mercury interface to one of these,
using the same approach as is used in the Mercury interface to CLP(R).

-- 
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
--------------------------------------------------------------------------