Chee-Kit Looi 1991

The problem of debugging Prolog programs

1. Prolog is logic programming language with clear declarative semantics for oure Prolog. This should make verification of programs simpler and easier.
2. A Prolog program can have both a declarative nd a procedural reading. A program debugger can address the declarative interpretation of a Prolog program separately from its procedural meaning. The destinction between the declarative and procedural meaning is not as clear for other languages like LISP and Pascal.
3. A Prolog program is very pront to errors that do not result in compile-time errors but in programs with uninteded meanings. "The totally defined semantics of a Prolog predicate leads to a different interpretation eith respect to errors. As normal values cannot be distinguished from error values, errors are extremely difficult to detect and understand. This is particular the case when a simple mistyping or misunderstanding concerning the nature of the predicate is involved." (Mishra 1984)
4. A Prolog program may or may not be multi-directional. A program debugger needs to explore what input and output modes the program may be correctly used for. We adopt the following description of modes:
   • o Nothing known about the mode
   • - the set of variables
   • + the set of nonvariable terms
   • ? The set of all terms
5. Prolog programs can be nondeterminate.
6. The computation model of Prolog is based on goal invocation, and goal success and failure. thus errors in Prolog programs occur when, for example, they finitely fail on goals that should succed, or succeed on goals on goals that should fail.
7. Prolog programs run on a model of computation that involves unification and epth-first search.
8. A Prolog program may have used a number of programming techniques specific to Prolog. An example of such a tecchnique is the use of an argument position to accumulate the result recursively and the use of another argument position to instantiate the final result.
9. In Prolog there are few system predicates which might serve as markers for heuristic template-matching.

Representation of task and programming knowledge One key component of the ITS is the representation of knowledge about programming and programming solutions

1. Prolog programming techniques by progamming techniques in Prolog, we mean the use of common implementation methods specific to the Prolog language which can be brought to bear a range of problems. While programming techniques have an important role to play in ITS for Prolog, a technique-based approach is itself not sufficient for bug diagnosis. The automatic detection of the use of techniques in a student's program is a difficult task because the student may have used a technique incorrectly or used an inappropriate technique. an automated debugger needs some expectation of what the student is intending to do.
2. programming plans Soloway and his co-researchers at Yale consider programming goals and plans as the two key components in representing problems and programming solutions. Programming plans describe stereotypic action sequences in programs and are intended to be language independent. The claim is that programmers write programs by determining what goals and constraints must be satisfied, and then selecting plans which satisfy these goals and constraints. PROUST is a computer program developed at Yale that analyses Pascal programs written by novice programmers. PROUST embodies the view that programmers use plans to map their intended goals into code. It task is thus an attempt to invert this mapping, mapping the code back into the programmer's goals. THe representation of a plan in PROUST is a frame with a set of slots. THe main part of the plan is the template which is fairly close to the Pascal code they are matched against. A template-like representation of plans as in PROUST is suitable only for imperative sequential languages like Pascal where there are keywords to anchor the analysis. In Prolog where the model of computation is based on unification, a template-matching procesds has to be more flexible, for example to recognize different but equivalent unfolded forms of a Prolog expression as equivalent
3. Cliche's a cliche is defined as a standard method for doing a task, a partial solution of some sort (Waters, 1985). We see the cliche in the Programmer's Apprentice (PA) as a high-level template that represents the dataflow and control flow of an algorithm wher the place-holders are the roles of the task. The concept of the PA's plans and cliches is similar to the concept of programming plans as used by Soloway. One difference is that Soloway's plans are organized round the goals they implement. Cliches provide a vocabulary of relevant intermediate and high-level concepts for the programmer to interact with the PA. THe idea of using cliches for program construction is intended to be language independent although cliches themselves are not language independent. To support a new language, a different library of cliches which are appropriate for writing programs in that language has to be provided. A syntactic cliche-matching approach would rely on template-matching against a set of prestored templates for the task. THe main difficulty is that there may be too many such templates to enumerate.
4. Alternative automated debugging approaches Murray (1986) gives a taxonomic classification of various debugging methodologyies developed over the last 15 years. There are two main flavours: dynamic analysis that examines the runnign of the program and static analysis that works on the code.
   • Positive side of static analysis: obviuos slips and miscodings cn be spotted quickly. Unreachable and redundant code can be detected and analysed. On the negative side: there is a need to interprete the student's intensions through heuristic code-matching, but that can be cumbersome and is dependent on having a representative library of plans and bugs.
   • Danamic analysis can find errors without doing a full analysis. It can more readily find out any bug symtoms and program misbehaviours. on the other hand, unreachable and redundant code cannot be deteced.
   • Combination of static and dynamic analyses: A static analysis permits an automated debugger to recognise bugs and suggest corrections for them, as there is some reference to be matched against. with dynamic analysis, an automated debugger is able to collect all the solutions a student program produces on successive forced backtracking from a goal call, and compare and analyse thse solutions vis-a-vis the correct solutions. Dynamic analysis allows an automated debugger to explore run-time properties and behaviour of Prolog programs at a lower computational cost than often quite involved static analysis. It is used also to confirm the run-time behaviour and properties arrived at by static analysis which in turn can be used to explain the program's run-time behaviour.
5. APROPROS2 : the analyses can be decomposed into two parts. THe first part performs multiple program analyses on the programs. The second part uses task-specific knowledge to analyse the program.
   • Mode analyses: mode inference uis used to determine which arguments of a predicate are used as input parameters in a Prolog program and which are used as output parameters. Mellish's method (1981) is used to infer a set of input modes for each predicateafter examining thw whole program.
   • Dataflow analysis: information about the use of variables is collected so that certain inferences can be made about the effect of these uses at other points of the program.Dataflow analysis identifies anomalies in the pattern of definition and use of variables: 1) references to undefined variables, 2) assignments of variables of values which are never used 3) unreachable code in the program 4) infinite loops. For ex: one argument position has a term which keeps bulding up resulting in a nonterminating computation or an incorrect computation because that argument can never match the structure in the corrsponding argument in the base case.
   • Type analysis: Types in Prolog represent sets of terms. Type inference can be used to infer the types of expressions when little or no information is given expicitly. We assign types to all possibles calls in which a predicate can be used. The type of every term may be inferred from the context using the type information of terms known. Type inference reduces to type checking when there is enough type information in a program that the type inference task becomes trivial. There are to main approaches to types in Prolog: In the Mycroft-O'Keefe system, a type assignment for a program is considered valid if it is preserved under resolution ("well-typed programs do not go wrong" 1984). This approach deals mainly with type checking. I n Mishra's approach, the type of a predicate is characterised as a conservative description of its success set ("ill-typed programs cannot success"- Mishra 1984). This approach deals with automatic type inference.
   • Misspelling analysis: misspelling predicate names, variable and atom names.
   • Program transformations: It applies common folding and unfolding rules to the student's program and the transformed program can then be used for subsequent analysis.
   • Detecting programming techniques: The task-specific analysis of APROPOS2:
   • the algorithm level: the desgin of the task solution. Bugs at the algorithm level reflect lack of understanding of the task, or an incorrect or inefficient strategy for solving the task.
   • The predicate definition level: the predecate definition decomposition of the chosen algorithm. Three types of bugs at the predicate definition level are detected: missing, extra and incorrect predicate definitions. Incorrect predicate definitions are procedures that have bugs at the implementation level.
   • The implementation level: the code that implements each predicate definition. At the implementation level, common bugs like these are detected at the coding level: missing and extra clasues, subgoals, wrong subgoals, wrong clause or subgoal order.

P-frame= Prolog-frame: A student's Prolog program is first parsed to convert all variable names to special atomic names to avoid unitended instantitaiton of variables and then transformes to an internal representation. APROPOS2 does the first part of its analysis (dataflow, mode, type inference) on this internal reprsentation. Features are abstracted from this analysis to construct a student P-frame, the structure of which is identical to the reference P-frame. A P-frame represents an equivalence class of implementations of an algorithm. APROPOS2 performs algorithm recognition by searching the best reference P-frames to match the student P-frames. It uses a heuristic scoring function to compute a weighted sum of P-frame slot differences to evaluate how well two P-frames match.

-- LeNguyenThinh -- 13 Dec 2004