[m-rev.] For review: changes to declarative debugger (Part 1)

[Ian MacLarty]

On Mon, Nov 08, 2004 at 02:55:46PM +1100, Zoltan Somogyi wrote:
> On 29-Sep-2004, Ian MacLarty <maclarty at cs.mu.OZ.AU> wrote:
> > 	% setup_binary_search(SearchSpace, TopId, BottomId, Response, 
> > 	%	SearchMode).
> > 	% Sets up the search mode to do a binary search between BottomId
> > 	% and TopId. 
> > 	%
> > :- pred setup_binary_search(search_space(T)::in, suspect_id::in,
> > 	suspect_id::in, search_mode::out) is det.
> > 
> > setup_binary_search(SearchSpace, TopId, BottomId, SearchMode) :-
> > 	(
> > 		get_path(SearchSpace, BottomId, TopId, [], Path)
> 
> Get_path should have a non-accumulator version. Its documentation should say
> on which side (front or back) the initial accumulator is appended.
> 
> > :- pred binary_search(S::in, array(suspect_id)::in, int::in, int::in, int::in,
> > 	search_space(T)::in, search_space(T)::out, search_mode::out,
> > 	search_response::out) is det <= mercury_edt(S, T).
> > 
> > binary_search(Store, PathArray, From, To, LastTested, !SearchSpace, NewMode, 
> > 		Response) :-
> 
> Wouldn't Bottom and Top be clearer names than From and To? With the latter,
> I don't know which is which. If you make the change, make it elsewhere as well.
I agree and have changed throughout.

> 
> > 	SuspectId = PathArray ^ elem(LastTested),
> > 	%
> > 	% Check what the result of the query about LastTested was and adjust
> > 	% the range appropriately.
> > 	%
> > 	(
> > 		% The oracle answered `erroneous'.
> > 		suspect_in_excluded_complement(!.SearchSpace, SuspectId)
> 
> Wouldn't 'included' be a better name than 'excluded_complement'?
> 
No "excluded complement" refers to the complement of a subtree rooted at an
erroneous node.  The complement has been excluded from the bug search.

I want to distinguish between nodes excluded because of other erroneous nodes
and nodes excluded because of other correct or inadmissible nodes.

Because it's not just the ancestors of an erroneous node that are excluded
(the siblings of all the ancestors as well as the descendents of the siblings
of all the ancestors are also excluded), I use "in_excluded_complement"
instead of say "ancestor_of_erroneous".  

My comment above suspect_in_excluded_complement reads:
        % Succeeds if the suspect has been marked erroneous or is in the
        % complement of a subtree with an erroneous root. Fails otherwise.
        %
Maybe I should change the name to excluded_because_of_erroneous?

> > 	% find_unknown_closest_to_middle(SearchSpace, PathArray, From, To, 
> > 	%	Unknown).
> > 	% Unknown is the position in PathArray of the suspect which has status
> > 	% unknown and is closest to halfway between From and To which are 
> > 	% also indexes into PathArray.  Fails if there are no unknown suspects
> > 	% between From and To (inclusive).
> > 	%
> > :- pred find_unknown_closest_to_middle(search_space(T)::in, 
> > 	array(suspect_id)::in, int::in, int::in, int::out) is semidet.
> > 
> > find_unknown_closest_to_middle(SearchSpace, PathArray, From, To, Unknown) :-
> > 	Middle = From + ((To - From) // 2),
> > 	find_unknown_closest_to_range(SearchSpace, PathArray, From, To, 
> > 		Middle, Middle, Unknown).
> > 
> > 	% find_unknown_closest_to_range(SearchSpace, PathArray, OuterFrom, 
> > 	%	OuterTo, InnerFrom, InnerTo, Unknown)
> > 	% Unknown is the position in PathArray between OuterFrom and InnerFrom
> > 	% (inclusive) or between InnerTo and OuterTo (inclusive) where the
> > 	% status of the suspect is unknown.
> 
> I suggest replacing this with something like:
> 
> % Unknown is a position in PathArray between OuterFrom and InnerFrom
> % (inclusive) where the status of the suspect is unknown. The preferred
> % position to return is as close as possible to InnerFrom and InnerTo,
> % with the proviso that elements between InnerTo and OuterTo (exclusive)
> % aren't tested, since the caller has already found they were not unknown.
> 
Okay, though I assume you mean "OuterFrom and OuterTo" on line 1 and 
"InnerFrom and InnerTo" on line 4?

> >  	% This type represents the possible truth values for nodes
> >  	% in the EDT.
> >  	%
> > -:- type decl_truth == bool.
> > +:- type decl_truth
> > +	--->	correct
> > +	;	erroneous
> > +	;	inadmissible.
> 
> Is this type also used for wrong answer analysis? If yes, then we need to
> use separate types for the two analyses, since inadmissible isn't applicable
> to wrong answer analysis.
> 
Why is inadmissible not applicable to wrong answer diagnosis?  The oracle can
assert that an input violates a precondition when we're doing either type of
analysis.  Lee speaks of the applications of inadmissibility to both 
types of diagnosis in his paper.

> > -	maybe(subterm_origin(edt_node(R)))::in, diagnoser_response::out,
> > -	diagnoser_state(R)::in, diagnoser_state(R)::out,
> > -	io__state::di, io__state::uo) is cc_multi <= annotated_trace(S, R).
> > +	maybe(subterm_origin(edt_node(R)))::in, diagnoser_response(R)::out,
> > +	diagnoser_state(R)::in, diagnoser_state(R)::out, io__state::di,
> > +	io__state::uo) is cc_multi <= annotated_trace(S, R).
> 
> We like to keep the declarations of argument pairs (like the two io__states)
> together.
> 
Done.

> >  handle_analyser_response(_, no_suspects, _, no_bug_found, D, D) -->
> >  	io__write_string("No bug found.\n").
> >  
> >  handle_analyser_response(Store, bug_found(Bug, Evidence), _, Response,
> > -	Diagnoser0, Diagnoser) -->
> > -
> > +		Diagnoser0, Diagnoser) -->
> >  	confirm_bug(Store, Bug, Evidence, Response, Diagnoser0, Diagnoser).
> 
> If you fix that, you should also switch to state variable notation.
> 
> If you know you will need to make changes to a module which uses obsolete
> formatting (e.g. DCGs instead of state variables), you should start with a
> separate diff that just updates the syntax without touching the semantics.
> That makes the next diff easier to review.
> 
Okay - I'll do that in future.

> > +	io__write_string(StdErr, "An internal error has occurred; "++
> > +		"diagnosis will be aborted.  Debugging\n"++
> > +		"message follows:\n"++Loc++": "++Msg++"\n"++
> > +		"Please report bugs to mercury-bugs at cs.mu.oz.au.\n", !IO),
> 
> Please leave spaces around ++ operators.
>
Okay. 

> > Index: browser/declarative_edt.m
> > ===================================================================
> > RCS file: browser/declarative_edt.m
> > diff -N browser/declarative_edt.m
> > --- /dev/null	1 Jan 1970 00:00:00 -0000
> > +++ browser/declarative_edt.m	28 Sep 2004 13:09:44 -0000
> > @@ -0,0 +1,1162 @@
> > +%-----------------------------------------------------------------------------%
> > +% Copyright (C) 1999-2003 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.
> > +%-----------------------------------------------------------------------------%
> 
> For a new file, the date should be 2004.
>
Fixed.

> > +% This module defines Evaluation Dependency Trees (EDTs) which represent the
> > +% dependencies between calls made during the execution of a buggy program.
> > +% Search spaces are also defined as a layer on top of EDTs.  A search space 
> > +% records extra information that is used when searching for bugs in EDTs and
> > +% also provides a way to reference nodes in the EDT independent of whether
> > +% a node is represented implicitly or explicitly.
> 
> You should also say what that "extra information" is, and what defines the
> search space's boundaries. The documentation of the search_space type will do
> nicely.
> 
I changed the comment at the beginning of declarative_edt.m to:

% This module defines Evaluation Dependency Trees (EDTs) which represent the
% dependencies between calls made during the execution of a buggy program.
% Search spaces are also defined as a layer on top of EDTs.
%
% The search space records extra information like which nodes have been
% eliminated from the bug search and which nodes have been skipped or are
% trusted and in future might also store information like the probability of
% each node being buggy, based on some heursitic(s).
%
% The search space provides a consistent view of the debug tree - combining
% seperately generated EDT subtrees into one tree.  Each node in the search
% space corresponds to a node either explicitly represented in a generated EDT
% subtree or the root of an implicitly represented EDT subtree.  We maintain
% the invarient that search space nodes always correspond with explicit nodes
% where an explicit version of the EDT subtree containing that node exists, and
% only correspond to implicit roots when an explicit version of the EDT subtree
% rooted at the node has not yet been generated.
%
% Every node in the EDT may not have a corresponing node in the search space:
% nodes are only added to the search space when they are needed by a
% particular search algorithm.
%
% By convention nodes in the search space are referred to as `suspects', while
% nodes in the EDT are referred to as `EDT nodes', or just `nodes'.
%

I haven't defined what the search space root is here, because I do that with
the search_space type definition.  Is that okay?

> > +		% If this node is an e_bug, then find the bug.
> > +		%
> > +	pred edt_root_e_bug(io_action_map::in, S::in, T::in, decl_e_bug::out)
> > +		is det,
> 
> You should provide a reference or a definition, either here or at the top
> of the module, for the e_bug/i_bug notation.
> 
Okay I changed the comments to the following and also renamed the methods, as
the "root" part doesn't seem to mean anything here (evey node is the root of
some subtree, so what's the point of using that term here?).

                % If this node is an E-bug, then return the bug.
                % An E-bug is an erroneous node whos children are all correct.
                %
        pred edt_get_e_bug(io_action_map::in, S::in, T::in, decl_e_bug::out)
                is det,

                % If this node is an I-bug then return the bug.
                % An I-bug is an erroneous node whos children are all correct
                % or inadmissible, with at least one child being inadmissible.
                %
        pred edt_get_i_bug(S::in, T::in, T::in, decl_i_bug::out) is det,

> > +		% edt_root_i_bug(Store, BugNode, InadmissibleChild, Bug) 
> > +		% Get the I-bug corresponding to the give erroneous node
> > +		% (BugNode) and its inadmissible child.
> > +		%
> > +	pred edt_root_i_bug(S::in, T::in, T::in, decl_i_bug::out) is det,
> 
> This predicate cannot be det without the precondition "If BugNode has an
> inadmissible child, then ...".
> 
> Be consistent with I-bug vs i_bug.
> 
See above.

> > +		% Gives the list of children of a tree.  If the tree is
> > +		% represented implicitly, then the procedure fails.
> > +		%
> > +	pred edt_children(S::in, T::in, list(T)::out) is semidet,
> 
> Gives the list of children of *the given tree node*.
I agree and have changed the comment.

> 
> > +		% Given a subterm of a tree, find the mode of that subterm
> > +		% and the origin of it amongst the parent, siblings or
> > +		% children.
> > +		%
> > +	pred edt_dependency(S, T, arg_pos, term_path, subterm_mode,
> > +			subterm_origin(T)),
> > +	mode edt_dependency(in, in, in, in, out, out) is det,
> 
> Use combined predmode declaration for consistency.
> 
Done.
> > +		% Just find the mode of the subterm.
> > +		%
> > +	pred edt_subterm_mode(S::in, T::in, arg_pos::in, term_path::in,
> > +		subterm_mode::out) is det,
> > +	
> > +		% Succeeds if the Node is the root of an implicit subtree.
> > +		% Fails otherwise.
> > +		%
> > +	pred edt_implicit_root(S::in, T::in) is semidet
> > +].
> 
> I would name this predicate edt_is_implicit_root.
> 
Done.
> > +:- type subterm_origin(T)
> 
> If you count arguments from the back, then you must document that here.
> 
Whether args are counted from the back or not is encapsulated in the arp_pos
type, so I wouldn't say such a comment would be relevant to the subterm_origin
type.

> > +	% Succeeds if the given search space contains no suspects.
> > +	%
> > +:- pred empty_search_space(search_space(T)::out) is det.
> 
> Make the documentation
> 
> % Returns a search space with no suspects.
> 
Done.

Thanks for the comments.

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