[mercury-users] Constraint puzzles - understanding how to go from Prolog to Mercury

[Daniel Patterson]

(sent this from the wrong address at first, hopefully this will go through and won't be a duplicate).

Wow, thanks! 

I think I'll need to look closely as the eqneq module to make the second one make total sense (I can understand why it works, but not _how_ it works), but the first one is great (and, in retrospect, it is obvious). 

On Sep 6, 2011, at 11:12 AM, Julien Fischer wrote:

> 
> Hi,
> 
> On Mon, 5 Sep 2011, Daniel Patterson wrote:
> 
>> An example used in The Art of Prolog (1986, page 216) is a puzzle that
>> follows the similar pattern of "There are N people, each who have a
>> different X, Y, and Z." followed by a series of clues that should
>> completely describe a unique solution (because of the constraints
>> about uniqueness). The prolog code they showed consisted of a series
>> of logical statements that amounted to that clue, and then further
>> logical statements to extract the desired information (the solution to
>> the puzzle).
>> 
>> In trying to translate this to Mercury, I ran into problems due to the
>> instantiatedness of some of the parts.
> 
> The current Mercury implementation does not support partial instantiation in a
> usable form -- from memory, it allows you to create partially instantiated
> structures but can't currently fill them in.
> 
> Also, note that Mercury does not (and will never) support Prolog style aliasing
> between free variables.
> 
>> I looked through the section of the reference manual on Solvers and the
>> corresponding paper by Becket et al from 2006, but I couldn't tell if that
>> was even talking about the type of problem I was trying to solve.
> 
> This problem can be solved using that approach provided you have a constraint
> solver that is expressive enough to describe the problem**.  (As it happens,
> there is simple solver in the Mercury samples directory that is sufficient
> -- see below.)
> 
> ** and efficient enough to find a solution in a reasonable amount of time.
> 
>> I also looked through the Prolog -> Mercury guide, but didn't notice anything
>> that pertained to these kind of problems.
>> 
>> Either way, the code I wrote (which was a simplified translation of
>> what was written in The Art of Prolog), was the following. This
>> problem involves the ranking of a programming competition between
>> three individuals from different countries who prefer different
>> sports. I've left out my attempts at writing the modes because none of
>> them worked!
> 
> ...
> 
>> The main problems seemed to arise from the fact that all of the predicates
>> were partially filling in the friends, so, for example, it would say that the
>> final instantiatedness was friend(ground,free,free), for example.
>> 
>> Are these types of problems solvable, and if so, how? Or does someone
>> have an example of the way that they have done it (it could be any
>> similar problem, not just this one)?
> 
> Here are two Mercury versions of this program: the first uses a generate-and-
> test style approach while the second uses a constrain-and-generate style
> approach using solver types.
> 
> (1)
> 
>    :- module puzzle1.
>    :- interface.
> 
>    :- import_module io.
> 
>    :- pred main(io::di, io::uo) is det.
> 
>    :- implementation.
> 
>    :- import_module list.
>    :- import_module solutions.
>    :- import_module string.
> 
>    main(!IO) :-
>        solutions(problem, Solns),
>        (
>            Solns = [],
>            io.write_string("No solutions.\n", !IO)
>        ;
>            Solns = [{Name, Sport}],
>            io.format("The Australian is %s.\n", [s(string(Name))], !IO),
>            io.format("Richard plays %s.\n", [s(string(Sport))], !IO)
>        ;
>            Solns = [_, _ | _],
>            io.write_string("Multiple solutions?", !IO)
>        ).
> 
>    :- type name ---> michael; richard; simon.
>    :- type nationality ---> american; australian; israeli.
>    :- type sport ---> tennis; basketball; cricket.
> 
>    :- type friend ---> friend(name, nationality, sport).
> 
>    :- pred problem({name, sport}::out) is nondet.
> 
>    problem({Name, Sport}) :-
>        friend(Friend1), friend(Friend2), friend(Friend3),
>        Friends = [Friend1, Friend2, Friend3],
> 
>        % Clue 1.
>        did_better(Man1Clue1, Man2Clue1, Friends),
>        name(Man1Clue1, michael),
>        sport(Man1Clue1, basketball),
>        nationality(Man2Clue1, american),
> 
>        % Clue 2.
>        did_better(Man1Clue2, Man2Clue2, Friends),
>        name(Man1Clue2, simon),
>        nationality(Man1Clue2, israeli),
>        sport(Man2Clue2, tennis),
> 
>        % Clue 3.
>        first(ManClue3, Friends),
>        sport(ManClue3, cricket),
> 
>        % Query: Who is the Australian?
>        list.member(Q1, Friends), name(Q1, Name), nationality(Q1, australian),
> 
>        % Query: What sport does Richard play?
>        list.member(Q2, Friends), name(Q2, richard), sport(Q2, Sport).
> 
>    :- pred friend(friend::out) is multi.
> 
>    friend(Friend) :-
>        ( Nationality = american
>        ; Nationality = australian
>        ; Nationality = israeli
>        ),
>        ( Sport = tennis
>        ; Sport = basketball
>        ; Sport = cricket
>        ),
>        ( Name = michael
>        ; Name = richard
>        ; Name = simon
>        ),
>        Friend = friend(Name, Nationality, Sport).
> 
>    :- pred did_better(friend::out, friend::out, list(friend)::in) is nondet.
> 
>    did_better(A, B, [A, B, _]).
>    did_better(A, C, [A, _, C]).
>    did_better(B, C, [_, B, C]).
> 
>    :- pred first(friend::out, list(friend)::in) is semidet.
> 
>    first(F, [F | _]).
> 
>    :- pred name(friend::in, name::out) is det.
> 
>    name(friend(Name, _, __), Name).
> 
>    :- pred nationality(friend::in, nationality::out) is det.
> 
>    nationality(friend(_, Nationality, _), Nationality).
> 
>    :- pred sport(friend::in, sport::out) is det.
> 
>    sport(friend(_, _, Sport), Sport).
> 
>    :- end_module puzzle1.
> 
> (2)
> 
> This version of the program uses solver types, in particular it uses the
> eqneq/1 solver type that is provided by the eqneq module in the Mercury samples.
> (In the directory samples/solver_types.)  The program needs to be compiled in
> a grade that supports trailing (e.g. asm_fast.gc.trseg or hlc.gc.trseg).
> 
> Some caveats:
> 
>  (i)   the search (labelling) strategy used here is pretty naive.
>  (ii)  explicitly posting the constraint that each friend has a different
>        name, plays a different sport, etc would reduce the size of the
>        search space.
>  (iii) the eqneq solver is only intended as an example, while it's fine
>        for small problems, it won't scale terribly well.
> 
>    :- module puzzle2.
>    :- interface.
> 
>    :- import_module io.
> 
>    :- pred main(io::di, io::uo) is det.
> 
>    :- implementation.
> 
>    :- import_module eqneq.
> 
>    :- import_module list.
>    :- import_module solutions.
>    :- import_module string.
> 
>    main(!IO) :-
>        solutions(problem, Solns),
>        (
>            Solns = [],
>            io.write_string("No solutions.\n", !IO)
>        ;
>            Solns = [{Name, Sport}],
>            io.format("The Australian is %s.\n", [s(string(Name))], !IO),
>            io.format("Richard plays %s.\n", [s(string(Sport))], !IO)
>        ;
>            Solns = [_, _ | _],
>            io.write_string("Multiple solutions?", !IO)
>        ).
> 
>    :- type nationality ---> american ; australian ; israeli.
>    :- type sport ---> tennis ; basketball ; cricket.
>    :- type name ---> michael ; richard ; simon.
> 
>    :- type friend(Name, Nationality, Sport)
>        --->    friend(Name, Nationality, Sport).
> 
>    :- inst friend(I) == bound(friend(I, I, I)).
> 
>    :- type friend_var == friend(eqneq(name), eqneq(nationality), eqneq(sport)).
>    :- type friend_vars == list(friend_var).
> 
>    :- type friend_value == friend(name, nationality, sport).
>    :- type friend_values == list(friend_value).
> 
>    :- pred friend(friend_var::out(friend(any))) is det.
> 
>    friend(Friend) :-
>        eqneq.new(Name),
>        eqneq.new(Nationality),
>        eqneq.new(Sport),
>        Friend = friend(Name, Nationality, Sport).
> 
>    :- pred problem({name, sport}::out) is nondet.
> 
>    problem({Name, Sport}) :-
>        friend(FriendVar1), friend(FriendVar2), friend(FriendVar3),
>        FriendVars = [FriendVar1, FriendVar2, FriendVar3],
> 
>        % Clue 1.
>        did_better(Man1Clue1, Man2Clue1, FriendVars),
>        name(Man1Clue1, michael),
>        sport(Man1Clue1, basketball),
>        nationality(Man2Clue1, american),
> 
>        % Clue 2.
>        did_better(Man1Clue2, Man2Clue2, FriendVars),
>        name(Man1Clue2, simon),
>        nationality(Man1Clue2, israeli),
>        sport(Man2Clue2, tennis),
> 
>        % Clue 3.
>        first(ManClue3, FriendVars),
>        sport(ManClue3, cricket),
> 
>        % Search.
>        label(FriendVars, FriendValues),
> 
>        % Query: Who is the Australian?
>        list.member(friend(Name, australian, _), FriendValues),
> 
>        % Query: What sport does Richard play?
>        list.member(friend(richard, _, Sport), FriendValues).
> 
>    :- pred did_better(friend_var::out(friend(any)), friend_var::out(friend(any)),
>        friend_vars::in(list(friend(any)))) is nondet.
> 
>    did_better(A, B, [A, B, _]).
>    did_better(A, C, [A, _, C]).
>    did_better(B, C, [_, B, C]).
> 
>    :- pred first(friend_var::out(friend(any)),
>        friend_vars::in(list(friend(any)))) is semidet.
> 
>    first(F, [F | _]).
> 
>    :- pred name(friend_var::in(friend(any)), name::in) is semidet.
> 
>    name(friend(NameVar, _, _), Name) :-
>        eqneq.bind(NameVar, Name).
> 
>    :- pred nationality(friend_var::in(friend(any)), nationality::in) is semidet.
> 
>    nationality(friend(_, NationalityVar, _), Nationality) :-
>        eqneq.bind(NationalityVar, Nationality).
> 
>    :- pred sport(friend_var::in(friend(any)), sport::in) is semidet.
> 
>    sport(friend(_, _, SportVar), Sport) :-
>        eqneq.bind(SportVar, Sport).
> 
>    :- pred label(friend_vars::in(list(friend(any))), friend_values::out) is nondet.
> 
>    label([], []).
>    label([FriendVar | FriendVars], [FriendValue | FriendValues]) :-
>        label_friend(FriendVar, FriendValue),
>        label(FriendVars, FriendValues).
> 
>    :- pred label_friend(friend_var::in(friend(any)), friend_value::out) is nondet.
> 
>    label_friend(Var, Value) :-
>        Var = friend(NameVar, NationalityVar, SportVar),
>        ( NameValue = michael
>        ; NameValue = richard
>        ; NameValue = simon),
>        eqneq.bind(NameVar, NameValue),
>        ( NationalityValue = american
>        ; NationalityValue = australian
>        ; NationalityValue = israeli
>        ),
>        eqneq.bind(NationalityVar, NationalityValue),
>        ( SportValue = tennis
>        ; SportValue = basketball
>        ; SportValue = cricket
>        ),
>        eqneq.bind(SportVar, SportValue),
>        Value = friend(NameValue, NationalityValue, SportValue).
> 
>    :- end_module puzzle2.
> 
> Julien.
> --------------------------------------------------------------------------
> mercury-users mailing list
> Post messages to:       mercury-users at csse.unimelb.edu.au
> Administrative Queries: owner-mercury-users at csse.unimelb.edu.au
> Subscriptions:          mercury-users-request at csse.unimelb.edu.au
> --------------------------------------------------------------------------


--------------------------------------------------------------------------
mercury-users mailing list
Post messages to:       mercury-users at csse.unimelb.edu.au
Administrative Queries: owner-mercury-users at csse.unimelb.edu.au
Subscriptions:          mercury-users-request at csse.unimelb.edu.au
--------------------------------------------------------------------------