Summary For Xu Chee 2003

• source-to-specification approach attempts to match a student's program against a specification that is a high-level description of the program's goals.This approach has been applied to functional programming languages Lisp, Prolog and imperative programming languages such as Pascal, C. An essential step in the approach is to understand the student program by matching it with code templates that are attached with corresponding specifications, or matching it with specifications called goal structures, schemata, plans, assertions, or processes. However, several problems arise: 1) unlike matching student programs using code templates for Lisp, Prolog, Pascal, C, it is extremly difficult to match any program in any programming language, including OO-languages such as C++, Java, Smalltalk, because there are two many possible variations permissible in student's programs. 2) It's difficult for instructors to write specifications that will be used to match the student programs. 3) matching a student's program with a program specification is not rigorous procedure because the problem does not exist in the realm of provable reasoning.
• specification-to-specification approach attempts to extract the formal specifications of both a student program and a reference program and then to perform automatic reasoning upon the extracted formal specifications (W.R. Murray, Automatic Program debugging for ITS. Morgan Kaufmann Publishers, 1998). In Talus of Murray, The Boyer-moore logic provides the formal specifications of both student programs and reference programs in LISP and automate the reasoning about program semantics. This approach would be an ideal approach if the formal specifications of programs can be derived automatically. However, it is still not possible to produce formal specifications automatically for real-world programs in Pascal, C/C++, Smalltalk, and Java. Therefore, automated specification-to-specification diagnosis is still infeasible at this time.
• source-to-source approach attempts to match a student program against a specimen program (also called a model program). It differs from the specification-to-specification approach in that the latter performs automatic reasoning at the level of formal specifications, whereas the source-to-source approach performs automatic reasoning at the level of program dependence graphs. A program dependence graph is a semantic reprsentation for programs, but it is not a formal specification. Programs are represented in program dependence graphs. They are transformed before being matched against pre-stored commonly used programming structures, called cliches. Limitations: 1) transformation-based diagnosis does not encompass intentions underlying student programs because it does not encode the knowledge needed to deal with intentional information.

• get a student program (SP)and a model program (MP)
• Represent the programs in AST: Programs are first processed by a parser, and the Abstract Syntax Trees of the two programs are generated. THe representations are called SPTree and MPTree.
• Perform Basic Transformation: Basic transformations that do not require definition-use information are performed to standardize SPTree and MPTree. There are 5 basic transformations: statement separation, temporary declaration, algebraic expression, control structure, and boolean expression standardization.
• Produce flow graphs for the programs: Flow graphs for the student program and the model program are produced based on SPTree and MPTree. In order to compare SP and MP at the semantic level, a program representation that presents the semantics of programs is required. Program Representation Graphs (PRGs) are used by Yang ("A program Integration Algorithm that accomodates semantics-preserving transformations",1992) in a program-integration algorithm to facilitate the semanti level program comparison. It combines the feature of Program Dependence Graphs (PDGs) and Static-single-Assignment (SSA) forms. A PDG consists of a Control Dependence Subgraph (CDS) and a Data Dependence Subgraph (DDS)
• Perform Advanced Transformations the advance transformations, which require DU information, are performed to standardize SPTree and MPTree further: Forward substitution and dead code removal. Dead Code Removal removes dead statements identified in a program from the AST representation of the program. If a temporary variable is not used in the program, the declaration of the variable is also removed.
• Represent the programs in AOPDGs: The AOPDGs for SP and MP are produced based on the flow graphs for the student program and the model program. By control-flow analysis, the system obtains Augmented Object-oriented control Dependence Subgraphs (AOCDS). By data-flow analysis, the system obtains Augmented Object-oriented Data Dependence Subgraphs of the APPDGs. We call the AOPDGs for SP and MP SPGraph and MPGraph respectively.
• compare the programs: A program matching algorithm compares SPGraph and MPGraph and identifies differences between the student program and the model program. The outputs are: a equivalent map, tuextual difference map, and an unmatched set.
• Detect errors: the compsarison results are processed further in a error detection step. The SP statements in the equivalent map and the textual difference map are recognized as correct statements. For every unmatched SP statement, the most similar unmatched MP statement is found, and the differences between the two statements are identified in SP. Among these differences, those that are actually legal variations of SP are leanred and eliminated by the system. Unresolved differences are reported as errors in the diagnosis report.