imported>Oxymoronic1: /* growthexperiments-addlink-summary-summary:2|0|1 */

2025-09-25T18:33:42Z

growthexperiments-addlink-summary-summary:2|0|1

New page

'''Algorithmic debugging''' (also called '''declarative debugging''') is a [[debugging]] technique that compares the results of sub-[[computations]] with what the [[programmer]] intended. The technique constructs an internal representation of all [[computations]] and sub-computations performed during the [[Execution (computing)|execution]] of a [[Software bug|buggy program]] and then asks the [[programmer]] about the [[Correctness (computer science)|correctness]] of such computations. By asking the [[programmer]] questions or using a [[formal specification]], the system can identify precisely where in a [[Computer program|program]] a [[Software bug|bug]] is located. [[Debugging]] techniques can dramatically reduce the time and effort spent on [[debugging]].

==Overview==

[[Debugging|Program debugging]] is an extremely common part of software development. Until the 1980s the craft of program debugging, practiced by every programmer, was without any theoretical foundation.<ref>Silva, Josep. "A survey on algorithmic debugging strategies." ''Advances in Engineering Software'' 42.11 (2011): 976-991/</ref> In the early 1980s, systematic and principled approaches to program debugging were developed. In general, a bug occurs when a programmer has a specific intention regarding what the program should do, yet the program actually written exhibits a different behavior than intended in a particular case.
One way of organizing the debugging process is to automate it (at least partially) via an algorithmic debugging technique.<ref>Zeller, Andreas. ''Why programs fail: a guide to systematic debugging''. Elsevier, 2009./</ref> The idea of algorithmic debugging is to have a tool that guides the programmer along the debugging process interactively: It does so by asking the programmer about possible bug sources.
The algorithmic debugging technique constructs an internal representation of all computations and sub-computations performed during the execution of a buggy program (an execution tree). Then, it asks the programmer about the correctness of such computations. The programmer answers "YES" when the result is correct or "NO" when the result is wrong. Some algorithmic debuggers also accept the answer "I don't know" when the programmer cannot give an answer (e.g., because the question is too complex). Thus, the answers of the programmer guide the search for the bug until it is isolated by discarding correct parts of the program. The algorithmic debugging process finds one bug at a time. In order to find different bugs, the process should be restarted again for each different bug.

==Origins, current and future directions==

Algorithmic debugging was first developed by [[Ehud Shapiro]] during his PhD research at [[Yale University]], as introduced in his PhD thesis,<ref>Shapiro, Ehud Y. (1983). ''Algorithmic program debugging''. Cambridge, Mass: MIT Press. {{ISBN|0-262-19218-7}}</ref> selected as a 1982 ACM Distinguished Dissertation. Shapiro implemented the method of algorithmic debugging in Prolog<ref>Clocksin, William F., and Christopher S. Mellish. ''Programming in PROLOG''. Vol. 4. Berlin etc.: Springer, 1987.</ref> (a general purpose logic [[programming language]]) for the debugging of [[Logic programming|logic programs]]. In case of [[Logic programming|logic programs]], the intended behavior of the program is a model (a set of simple true statements) and bugs are manifested as program [[Completeness (logic)|incompleteness]] (inability to prove a true statement) or [[Correctness (computer science)|incorrectness]] (ability to prove a false statement). The algorithm would identify a false statement in the program and provide a counter-example to it or a missing true statement that it or its generalization should be added to the program. A method to handle [[non-termination]] was also developed.
The research and development in the field of algorithmic debugging has made major improvements over the original algorithms for debugging [[Prolog]] and other and extended the ideas to other language paradigms such as [[functional languages]] and [[Object-oriented programming|object oriented languages]].<ref>Naish, Lee. ''A declarative debugging scheme''. Department of Computer Science, University of Melbourne, 1995.</ref>
Three decades since its introduction, algorithmic debugging is still an active field of [[computer science]] research<ref>Caballero, Rafael, Riesco, Adrián, Silva, Josep. ''A survey of algorithmic debugging''. ACM Computing Surveys, Volume 50 Issue 4, 2017.</ref> and will probably remain so for decades as no panacea is in sight.

==References==
{{Reflist}}

[[Category:Debugging]]

Algorithmic program debugging - Revision history

imported>Oxymoronic1: /* growthexperiments-addlink-summary-summary:2|0|1 */