Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-23T11:49:24.819Z Has data issue: false hasContentIssue false
  • English
  • Français

Stepwise debugging of answer-set programs*

Published online by Cambridge University Press:  17 October 2017

JOHANNES OETSCH ,
JÖRG PÜHRER Open the ORCID record for JÖRG PÜHRER [Opens in a new window]  and
HANS TOMPITS
JOHANNES OETSCH
Affiliation:
Technische Universität Wien, Institut für Informationssysteme 184/3, Favoritenstrasse 9-11, A-1040 Vienna, Austria, (e-mail: [email protected])
JÖRG PÜHRER
Affiliation:
Universität Leipzig, Institut für Informatik, Augustusplatz 10, D-04109 Leipzig, Germany, (e-mail: [email protected])
HANS TOMPITS
Affiliation:
Technische Universität Wien, Institut für Informationssysteme 184/3, Favoritenstrasse 9-11, A-1040 Vienna, Austria, (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We introduce a stepping methodology for answer-set programming (ASP) that allows for debugging answer-set programs and is based on the stepwise application of rules. Similar to debugging in imperative languages, where the behaviour of a program is observed during a step-by-step execution, stepping for ASP allows for observing the effects that rule applications have in the computation of an answer set. While the approach is inspired from debugging in imperative programming, it is conceptually different to stepping in other paradigms due to non-determinism and declarativity that are inherent to ASP. In particular, unlike statements in an imperative program that are executed following a strict control flow, there is no predetermined order in which to consider rules in ASP during a computation. In our approach, the user is free to decide which rule to consider active in the next step following his or her intuition. This way, one can focus on interesting parts of the debugging search space. Bugs are detected during stepping by revealing differences between the actual semantics of the program and the expectations of the user. As a solid formal basis for stepping, we develop a framework of computations for answer-set programs. For fully supporting different solver languages, we build our framework on an abstract ASP language that is sufficiently general to capture different solver languages. To this end, we make use of abstract constraints as an established abstraction for popular language constructs such as aggregates. Stepping has been implemented in SeaLion, an integrated development environment for ASP. We illustrate stepping using an example scenario and discuss the stepping plugin of SeaLion. Moreover, we elaborate on methodological aspects and the embedding of stepping in the ASP development process.

Keywords

answer-set programmingdebuggingsteppingprogram analysis
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 18 , Issue 1 , January 2018 , pp. 30 - 80
Copyright
Copyright © Cambridge University Press 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

*

This work was partially supported by the Austrian Science Fund (FWF) under project P21698, the German Research Foundation (DFG) under Grants BR-1817/7-1 and BR 1817/7-2 and the European Commission under project IST-2009-231875 (OntoRule).

References

Alviano, M., Dodaro, C., Leone, N. and Ricca, F. 2015. Advances in WASP. In Proc. of Logic Programming and Nonmonotonic Reasoning - 13th International Conference, LPNMR, Lexington, KY, USA, September 27–30, 2015, F. Calimeri, G. Ianni and M. Truszczyński, Eds. Lecture Notes in Computer Science, vol. 9345. Springer, 40–54.Google Scholar
Ben-Eliyahu, R. and Dechter, R. 1994. Propositional semantics for disjunctive logic programs. Annals of Mathematics and Artificial Intelligence, 12, 1–2, 53–87.CrossRefGoogle Scholar
Brain, M. and De Vos, M. 2005. Debugging logic programs under the answer set semantics. In Proc. of the 3rd International Workshop on Answer Set Programming (ASP'05), Advances in Theory and Implementation, Bath, UK, September 27–29, 2005, M. De Vos and A. Provetti, Eds. CEUR Workshop Proceedings, vol. 142. CEUR-WS.org.Google Scholar
Brain, M., Gebser, M., Puehrer, J., Schaub, T., Tompits, H. and Woltran, S. 2007a. That is illogical Captain! The debugging support tool spock for answer-set programs – System description. In Proc. of the 1st International Workshop on Software Engineering for Answer Set Programming (SEA'07), Tempe, AZ, USA, May 14, 2007, M. De Vos and T. Schaub, Eds., 71–85.Google Scholar
Brain, M., Gebser, M., Pührer, J., Schaub, T., Tompits, H. and Woltran, S. 2007b. Debugging ASP programs by means of ASP. In Proc. of the 9th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'07), Tempe, AZ, USA, May 15–17, 2007, Baral, C., Brewka, G., and Schlipf, J. S., Eds. Lecture Notes in Computer Science, vol. 4483. Springer, 31–43.Google Scholar
Brochenin, R., Lierler, Y. and Maratea, M. 2014. Abstract disjunctive answer set solvers. In Proc. of the 21st European Conference on Artificial Intelligence (ECAI'14), Prague, Czech Republic, Aug. 18–22, 2014, Schaub, T., Friedrich, G., and O'Sullivan, B., Eds. Frontiers in Artificial Intelligence and Applications, vol. 263. IOS Press, 165–170.Google Scholar
Busoniu, P.-A., Oetsch, J., Pührer, J., Skočovský, P. and Tompits, H. 2013. Sealion: An eclipse-based IDE for answer-set programming with advanced debugging support. Theory and Practice of Logic Programming 13, 4–5, 657–673.Google Scholar
Caballero, R., García-Ruiz, Y. and Sáenz-Pérez, F. 2008. A theoretical framework for the declarative debugging of datalog programs. In Revised Selected Papers of the 3rd International Workshop on Semantics in Data and Knowledge Bases (SDKB'08), Nantes, France, March 29, 2008, Schewe, K.-D. and Thalheim, B., Eds. Lecture Notes in Computer Science, vol. 4925. Springer, 143–159.Google Scholar
Denecker, M. 2000. Extending classical logic with inductive definitions. In Proc. of the 1st International Conference on Computational Logic (CL'10), London, UK, July 24–28, 2000, Lloyd, J. W., Dahl, V., Furbach, U., Kerber, M., Lau, K., Palamidessi, C., Pereira, L. M., Sagiv, Y. and Stuckey, P. J., Eds. Lecture Notes in Computer Science, vol. 1861. Springer, 703–717.Google Scholar
Denecker, M. and Ternovska, E. 2008. A logic of nonmonotone inductive definitions. ACM Transactions on Computational Logic 9, 2.CrossRefGoogle Scholar
Denecker, M., Vennekens, J., Bond, S., Gebser, M. and Truszczyński, M. 2009. The second answer set programming competition. In Proc. of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'09), Potsdam, Germany, September 14–18, 2009, Erdem, E., Lin, F., and Schaub, T., Eds. Lecture Notes in Computer Science, vol. 5753. Springer, 637–654.Google Scholar
Dodaro, C., Gasteiger, P., Musitsch, B., Ricca, F. and Shchekotykhin, K. M. 2015. Interactive debugging of non-ground ASP programs. In Proc. of Logic Programming and Nonmonotonic Reasoning - 13th International Conference, LPNMR 2015, Lexington, KY, USA, September 27–30, 2015, Calimeri, F., Ianni, G. and Truszczyński, M., Eds. Lecture Notes in Computer Science, vol. 9345. Springer, 279–293.Google Scholar
Eiter, T., Ianni, G., Schindlauer, R. and Tompits, H. 2005. A uniform integration of higher-order reasoning and external evaluations in answer-set programming. In Proc. of the 19th International Joint Conference on Artificial Intelligence (IJCAI'05), Edinburgh, Scotland, UK, July 30–August 5, 2005, Kaelbling, L. P. and Saffiotti, A., Eds. Professional Book Center, 90–96.Google Scholar
Faber, W., Leone, N. and Pfeifer, G. 2004. Recursive aggregates in disjunctive logic programs: Semantics and complexity. In Proc. of the 9th European Conference on Logics in Artificial Intelligence (JELIA'04). Lecture Notes in Computer Science, vol. 3229. Springer, 200–212.Google Scholar
Faber, W., Pfeifer, G. and Leone, N. 2011. Semantics and complexity of recursive aggregates in answer set programming. Artificial Intelligence 175, 1, 278–298.CrossRefGoogle Scholar
Ferraris, P. 2011. Logic programs with propositional connectives and aggregates. ACM Transactions on Computational Logic 12, 4, 25.CrossRefGoogle Scholar
Frühstück, M., Pührer, J. and Friedrich, G. 2013. Debugging answer-set programs with Ouroboros – Extending the SeaLion plugin. In Proc. of the 12th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'13), Corunna, Spain, September 15–19, 2013, Cabalar, P. and Son, T. C., Eds. Lecture Notes in Computer Science, vol. 8148. Springer, 323–328.Google Scholar
Gebser, M., Kaminski, R., König, A. and Schaub, T. 2011. Advances in gringo series 3. In Proc. of the 11th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'11), Vancouver, Canada, May 16–19, 2011, Delgrande, J. P. and Faber, W., Eds. Lecture Notes in Computer Science, vol. 6645. Springer, 345–351.Google Scholar
Gebser, M., Kaufmann, B. and Schaub, T. 2012. Conflict-driven answer set solving: From theory to practice. Artificial Intelligence 187–188, 52–89.Google Scholar
Gebser, M., Lee, J. and Lierler, Y. 2011. On elementary loops of logic programs. Theory and Practice of Logic Programming 11, 6, 953–988.Google Scholar
Gebser, M., Pührer, J., Schaub, T. and Tompits, H. 2008. A meta-programming technique for debugging answer-set programs. In Proc. of the 23rd AAAI Conference on Artificial Intelligence (AAAI'08), Chicago, IL, USA, July 13–17, 2008, Fox, D. and Gomes, C. P., Eds. AAAI Press, 448–453.Google Scholar
Gebser, M., Pührer, J., Schaub, T., Tompits, H. and Woltran, S. 2009. Spock: A debugging support tool for logic programs under the answer-set semantics. In Revised Selected Papers of the 17th International Conference on Applications of Declarative Programming and Knowledge Management (INAP'07) and 21st Workshop on (Constraint) Logic Programming (WLP'07), Seipel, D., Hanus, M. and Wolf, A., Eds. Lecture Notes in Computer Science, vol. 5437. Springer, 247–252.Google Scholar
Gelfond, M. and Lifschitz, V. 1991. Classical negation in logic programs and disjunctive databases. New Generation Computing 9, 3/4, 365–386.CrossRefGoogle Scholar
Kloimüllner, C., Oetsch, J., Pührer, J. and Tompits, H. 2013. Kara: A system for visualising and visual editing of interpretations for answer-set programs. In Revised Selected Papers of the 19th International Conference on Applications of Declarative Programming and Knowledge Management (INAP'11) and the 25th Workshop on Logic Programming (WLP'11), Vienna, Austria, September 28–30, 2011. Lecture Notes in Computer Science, vol. 7773. Springer, 325–344.Google Scholar
Lee, J. 2005. A model-theoretic counterpart of loop formulas. In Proc. of the 19th International Joint Conference on Artificial Intelligence (IJCAI'05), Edinburgh, Scotland, UK, July 30–August 5, 2005, Kaelbling, L. P. and Saffiotti, A., Eds. Professional Book Center, 503–508.Google Scholar
Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S. and Scarcello, F. 2006. The DLV system for knowledge representation and reasoning. ACM Transactions on Computational Logic 7, 3, 499–562.Google Scholar
Li, T., Vos, M. D., Padget, J., Satoh, K. and Balke, T. 2015. Debugging ASP using ILP. In Technical Communications of the 31st International Conference on Logic Programming (ICLP 2015), Cork, Ireland, August 31–September 4, 2015, Vos, M. D., Eiter, T., Lierler, Y. and Toni, F., Eds. CEUR Workshop Proceedings, vol. 1433. CEUR-WS.org.Google Scholar
Lierler, Y. 2011. Abstract answer set solvers with backjumping and learning. Theory and Practice of Logic Programming 11, 2–3, 135–169.Google Scholar
Lierler, Y. and Truszczyński, M. 2016. On abstract modular inference systems and solvers. Artificial Intelligence 236, 65–89.Google Scholar
Liu, L., Pontelli, E., Son, T. C. and Truszczyński, M. 2010. Logic programs with abstract constraint atoms: The role of computations. Artificial Intelligence 174, 3–4, 295–315.Google Scholar
Marek, V. W. and Remmel, J. B. 2004. Set constraints in logic programming. In Proc. of the 7th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'04), Fort Lauderdale, FL, USA, January 6–8, 2004, Lifschitz, V. and Niemelä, I., Eds. LNCS, vol. 2923. Springer, 167–179.Google Scholar
Marek, V. W. and Truszczyński, M. 1999. Stable models and an alternative logic programming paradigm. In The Logic Programming Paradigm: A 25-Year Perspective, Apt, K. R., Marek, V. W., Truszczyński, M. and Warren, D. S., Eds. Springer, 375–398.Google Scholar
Marek, V. W. and Truszczyński, M. 2004. Logic programs with abstract constraint atoms. In Proc. of the 19th National Conference on Artificial Intelligence (AAAI'04), San Jose, CA, USA, July 25–29, 2004, Ferguson, G. and McGuinness, D., Eds. AAAI Press, 86–91.Google Scholar
Mikitiuk, A., Moseley, E. and Truszczyński, M. 2007. Towards debugging of answer-set programs in the language PSpb. In Proc. of the 2007 International Conference on Artificial Intelligence (ICAI'07), Volume II, Las Vegas, NV, USA, June 25–28, 2007, Arabnia, H. R., Yang, M. Q. and Yang, J. Y., Eds. CSREA Press, 635–640.Google Scholar
Niemelä, I. 1999. Logic programs with stable model semantics as a constraint programming paradigm. Annals of Mathematics and Artificial Intelligence 25, 3–4, 241–273.CrossRefGoogle Scholar
Nieuwenhuis, R., Oliveras, A. and Tinelli, C. 2006. Solving SAT and SAT modulo theories: From an abstract Davis-Putnam-Logemann-Loveland procedure to dpll(T). Journal of the ACM 53, 6, 937–977.Google Scholar
Oetsch, J., Pührer, J. and Tompits, H. 2010a. Catching the Ouroboros: On debugging non-ground answer-set programs. Theory and Practice of Logic Programming 10, 4–6 (July), 513–529.Google Scholar
Oetsch, J., Pührer, J. and Tompits, H. 2010b. Let's break the rules: Interactive procedural-style debugging of answer-set programs. In Proc. of the 24th Workshop on (Constraint) Logic Programming (WLP'10), Cairo, Egypt, September 14–16, 2010, Abdennadher, S., Ed. Technical Report, Faculty of Media Engineering and Technology, German University in Cairo, 77–87.Google Scholar
Oetsch, J., Pührer, J. and Tompits, H. 2011. Stepping through an answer-set program. In Proc. of the 11th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'11), Vancouver, Canada, May 16–19, 2011. Lecture Notes in Computer Science, vol. 6645. Springer, 134–147.Google Scholar
Oetsch, J., Pührer, J. and Tompits, H. 2012a. An FLP-style answer-set semantics for abstract-constraint programs with disjunctions. In Technical Communications of the 28th International Conference on Logic Programming (ICLP'12), Budapest, Hungary, Dovier, A. and Costa, V. S., Eds. LIPIcs, vol. 17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 222–234.Google Scholar
Oetsch, J., Pührer, J. and Tompits, H. 2012b. Stepwise debugging of description-logic programs. In Correct Reasoning - Essays on Logic-Based AI in Honour of Vladimir Lifschitz, Erdem, E., Lee, J., Lierler, Y. and Pearce, D., Eds. Lecture Notes in Computer Science, vol. 7265. Springer, 492–508.Google Scholar
Oetsch, J., Pührer, J. and Tompits, H. 2013. The SeaLion has landed: An IDE for answer-set programming–Preliminary report. In Revised Selected Papers of the 19th International Conference on Applications of Declarative Programming and Knowledge Management (INAP'11) and the 25th Workshop on Logic Programming (WLP'11), Vienna, Austria, September 28–30, 2011. Lecture Notes in Computer Science, vol. 7773. Springer, 305–324.Google Scholar
Polleres, A., Frühstück, M., Schenner, G. and Friedrich, G. 2013. Debugging non-ground ASP programs with choice rules, cardinality constraints and weight constraints. In Proc. of the 12th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'13), Corunna, Spain, September 15–19, 2013, Cabalar, P. and Son, T. C., Eds. Lecture Notes in Computer Science, vol. 8148. Springer, 452–464.Google Scholar
Pontelli, E., Son, T. C. and El-Khatib, O. 2009. Justifications for logic programs under answer set semantics. Theory and Practice of Logic Programming 9, 1, 1–56.Google Scholar
Pührer, J. 2007. On debugging of propositional answer-set programs. Master's thesis, Vienna University of Technology, Vienna, Austria.Google Scholar
Pührer, J. 2014. Stepwise Debugging in Answer-Set Programming: Theoretical Foundations and Practical Realisation. PhD thesis, Vienna University of Technology, Vienna, Austria. Accessed 14 December 2016. URL: http://repositum.tuwien.ac.at/urn:nbn:at:at-ubtuw:1-75281 [online].Google Scholar
Redl, C. 2016. The DLVHEX system for knowledge representation: Recent advances (system description). Theory and Practice of Logic Programming 16, 5–6, 866–883.Google Scholar
Shapiro, E. Y. 1982. Algorithmic Program Debugging. PhD thesis, Yale University, New Haven, CT, USA.Google Scholar
Shchekotykhin, K. M. 2015. Interactive query-based debugging of ASP programs. In Proc. of the 29th AAAI Conference on Artificial Intelligence (AAAI'15), Austin, TX, USA, January 25–30, 2015, Bonet, B. and Koenig, S., Eds. AAAI Press, 1597–1603.Google Scholar
Simons, P., Niemelä, I. and Soininen, T. 2002. Extending and implementing the stable model semantics. Artificial Intelligence 138, 181–234.Google Scholar
Syrjänen, T. 2006. Debugging inconsistent answer set programs. In Proc. of the 11th International Workshop on Non-Monotonic Reasoning (NMR'06), Lake District, UK, May 30–June 1, 2006, Dix, J. and Hunter, A., Eds. Institut für Informatik, Technische Universität Clausthal, Technical Report, 77–83.Google Scholar
Truszczyński, M. 2010. Reducts of propositional theories, satisfiability relations, and generalizations of semantics of logic programs. Artificial Intelligence 174, 16–17, 1285–1306.Google Scholar
Wittocx, J., Vlaeminck, H. and Denecker, M. 2009. Debugging for model expansion. In Proc. of the 25th International Conference on Logic Programming (ICLP'09), Pasadena, CA, USA, July 14–17, 2009, Hill, P. M. and Warren, D. S., Eds. Lecture Notes in Computer Science, vol. 5649. Springer, 296–311.Google Scholar
Supplementary material: PDF

Oetsch et al supplementary material

Oetsch et al supplementary material 1

Download Oetsch et al supplementary material(PDF)
PDF 247.4 KB