[m-dev.] PADL'06 paper

[Ian MacLarty]

Zoltan's and my paper, "Controlling search space materialization in a 
practical declarative debugger", got accepted at PADL'06.

Here are the review comments:

Begin forwarded message:

> From: "PADL'06" <pvh at cs.brown.edu>
> Date: 30 September 2005 22:56:42 GMT+10:00
> To: maclarty at cs.mu.OZ.AU
> Subject: reviews on your PADL'06 paper
> Reply-To: "PADL'06" <pvh at cs.brown.edu>
>
> Paper: 9
> Title: Controlling search space materialization in a practical 
> declarative debugger
>
> -------------------- review 118 --------------------
>
> OVERALL RATING: 1 (weak accept)
> CONFIDENCE: 3 (high)
> CLARITY: 4 (good)
> RELEVANCE: 4 (good)
> SIGNIFICANCE: 4 (good)
> ORIGINALITY: 3 (fair)
> OVERALL RATING: 4 (good)
>
> ----------------------- REVIEW --------------------
>
> In debugging in a search based framework, it is necessary to decide 
> which nodes in the search tree to make explicit during re-execution. 
> The underlying consideration that drives the work in this paper is the 
> number of nodes that result from using a particular policy that, in 
> turn, gives an indication of the amount of space needed for each 
> expansion wave. A simple strategy is to assume a fixed branching 
> factor, that could itself be determined by a dynamic calculation. The 
> paper shows that this is not a good model to use in typical 
> applications; the analysis is that branching profiles can be different 
> over different parts of the search and this can result in bad 
> estimates of (average) branching factor. A more elaborate "runtime" 
> scheme called the ideal depth strategy is then described that ensures 
> no more nodes than the limit are ever made explicit but that, 
> simultaneously, makes an attempt to get close to this limit. Empirical 
> evidence is provided for the fact that the latter!
>   objective is achieved.
>
> The work in the paper is certainly relevant to the practice of 
> declarative programming and the authors (obliquely) offer evidence for 
> the fact that their technique has been useful in the Mercury system. 
> These are arguments for acceptance. On the negative side, the 
> presentation of the specific "winning" algorithm is poor to a point 
> where I am not sure I have understood all its details. Based on what I 
> have understood, the idea does not seem to be very deep. In another 
> direction, I was not quite able to see what kind of a 
> "rematerialization profile" the heuristic ends up creating for the 
> frontier of the tree and how this impacts on the debugging process. 
> Trying to get close to the node limit is important but trying to get 
> quickly to the point of the bug may be more important and the authors 
> should say more about how the method presented affects this latter 
> ability.
>
>
> -------------------- review 29 --------------------
>
> OVERALL RATING: 2 (accept)
> CONFIDENCE: 3 (high)
> CLARITY: 5 (excellent)
> RELEVANCE: 4 (good)
> SIGNIFICANCE: 4 (good)
> ORIGINALITY: 4 (good)
> OVERALL RATING: 4 (good)
>
> ----------------------- REVIEW --------------------
>
> The authors propose a new algorithm for keeping track of the very 
> large number of program points that can arise in a declarative 
> debugger.  The problem is clearly defined, problems with old solutions 
> are described well, and the “ideal” solution is then presented.  The 
> effectiveness of the technique is given via benchmarks.
>
> Although the contribution here isn’t huge, I think that it’s a novel 
> solution that contributes to solving an important problem, namely 
> implementing effective declarative debuggers.  It seems a little 
> long-winded in places, and I would prefer seeing a broader range of 
> benchmarks, but otherwise I think that it’s a suitable paper for PADL.
>
>
> -------------------- review 5 --------------------
>
> OVERALL RATING: 2 (accept)
> CONFIDENCE: 4 (expert)
> CLARITY: 3 (fair)
> RELEVANCE: 5 (excellent)
> SIGNIFICANCE: 4 (good)
> ORIGINALITY: 4 (good)
> OVERALL RATING: 4 (good)
>
> ----------------------- REVIEW --------------------
>
> The paper presents a strategy of "execution replay" in the context of
> Mercury for debugging. "Execution replay" is an active topic of
> research for parallel and distributed languages. It consists of
> designing strategies in order to store minimal abstract information 
> about
> executions in order to be able to faithfully replay executions. The
> problem is that in general it is impossible to store everything. The
> point is then to design what information to compute and store in order
> to be able to replay.
>
> The problems are more accute in // programming because of race and
> probe effects. The problem is still relevant for deterministic
> languages for debugging. Indeed, debugging strategies, whether
> automatic (algorithmic debugging) or manual (the user in command), do
> all, in essence, traverse a search space too large to be stored.
>
> This article, presents two naive heuritics which do not work (with
> explanations of why is this) and one heuristic which is quite
> convincing.
>
> The search space is a tree (as designed by Nilsson et al). The "good"
> heuristic computes the number of nodes of a given subtree during the
> execution and stores this abstraction in order to decide what to store
> during the traversal.
>
> The measurements do properly illustrate that there is some balance
> between re-execution and storage. For each execution, there is a limit
> node number for which traversal with this limited storage gives better
> execution times than re-executing all the time and better storage
> consumption than storing everything.
>
> I believe that the topic is relevant for the conference. Indeed
> declarative debugging is probably only meaningful for Mercury a real
> declarative langage, and the adressed problems improve implementation
> of debugging tools.
>
> The research is also original. Since the work of Plaisted in
> 82 I am not aware of a significant improvement in this area for
> declarative languages.
>
> The work is significant because it would help even for traditional
> debugging even if the authors do not seem aware of it.
>
> The paper is reasonably well written I rated the clarity "fair" only,
> because
>
> 	- "Execution replay" must be mentioned to put that article in
> perspective. At present, it may look to non expert eyes like a small
> hack in an obscure corner. See for example the survey of Ronnsse et
> al. at AADEBUG 2000.
>
> 	- Instead of presenting the algorithms first. The paper would
> have a much greater impact if the *data structure* on which the
> algorithms work was properly defined. Indeed, to my point of view, the
> main contribution of the article is the "abstract search tree" with
> the nodes containing the execution details and/or the count of
> events. This data structure could be the basis of numerous traversal
> strategies. Enhancing this data structure offers good perspectives. If
> the paper is accepted, I strongly advise the authors to formally
> define this data structure.
>
> 	- I do not think that the 3 pages describing the failing
> heuritics are all needed... Shortening them and adding the above
> requested definition would make a much stronger paper !
>
>
> 	- Debugging work in Logic programming must also be cited
> (Brayshaw, Ducasse, Eisenstadt, Lloyd, Naish, for example). As a
> matter of fact the reference list is quite poor (5 self references,
> and the others go way back...).
>


--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------