[m-rev.] diff: cleanups for solver types example
Julien Fischer
juliensf at csse.unimelb.edu.au
Tue Dec 7 15:38:15 AEDT 2010
Branches: main
samples/solver_types/eqneq.m:
samples/solver_types/sudoku.m:
samples/solver_types/test_eqneq.m:
Add feature set pragmas that specify that trailing is required.
Make it impossible for the labelling predidate to be reordered
so that it is called before the constraints are posted.
Minor formatting fixes.
Julien.
Index: eqneq.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/samples/solver_types/eqneq.m,v
retrieving revision 1.2
diff -u -r1.2 eqneq.m
--- eqneq.m 31 Oct 2007 04:27:29 -0000 1.2
+++ eqneq.m 7 Dec 2010 04:32:41 -0000
@@ -1,20 +1,19 @@
%-----------------------------------------------------------------------------%
-% eqneq.m
-% Ralph Becket <rafe at csse.unimelb.edu.au>
-% Fri Feb 9 13:31:22 EST 2007
% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
+%-----------------------------------------------------------------------------%
+%
+% Author: Ralph Becket
%
% Simple solver type supporting equality and disequality constraints.
%
%-----------------------------------------------------------------------------%
:- module eqneq.
-
:- interface.
:- import_module list.
-
+%-----------------------------------------------------------------------------%
% An eqneq(T) variable may be bound to a ground value of type T or it may
% be unbound. Equality and disequality constraints may be posted between
@@ -58,6 +57,10 @@
:- import_module set.
:- import_module univ.
+:- pragma require_feature_set([trailing]).
+
+%-----------------------------------------------------------------------------%
+
% An eqneq is represented by an eqneq_id, which is a key in the
% mutable constraint_store map.
%
@@ -126,14 +129,13 @@
% short).
%
:- pred deref(constraint_store::in, eqneq_id::in, eqneq_id::out,
- eqneq_rep::out, int::out) is det.
+ eqneq_rep::out, int::out) is det.
deref(ConstraintStore, EqNeqId0, EqNeqId, EqNeqRep, Depth) :-
deref_2(ConstraintStore, EqNeqId0, EqNeqId, EqNeqRep, 0, Depth).
-
:- pred deref_2(constraint_store::in, eqneq_id::in, eqneq_id::out,
- eqneq_rep::out, int::in, int::out) is det.
+ eqneq_rep::out, int::in, int::out) is det.
deref_2(ConstraintStore, EqNeqId0, EqNeqId, EqNeqRep, Depth0, Depth) :-
EqNeqRep0 = ConstraintStore ^ det_elem(EqNeqId0),
@@ -354,19 +356,17 @@
%-----------------------------------------------------------------------------%
all_different([]).
-
all_different([X | Xs]) :-
all_different_2(X, Xs),
all_different(Xs).
-
:- pred all_different_2(eqneq(T)::ia, list(eqneq(T))::ia) is semidet.
all_different_2(_, []).
-
all_different_2(X, [Y | Ys]) :-
neq(X, Y),
all_different_2(X, Ys).
%-----------------------------------------------------------------------------%
+:- end_module eqneq.
%-----------------------------------------------------------------------------%
Index: sudoku.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/samples/solver_types/sudoku.m,v
retrieving revision 1.1
diff -u -r1.1 sudoku.m
--- sudoku.m 15 Feb 2007 00:27:17 -0000 1.1
+++ sudoku.m 7 Dec 2010 04:32:41 -0000
@@ -1,22 +1,19 @@
%-----------------------------------------------------------------------------%
-% sudoku.m
-% Ralph Becket <rafe at csse.unimelb.edu.au>
-% Fri Feb 9 15:03:53 EST 2007
% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
+%-----------------------------------------------------------------------------%
+%
+% Author: Ralph Becket
%
% Sudoku test case for the eqneq type.
%
%-----------------------------------------------------------------------------%
:- module sudoku.
-
:- interface.
:- import_module io.
-
-
-:- pred main(io :: di, io :: uo) is cc_multi.
+:- pred main(io::di, io::uo) is cc_multi.
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
@@ -28,6 +25,8 @@
:- import_module list.
:- import_module string.
+:- pragma require_feature_set([trailing]).
+
%-----------------------------------------------------------------------------%
main(!IO) :-
@@ -43,7 +42,7 @@
( if solve_sudoku(Start, Solution) then
write_solution(9, Solution, !IO)
else
- io.write_string("no solution\n", !IO)
+ io.write_string("No solution.\n", !IO)
)
;
ReadResult = error(_, Error),
@@ -58,73 +57,80 @@
io.set_exit_status(1, !IO)
)
else
- io.write_string("usage: sudoku filename\n", !IO),
+ io.write_string("usage: sudoku <filename>\n", !IO),
io.set_exit_status(1, !IO)
).
%-----------------------------------------------------------------------------%
- % Solve a sudoko problem.
+ % Solve a sudoku problem.
%
:- pred solve_sudoku(list(string)::in, list(int)::out) is nondet.
solve_sudoku(Start, Solution) :-
-
+ % The following if-then-else is used to ensure that the call to
+ % label_board/2 occurs after the constraints have been posted.
+ % (In principle the compiler could should reorder the code so that
+ % that label_board/2 occurs before they have been posted.)
+ ( if
% Set up the board.
%
- init_board(Start, Board),
+ init_board(Start, Board),
- Board = [X11, X12, X13, X14, X15, X16, X17, X18, X19,
- X21, X22, X23, X24, X25, X26, X27, X28, X29,
- X31, X32, X33, X34, X35, X36, X37, X38, X39,
-
- X41, X42, X43, X44, X45, X46, X47, X48, X49,
- X51, X52, X53, X54, X55, X56, X57, X58, X59,
- X61, X62, X63, X64, X65, X66, X67, X68, X69,
-
- X71, X72, X73, X74, X75, X76, X77, X78, X79,
- X81, X82, X83, X84, X85, X86, X87, X88, X89,
- X91, X92, X93, X94, X95, X96, X97, X98, X99],
+ Board = [X11, X12, X13, X14, X15, X16, X17, X18, X19,
+ X21, X22, X23, X24, X25, X26, X27, X28, X29,
+ X31, X32, X33, X34, X35, X36, X37, X38, X39,
+
+ X41, X42, X43, X44, X45, X46, X47, X48, X49,
+ X51, X52, X53, X54, X55, X56, X57, X58, X59,
+ X61, X62, X63, X64, X65, X66, X67, X68, X69,
+
+ X71, X72, X73, X74, X75, X76, X77, X78, X79,
+ X81, X82, X83, X84, X85, X86, X87, X88, X89,
+ X91, X92, X93, X94, X95, X96, X97, X98, X99],
% The digits in each row must be different.
%
- eqneq.all_different([X11, X12, X13, X14, X15, X16, X17, X18, X19]),
- eqneq.all_different([X21, X22, X23, X24, X25, X26, X27, X28, X29]),
- eqneq.all_different([X31, X32, X33, X34, X35, X36, X37, X38, X39]),
- eqneq.all_different([X41, X42, X43, X44, X45, X46, X47, X48, X49]),
- eqneq.all_different([X51, X52, X53, X54, X55, X56, X57, X58, X59]),
- eqneq.all_different([X61, X62, X63, X64, X65, X66, X67, X68, X69]),
- eqneq.all_different([X71, X72, X73, X74, X75, X76, X77, X78, X79]),
- eqneq.all_different([X81, X82, X83, X84, X85, X86, X87, X88, X89]),
- eqneq.all_different([X91, X92, X93, X94, X95, X96, X97, X98, X99]),
+ eqneq.all_different([X11, X12, X13, X14, X15, X16, X17, X18, X19]),
+ eqneq.all_different([X21, X22, X23, X24, X25, X26, X27, X28, X29]),
+ eqneq.all_different([X31, X32, X33, X34, X35, X36, X37, X38, X39]),
+ eqneq.all_different([X41, X42, X43, X44, X45, X46, X47, X48, X49]),
+ eqneq.all_different([X51, X52, X53, X54, X55, X56, X57, X58, X59]),
+ eqneq.all_different([X61, X62, X63, X64, X65, X66, X67, X68, X69]),
+ eqneq.all_different([X71, X72, X73, X74, X75, X76, X77, X78, X79]),
+ eqneq.all_different([X81, X82, X83, X84, X85, X86, X87, X88, X89]),
+ eqneq.all_different([X91, X92, X93, X94, X95, X96, X97, X98, X99]),
% The digits in each column must be different.
%
- eqneq.all_different([X11, X21, X31, X41, X51, X61, X71, X81, X91]),
- eqneq.all_different([X12, X22, X32, X42, X52, X62, X72, X82, X92]),
- eqneq.all_different([X13, X23, X33, X43, X53, X63, X73, X83, X93]),
- eqneq.all_different([X14, X24, X34, X44, X54, X64, X74, X84, X94]),
- eqneq.all_different([X15, X25, X35, X45, X55, X65, X75, X85, X95]),
- eqneq.all_different([X16, X26, X36, X46, X56, X66, X76, X86, X96]),
- eqneq.all_different([X17, X27, X37, X47, X57, X67, X77, X87, X97]),
- eqneq.all_different([X18, X28, X38, X48, X58, X68, X78, X88, X98]),
- eqneq.all_different([X19, X29, X39, X49, X59, X69, X79, X89, X99]),
-
- % The digits in each subsquare must be different.
- %
- eqneq.all_different([X11, X12, X13, X21, X22, X23, X31, X32, X33]),
- eqneq.all_different([X14, X15, X16, X24, X25, X26, X34, X35, X36]),
- eqneq.all_different([X17, X18, X19, X27, X28, X29, X37, X38, X39]),
- eqneq.all_different([X41, X42, X43, X51, X52, X53, X61, X62, X63]),
- eqneq.all_different([X44, X45, X46, X54, X55, X56, X64, X65, X66]),
- eqneq.all_different([X47, X48, X49, X57, X58, X59, X67, X68, X69]),
- eqneq.all_different([X71, X72, X73, X81, X82, X83, X91, X92, X93]),
- eqneq.all_different([X74, X75, X76, X84, X85, X86, X94, X95, X96]),
- eqneq.all_different([X77, X78, X79, X87, X88, X89, X97, X98, X99]),
-
+ eqneq.all_different([X11, X21, X31, X41, X51, X61, X71, X81, X91]),
+ eqneq.all_different([X12, X22, X32, X42, X52, X62, X72, X82, X92]),
+ eqneq.all_different([X13, X23, X33, X43, X53, X63, X73, X83, X93]),
+ eqneq.all_different([X14, X24, X34, X44, X54, X64, X74, X84, X94]),
+ eqneq.all_different([X15, X25, X35, X45, X55, X65, X75, X85, X95]),
+ eqneq.all_different([X16, X26, X36, X46, X56, X66, X76, X86, X96]),
+ eqneq.all_different([X17, X27, X37, X47, X57, X67, X77, X87, X97]),
+ eqneq.all_different([X18, X28, X38, X48, X58, X68, X78, X88, X98]),
+ eqneq.all_different([X19, X29, X39, X49, X59, X69, X79, X89, X99]),
+
+ % The digits in each subsquare must be different.
+ %
+ eqneq.all_different([X11, X12, X13, X21, X22, X23, X31, X32, X33]),
+ eqneq.all_different([X14, X15, X16, X24, X25, X26, X34, X35, X36]),
+ eqneq.all_different([X17, X18, X19, X27, X28, X29, X37, X38, X39]),
+ eqneq.all_different([X41, X42, X43, X51, X52, X53, X61, X62, X63]),
+ eqneq.all_different([X44, X45, X46, X54, X55, X56, X64, X65, X66]),
+ eqneq.all_different([X47, X48, X49, X57, X58, X59, X67, X68, X69]),
+ eqneq.all_different([X71, X72, X73, X81, X82, X83, X91, X92, X93]),
+ eqneq.all_different([X74, X75, X76, X84, X85, X86, X94, X95, X96]),
+ eqneq.all_different([X77, X78, X79, X87, X88, X89, X97, X98, X99])
+ then
% Assign a digit to each square on the board.
%
- label_board(Board, Solution).
+ label_board(Board, Solution)
+ else
+ false
+ ).
%-----------------------------------------------------------------------------%
@@ -136,7 +142,6 @@
:- pred init_board(list(string)::in, list(eqneq(int))::oa) is semidet.
init_board([], []).
-
init_board([Start | Starts], [EqNeq | EqNeqs]) :-
eqneq.new(EqNeq),
( if string.to_int(Start, X)
@@ -152,7 +157,6 @@
:- pred label_board(list(eqneq(int))::ia, list(int)::out) is nondet.
label_board([], []).
-
label_board([EqNeq | EqNeqs], [X | Xs]) :-
( X = 1 ; X = 2 ; X = 3
; X = 4 ; X = 5 ; X = 6
@@ -181,4 +185,5 @@
).
%-----------------------------------------------------------------------------%
+:- end_module sudoku.
%-----------------------------------------------------------------------------%
Index: test_eqneq.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/samples/solver_types/test_eqneq.m,v
retrieving revision 1.1
diff -u -r1.1 test_eqneq.m
--- test_eqneq.m 15 Feb 2007 00:27:18 -0000 1.1
+++ test_eqneq.m 7 Dec 2010 04:32:41 -0000
@@ -1,22 +1,19 @@
%-----------------------------------------------------------------------------%
-% test_eqneq.m
-% Ralph Becket <rafe at csse.unimelb.edu.au>
-% Mon Feb 12 12:33:57 EST 2007
% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
+%-----------------------------------------------------------------------------%
+%
+% Author: Ralph Becket.
%
-% Test case.
+% A simple test of the eqneq solver defined in eqneq.m.
%
%-----------------------------------------------------------------------------%
:- module test_eqneq.
-
:- interface.
:- import_module io.
-
-
-:- pred main(io :: di, io :: uo) is cc_multi.
+:- pred main(io::di, io::uo) is cc_multi.
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
@@ -28,6 +25,8 @@
:- import_module list.
:- import_module string.
+:- pragma require_feature_set([trailing]).
+
%-----------------------------------------------------------------------------%
main(!IO) :-
@@ -35,7 +34,7 @@
io.print(Solution, !IO),
io.nl(!IO)
else
- io.print("no solution\n", !IO)
+ io.print("No solution.\n", !IO)
).
%-----------------------------------------------------------------------------%
@@ -43,22 +42,26 @@
:- pred solve(list(int)::out) is nondet.
solve(Solution) :-
- eqneq.n_new(9, Xs),
- Xs = [X1, X2, X3, X4, X5, X6, X7, X8, X9],
- X1 = X4, X4 = X7,
- X2 = X5, X5 = X8,
- X3 = X6, X6 = X9,
- neq(X1, X2),
- neq(X1, X3),
- neq(X2, X3),
- label(Xs, Solution).
+ ( if
+ eqneq.n_new(9, Xs),
+ Xs = [X1, X2, X3, X4, X5, X6, X7, X8, X9],
+ X1 = X4, X4 = X7,
+ X2 = X5, X5 = X8,
+ X3 = X6, X6 = X9,
+ neq(X1, X2),
+ neq(X1, X3),
+ neq(X2, X3)
+ then
+ label(Xs, Solution)
+ else
+ false
+ ).
%-----------------------------------------------------------------------------%
:- pred label(list(eqneq(int))::ia, list(int)::out) is nondet.
label([], []).
-
label([EqNeq | EqNeqs], [X | Xs]) :-
( X = 1 ; X = 2 ; X = 3
; X = 4 ; X = 5 ; X = 6
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to: mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions: mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------
More information about the reviews
mailing list