[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 Code = map_impure(ask_value_det, Vars),
            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
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