Source-linked AI summary
Automated Feedback Generation for Introductory Programming Assignments
Rishabh Singh, Sumit Gulwani, Armando Solar-Lezama
TL;DR
The paper tackles the challenge of providing precise feedback for large-scale introductory programming courses, where manual and peer feedback do not scale reliably. It combines reference implementations, correction-rule error models, and constraint-based synthesis to derive minimal fixes. Evaluations on thousands of student attempts show that the technique can correct 65% of incorrect solutions.
Problem
Large introductory programming courses need precise, personalized feedback, but manual, peer, and test-case-based approaches have important scalability or quality limitations.
Method
The system uses a reference implementation, a high-level error model, and constraint-based synthesis to find minimal corrections matching the reference behavior.
Results
65% of incorrect solutions were corrected in evaluations on thousands of real student attempts.
Takeaways & Limitations
Relatively simple correction rules can support automated feedback for large sets of introductory programming submissions.
Takeaways & Limitations
The approach cannot correct some big conceptual errors with local correction rules, including mistakes requiring statements to be introduced or moved.
Abstract
from arXiv · showhide
We present a new method for automatically providing feedback for introductory programming problems. In order to use this method, we need a reference implementation of the assignment, and an error model consisting of potential corrections to errors that students might make. Using this information, the system automatically derives minimal corrections to student's incorrect solutions, providing them with a quantifiable measure of exactly how incorrect a given solution was, as well as feedback about what they did wrong. We introduce a simple language for describing error models in terms of correction rules, and formally define a rule-directed translation strategy that reduces the problem of finding minimal corrections in an incorrect program to the problem of synthesizing a correct program from a sketch. We have evaluated our system on thousands of real student attempts obtained from 6.00 and 6.00x. Our results show that relatively simple error models can correct on average 65% of all incorrect submissions.
1. Introduction
The paper addresses the difficulty of giving precise, scalable feedback on introductory programming assignments by combining reference implementations with error models and synthesis. Evaluations on thousands of student attempts report feedback for 65% of incorrect solutions.
- Motivation: MOOC-scale programming courses need personalized feedback, but traditional classroom feedback approaches do not scale to thousands of students.Test-case feedback can be inadequate for beginners, while manual teaching-assistant feedback is prohibitive and peer feedback may be delayed, incomplete, too general, or wrong.
- Approach: The technique uses a correct reference implementation and an error model describing predictable student mistakes to guide automated feedback.The known specification and recurring homework errors make a model-based feedback approach possible.
- Approach: Constraint-based synthesis frames feedback generation as finding a correct program that matches the reference behavior while applying a minimal set of corrections.The system symbolically explores correction combinations and supports dynamic typing and complex Python constructs.
- Challenges: The assumptions that enable model-based feedback also require reasoning about program equivalence, parameterized error models, and coordinated fixes in error-dense programs.The paper notes that local one-path-at-a-time bug correction may fail when fixes are needed in multiple places.
- Evaluation: 65% of incorrect submissions received feedback in evaluations of thousands of real attempts from 6.00 and 6.00x classes and related sources.The reported average runtime was about 10 seconds on average.
2. Overview of the approach
The approach uses an instructor’s reference implementation and error model to generate minimal corrections and precise feedback for incorrect Python solutions. It translates correction choices into a synthesis problem, handling dynamically typed Python and large candidate spaces.
- Workflow: The tool compares a student’s solution with a reference implementation and searches for the minimum-cost set of corrections that makes their behavior equivalent.For the computeDeriv example, it identifies three corrections involving a return value, an unnecessary conditional, and loop bounds.
- Workflow: The generated feedback can identify the error location, problematic expression, modified sub-expression, and replacement value.A feedback-level parameter controls which combinations of these four pieces are shown.
- Workflow: The instructor supplies a reference implementation, argument and return types, and an error model describing potential student mistakes through correction rules.The error model can include optional replacements for return expressions, range bounds, and Boolean conditions.
- Solution Strategy: The solution strategy translates the student program first into g MPY, which represents correction choices and their costs, and then into a Sketch program.g MPY uses expression choices with an unchanged, zero-cost option; Sketch represents these choices as synthesis holes.
- Solution Strategy: The correction search can become exponential, reaching more than 10^12 candidate programs for some benchmarks, so constraint-based synthesis is used to search efficiently.For the simple example, three rules induce 32 candidate programs.
- Synthesizing Corrections with Sketch: The translation models dynamically typed Python with Sketch structs and represents g MPY set-expressions with Sketch holes.The MultiType representation supports integer, Boolean, type, list, and tuple values, while list contents use a length field and an array of MultiType elements.
3. EML: Error Model Language
EML represents student-error corrections as weighted rewrite rules over MPY programs, translating them into g MPY representations of candidate programs. Well-formed models make this transformation deterministic and terminating while preserving correction costs for minimal-fix search.
- EML semantics: EML rewrite rules transform MPY program elements into weighted sets of g MPY program elements representing possible corrections.Rules can target terms, expressions, statements, methods, or whole programs; each correction normally costs 1.
- MPY and g MPY: g MPY compactly represents large collections of MPY programs through set-expressions and set-statements.Composite sets combine constituent alternatives, such as operands and operators, to encode many expressions succinctly.
- Weighted translation: The [[ ]] function recursively constructs weighted candidate sets by taking cross-products of constituent alternatives and adding their correction costs.For indexed expressions, the resulting cost is the sum of the index and container sub-expression costs.
- Correction rules: EML supports recursive tagged sub-expressions, scoped same-type variable alternatives, and correction rules for indexing, initialization, ranges, comparisons, and returns.The computeDeriv model includes rules for common indexing, range, comparison, and list-return mistakes.
- Termination: Well-formed rewrite rules require tagged right-hand-side subterms to have smaller syntax trees than their left-hand sides, guaranteeing that TE terminates.The theorem follows because every recursive rule application reduces the syntax-tree size requiring further transformation.
- Transformation: The transformation function recursively applies matching rules and returns all transformed alternatives, while ambiguity is represented through alternative transformations.Instructors can use combined rules when multiple corrections should apply together.
4. Constraint-based Solving of g MPY programs
The system translates g MPY programs into SKETCH programs for constraint-based analysis. This translation covers Python-like constructs and represents set-expression choices with SKETCH functions.
- Translation pipeline: g MPY programs are translated into SKETCH programs to perform constraint-based analysis.The translation is the second stage after rewriting student programs with the error model.
- Translation pipeline: The translation maps Python-like g MPY constructs to SKETCH and converts set-expression choices into SKETCH functions.These are identified as the main aspects of the translation.
- Dynamic typing: Dynamic typing is represented with MultiType variables, and translated assignments and binary additions invoke corresponding MultiType operations.For example, assignment becomes assignMT(a, b), while addition becomes binOpMT(a, b, ADD_OP).
1 MultiType addMT(MultiType a, MultiType b){
The SKETCH translation turns g MPY alternatives into synthesizable program choices while preserving language semantics through MultiType operations and driver functions. CEGISMIN then searches for verified completions with minimal correction cost and maps selected holes back to feedback messages.
- Set-expression translation: Set-expressions are translated into SKETCH functions whose holes let the synthesizer choose among alternative corrections.Default and non-default alternatives are selected through conditional holes, while singleton sets translate directly to their expressions.
- Set-expression translation: Translation recursively handles conditional assignment choices and converts infix operators into function calls before translating them to SKETCH.Assignments with choices on the left-hand side are desugared into separate conditional assignments.
- Function calls: Function-call translation can use student implementations, teacher implementations, or uninterpreted sub-functions.These options support recursive problems and programs that call other student-written functions.
- Driver functions: MultiType driver functions convert primitive SKETCH inputs into MultiType values, call translated functions, and convert returned values back to primitive types.This bridges SKETCH’s primitive-type equivalence checking with Python-like dynamically typed programs.
- Constraint-based synthesis: CEGISMIN extends CEGIS to synthesize verified sketches while iteratively adding counterexamples and constraints that minimize hole values.When verification succeeds, the algorithm records a minimum hole value and constrains later solutions to improve it.
- Feedback generation: After synthesis, unknown integer-hole values are mapped to correction choices and then to natural-language feedback messages.Each correction rule is associated with a message describing the corresponding student error and fix.
5. Implementation and Experiments
The implementation and experiments evaluate a Python-to-SKETCH feedback tool on real introductory-programming submissions, showing broad correction coverage while exposing limits from conceptual errors and unsupported features.
- Implementation: The tool converts Python programs to SKETCH, uses CEGISMIN-backed synthesis, and represents error models as Python AST correction rules.It also supports assigning different cost measures to correction rules.
- Overall performance: 65% of incorrect student attempts received appropriate corrections in around 10 seconds on average.Experiments used 4-bit input-integer bounds and maximum input-list length 4 after removing syntax-error attempts.
- Failure cases: 35% of incorrect attempts lacked feedback because they were completely incorrect, contained big conceptual errors, or used unimplemented features.Less than 1% of attempts timed out under the two-minute limit.
- Failure cases: 260/541 eval-poly-6.00x attempts used list.index incorrectly, illustrating conceptual mistakes that local correction rules cannot fix.Other difficult mistakes involved introducing or moving statements between locations.
- Correction complexity: A large fraction of attempts required 3 or 4 coordinated corrections, motivating symbolic reasoning over correction interactions.The system encodes the outcomes of different corrections across all input values.
- Error-model analysis: Adding a single error-model rule could correct hundreds of attempts, while a compute-deriv model generalized less effectively than problem-specific models.The generalized model still fixed some incorrect attempts and provided a starting point for adding problem-specific rules.
6. Related Work
Related approaches provide feedback through code matching, student-intention models, repair, debugging, or synthesis. This approach instead performs bounded symbolic semantic equivalence without restricting student algorithms and handles declarative correction-rule interactions modularly.
- Automated tutors: Automated programming tutors commonly use test cases or peer feedback, but the paper also surveys code-based and intention-based matching systems.The surveyed systems include LAURA, TALUS, LISP tutor, MENO-II, and PROUST.
- Automated tutors: Code-based matching can require enumerating many teacher algorithms and variants, while intention-based matching can constrain students to predefined structures.These limitations motivate alternatives that do not depend on fixed algorithm catalogs or plans.
- This approach: The approach compares student and teacher programs through exhaustive bounded symbolic verification and makes no assumptions about students’ algorithms or plans.Its local correction rules are declarative, with complex interactions handled by the solver.
- Program repair: Unlike mutation-based repair, which faces a mutant state space of 10^12, this approach uses symbolic search over correct solutions.The related repair methods also include model-based diagnosis, template-based SMT correction, and genetic programming.
- Program synthesis: Program synthesis systems such as SKETCH complete partial programs against reference implementations using constraint-based reasoning, providing the underlying synthesis paradigm.The paper places its feedback technique within broader synthesis applications.
7. Conclusions
The paper presents automated feedback that combines error models with constraint-based synthesis to compute minimal corrections for introductory programming solutions. Evaluated on a large benchmark set, the technique corrected 65% of incorrect solutions and is positioned as a complement to manual and test-case feedback.
- Conclusion: The technique uses error models describing potential corrections and constraint-based synthesis to compute minimal corrections to incorrect solutions.It is intended to complement manual and test-case-based feedback.
- Conclusion: 65% of incorrect solutions were corrected on a large benchmark set.The conclusion presents this as the principal evaluation outcome.
- Conclusion: The authors believe the technique could support automated feedback for hundreds of thousands of students in online introductory programming courses.The stated scope includes courses taught by MITx and Udacity.