[m-rev.] for review: divide and query search for declarative debugger

[Ian MacLarty]

> > I've changed the comment to the following:
> > 	% Find the first unknown suspect in the descendents of SuspectIds whose
> > 	% weight is less than or equal to half the weight of TopId.  This is 
> > 	% done by considering the heaviest suspect in SuspectIds and then the
> > 	% heaviest child of the heaviest suspect in SuspectId and so on.
> > 	% MaybeLastUnknown is the last node that was unknown in the search (if
> > 	% any).  
> 
> This should be rephrased as per our in-person discussion.
> 
> Also, you should probably add an extra comment about how the algorithm
> could be improved, also as per that discussion.
> 

What I've done is implement the improvement we talked about.  This also makes
the description of the predicate simpler.

I also fixed a little bug in the find_middle_weight_if_children predicate which
I introduced in my last diff.

diff -u browser/declarative_analyser.m browser/declarative_analyser.m
--- browser/declarative_analyser.m	4 Jan 2005 02:15:31 -0000
+++ browser/declarative_analyser.m	4 Jan 2005 05:36:00 -0000
@@ -901,16 +901,16 @@
 	% given suspect id, otherwise return a require_explicit_subtree
 	% search response in the last argument.
 	%
-:- pred find_middle_weight_if_children(S::in, suspect_id::in,
+:- pred find_middle_weight_if_children(S::in, suspect_id::in, suspect_id::in,
 	maybe(suspect_id)::in, search_space(T)::in, search_space(T)::out,
 	search_response::out) is det <= mercury_edt(S, T).
 
-find_middle_weight_if_children(Store, SuspectId, MaybeLastUnknown,
+find_middle_weight_if_children(Store, SuspectId, TopId, MaybeLastUnknown,
 		!SearchSpace, Response) :-
 	(
 		children(Store, SuspectId, !SearchSpace, Children)
 	->
-		find_middle_weight(Store, Children, SuspectId,
+		find_middle_weight(Store, Children, TopId,
 			MaybeLastUnknown, !SearchSpace, Response)
 	;
 		Response = require_explicit_subtree(SuspectId)
@@ -918,10 +918,9 @@
 
 	% find_middle_weight(Store, SuspectIds, TopId, MaybeLastUnknown,
 	%	!SearchSpace, Response).
-	% Find the first unknown suspect in the descendents of SuspectIds whose
-	% weight is less than or equal to half the weight of TopId.  This is 
-	% done by considering the heaviest suspect in SuspectIds and then the
-	% heaviest child of the heaviest suspect in SuspectId and so on.
+	% Find the unknown suspect whose weight is closest to half the weight
+	% of TopId, considering only the heaviest suspect in SuspectIds, the
+	% heaviest child of the heaviest suspect in SuspectIds and so on.
 	% MaybeLastUnknown is the last node that was unknown in the search (if
 	% any).  
 	%
@@ -960,13 +959,32 @@
 		;
 			NewMaybeLastUnknown = MaybeLastUnknown
 		),
-		find_middle_weight_if_children(Store, Heaviest, 
+		find_middle_weight_if_children(Store, Heaviest, TopId,
 			NewMaybeLastUnknown, !SearchSpace, Response)
 	;
 		(
 			suspect_unknown(!.SearchSpace, Heaviest)
 		->
-			Response = question(Heaviest)
+			(
+				MaybeLastUnknown = yes(LastUnknown),
+				LastUnknownWeight = get_weight(!.SearchSpace, 
+					LastUnknown),
+				%
+				% If the last unknown suspect was closer to
+				% the target weight then ask about it.
+				%
+				( 
+					LastUnknownWeight - Target <
+						Target - MaxWeight
+				->
+					Response = question(LastUnknown)
+				;					
+					Response = question(Heaviest)
+				)
+			;
+				MaybeLastUnknown = no,
+				Response = question(Heaviest)
+			)
 		;
 			(
 				MaybeLastUnknown = yes(LastUnknown),
@@ -975,7 +993,7 @@
 				MaybeLastUnknown = no,
 				% Look deeper until we find an unknown:
 				find_middle_weight_if_children(Store, Heaviest,
-					no, !SearchSpace, Response)
+					TopId, no, !SearchSpace, Response)
 			)
 		)		
 	).

Ian.

--------------------------------------------------------------------------
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
--------------------------------------------------------------------------