Probabilistic Declarative Debugging

Lee Naish

We present a probabilistic approach to the search strategy for declarative debugging. We focus on diagnosing wrong answers in pure Prolog programs but the approach can be adapted to other languages (for example, functional languages) and bug symptoms. Drawing information from source code and the execution of passed and failed test cases, different search heuristics are combined using probability theory. This reduces the expected number and complexity of questions. We appeal to rationality to compare several search algorithms. Algorithms such as ours, which use more information and make weaker assumptions, generally have better performance. Examples are also given to illustrate how the algorithm can perform extremely well when certain heuristics are effective, and reasonably well even when the heuristics are ineffective.