# [mercury-users] Better way of writing this?

Peter Hawkins peter at hawkins.emu.id.au
Thu Jun 30 14:16:22 AEST 2005

```Hi...

I brought this up with people earlier today, but the verdict was I
should send email to mercury-users (like this one). I'm trying to write
code to find maximal weighted Hamming codes using the new set solver,
and I can't think of a better way of writing a particular piece of code
than an exceedingly ugly method. The problem is described on pages 30
and 31 of http://www.hawkins.emu.id.au/papers/hons_thesis.pdf.

Here is the relevant predicate:

% Warning: ** highly odd Mercury code follows **
% optimize finds a maximal set of codewords satisfying the other
% constraints. In order to do this, we repeatedly leave choicepoints,
% attempt to solve the problem for a particular size and then fail back
% to the unlabelled state. We pass back the solution we found (if
any) via
% a non-backtrackable reference. If we found a solution, we then attempt
% to find a larger solution recursively.
%
% Note that this predicate has a 'failure' determinism. It always fails!
% It works its magic through impure side-effects.
:- impure pred optimize(list(cset)::ia, labelling_options::in,
int::in, int::in, int::in, int::in,
nb_reference(list(set(int)))::in,
nb_reference(bool)::in) is failure.
optimize(Vars, LabellingOpts, S, B, D, W, SolnRef, OptimalRef) :-
% We really want an impure IO predicate, so we use the
unsafe_io_state
% from unsafe.m
io.format("Searching for solution with %d variables.\n",
[i(S)], unsafe_io_state, _),

% Disjunction to leave a choicepoint
(
(if (propagate(Vars), labelling(Vars, LabellingOpts)) then
% Found a solution to this instance. Save the solution,
% and then fail back to the outer choicepoint in order to
% try the next-largest case.
impure update(SolnRef, Code)
else
% We had a labelling failure, so clearly the previous
% solution we found was optimal.
impure update(OptimalRef, yes)
),
fail
;
% Only execute this disjunct if we succeeded in finding a
% solution to the last labelling. If we failed, then we would
% have set OptimalRef to yes.
semipure value(OptimalRef, no),

% Add a new variable and the corresponding constraints
NV = n_bit_cset(B),
(if W > 0 then card(NV, W) else true),
post_constraint_list(anylist.map(inter_constraint(B, D, NV), Vars)),

% Recurse
impure optimize([NV | Vars], LabellingOpts, S + 1, B, D, W, SolnRef,
OptimalRef)
).

Any suggestions? (I'm hoping the code is self-explanatory, but I can
provide further explanation of what it's doing if needed. I'm assuming a
passing familiarity with finite-domain constraint solvers).

Note that create new variables is not 'free', and we want to reuse
constraint variables if at all possible. (Here new variables are created
by n_bit_cset/1).

=)
Peter

--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au