Automatic Diagnosis of Student Programs in Programming Learning Environments

1 Introduction

It is essential for a programming learning environment to be able to determine whether a program written by a student is correct. The system should recognize correct student pro­ grams even they contain diverse variations. The system should also be able to identify errors together with the cor­ rections needed if the student's program is incorrect.

Research on the automatic diagnosis of student programs relates to many fields such as programming learning envi­ ronments [Ramadhan and du Boulay, 1992; Ueno,l995], automatic program assessment [Thorburn and Rowe, 1997], program analysis and understanding [Rich and Wills, 1990], and software maintenance [Kozaczynski eta/., 1992]. How­ ever, there are few prototypes of systems focusing on the problem of automatic diagnosis of programming errors. Ex­ isting work includes Adam & Laurent [ 1980], Johnson & Soloway [1985], and Murray [1988]. To our knowledge, no existing system performs the automatic diagnosis of pro­ gramming errors entirely satisfactorily today due to the dif­ ficulty of the problem.

In this paper, we describe a method to automate the diag­ nosis of students' programming errors in programming learning environments. Specimen programs (also called model programs) are used as the input to the diagnosis of student programming errors. The automatic diagnosis of students' programming errors is achieved by semantically comparing the student program with a specimen program after both have been standardized by program transforma­ tions. Programs are represented as Abstract Syntax Trees (ASTs) and Augumented Object-oriented Program Depend­ ence Graphs (AOPDGs).

The method has been implemented using Smalltalk in S1PLeS-11, an automatic program diagnosis system for Smalltalk programming learning environments. The system has been tested on approximately 330 student programs for various tasks. Experimental results show that, using the method, semantic errors in a student program can be identi­ fied rigorously and safely. Semantics-preserving variations in a student program can be either eliminated or accommo­ dated.

This method is essential for the development of pro­ gramming learning environments. The generality of the method makes it applicable to other object-oriented pro­ gramming languages such as C++ and Java as well because the AOPDG representation is applicable to general object­ oriented programming languages. It is also applicable to non-objected-oriented programming languages where pro­ grams can be represented in ordinary augmented depend­ ence graphs. The techniques of (a) the improved program dependence graph representation, (b) program standardiza­ tion by transformations, and (c) semantic level program comparison, are also useful in other research fields including program understanding and software maintenance.

2 Automatic Diagnosis Procedure

In our approach, for a programming task, different model programs are used to diagnose student programs that are coded based on different algorithms. Student programs us­ ing the same algorithm are standardized and compared to their corresponding model program. The automatic diagno­ sis procedure in SIPLeS-II is shown in Fig. I.

In SIPLeS-II, a student program (SP) and a model pro­ gram (MP) represented in source code are obtained. Pro­ grams are first processed by a parser and the parse trees of the two programs are generated. Based on a set of Backus­ Naur Forms (BNF) for Smalltalk, the AST representations of the two programs are produced, called SPTree and MPTree. The AST representation is suitable for the program analysis at the syntax level and for the program transforma­ tions [Loveman, 1977]. After that, basic transformations, which do not require definition-use information (DU infor­ mation) are performed to standardize the SPTree and the MPTree.

In order to calculate DU information, flow graphs for the student program and the model program are produced based on the SPTree and the MPTree. Several kinds of~ vertices are augmented to the flow graphs in order to combine them with features of Static Single Assignment (SSA) form where every use of a variable is only defined by one defini­ tion. The DU information for the two programs are calcu­ lated and used both in the advanced standardization trans­ formations and the generation of the data dependence sub­ graphs in AOPDG representations. We call the AOPDGs for the SP and the MP SPGraph and MPGraph respectively.

The comparison between the SPGraph and the MPGraph produces the following results. ( l) A mapping between SP statements and their semantics-equivalent MP statements. We call this the equivalent map. (2) A mapping between SP

statements and MP statements that are semantics-equivalent but textually different from the SP statements. We called this the textual difference map. (3) A set that includes un­ matched statements in the SP and the MP. The set is called the unmatched set.

Based on the comparison results, the SP statements in the equivalent map and the textual difference map are recog­ nized as correct statements in the error-detection step. For every unmatched SP statement, the most similar unmatched MP statement is found and the differences between the two statements are identified. Among these differences, those that are actually legal variations are learned and eliminated by the system. Unresolved differences are reported as errors in the student program. Unmatched statements in the SP with no unresolved difference identified are reported as controlling errors in the diagnosis report.

3 An example

We use a running example to explain our approach. The task description is given below.

Define a me thod called t ax iFeeWith : mil e isBookingCase : bookingCase . If "bookingCase" is true , a booking fee of $2 .00 s hould b e charged, and the pric e per mile is $3 . 00 ; otherwise, no book ing fee is charged, and the price per mile is $2.50. The total taxi fee is calculated by mile*price + bookingFee.

A model program is the following, where names for the method head and statements are given at the left-hand side.

A possible student program is given below. The differences between the SP and the MP are indicated, they will be dis­ cussed later.

3.1 Possible semantics-preserving variations in a student program

In programming learning environments, a program written by a student may have many semantics-preserving variations (SPVs) compared to a model program. In general, there are I2 possible types of variations. These are given below.

• SPV 1: Different algorithms may be used. The student program will be quite different from the model pro­ gram.
• SPV2: Different format of writing program at the source code level. For example, more or less spaces, com­ ments, etc.
• SPV3: Different ways of writing message sequences. For example, message sequences may be written in cas­ caded messages.
• SPV4: Different temporary variable declarations. Tem­ porary variables may be declared in a method tempo­ rary variable declaration or in a block temporary vari­ able declaration.
• SPVS: Different ways of writing algebraic expressions.
• SPV6: Different messages used for a same control structure.
• SPV7: Different numbers of temporary variables or block temporary variables are used.
• SPV8: There are may be some dead codes or some statements for debugging purpose in the student pro­ gram.
• SPV9: Different statement orders.
• SPVIO: Different parameter names in the method head or different temporary variable names or different block temporary variable names are used.
• SPV 11: Different control structure used. The way of computation in the SP is different from that in the MP.
• SPVI2: Different ways of writing a statement. A com­ ponent in a statement in SP is different from that in a statement in MP although the computational results of the two components are the same.

3.2 Differences between the MP and the SP

A human tutor may identify the following six differences between the student program and the model program.

• Difference! (SPV 10): Different parameter names are used in SEntry and SS0011.
• Difference2 (SPV 9): Different statement orders of SS1121 and S1122 compared to that of MS1321 and MS1322.
• Difference3 (SPV 2): Different source-code format in SS1122 compared to that in MS1322. There is an extra "."before the'']" in SS1122.
• Difference4 (SPV II): Different values produced at the point of SS0011. price and bookingFee are calculated out of the ifFalse: control structure in the MP, whereas they

are calculated inside the ifFalse: control structure in the SP. However, this is a semantics-preserving variation, because at the point of SS0012, the values produced are the same compared to the values produced in the MP at the point ofMS0014End.

• DifferenceS (Error): Different computation carried out in SS0012 compared to MS0014End. This is a semantic variation, which is an error in the student program.
• Difference6 (SPV 7): Different numbers of temporary variables are used in SS0012 and SS0013End. The dif­ ference changes the way computations are executed without changing the values computed.

The challenge in the automatic diagnosis of students' pro­ gramming errors in this example rests in identifying Differ­ enceS as an error in the student program while accommo­ dating other semantics-preserving changes in the student program.

4 Program Representations

Three representations of programs are used in the diagnosis procedure: source code representation, AST representation, and AOPDG representation. The AST representation is amenable for program transformation. The AOPDG repre­ sentation combines the strengths of OPDG representation [McGregor et a/., 1996] and the program representation graph (PRG) [Yang eta/., 1992]. It is used for the semantic level comparison of programs [Horwitz, 1990]. The merits of the AOPDG representation include: ( 1) it eliminates many variations existing at the source code level and AST level, (2) it is indispensable for the program comparison algorithm, and (3) it makes the comparison accommodate semantics-preserving behavioral changes in the student pro­ gram compared to the model program.

4.1 AST representation

The generation of the abstract syntax tree for a program is b~sed on the Backus-Naur Forms (BNF) of the program­ mmg language. An AST representation of a program is a frame-based representation based on the parsing tree with additional program analysis information added.

Representing programs in AST eliminates SPV2 in pro­ grams. In the running example, Difference3, the "." before the "]", is eliminated.

4.2 AOPDG representation

An AOPDG for a program is constructed based on the aug­ mented object-oriented flow graph (AOFG) of the program and the DU information calculated. An AOFG is constructed from the OFG of the program, and an OFG is an improved fl~w graph. It accommodates the situation in pure object­ onented programs that statement sequence may appear in a block as a component of another statement. This is not al­ lowed in programs such as C++ and Java. In the OFG, there are additional flow edges coming out from a conditional node besides the usual true/false branches.

To construct an AOFG from an OFG, a vertex labeled "~initial: x := initial(x)" is added at the beginning of the OFG for each variable x that may be used before being defmed. A ~ vertex labeled "~enter x := x" . is added inside each loop statement immediately before the loop predicate for each variable x that is defmed within the loop, and it is live im­ mediately before the loop predicate (i.e., x may be use~ ei­ ther inside the loop, after the l<:>op, or by the loop predicate before being redefmed). A vertex labeled "~exit x := x" is added immediately after the loop for each variable that is defmed within the loop and is live after the loop.

An AOPDG consists of an augmented object-oriented control dependence subgraph (AOCDS) and an augmented object-oriented data dependence subgraph (AODDS). Simi­ lar to the construction of CDS and DDS, AOCDS for a pro­ gram is constructed based on AOFG, and AODDS is con­ structed by calculating DU information on AOFG.

In AOCDS representation, there are six types of vertices: entry vertex, end vertex, statement vertex, initialization ~ vertex, enter ~ vertex, and exit ~ vertex. The source of a control ~dge in AOCDS is always either an entry vertex or a predicate vertex (i.e. a conditional statement vertex).

There are five types of control dependence edges: control­ true, controlfalse, controlloop, entertrue, and enterfalse, and the types of dependence edges are flow1, flow2, ... , flown, flowtrue, flowfalse, flowenter, flowexit, and flowwhile.

By representing the programs in AOPDGs, SPV9 in pro­ grams is eliminated. In the running exa~ple ·. the. AOP~� representations of the SP, SPGraph, are given m Fig. 2. Dif­ ference2 in the SP is eliminated by representing the SP and the MP in AOPDGs.

5 Program Transformations

The basic standardization transformations performed are as follows. (I) The statement separation standardizes cascaded messages to a message sequence. (2) The temporary decla­ ration standardization makes all temporary variables to be only defmed in the method temporary variable declaration. (3) The algebraic expression standardization applies a set of rules of associativity, commutativity, and distributivity on an algebraic expression until no more transformation rules can be applied. (4) Control structure standardization standar~­ izes all control structures into one of three structures----11True:ifFalse:, whileTrue:, and to:by:do:-by applying 14 trans­ formation rules such as receiver i!True: b17receiver ifTrue: b1 ifFalse: [], where b1 is a block.

With basic standardization transformations, SPV3, SPV4, SPV5, and SPV6 are eliminated in programs. In the running example, algebraic expression standardization is applied on both SPTree and MPTree, and control structure standardi­ zation is applied on the MPTree.

Advanced standardization transformations of forward substitution and dead code removal [Muchnick, 1997] are used to eliminate SPV7. In the running example, no ad­ vanced standardization transformation is applicable to the MP. For the SP, SS0013End is changed by forward substitu­ tion and SS0012 is removed by dead code removal. Differ­ ence6 in the SP is eliminated. The SP standardized by ad­ vanced standardization transformations is given below; this corresponds to the AOPDG in Fig.2.

6 Program Comparison

The comparison algorithm is based on the idea that two statements with different operators, different operands, or different controlling predicates will have difference behav­ iors. The vertices in the student AOPDG (i.e. the statements in the student program) and the vertices in the model AOPDG are classified into a same partition set in initial partition. A stable coarsest refinement of the initial partition is computed using a basic partitioning algorithm [Yang et a/., 1992]. The idea in the basic partitioning algorithm is that a set in a partition containing several vertices whose predecessors belong to different sets in the partition must be split into smaller sets according to the partitions of their predecessors. The results of the comparison reveal the se­ mantic differences between the student program and the model program and accommodate the semantics-preserving behavior changes between the two programs.

SPV 11 is accommodated in program comparison. In the running example, the refined partition is given below, where the names of the partition sets are shown on left. The equivalent map, the textual difference map, and the un­ matched map are also given.

Refined partition

The equivalent map

{taxiFeeWith:isBookingCase: 0.0 2.5 ifTrue:ifFalse: 3.0 2.0}

The textual difference map

{taxiFeeWith:isBookingCase: ifTrue:ifFalse:}

The unmatched map

{+ NEW3}

Difference 1 is correctly identified as textual difference in this step because taxiFeeWith:isBookingCase: ~(MEntry SEntry) and ifTrue:ifFalse:~(MS0013 SS0011) are in the textual differ­ ence map. Difference4 is accommodated in the comparison because O.O~(MS0011 SS1124) and 2.5~(MS0012 SS1123) are in the equivalent map. DifferenceS is correctly identified as a semantic error because +~(MS0014End) and NEW3~(SS0012End) are in the unmatched map.

7 Error Detection

The results of the comparison report those statements in the SP that have semantic errors. However, a programming learning environment should be able to pinpoint the errors in the incorrect statements and to provide corrections of the errors. An error detection step is necessary. In this step, SPY 10 is eliminated by changing the model program ac­ cording to the textual difference map. The system pinpoints errors in an incorrect student statement by comparing it with the most similar model statement. The system also learns equivalent expressions used in the SP and the MP to elimi­ nate SPV12. The diagnosis report for the running example is given below.

8 Variations and Handling Strategies

All of the 12 semantics-preserving variations except SPV1 are handled by various strategies discussed above. For SPV 1, different model programs corresponding to different algorithms are used to diagnose student programs that use different algorithms. Hence, when a student program signifi­ cantly differs from all the model programs, a new model program must be input by the teacher.

The semantic differences left in the student program are identified as student programming errors in the diagnosis report. It is possible that a reported error may actually be a semantics-preserving variation because it is not included in the 12 types of SPVs. However, in our approach, it is im­ possible to miss an error if one actually exists. Hence, the approach described here is both safe and conservative.

9 Results and Discussion

TABLE 1 Test results of SIPLeS-11

In this paper, we proposed a new approach for automatic diagnosis of students' programming errors in programming learning environments. In this approach, automatic diagno­ sis of student programs is achieved by comparing the stu­ dent program with the model program after both have been standardized by program transformations. The approach is implemented in a system called SJPLeS-II using Small­ talk!VisualWorks 2.5. It has been tested on approximately 330 student programs for 7 different programming tasks. The test results are shown in Table 1.

From Table 1, we see that both the rate of correct pro­ gram diagnosis and the rate of correct statement diagnosis are I 00% after the system learns sufficient model programs. From the figures shown in Table 1, the number of model programs needed for diagnosing a method definition is in the order of 3 to 5, and the number of the model programs needed for diagnosing a class definition is I only.

Our experimental data also show that after the system has processed about 25 student programs for a programming task, the possibility of failing to diagnose errors due to the lack of a model program is less than 10%. This means that the number of model programs required becomes quite sta­ ble after about 25 student programs are processed. It is rea­ sonable to believe that, in practice, the number of model programs required is small although in theory the number of model programs needed is undecidable . .

In summary, the new features of our approach are as fol­ lows:

• The AOPDG program representation reflects semantic information of the program, eliminates many non­ semantic variations, and is amenable to transformations and comparison.
• Programs are analyzed, standardized, and compared rigorously at the semantic level. By "rigorously", we mean that the results are guaranteed to be correct.
• Student programming errors are identified safely. By "safely", we mean that the approach may regard an ac­ tually correct statement as an incorrect statement, but the approach will never regard an actually incorrect statement to be a correct statement. It is a conservative approach.
• Correct programs are recognized by the system han­ dling all the possible variations.
• Errors in incorrect programs are identified and correc­ tions to the errors are also provided.

This method is essential for the development of pro­ gramming learning environments. The techniques of (a)the improved program dependence graph representa­ tion-AOPDG, (b) program standardization by transfor­ mations, and (c) semantic level program comparison, are also useful in other research fields including program understanding and software maintenance.

Our future work includes refining the method and ap­ plying the approach to program understanding and soft­ ware maintenance.