Proceedings

Dependency Directed Reasoning in the Analysis of Programs which Modify Complex Data Structures

Download BibTeX Cite

Proceedings of the Sixth International Joint Conference on Artificial Intelligence. .

© 1979 International Joint Conferences on Artificial Intelligence

Abstract

REASON is the deductive component of a luger program understanding system called the Programmer's Apprentice [I~ REASON's key features are : (I) Its use of the Truth Maintenance System [2) to record and manipulate the justifications for its deductions, (2) A discipline of explicitly recording control information In a form which may be manipulated by the reasoning system itself and (3) Its goal of producing a a ·common sense· explanation of how a program functions, as opposed to the formal proofs common in verification. One particularly difficult problem which such a system 1nust face is the analysis of program which allow dest~tlve modifications of potentially shared data structures. Our observation is that experienc.cl programmen tend to make simplifying assumptions when analyzing such programs; even if the. usumptions .... found to be r• theJ can be useful in guiding a more eccurate analysis. Thit paper shows how REASON mlmicl this behaYior of expert programmen.

  1. Rich, C. and Shrobe, H. (19781 "Initial Report on a LISP Programmer's Apprentice", IEEE Trans. on Soft. Eng., V4 #6, November 1978, pp. 456-467.
  2. Doyle, Jon Tl'lltll Maintenance Systems for Problem Sohing, M.I.T. Artificial Intelligence Laboratory Technical Report 419, January 1978.
  3. Suzuki, N "Automatic Verification of Programs with Complex Data Structures•, Stanford AIM-279, February 1976.
  4. McCarthy, J. and Hayes, P. "Some Philosophical Problems from the Standpoint of Artificial Intelligence", Machine Intelligence 4, American Elsevier, N.Y. (S) deKieer, J., Doyle, J., Steele, G. & Sussman, GJ. "AMORD: Explicit Control of Reasoning•, Proceedings of the Symposium on Artificial Intelligence and Programming Languages, August 1977.
  5. Shrobe, Howard Logic and Reasoning for Complex Program Understanding, PhD Thesis, MIT, August 1978.
  6. Burstall, R. M. "Some Techniques for Proving Properties of Programs Which Alter Data Structures, Machine Intelligence 7, Edinburgh University Press.
  7. Sussman, G.J. A Computational Model of Skill Acquisition, M.I.T.. Department of Mathematics Ph.D. Thesis; M.I.T. Artificial Intelligence Laboratory Technical Report 297, August 1973;
  8. A CtJmpt11n-Model of Skill AcquWtlon, New York, American Elsiver 1975.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards