Advanced Techniques for Algorithmic Debugging

Abstract

Algorithmic Debugging (a.k.a. Declarative Debugging) is a semi-automatic debugging technique that allows the programmer to isolate the code where a bug is located without the need to see the source code. To do so, the programmer answers the questions performed by the debugger until it finds the bug and shows it to the user. These questions are chosen by the debugger using a strategy, and thus the reduction of the number of questions is a main objective of this debugging technique. In practice, the strategy that performs less questions has been Divide & Query (D&Q for short) since its definition 30 years ago. This strategy has been considered optimal in the worst case. In this work we show that D&Q is not optimal and we introduce two new strategies that have proved to be better. One of them is a new version of D&Q where its behavior is improved in some situations. While the other is the first version of a new strategy that is optimal in the worst case. Moreover, we present new techniques that improve the efficiency of Algorithmic Debugging, allowing the debugger to speed-up the questions asked to the user and to reduce the number of questions performed regardless of the used strategy.