[mercury-users] Constraint puzzles - understanding how to go from Prolog to Mercury
Julien Fischer
juliensf at csse.unimelb.edu.au
Wed Sep 7 01:12:08 AEST 2011
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
--------------------------------------------------------------------------
More information about the users
mailing list