Detecting Prolog programming techniques using abstract interpretation
Bowles, Andrew W.
There have been a number of attempts at developing intelligent tutoring systems (ITSs) for teaching students various programming languages. An important component of such an ITS is a debugger capable of recognizing errors in the code the student writes and possibly suggesting ways of correcting such errors. The debugging process involves a wealth of knowledge about the programming language, the student and the individual problem at hand, and an automated debugging component makes use of a number of tools which apply this knowledge. Successive ITSs have incorporated a wider range of knowledge and more powerful tools. The research described in this thesis should be seen as carrying on with this succes¬ sion. Specifically, we attempt to enhance an existing Prolog ITS (PITS) debugger called APR0P0S2 developed by Looi. The enhancements take the form of a richer language with which to describe Prolog code and more powerful tools with which constructs in this language may be detected in Prolog code. The richer language is based on the notion of programming techniques—common patterns in code which capture in some sense an expert's understanding of Prolog. The tools are based on Prolog abstract interpretation—a program analysis method for inferring dynamic properties of code. Our research makes contributions to both these areas. We develop a language for describing classes of Prolog programming techniques that manipulate data-structures. We define classes in this language for common Prolog techniques such as accumulator pairs and difference structures. We use abstract interpretation to infer the dynamic features with which techniques are described. We develop a general framework for abstract interpretation which is described in Prolog, so leading directly to an implementation. We develop two abstract domains—one which infers general data flow information about the code and one which infers particularly detailed type information—and describe the implementation of the former.