Towards an Intelligent Debugging System for Pascal Programs: On the Theory and Algorithms of Plan Recognition in Rich's Plan Calculus

Lutz, Rudi (1993). Towards an Intelligent Debugging System for Pascal Programs: On the Theory and Algorithms of Plan Recognition in Rich's Plan Calculus. PhD thesis The Open University.

DOI: https://doi.org/10.21954/ou.ro.0001017d

Abstract

This thesis presents work in progress on building an intelligent general purpose, domain-free debugging system for Pascal programs. This system (IDS) is based on Rich’s surface plan/plan calculus graph formalisms, and this thesis develops theory and algorithms for performing program understanding within this framework.

This thesis is in three parts, the first part describes why an ability to do both plan recognition and general purpose reasoning is essential for debugging programs.

The second part of this thesis describes the plan calculus and shows how it offers the ability to combine both general purpose reasoning, and (graph-based) plan recognition. It then goes on to present a new polynomial time algorithm (a generalisation of traditional chart parsing for string grammars) for doing bottom-up, or top-down, analysis of surface plans. This algorithm is presented in the framework of restricted structure sharing flow graph grammars developed for this purpose. To justify the use of such grammars this part of the thesis develops the theory of deterministic operations in the plan calculus, and also develops the theory of generalised control flow environments to justify the way control flow information is handled.

The final part gives an overview of IDS, and modifies the above algorithm to cope with various parts of the plan calculus that do not exactly fit into the framework we have developed. Thus this thesis gives a complete account of how to perform plan recognition in Rich’s framework. This part of the thesis also describes the translation process from Pascal to surface plans, and presents a technique for translating plans expressed in Rich’s notation, into suitable rules for the parser to use. Finally it presents some preliminary work on exactly how a debugging system using these techniques might go about locating and fixing bugs in programs.