Algorithmic program diagnosis

ABSTRACT

The notion of program correctness with respect to an interpretation is defined for a class of programming languages. Under this definition, if a program terminates with an incorrect output then it contains an incorrect procedure. Algorithms for detecting incorrect procedures are developed. These algorithms formalize what experienced programmers may know already.A logic program implementation of these algorithms is described. Its performance suggests that the algorithms can be the backbone of debugging aids that go far beyond what is offered by current programming environments.Applications of algorithmic debugging to automatic program construction are explored.

REFERENCES

• 1: K. R. Apt and M. H. van Emden. Contrubutions to the Theory of Logic Programming. Technical Report CS-80-12, Department of Computer Science, University of Waterloo, February, 1980.
• 2: R. M. Burstall , John Darlington, A Transformation System for Developing Recursive Programs, Journal of the ACM (JACM), v.24 n.1, p.44-67, Jan. 1977 [doi>10.1145/321992.321996]
• 3: Lawrence Byrd. Prolog Debugging Facilities. Technical note, Department of Artificial Intelligence, Edinburgh University. 1980.
• 4: Keith L. Clark. Negation as Failure. In H. Gallaire and J. Minker, editor, Logic and Data Bases,. Plenum, 1978.
• 5: Randall Davis. Applications of Meta Level Knowledge to the Construction, Maintenance and Use of Large Knowledge Bases. Technical Report STAN-CS-76-552, Computer Science Department, Stanford University, July, 1976.
• 6: M. H. Van Emden , R. A. Kowalski, The Semantics of Predicate Logic as a Programming Language, Journal of the ACM (JACM), v.23 n.4, p.733-742, Oct. 1976 [doi>10.1145/321978.321991]
• 7: Susan L. Gerhart and Lawrence Yelowitz. Observations of Fallibility in Applications of Modern Programming Methodologies. IEEE Transactions on Software Engeneering SE-2:195--207, September, 1976.
• 8: E. M. Gold. Language identification in the limit. Information and Control 10:447--474, 1967.
• 9: C. J. Hogger, Derivation of Logic Programs, Journal of the ACM (JACM), v.28 n.2, p.372-392, April 1981 [doi>10.1145/322248.322258]
• 10: Robert A. Kowalski. Predicate Logic as a Programming Language. In Proceedings of the IFIP Congress, pages 569--574. IFIP, Amsterdam, 1974.
• 11: Zohar Manna , Richard Waldinger, Studies in Automatic Programming Logic, Elsevier Science Inc., New York, NY, 1977
• 12: Zohar Manna and Richard Waldinger. Synthesis: Dreams → Programs. IEEE Transactions on Software Engeneering SE-5:294--328, July, 1979.
• 13: Zohar Manna, Introduction to Mathematical Theory of Computation, McGraw-Hill, Inc., New York, NY, 1974
• 14: Luís Moniz Pereira , António Porto, Selective Bachtracking for Logic Programs, Proceedings of the 5th Conference on Automated Deduction, p.306-317, July 08-11, 1980
• 15: L. Pereira, F. Pereira and D. Warren. User's Guide to DECsystem-10 PROLOG. Technical Report 03/13/5570, Labortorio Nacional De Engenharia Civil, Lisbon, September, 1978. Provisional version.
• 16: Erik Sandewall, Programming in an Interactive Environment: the ``Lisp'' Experience, ACM Computing Surveys (CSUR), v.10 n.1, p.35-71, March 1978 [doi>10.1145/356715.356719]
• 17: Ehud Shapiro , Gregg Collins , Lewis Johnson , John Ruttenberg, PASES: a programming environment for PASCAL, ACM SIGPLAN Notices, v.16 n.8, p.50-57, August 1981 [doi>10.1145/947874.947878]
• 18: Ehud Y. Shapiro. Execution and Debugging of Logic Programs With Uncertainties. In preparation. 1981.
• 19: Ehud Y. Shapiro. Inductive Inference of Theories from Facts. Technical Report 192, Yale University, Department of Computer Science, February, 1981.
• 20: Ehud Y. Shapiro. An Algorithm that Infers Theories from Facts. In IJCAI-81, No. 7. IJCAI, August, 1981.
• 21: T. Teitelbaum and T. Reps. The Cornell Synthesizer: a Syntax-Directed Programming Environement. Technical Report TR79-381, Department of Computer Science, Cornell University, July, 1979.
• 22: Warren Teitelman. INTERLISP Reference Manual. Technical Report, Xerox Palo Alto Research Center, September, 1978.
• 23: Niklaus Wirth, Program development by stepwise refinement, Communications of the ACM, v.14 n.4, p.221-227, April 1971 [doi>10.1145/362575.362577]