Source-linked AI summary
Automated Clustering and Program Repair for Introductory Programming Assignments
Sumit Gulwani, Ivan Radiček, Florian Zuleger
TL;DR
Introductory programming feedback is labor-intensive and difficult to scale in MOOCs, while failing tests alone may not provide enough guidance. The paper presents Clara, a fully automated repair approach that uses existing correct student solutions, and evaluates it on MOOC attempts and in an interactive user study. Clara repaired 97% of incorrect attempts, with 81% of generated repairs judged good-quality, and received an average usefulness rating of 3.4/5.
Problem
Scaling personalized feedback for introductory programming, especially in MOOCs, is difficult, and failing test cases may not provide sufficiently guided feedback.
Method
Clara automatically clusters correct student solutions and uses them to generate minimal repairs for incorrect attempts.
Results
Clara repaired 97% of 4,293 incorrect MOOC attempts, with 81% of generated repairs judged good-quality, and users rated feedback usefulness 3.4/5.
Takeaways & Limitations
The evaluation supports using Clara to generate many high-quality repairs automatically and in an interactive teaching setting.
Takeaways & Limitations
The approach was evaluated on small to medium-sized programs, while extension to larger programming problems was left for future work.
Abstract
from arXiv · showhide
Providing feedback on programming assignments is a tedious task for the instructor, and even impossible in large Massive Open Online Courses with thousands of students. Previous research has suggested that program repair techniques can be used to generate feedback in programming education. In this paper, we present a novel fully automated program repair algorithm for introductory programming assignments. The key idea of the technique, which enables automation and scalability, is to use the existing correct student solutions to repair the incorrect attempts. We evaluate the approach in two experiments: (I) We evaluate the number, size and quality of the generated repairs on 4,293 incorrect student attempts from an existing MOOC. We find that our approach can repair 97% of student attempts, while 81% of those are small repairs of good quality. (II) We conduct a preliminary user study on performance and repair usefulness in an interactive teaching setting. We obtain promising initial results (the average usefulness grade 3.4 on a scale from 1 to 5), and conclude that our approach can be used in an interactive setting.
1 Introduction
The paper addresses the difficulty of scaling personalized feedback in introductory programming, especially MOOCs, by proposing automated repair based on existing correct student solutions. Clara repairs most incorrect attempts and produces promising feedback in an interactive teaching setting.
- Motivation: The approach targets a feedback problem that requires substantial teaching effort and is difficult to scale to thousands of MOOC students.Failing test cases are useful but insufficient for students seeking more guided feedback.
- Approach: Clara uses existing correct student solutions to repair incorrect attempts, exploiting the large pool of solutions available in MOOCs.Correct solutions are automatically clustered, and repairs use expressions from multiple correct solutions.
- Evaluation: 97% of 4,293 incorrect MITx MOOC attempts were repaired, with repairs taking 3.2s on average.The dataset also contained 12,973 correct attempts, for 17,266 total Python attempts.
- Evaluation: 81% of generated repairs were judged good-quality, and their sizes matched the required program changes.Quality and repair size were assessed through manual inspection.
- Evaluation: 3.4/5 was the average usefulness rating in a preliminary study of repair-based feedback.The study involved 52 participants solving six C assignments.
- Approach: The approach automatically clusters correct solutions using dynamic analysis and repairs incorrect attempts by selecting minimal-cost candidates.The paper presents clustering, automated repair, and evaluation on a large MOOC dataset as core contributions.
2 Overview
The overview illustrates clustering and repair on student solutions to a derivative assignment. Clara groups dynamically equivalent correct programs, mines their alternative expressions, and combines local repairs into a minimal-cost whole-program repair.
- Clustering: Clustering improves scalability by avoiding separate consideration of dynamically equivalent correct solutions and increases repair diversity by mining their different expressions.The two goals are explicitly identified as scalability and diversity of repairs.
- Clustering: Clustering groups correct solutions with the same looping structure and corresponding variable-value traces, even when their syntax differs.The matching relation requires equivalent control-flow and a bijective variable relation preserving execution values.
- Clustering: 15 syntactically different expressions for the loop assignment and 6 for the return expression were found among dynamically equivalent solutions.These alternative expressions provide repair choices while preserving observed behavior.
- Repair: For an incorrect implementation and a correct-program cluster, Clara generates local repairs for variables and program locations.A local repair may modify an expression or leave it unchanged when the expressions already match.
- Repair: Constraint optimization selects a consistent subset of local repairs with the smallest cost to form a whole-program repair.The top-level procedure runs against each cluster and chooses the minimal-cost repair using syntactic distance.
3 Program Model
The program model represents imperative programs through locations, variables, updates, successors, expressions, memories, and execution traces. It models loop structure explicitly and represents loop-free conditionals as expressions.
- Expressions: Expressions are built from variables, constants, and operations, with special variables for conditions and return values.The model reserves ? for conditions and return for return values.
- Program representation: A program is modeled as locations, an initial location, variables, an update function, and a successor function.The successor function maps locations and Boolean conditions either to another location or to the end marker.
- Execution semantics: The computation domain includes true, false, and an undefined value ⊥.Memories map variables and their primed versions to values in this domain.
- Execution semantics: Execution produces traces of location-memory pairs, where memory records variable values before and after each location is evaluated.The semantics initialize memory from the input and propagate updated values through successor locations.
- Control-flow: Loop-free if-then-else statements are recursively converted into ite expressions, while branching containing loops remains in the control-flow.This representation supports the selected control-flow granularity for matching.
- Example: In the derivative example, locations represent the code before the loop, its condition, the loop body, and the code after the loop.The model assigns expressions to variables at each location and executes the resulting trace on an input memory.
4 Matching and Clustering
Matching compares programs through control-flow and execution traces over a fixed input set, using a bijective variable relation. Clusters are equivalence classes of matching correct programs whose expressions supply alternatives for repair.
- Matching: Programs match when they have the same control-flow and corresponding variables take the same values in the same order over the selected inputs.The paper calls this relation dynamic equivalence because it is evaluated on a fixed finite input set.
- Matching: The matching algorithm executes both programs, identifies variables with identical value projections, and searches for a bijective matching witness.Potential matches are collected before constructing the bijective mapping.
- Matching: Expression matching requires corresponding expressions to produce equal values at the relevant locations across the collected traces.A matching-equivalence lemma connects expression matching with program matching.
- Clustering: Clusters are equivalence classes of the matching relation over correct programs, with one representative providing a common variable vocabulary.Expressions from every program in a cluster are translated into the representative’s variables.
- Clustering: Expressions collected from one cluster are dynamically equivalent even when they are syntactically different, supplying alternatives for repair.The representative choice is arbitrary because all cluster expressions match over the input traces.
5 Repair Algorithm
The repair algorithm constructs local repairs that align an incorrect implementation with a correct-solution cluster, then selects a consistent minimum-cost combination. It relies on structural matching, partial variable relations, and an ILP-based search, with soundness guaranteed for the resulting repair.
- Repair algorithm: The algorithm repairs an implementation relative to a cluster representative while preserving its control-flow structure.The goal is to modify the implementation minimally so it matches the cluster.
- Local repairs: Local repairs replace individual expressions or leave already matching expressions unchanged under a partial variable relation.Modified expressions receive a cost based on their difference; unchanged matches have zero cost.
- Repair construction: A full repair is a consistent set of local repairs sharing a total variable relation, with cost equal to the sum of local-repair costs.The repaired implementation applies the selected expression replacements while retaining unchanged expressions.
- Correctness: The resulting repair is sound: the repaired implementation matches the cluster representative under the paper’s behavioral equivalence relation.This guarantee follows from the consistency conditions and the expression-matching lemma.
- Optimization: FindRepair encodes the minimum-cost consistent subset as a zero-one integer linear program and delegates optimization to an off-the-shelf solver.The ILP includes variables for implementation-to-cluster variable pairs and possible local repairs.
- Candidate generation: The algorithm builds possible local repairs by checking expression matches and importing expressions from the cluster under partial variable mappings.These candidates include both zero-cost unchanged expressions and translated replacement expressions.
6 Implementation and Experiments
The evaluation measures Clara’s repair coverage, size, quality, comparison with AutoGrader, and interactive usefulness. Results show broad automated coverage, mostly non-trivial and good-quality repairs, but limitations remain for unsupported constructs, unmatched control flow, larger programs, and test-set soundness.
- MOOC evaluation: 97.44% of attempts received automatically generated repairs, while 110 cases failed because of unsupported features, unmatched control flow, or numeric precision errors.The authors identify unmatched control flow as the fundamental limitation of the approach.
- Repair size: 68% of repairs had relative size < 0.3, indicating that Clara usually changed only part of the student program rather than replacing it entirely.The reported proportions were 53% below 0.2 and 25% below 0.1; empty attempts produced infinite relative size.
- Repair quality: 81 of 100 manually inspected cases produced good-quality repairs, including 72 smallest natural repairs and 9 nearly smallest repairs with an unnecessary modification.Eleven repairs were correct but differed from the student’s idea, while eight cases were too unclear to assess.
- Comparison with AutoGrader: 97.44% of attempts were repaired by Clara versus 19.29% by AutoGrader, although AutoGrader produced smaller repairs in around 10% of cases.Among cases where both tools generated repairs, the authors found no notable overall quality difference.
- User study: In the interactive user study, feedback was generated for 88.52% of incorrect attempts and received an average usefulness grade of 3.4 from 52 participants.The usefulness results were based on 191 grades and are described as preliminary.
- Threats to validity: The evaluation covers small to medium introductory programs, and repairs are guaranteed correct only over the given test cases.Extending the approach to larger programming problems is left for future work.
7 Related Work
The paper situates its approach among automated feedback, program classification, and program repair methods, emphasizing dynamic analysis and fully automated repairs for introductory education.
- Prior educational feedback systems commonly use automatically generated or instructor-selected failing test cases, but these provide less guidance than repair-based feedback.
- CodeWebs and related classification approaches group programs using execution or syntactic features, whereas this work uses clustering and repair based on dynamic equivalence.
- The paper uses dynamic analysis for scalability, targeting small educational programs rather than the larger programs addressed by many non-educational repair approaches.
- Other automated repair systems have shown low repair rates or limited repair forms in educational settings, whereas this approach is designed to provide complete repairs.
- AutoGrader requires instructor-provided reference solutions and rewrite rules, while the paper’s approach is completely automatic and can generate more complicated repairs.
- Refazer learns transformations from student edits without a cost model, while this approach selects the smallest repair; Rivers and Koedinger use syntax equivalence, while this work uses dynamic equivalence.
8 Future Work
The paper identifies limitations in repair cost modeling, control-flow matching, feedback presentation, and pedagogical evaluation, leaving broader capabilities and educational questions for future work.
- The current cost function compares only syntactic differences between original and replacement expressions, although variable roles or semantic distance could provide additional information.
- The algorithms require matching control-flow, and extending them to programs with different or merely similar control-flow is left for future work.
- The tool currently outputs textual repair descriptions, while instructor-annotated variables could support more abstract, variable-specific feedback.
- Future pedagogical work includes deciding how much repair information to reveal, whether automated help should be penalized, and how much students learn from it.
9 Conclusion
The paper presents clustering and repair algorithms that use existing correct student solutions to repair incorrect introductory-programming submissions. Its evaluation reports many automatic, complicated, and high-quality repairs, including in interactive teaching.
- The approach uses tens of thousands of existing correct MOOC solutions to repair incorrect student attempts without manual intervention.
- The evaluation reports that Clara can generate complicated repairs and support interactive teaching settings.
- The evaluation reports good-quality repairs in a large percentage of cases.
A List of Problems in the Evaluation
The evaluation covers introductory programming problems involving numerical computation, sequences, tuples, digit properties, reversals, factorials, and formatted visual patterns.
- The evaluation includes derivative and polynomial problems that require numerical computation and return numeric values or lists of floats.
- The problem set includes tuple selection and Fibonacci-sequence tasks, covering structured data and recursive numerical definitions.
- Several tasks involve digit-based or integer properties, including special numbers, reverse differences, and counting factorial numbers in an interval.
- The evaluation also includes formatted output problems requiring rhombus and trapezoid patterns, with explicit constraints on spaces and empty final lines.
B Additional Code Examples
These examples compare Clara with AutoGrader and show both broader repair coverage and occasional unnecessary modifications. Clara can generate correct repairs that AutoGrader cannot, but its control-flow requirement may add redundant changes.
- Repairs beyond AutoGrader: Clara generates repairs for examples that AutoGrader cannot repair because they require fresh variables, new statements, or unsupported expression changes.AutoGrader’s error model does not support these modifications in the cited examples.
- Unnecessary modifications: Clara sometimes generates a correct repair with an unnecessary modification because the closest correct attempt has reversed branches.The repair algorithm requires the same control-flow, so it suggests modifications that could otherwise be omitted.
- Repairs beyond AutoGrader: 0.48 is the relative cost of one Clara repair in the example where AutoGrader cannot repair the attempt.
- Repairs beyond AutoGrader: 0.19 is the relative cost of another Clara repair, while AutoGrader again fails to generate any repair.
- Unnecessary modifications: Removing such redundant modifications would require relaxing Clara’s control-flow requirement, but the paper does not identify how to do so.