Divide-and-query and subterm dependency tracking in the mercury declarative debugger

ABSTRACT

We have implemented a declarative debugger for Mercury that is capable of finding bugs in large, long-running programs. This debugger implements several search strategies. We discuss the implementation of two of these strategies and the conditions under which each strategy is useful.The divide and query strategy tries to minimize the number of questions asked of the user. While divide and query can reduce the number of questions to roughly logarithmic in the size of the computation, implementing it presents practical difficulties for computations whose representations do not fit into memory. We discuss how we get around this problem, making divide and query practical.Our declarative debugger allows users to specify exactly which part of an atom is wrong. The subterm dependency tracking strategy exploits this extra information to jump directly to the part of the program that computed the wrong subterm. In many cases, only a few such jumps are required to arrive at the bug. Subterm dependency tracking can converge on the bug even more quickly than divide and query, and it tends to yield question sequences that are easier for users to answer.

REFERENCES

• 1: Mark Brown and Zoltan Somogyi. Annotated event traces for declarative debugging. Available from http://www.cs.mu.oz.au/mercury/, 2003.
• 2: Lawrence Byrd. Understanding the control flow of Prolog programs. In Proceedings of the 1980 Logic Programming Workshop, pages 127--138, Debrecen, Hungary, July 1980.
• 3: Peter Fritzson , Nahid Shahmehri , Mariam Kamkar , Tibor Gyimothy, Generalized algorithmic debugging and testing, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.4, p.303-322, Dec. 1992 [doi>10.1145/161494.161498]
• 4: Bil Lewis. Debugging backwards in time. In Proceedings of AADEBUG '03, Ghent, Belgium, September 2003.
• 5: Lee Naish. A declarative debugging scheme. Journal of Functional and Logic Programming, 1997(3), April 1997.
• 6: Lee Naish. A three-valued declarative debugging scheme. Australian Computer Science Communications, 22(1):166--173, January 2000.
• 7: Henrik Nilsson , Jan Sparud, The Evaluation Dependence Tree as a Basis for Lazy FunctionalDebugging, Automated Software Engineering, v.4 n.2, p.121-150, April 1997 [doi>10.1023/A:1008681016679 ]
• 8: Luís Moniz Pereira, Rational Debugging in Logic Programming, Proceedings of the Third International Conference on Logic Programming, p.203-210, July 14-18, 1986
• 9: D. A. Plaisted. An efficient bug location algorithm. In Proceedings of ICLP '84, pages 151--158, Uppsala, Sweden, July 1984.
• 10: Stéphane Schoenig , Mireille Ducassé, A Backward Slicing Algorithm for Prolog, Proceedings of the Third International Symposium on Static Analysis, p.317-331, September 24-26, 1996
• 11: Ehud Y. Shapiro, Algorithmic Program DeBugging, MIT Press, Cambridge, MA, 1983
• 12: Zoltan Somogyi. Idempotent I/O for safe time travel. In Proceedings of AADEBUG '03, pages 13--24, Ghent, Belgium, September 2003.
• 13: Zoltan Somogyi and Fergus Henderson. The implementation technology of the Mercury debugger. In Proceedings of the Tenth Workshop on Logic Programming Environments, pages 35--49, Las Cruces, New Mexico, November 1999.
• 14: Zoltan Somogyi, Fergus Henderson, and Thomas Conway. The execution algorithm of Mercury, an efficient purely declarative logic programming language. Journal of Logic Programming, 26(1-3):17--64, October-December 1996.
• 15: Jan Sparud , Colin Runciman, Complete and Partial Redex Trails of Functional Computations, Selected Papers from the 9th International Workshop on Implementation of Functional Languages, p.160-177, September 10-12, 1997
• 16: Mark Weiser, Program slicing, Proceedings of the 5th international conference on Software engineering, p.439-449, March 09-12, 1981, San Diego, California, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Debugging aids

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Diagnostics; Tracing

General Terms:
Algorithms, Human Factors

Keywords:
algorithmic debugging, declarative debugging, divide-and-query, program slicing