Gegg-Harrison 1991

Chapter 3 state of the art debuggers

Automated program debugging involves recognizing the algorithm employed by the programmer and detecting any errors that exist in her program.

• Algorithm Recognition
  • Dynamic Analysis: viewing the execution of the student's program. System that perform dynamic analysis include PDS6 (Shapiro83) and SCENT-3 (McCallaGreer and SCENT Team 88).
  • Static Analysis: The systems which perform static analysis can be further divided into plan library approach, and transformation approaches
    • Plan Library: approaches decompose the problems inot collections of well-defined operations. These collections of operations are stored in a library of plans. There are 3 major classes of plan library approaches.
      • In Plan Parsing approaches (RECOGNIZER, Wills90), plans are represented by grammars and studentprgoams are parsed in terms of the grammars.
      • Plan Matching approaches (PROUST, TALUS, APROPOS2) represent plans using frame-like templates. The student's program is heuristically matched to appropriate templates in the library and the one with the best match is identified as the one used by the student.
      • Model Tracing approaches (LISP tutor) avoid the task of algorithm recognition by modeling the entire programming process and constraining their student to conform to "expert" programming behaviour. In model tracing each action taken by the student is mapped to a set of production rules. predefined sets of rules are classified as "ideal" rules which represent actions that a programming "expert" would take, while other rules are classified as buggy rules reprsenting actions erronously taken by "novice" programmers. By tracing the actions of the student with collections of these rules, model tracing approaches are able to build a model of the student and intervene whenever the student shows less than ideal behavior.
    • Transformation approaches represent the "correct" implementation by a single normal form program and attempt to transform the student's program into the canonical form of the normal form program. THe only system that uses this technique is the LAURA system for debugging Fortran programs. LAURA represents its normal form programs as graphs and transform the student's Fortran program into this canonical graph form by using a set of equivalence-preserving transformation rules.
• Bug Detection Bug detection is the task of locating errors in the student's implementation of the algorithm identified in the algorithm recognition phase.
  • Dynamic Analysis: PDS6, SCENT-3 use dynamic analysis for both algorithm recognition and bug detection. APROPOS2 is an exception case. APROPOS2 recognizes algorithms statically by matching them against a library of algorithms and then detects the bugs dynamically by executing the program on a set of I/O pairs associated with the algorithm having the best match.
  • Static Analysis
    • Bug Library approaches are the counterpart to plan library approaches for algorithm recognition. These systems (LISP tutor, PROUST) have libraries of common bugs usually represented as sets of production rules which are used to compare segments of the student's program which do not match their corresponding segments in the "correct" implementation of the selected algorithm.
    • Program verification approaches attempt to apply formal methods to prove the equivalence of corresponding segments of code that do not match (e.g., TALUS attempts to prove the equivalence of corresponding segments of code by invoking the Boyer-Moore Theorem Prover (Boyer & Moore) and detecting bugs via failed inductive proofs).
    • Transformation-based approaches (e.g., LAURA) highlight bugs by finding segments of code in the student's transformed program which do not match the corresponding segment of code in the normal form program.

-- LeNguyenThinh -- 05 Jan 2005