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 integrated development environment (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.

Artificial intelligence (AI) approaches to problem-solving and decision-making are becoming more and more complex, leading to a decrease in the understandability of solutions. The European Union’s new General Data Protection Regulation tries to tackle this problem by stipulating a “right to explanation” for decisions made by AI systems. One of the AI paradigms that may be affected by this new regulation is answer set programming (ASP). Thanks to the emergence of efficient solvers, ASP has recently been used for problem-solving in a variety of domains, including medicine, cryptography, and biology. To ensure the successful application of ASP as a problem-solving paradigm in the future, explanations of ASP solutions are crucial. In this survey, we give an overview of approaches that provide an answer to the question of why an answer set is a solution to a given problem, notably off-line justifications, causal graphs, argumentative explanations, and why-not provenance, and highlight their similarities and differences. Moreover, we review methods explaining why a set of literals is not an answer set or why no solution exists at all.

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.

Mathematical programming formulations can yield faulty answers. Models can be unbounded, infeasible, or optimal with unrealistic answers. This article presents techniques for theory-based discovery of the cause of faulty models. The approaches are demonstrated in the context of linear programming. They have been computerized and interfaced using the General Algebraic Modeling System (GAMS), and are distributed free of charge through new GAMS versions and an online web page.

Coding standards and good practices are fundamental to a disciplined approach to software projects irrespective of programing languages being employed. Prolog programing can benefit from such an approach, perhaps more than programing in other languages. Despite this, no widely accepted standards and practices seem to have emerged till now. The present paper is a first step toward filling this void: It provides immediate guidelines for code layout, naming conventions, documentation, proper use of Prolog features, program development, debugging, and testing. Presented with each guideline is its rationale and, where sensible options exist, illustrations of the relative pros and cons for each alternative. A coding standard should always be selected on a per-project basis, based on a host of issues pertinent to any given programing project; for this reason the paper goes beyond the mere provision of normative guidelines by discussing key factors and important criteria that should be taken into account when deciding on a full-fledged coding standard for the project.

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.

This paper develops automated testing and debugging techniques for answer set solver development. We describe a flexible grammar-based black-box ASP fuzz testing tool which is able to reveal various defects such as unsound and incomplete behavior, i.e. invalid answer sets and inability to find existing solutions, in state-of-the-art answer set solver implementations. Moreover, we develop delta debugging techniques for shrinking failure-inducing inputs on which solvers exhibit defective behavior. In particular, we develop a delta debugging algorithm in the context of answer set solving, and evaluate two different elimination strategies for the algorithm.

Tracers provide users with useful information about program executions. In thisarticle, we propose a “tracer driver”. From a single tracer,it provides a powerful front-end enabling multiple dynamic analysis tools to beeasily implemented, while limiting the overhead of the trace generation. Therelevant execution events are specified by flexible event patterns and a largevariety of trace data can be given either systematically or “ondemand”. The proposed tracer driver has been designed in the contextof constraint logic programming (CLP); experiments have been made withinGNU-Prolog. Execution views provided by existing tools have been easily emulatedwith a negligible overhead. Experimental measures show that the flexibility andpower of the described architecture lead to good performance. The tracer driveroverhead is inversely proportional to the average time between two tracedevents. Whereas the principles of the tracer driver are independent of thetraced programming language, it is best suited for high-level languages, such asCLP, where each traced execution event encompasses numerous low-level executionsteps. Furthermore, CLP is especially hard to debug. The current environments donot provide all the useful dynamic analysis tools. They can significantlybenefit from our tracer driver which enables dynamic analyses to be integratedat a very low cost.

This paper introduces a framework of parametric descriptive directional types for Constraint Logic Programming (CLP). It proposes a method for locating type errors in CLP programs, and presents a prototype debugging tool. The main technique used is checking correctness of programs w.r.t. type specifications. The approach is based on a generalization of known methods for proving the correctness of logic programs to the case of parametric specifications. Set constraint techniques are used for formulating and checking verification conditions for (parametric) polymorphic type specifications. The specifications are expressed in a parametric extension of the formalism of term grammars. The soundness of the method is proved, and the prototype debugging tool supporting the proposed approach is illustrated on examples. The paper is a substantial extension of the previous work by the same authors concerning monomorphic directional types.

A manuscript with an unknown random number M of misprints is subjected to a series of proofreadings in an effort to detect and correct the misprints. On the nthproofreading, each remaining misprint is detected independently with probability pn– 1. Each proofreading costs an amount CP > 0, and if one stops after n proofreadings, each misprint overlooked costs an amount cn > 0. Two models are treated based on the distribution of M. In the Poisson model, the optimal stopping rule is seen to be a fixed sample size rule. In the binomial model, the myopic rule is optimal in many important cases. A generalization is made to problems in which individual misprints may have distinct probabilities of detection and distinct overlook costs.