Answer Set Programming (ASP) is one of the major declarative programming paradigms in the area of logic programming and non-monotonic reasoning. Despite that ASP features a simple syntax and an intuitive semantics, errors are common during the development of ASP programs. In this paper we propose a novel debugging approach allowing for interactive localization of bugs in non-ground programs. The new approach points the user directly to a set of non-ground rules involved in the bug, which might be refined (up to the point in which the bug is easily identified) by asking the programmer a sequence of questions on an expected answer set. The approach has been implemented on top of the ASP solver WASP. The resulting debugger has been complemented by a user-friendly graphical interface, and integrated in ASPIDE, a rich IDE for answer set programs. In addition, an empirical analysis shows that the new debugger is not affected by the grounding blowup limiting the application of previous approaches based on meta-programming. Under consideration in Theory and Practice of Logic Programming (TPLP).
There are multiple approaches to ASP debugging suggested in the literature including algorithmic @cite_14 @cite_33 , stepping-based @cite_37 and meta-programming @cite_13 @cite_1 @cite_25 @cite_44 @cite_11 methods. Among the algorithmic approaches @cite_14 aims at explaining: (a) why a set of atoms @math is in an answer set @math , and (b) why @math is not in any answer set. allows a programmer: (1) to query for an explanation of an observed fault, (2) to analyze the obtained results and (3) reformulate the query to make it more precise. In our approach refinements are found automatically once the user provides additional knowledge on an expected answer set, thus, making the steps (2) and (3) obsolete.
@cite_37 @cite_14 @cite_33 @cite_1 @cite_44 @cite_13 @cite_25 @cite_11
2171836055 2138596350 50549667 2169041689
Answer-set programming (ASP) is widely recognised as a viable tool for declarative problem solving. However, there is currently a lack of tools for developing answer-set programs. In particular, providing tools for debugging answer-set programs has recently been identified as a crucial prerequisite for a wider acceptance of ASP. In this paper, we introduce a meta-programming technique for debugging in ASP. The basic question we address is why interpretations expected to be answer sets are not answer sets of the program to debug. We thus deal with finding semantical errors of programs. The explanations provided by our method are based on an intuitive scheme of errors that relies on a recent characterisation of the answer-set semantics. Furthermore, as we are using a meta-programming technique, debugging queries are expressed in terms of answer-set programs themselves, which has several benefits: For one, we can directly use ASP solvers for processing debugging queries. Indeed, our technique can easily be implemented, and we devised a corresponding prototype debugging system. Also, our approach respects the declarative nature of ASP, and the capabilities of the system can easily be extended to incorporate differing debugging features. The paper introduces the notion of offline justification for answer set programming (ASP). Justifications provide a graph-based explanation of the truth value of an atom with respect to a given answer set. The paper extends also this notion to provide justification of atoms during the computation of an answer set (on-line justification) and presents an integration of online justifications within the computation model of SMODELS. Offline and online justifications provide useful tools to enhance understanding of ASP, and they offer a basic data structure to support methodologies and tools for debugging answer set programs. A preliminary implementation has been developed in . In recent years, Answer Set Programming ASP, logic programming under the stable model or answer set semantics, has seen several extensions by generalizing the notion of an atom in these programs: be it aggregate atoms, HEX atoms, generalized quantifiers, or abstract constraints, the idea is to have more complicated satisfaction patterns in the lattice of Herbrand interpretations than traditional, simple atoms. In this paper we refer to any of these constructs as generalized atoms. It is known that programs with generalized atoms that have monotonic or antimonotonic satisfaction patterns do not increase complexity with respect to programs with simple atoms if satisfaction of the generalized atoms can be decided in polynomial time under most semantics. It is also known that generalized atoms that are nonmonotonic being neither monotonic nor antimonotonic can, but need not, increase the complexity by one level in the polynomial hierarchy if non-disjunctive programs under the FLP semantics are considered. In this paper we provide the precise boundary of this complexity gap: programs with convex generalized atom never increase complexity, while allowing a single non-convex generalized atom under reasonable conditions always does. We also discuss several implications of this result in practice. An important issue towards a broader acceptance of answer-set programming (ASP) is the deployment of tools which support the programmer during the coding phase. In particular, methods for debugging an answer-set program are recognised as a crucial step in this regard. Initial work on debugging in ASP mainly focused on propositional programs, yet practical debuggers need to handle programs with variables as well. In this paper, we discuss a debugging technique that is directly geared towards non-ground programs. Following previous work, we address the central debugging question why some interpretation is not an answer set. The explanations provided by our method are computed by means of a meta-programming technique, using a uniform encoding of a debugging request in terms of ASP itself. Our method also permits programs containing comparison predicates and integer arithmetics, thus covering a relevant language class commonly supported by all state-of-the-art ASP solvers.