[m-rev.] for review: bug fix for try_all/2

[Mark Brown]

On 08-Dec-2004, Simon Taylor <stayl at cs.mu.OZ.AU> wrote:
> On 08-Dec-2004, Mark Brown <mark at cs.mu.OZ.AU> wrote:
> > Fix a bug in try_all/2 in the library.  The documentation says that it puts
> > the exception at the end of the result list, but the implementation puts
> > it at the start (and the test case in tests/hard_coded/exceptions checks
> > that the exception is at the start).
> > 
> > The fix is to change the documentation to match the implementation.  The
> > rationale for this decision is that it is probably more useful to have the
> > exception at the start of the list where its presence or absence can be
> > easily checked.
> 
> That's a pretty awful interface.
> Wouldn't something like the following be better?
> 
> 	% try_all(Pred, MaybeException, ResultsUpToException)
> :- pred try_all(pred(T), maybe(univ), list(T)).

Agreed.  The new diff follows, and is for review.

Cheers,
Mark.

Estimated hours taken: 1

Improve the interface of exception__try_all by separating the output into
a maybe-exception and a list of solutions.  This makes it easier to test
whether an exception occurred, and removes the need for solutions to be
wrapped in an exception_result.

This also obviates a bug in the previous implementation/documentation
of try_all.

Although this change is not backwards compatible, the fact that no one
reported the existing bug for the last four years suggests that that
shouldn't be much of an issue.

NEWS:
	Mention the change.

library/exception.m:
	Modify the interface, implementation and documentation of try_all
	to reflect the above.

	Rewrite the documentation of incremental_try_all so as not to refer
	to the old version of try_all.  The meaning of incremental_try_all
	is not changed.

tests/hard_coded/exceptions/test_try_all.{m,exp}:
	Update the test case to reflect the new interface.

Index: NEWS
===================================================================
RCS file: /home/mercury1/repository/mercury/NEWS,v
retrieving revision 1.350
diff -u -r1.350 NEWS
--- NEWS	11 Nov 2004 13:46:41 -0000	1.350
+++ NEWS	9 Dec 2004 05:54:13 -0000
@@ -205,6 +205,9 @@
 * exception.m now contains a predicate throw_if_near_stack_limits which
   can be used to prevent an application running out of stack space.
 
+* We've changed the interface of exception.try_all/2 to separate
+  exceptional results from normal results.
+
 * We've added predicates multi_map.to_flat_assoc_list/2 and
   multi_map.from_flat_assoc_list/2. 
 
Index: library/exception.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/exception.m,v
retrieving revision 1.95
diff -u -r1.95 exception.m
--- library/exception.m	16 Aug 2004 03:51:05 -0000	1.95
+++ library/exception.m	9 Dec 2004 12:42:56 -0000
@@ -97,52 +97,54 @@
 :- mode try_store(pred(out, di, uo) is cc_multi,
 	out(cannot_fail), di, uo) is cc_multi.
 
-	% try_all(Goal, ResultList):
+	% try_all(Goal, MaybeException, Solutions):
 	%
 	% Operational semantics:
-	%	Try to find all solutions to Goal(R), using backtracking.
-	%	Collect the solutions found in the ResultList, until
-	%	the goal either throws an exception or fails.
-	%	If it throws an exception, put that exception at the end of
-	%	the ResultList.
+	%	Try to find all solutions to Goal(S), using backtracking.
+	%	Collect the solutions found in Solutions, until the goal
+	%	either throws an exception or fails.  If it throws an
+	%	exception E then MaybeException = yes(E), otherwise
+	%	MaybeException = no.
 	%
-	% Declaratively:
-	%       try_all(Goal, ResultList) <=>
-	%		(if
-	%			list__reverse(ResultList,
-	%				[Last | AllButLast]),
-	%			Last = exception(_)
-	%		then
-	%			all [M] (list__member(M, AllButLast) =>
-	%				(M = succeeded(R), Goal(R))),
-	%		else
-	%			all [M] (list__member(M, ResultList) =>
-	%				(M = succeeded(R), Goal(R))),
-	%			all [R] (Goal(R) =>
-	%				list__member(succeeded(R),
-	%					ResultList)),
-	%		).
-
-:- pred try_all(pred(T), list(exception_result(T))).
-:- mode try_all(pred(out) is det,     out(try_all_det))     is cc_multi.
-:- mode try_all(pred(out) is semidet, out(try_all_semidet)) is cc_multi.
-:- mode try_all(pred(out) is multi,   out(try_all_multi))   is cc_multi.
-:- mode try_all(pred(out) is nondet,  out(try_all_nondet))  is cc_multi.
+	% Declaratively it is equivalent to:
+	%	all [S] (list__member(S, Solutions) => Goal(S)),
+	%	(
+	%		MaybeException = yes(_)
+	%	;
+	%		MaybeException = no,
+	%		all [S] (Goal(S) => list__member(S, Solutions))
+	%	).
+
+:- pred try_all(pred(T), maybe(univ), list(T)).
+:- mode try_all(pred(out) is det,     out, out(nil_or_singleton_list))
+	is cc_multi.
+:- mode try_all(pred(out) is semidet, out, out(nil_or_singleton_list))
+	is cc_multi.
+:- mode try_all(pred(out) is multi,   out, out) is cc_multi.
+:- mode try_all(pred(out) is nondet,  out, out) is cc_multi.
 
 :- inst [] ---> [].
-:- inst try_all_det ---> [cannot_fail].
-:- inst try_all_semidet ---> [] ; [cannot_fail].
-:- inst try_all_multi ---> [cannot_fail | try_all_nondet].
-:- inst try_all_nondet == list_skel(cannot_fail).
+:- inst nil_or_singleton_list ---> [] ; [ground].
 
 	% incremental_try_all(Goal, AccumulatorPred, Acc0, Acc):
 	%
-	% Same as
-	%	try_all(Goal, Results),
-	%	std_util__unsorted_aggregate(Results, AccumulatorPred,
-	%		Acc0, Acc)
-	% except that operationally, the execution of try_all
-	% and std_util__unsorted_aggregate is interleaved.
+	% Declaratively it is equivalent to:
+	%	try_all(Goal, MaybeException, Solutions),
+	%	list__map(wrap_success, Solutions, Results),
+	%	list__foldl(AccumulatorPred, Results, Acc0, Acc1),
+	%	(
+	%		MaybeException = no,
+	%		Acc = Acc1
+	%	;
+	%		MaybeException = yes(Exception),
+	%		AccumulatorPred(exception(Exception), Acc1, Acc)
+	%	)
+	%
+	% where (wrap_success(S, R) <=> R = succeeded(S)).
+	%
+	% Operationally, however, incremental_try_all/5 will call
+	% AccumulatorPred for each solution as it is obtained, rather than
+	% first building a list of the solutions.
 
 :- pred incremental_try_all(pred(T), pred(exception_result(T), A, A), A, A).
 :- mode incremental_try_all(pred(out) is nondet,
@@ -219,15 +221,15 @@
 :- mode try_store(in(bound(cc_multi)), pred(out, di, uo) is cc_multi,
 				    out(cannot_fail), di, uo) is cc_multi.
 
-:- pred try_all(determinism,        pred(T), list(exception_result(T))).
+:- pred try_all(determinism,        pred(T), maybe(univ), list(T)).
 :- mode try_all(in(bound(det)),	    pred(out) is det,
-				    	     out(try_all_det)) is cc_multi.
+				    out, out(nil_or_singleton_list))
+				    is cc_multi.
 :- mode try_all(in(bound(semidet)), pred(out) is semidet,
-				    	     out(try_all_semidet)) is cc_multi.
-:- mode try_all(in(bound(multi)),   pred(out) is multi,
-				    	     out(try_all_multi)) is cc_multi.
-:- mode try_all(in(bound(nondet)),  pred(out) is nondet,
-				    	     out(try_all_nondet)) is cc_multi.
+				    out, out(nil_or_singleton_list))
+				    is cc_multi.
+:- mode try_all(in(bound(multi)),   pred(out) is multi, out, out) is cc_multi.
+:- mode try_all(in(bound(nondet)),  pred(out) is nondet, out, out) is cc_multi.
 
 :- type determinism
 	--->	det
@@ -447,42 +449,67 @@
 				wrap_success_or_failure(Goal, R)),
 		wrap_exception, Result).
 
-/**********
-% This doesn't work, due to
-% 	bash$ mmc exception.m
-% 	Software error: sorry, not implemented: taking address of pred
-% 	`wrap_success_or_failure/2' with multiple modes.
-% Instead, we need to switch on the Detism argument.
-
-try_all(Goal, ResultList) :-
-	unsorted_solutions(builtin_catch(wrap_success(Goal), wrap_exception),
-		ResultList).
-**********/
+% We switch on the Detism argument for a similar reason to above.
 
-try_all(Goal, ResultList) :-
+try_all(Goal, MaybeException, Solutions) :-
 	get_determinism(Goal, Detism),
-	try_all(Detism, Goal, ResultList).
+	try_all(Detism, Goal, MaybeException, Solutions).
 
-try_all(det, Goal, [Result]) :-
-	try(det, Goal, Result).
-try_all(semidet, Goal, ResultList) :-
+try_all(det, Goal, MaybeException, Solutions) :-
+	try(det, Goal, Result),
+	(
+		Result = succeeded(Solution),
+		Solutions = [Solution],
+		MaybeException = no
+	;
+		Result = exception(Exception),
+		Solutions = [],
+		MaybeException = yes(Exception)
+	).
+try_all(semidet, Goal, MaybeException, Solutions) :-
 	try(semidet, Goal, Result),
-	( Result = failed, ResultList = []
-	; Result = succeeded(_), ResultList = [Result]
-	; Result = exception(_), ResultList = [Result]
+	(
+		Result = failed,
+		Solutions = [],
+		MaybeException = no
+	;
+		Result = succeeded(Solution),
+		Solutions = [Solution],
+		MaybeException = no
+	;
+		Result = exception(Exception),
+		Solutions = [],
+		MaybeException = yes(Exception)
 	).
-try_all(multi, Goal, ResultList) :-
+try_all(multi, Goal, MaybeException, Solutions) :-
 	unsorted_solutions((pred(Result::out) is multi :-
 		catch_impl((pred(R::out) is multi :-
 				wrap_success(Goal, R)),
 			wrap_exception, Result)),
-		ResultList).
-try_all(nondet, Goal, ResultList) :-
+		ResultList),
+	list__foldl2(process_one_exception_result, ResultList,
+		no, MaybeException, [], Solutions).
+try_all(nondet, Goal, MaybeException, Solutions) :-
 	unsorted_solutions((pred(Result::out) is nondet :-
 		catch_impl((pred(R::out) is nondet :-
 				wrap_success(Goal, R)),
 			wrap_exception, Result)),
-		ResultList).
+		ResultList),
+	list__foldl2(process_one_exception_result, ResultList,
+		no, MaybeException, [], Solutions).
+
+:- pred process_one_exception_result(exception_result(T)::in,
+	maybe(univ)::in, maybe(univ)::out, list(T)::in, list(T)::out) is det.
+
+process_one_exception_result(exception(E), !MaybeException, !Solutions) :-
+	% Ignore all but the last exception that is in the list.  This is
+	% okay since there should never be more than one.
+	!.MaybeException = _,
+	!:MaybeException = yes(E).
+process_one_exception_result(succeeded(S), !MaybeException, !Solutions) :-
+	!:Solutions = [S | !.Solutions].
+process_one_exception_result(failed, !MaybeException, !Solutions) :-
+	error("exception.process_one_exception_result: unexpected failure").
 
 incremental_try_all(Goal, AccPred, Acc0, Acc) :-
 	unsorted_aggregate((pred(Result::out) is nondet :-
Index: tests/hard_coded/exceptions/test_try_all.exp
===================================================================
RCS file: /home/mercury1/repository/tests/hard_coded/exceptions/test_try_all.exp,v
retrieving revision 1.2
diff -u -r1.2 test_try_all.exp
--- tests/hard_coded/exceptions/test_try_all.exp	13 Jan 2001 02:30:32 -0000	1.2
+++ tests/hard_coded/exceptions/test_try_all.exp	9 Dec 2004 12:35:54 -0000
@@ -1,12 +1,36 @@
-det_throw: [exception(univ_cons("det_throw"))]
-det_succeed: [succeeded("det_succeed")]
-semidet_throw: [exception(univ_cons("semidet_throw"))]
-semidet_succeed: [succeeded("semidet_succeed")]
-semidet_fail: []
-multi_throw: [exception(univ_cons("multi_throw"))]
-multi_succeed: [succeeded("multi_succeed 2"), succeeded("multi_succeed 1")]
-multi_succeed_then_throw: [exception(univ_cons("multi_succeed_then_throw 3")), succeeded("multi_succeed_then_throw 2"), succeeded("multi_succeed_then_throw 1")]
-nondet_throw: [exception(univ_cons("nondet_throw"))]
-nondet_succeed: [succeeded("nondet_succeed 2"), succeeded("nondet_succeed 1")]
-nondet_fail: []
-nondet_succeed_then_throw: [exception(univ_cons("nondet_succeed_then_throw 3")), succeeded("nondet_succeed_then_throw 2"), succeeded("nondet_succeed_then_throw 1")]
+det_throw:
+	yes(univ_cons("det_throw"))
+	[]
+det_succeed:
+	no
+	["det_succeed"]
+semidet_throw:
+	yes(univ_cons("semidet_throw"))
+	[]
+semidet_succeed:
+	no
+	["semidet_succeed"]
+semidet_fail:
+	no
+	[]
+multi_throw:
+	yes(univ_cons("multi_throw"))
+	[]
+multi_succeed:
+	no
+	["multi_succeed 1", "multi_succeed 2"]
+multi_succeed_then_throw:
+	yes(univ_cons("multi_succeed_then_throw 3"))
+	["multi_succeed_then_throw 1", "multi_succeed_then_throw 2"]
+nondet_throw:
+	yes(univ_cons("nondet_throw"))
+	[]
+nondet_succeed:
+	no
+	["nondet_succeed 1", "nondet_succeed 2"]
+nondet_fail:
+	no
+	[]
+nondet_succeed_then_throw:
+	yes(univ_cons("nondet_succeed_then_throw 3"))
+	["nondet_succeed_then_throw 1", "nondet_succeed_then_throw 2"]
Index: tests/hard_coded/exceptions/test_try_all.m
===================================================================
RCS file: /home/mercury1/repository/tests/hard_coded/exceptions/test_try_all.m,v
retrieving revision 1.1
diff -u -r1.1 test_try_all.m
--- tests/hard_coded/exceptions/test_try_all.m	19 Jun 2000 07:19:09 -0000	1.1
+++ tests/hard_coded/exceptions/test_try_all.m	9 Dec 2004 12:29:56 -0000
@@ -1,5 +1,5 @@
 %---------------------------------------------------------------------------%
-% Copyright (C) 2000 The University of Melbourne.
+% Copyright (C) 2000, 2004 The University of Melbourne.
 % This file may only be copied under the terms of the GNU Library General
 % Public License - see the file COPYING.LIB in the Mercury distribution.
 %---------------------------------------------------------------------------%
@@ -14,38 +14,50 @@
 :- pred main(io__state::di, io__state::uo) is cc_multi.
 
 :- implementation.
-:- import_module std_util, exception, list, int.
+:- import_module std_util, exception, list, int, string.
 
 main --> 
-	{ try_all(det_throw, DetThrowResult) },
-	print("det_throw: "), print(DetThrowResult), nl,
-	{ try_all(det_succeed, DetSucceedResult) },
-	print("det_succeed: "), print(DetSucceedResult), nl,
-
-	{ try_all(semidet_throw, SemidetThrowResult) },
-	print("semidet_throw: "), print(SemidetThrowResult), nl,
-	{ try_all(semidet_succeed, SemidetSucceedResult) },
-	print("semidet_succeed: "), print(SemidetSucceedResult), nl,
-	{ try_all(semidet_fail, SemidetFailResult) },
-	print("semidet_fail: "), print(SemidetFailResult), nl,
-
-	{ try_all(multi_throw, MultiThrowResult) },
-	print("multi_throw: "), print(MultiThrowResult), nl,
-	{ try_all(multi_succeed, MultiSucceedResult) },
-	print("multi_succeed: "), print(MultiSucceedResult), nl,
-	{ try_all(multi_succeed_then_throw, MultiSucceedThenThrowResult) },
-	print("multi_succeed_then_throw: "),
-	print(MultiSucceedThenThrowResult), nl,
-
-	{ try_all(nondet_throw, NondetThrowResult) },
-	print("nondet_throw: "), print(NondetThrowResult), nl,
-	{ try_all(nondet_succeed, NondetSucceedResult) },
-	print("nondet_succeed: "), print(NondetSucceedResult), nl,
-	{ try_all(nondet_fail, NondetFailResult) },
-	print("nondet_fail: "), print(NondetFailResult), nl,
-	{ try_all(nondet_succeed_then_throw, NondetSucceedThenThrowResult) },
-	print("nondet_succeed_then_throw: "),
-	print(NondetSucceedThenThrowResult), nl.
+	{ try_all(det_throw, DetThrowExcp, DetThrowSols) },
+	print_result("det_throw", DetThrowExcp, DetThrowSols),
+	{ try_all(det_succeed, DetSucceedExcp, DetSucceedSols) },
+	print_result("det_succeed", DetSucceedExcp, DetSucceedSols),
+
+	{ try_all(semidet_throw, SemidetThrowExcp, SemidetThrowSols) },
+	print_result("semidet_throw", SemidetThrowExcp, SemidetThrowSols),
+	{ try_all(semidet_succeed, SemidetSucceedExcp, SemidetSucceedSols) },
+	print_result("semidet_succeed", SemidetSucceedExcp, SemidetSucceedSols),
+	{ try_all(semidet_fail, SemidetFailExcp, SemidetFailSols) },
+	print_result("semidet_fail", SemidetFailExcp, SemidetFailSols),
+
+	{ try_all(multi_throw, MultiThrowExcp, MultiThrowSols) },
+	print_result("multi_throw", MultiThrowExcp, MultiThrowSols),
+	{ try_all(multi_succeed, MultiSucceedExcp, MultiSucceedSols) },
+	print_result("multi_succeed", MultiSucceedExcp, MultiSucceedSols),
+	{ try_all(multi_succeed_then_throw, MultiSucceedThenThrowExcp,
+		MultiSucceedThenThrowSols) },
+	print_result("multi_succeed_then_throw", MultiSucceedThenThrowExcp,
+		MultiSucceedThenThrowSols),
+
+	{ try_all(nondet_throw, NondetThrowExcp, NondetThrowSols) },
+	print_result("nondet_throw", NondetThrowExcp, NondetThrowSols),
+	{ try_all(nondet_succeed, NondetSucceedExcp, NondetSucceedSols) },
+	print_result("nondet_succeed", NondetSucceedExcp, NondetSucceedSols),
+	{ try_all(nondet_fail, NondetFailExcp, NondetFailSols) },
+	print_result("nondet_fail", NondetFailExcp, NondetFailSols),
+	{ try_all(nondet_succeed_then_throw, NondetSucceedThenThrowExcp,
+		NondetSucceedThenThrowSols) },
+	print_result("nondet_succeed_then_throw", NondetSucceedThenThrowExcp,
+		NondetSucceedThenThrowSols).
+
+:- pred print_result(string::in, maybe(univ)::in, list(string)::in,
+	io::di, io::uo) is det.
+
+print_result(Name, Excp, Sols) -->
+	print(Name ++ ":\n\t"),
+	print(Excp),
+	print("\n\t"),
+	print(Sols),
+	nl.
 
 :- pred det_throw(string::out) is det.
 det_throw(_) :- throw("det_throw").
--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------