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

[Mark Brown]

On 31-Dec-2004, Ian MacLarty <maclarty at cs.mu.OZ.AU> wrote:
> On Thu, Dec 30, 2004 at 04:55:17PM +1100, Mark Brown wrote:
> > > +
> > > +	% find_middle_weight(Store, SuspectIds, TopId, MaybeLastUnknown,
> > > +	%	!SearchSpace, Response).
> > > +	% Find the suspect that splits the portion of the search space rooted
> > > +	% at TopId into roughly equal portions by weight.  SuspectIds is 
> > 
> > Don't use "roughly"; be more specific about the meaning of this predicate.
> > For example, you could add the sentence:
> > 
> > 	The weight of the chosen suspect will be as close to half the
> > 	weight of TopId as any other suspect being considered.
> > 
> 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.

> > > +	% now zero.
> > 
> > It appears that the weight field does not actually get set to zero, even
> > though the weight is considered to be zero at this point.  You should document
> > above that the weight field doesn't contain a meaningful value if the suspect
> > is valid.
> > 
> 
> It IS set to zero near the top of the predicate:
> 
> +	map.set(!.SearchSpace ^ store, SuspectId, 
> +		(Suspect ^ status := Status) ^ weight := 0, SuspectStore),

Ok.

> > > @@ -770,32 +800,24 @@
> > >  		adjust_unexplored_leaves(yes(Suspect ^ status), erroneous, 
> > >  			!SearchSpace)
> > >  	;
> > > -		Suspect ^ children = yes(Children),
> > > -		%
> > > -		% If the suspect was correct, inadmissible or pruned then we
> > > -		% should make all the descendents unknown again.
> > > -		%
> > > -		(
> > > -			excluded_subtree(Suspect ^ status, yes)
> > > -		->
> > > -			list.foldl(propagate_status_downwards(unknown, 
> > > -				[correct, inadmissible]), Children,
> > > -				!SearchSpace)
> > > -		;
> > > -			true
> > > -		)
> > > +		Suspect ^ children = yes(_)
> > >  	),
> > > -	propagate_status_upwards(in_erroneous_subtree_complement, [erroneous], 
> > > -		SuspectId, _, !SearchSpace),
> > > +	propagate_status_upwards(in_erroneous_subtree_complement, 
> > > +		[erroneous, correct, inadmissible], SuspectId, _,
> > > +		!SearchSpace),
> > >  	!:SearchSpace = !.SearchSpace ^ root := yes(SuspectId).
> > 
> > I don't understand these changes to assert_suspect_is_erroneous.  Could you
> > please document it in the log message, or add comments to the code here, or
> > preferably both?
> > 
> 
> I've added the following to the CVS log:
> 
> 	Remove some code that will never be executed in 
> 	assert_suspect_is_erroneous/3.  The code handles a case when 
> 	a correct or inadmissible suspect is marked erroneous.  This can
> 	only happen when a search is being revised in which case the
> 	correct or erroneous suspect would be marked unknown.
> 
> 	When marking suspects as in the complement of an erroneous subtree
> 	stop marking if a correct or inadmissible node is encountered since
> 	descendents of these will already have been removed from the bug
> 	search.

Ok, that's fine.

> 
> > > @@ -804,27 +826,44 @@
> > >  		skipped(N), Store),
> > >  	!:SearchSpace = !.SearchSpace ^ store := Store.
> > >  
> > > -revise_root(!SearchSpace) :-
> > > +revise_root(Store, !SearchSpace) :-
> > >  	(
> > >  		!.SearchSpace ^ root = yes(RootId),
> > >  		force_propagate_status_downwards(unknown, 
> > > -			[correct, inadmissible], RootId, Leaves, !SearchSpace),
> > > -		list.foldl(force_propagate_status_downwards(unknown, [correct,
> > > -			inadmissible]), Leaves, !SearchSpace),
> > > -		propagate_status_upwards(unknown, [erroneous], RootId, Lowest, 
> > > +			[correct, inadmissible], RootId, StopSuspects, 
> > >  			!SearchSpace),
> > > -		(
> > > -			suspect_erroneous(!.SearchSpace, Lowest)
> > > -		->
> > > +		list.foldl(force_propagate_status_downwards(unknown, [correct,
> > > +			inadmissible]), StopSuspects, !SearchSpace),
> > > +		propagate_status_upwards(unknown, [erroneous, correct,
> > > +			inadmissible], RootId, Lowest, !SearchSpace),
> > > +		( suspect_erroneous(!.SearchSpace, Lowest) ->
> > >  			!:SearchSpace = !.SearchSpace ^ root := yes(Lowest)
> > >  		;
> > >  			!:SearchSpace = !.SearchSpace ^ root := no
> > > -		)
> > > +		),
> > > +		%
> > > +		% Recompute the suspect weights from the bottom up.
> > > +		%
> > > +		map.keys(!.SearchSpace ^ store, AllSuspects),
> > > +		list.filter(suspect_is_leaf(!.SearchSpace), AllSuspects, 
> > > +			Leaves),
> > > +		recalc_weights_upto_ancestor(Store, Lowest, Leaves, 
> > > +			!SearchSpace)
> > >  	;
> > >  		!.SearchSpace ^ root = no,
> > >  		throw(internal_error("revise_root", "no root"))
> > >  	).
> > 
> > Likewise I don't fully understand the changes to revise_root.  The comment
> > on the declaration of it probably needs to be updated.  I'll review these
> > parts of the change after you post a relative diff.
> > 
> 
> The only differences are that I changed a variable named Leaves to 
> StopSuspects, reformatted an if-then-else and added the bit that recomputes the
> weights of the suspects.

Ok.

> > > @@ -1008,12 +1045,14 @@
> > >  	propagate_status_downwards(Status, StopStatusSet, SuspectId, _, 
> > >  		!SearchSpace).
> > >  
> > > +	% An accumulator version of propagate_status_downwards.
> > > +	%
> > >  :- pred propagate_status_downwards(suspect_status::in, 
> > >  	list(suspect_status)::in, suspect_id::in, 
> > >  	list(suspect_id)::in, list(suspect_id)::out, 
> > >  	search_space(T)::in, search_space(T)::out) is det.
> > 
> > The conventional name for such a predicate would be
> > propagate_status_downwards_2, by the way.
> > 
> 
> I prefer to use this convention only when the predicate is just called from
> the predicate with the same name but without the "_2".  In this case 
> the accumulator version of propagate_status_downwards is also called from
> force_propagate_status_downwards.

Fair enough.

Other than the suggestion near the top, this change looks fine.

Cheers,
Mark.

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