Source-linked AI summary
Learning Syntactic Program Transformations from Examples
Reudismam Rolim, Gustavo Soares, Loris D'Antoni, Oleksandr Polozov, Sumit Gulwani, Rohit Gheyi, Ryo Suzuki, Bjoern Hartmann
TL;DR
Existing tools make only predefined classes of code transformations available, while instructors and developers repeatedly need related edits generalized across programs. REFAZER learns transformations from edits using a DSL, synthesis constraints, and ranking, fixing 87% of students’ incorrect submissions and learning intended transformations in 83% of repetitive-edit cases. Its evaluations cover student assignments and repetitive edits in open-source C# projects.
Problem
Existing transformation tools rely on catalogs that are hard to extend, while recurring edits and student fixes require automatically learned generalizations.
Method
REFAZER uses a DSL for AST rewrite rules, domain-specific synthesis constraints, and ranking functions to learn transformations from code-edit examples.
Results
REFAZER fixed incorrect submissions for 87% of students and learned the intended transformation in 83% of repetitive-edit scenarios.
Takeaways & Limitations
The evaluations demonstrate REFAZER’s use for learning student-submission fixes and applying repetitive developer edits across code locations.
Abstract
from arXiv · showhide
IDEs, such as Visual Studio, automate common transformations, such as Rename and Extract Method refactorings. However, extending these catalogs of transformations is complex and time-consuming. A similar phenomenon appears in intelligent tutoring systems where instructors have to write cumbersome code transformations that describe "common faults" to fix similar student submissions to programming assignments. We present REFAZER, a technique for automatically generating program transformations. REFAZER builds on the observation that code edits performed by developers can be used as examples for learning transformations. Example edits may share the same structure but involve different variables and subexpressions, which must be generalized in a transformation at the right level of abstraction. To learn transformations, REFAZER leverages state-of-the-art programming-by-example methodology using the following key components: (a) a novel domain-specific language (DSL) for describing program transformations, (b) domain-specific deductive algorithms for synthesizing transformations in the DSL, and (c) functions for ranking the synthesized transformations. We instantiate and evaluate REFAZER in two domains. First, given examples of edits used by students to fix incorrect programming assignment submissions, we learn transformations that can fix other students' submissions with similar faults. In our evaluation conducted on 4 programming tasks performed by 720 students, our technique helped to fix incorrect submissions for 87% of the students. In the second domain, we use repetitive edits applied by developers to the same project to synthesize a program transformation that applies these edits to other locations in the code. In our evaluation conducted on 59 scenarios of repetitive edits taken from 3 C# open-source projects, REFAZER learns the intended program transformation in 83% of the cases.
I. INTRODUCTION
REFAZER learns syntactic program transformations from concrete code edits, addressing the difficulty of extending predefined automation catalogs and generalizing edits across variables and expressions. Evaluations show it fixes many student submissions and recovers repetitive developer edits across codebases.
- Problem: Existing IDEs and analyzers rely on predefined transformation catalogs that are hard to extend.This motivates the question of whether program transformations can be learned automatically.
- Opportunity: Code edits from repositories and version histories provide input-output examples for learning program transformations.The approach targets both developer edits and recurring fixes in student submissions.
- Challenge: Similar edits share structure while differing in variables and expressions, requiring abstraction at an appropriate level.Over-specialization can miss unseen cases, while over-generalization can produce incorrect edits.
- Technique: REFAZER synthesizes transformations with a DSL of AST rewrite rules, domain-specific constraints, and ranking functions.The constraints reduce the search space, while ranking selects among transformations consistent with the examples.
- Evaluation: 87% of students had incorrect submissions fixed across 4 programming tasks involving 720 students.A submission counted as fixed when it passed the instructors’ test suite.
- Evaluation: 83% of 59 repetitive-edit scenarios yielded the intended transformation across 3 open-source C# projects.The transformations used 2.8 examples on average and could apply edits to as many as 60 program locations.
II. MOTIVATING EXAMPLES
The section introduces two motivating examples centered on repetitive program transformations.
- The section begins by presenting two motivating examples.
- Both examples concern repetitive program transformations.
- These examples motivate the paper’s discussion of program transformations.
A. Fixing programming assignment submissions
REFAZER learns transformations from student edits to automate feedback for recurring programming faults. It abstracts shared edit structure while preserving varying expressions and variables.
- More than 100 students exhibited the same fault in a Spring 2016 programming assignment.
- REFAZER learns rubric checks from student submissions to reduce the burden of manually compiling feedback.
- Its rewrite rule matches AST subtrees rooted at * with a variable second operand and inserts a term application on that variable.
- The learned rule abstracts both the variable name and the first operand of the multiplication.
III. TECHNIQUE
REFAZER uses programming-by-example synthesis to generate AST transformations from edit examples. Its design combines a transformation DSL, witness functions, and robustness-based ranking.
- PROSE synthesizes DSL programs consistent with input-output specifications using deduction, search, and ranking.
- Witness functions backpropagate specifications from DSL operators to their subexpressions, enabling efficient top-down synthesis.
- The workflow receives an example-based edit specification and returns a transformation.
- Ranking functions prioritize transformations according to robustness, or their likelihood of being correct generally.
A. A DSL of AST transformations
LT describes AST transformations with rewrite rules that select locations by patterns and apply tree-edit operations. It supports concrete and abstract matching plus references to context-dependent AST nodes.
- LT combines tree edits, list processing, and tree pattern matching to describe program transformations.
- A transformation is a list of rewrite rules, each pairing an operation with locations selected by filtering AST nodes against a pattern.
- Patterns combine concrete AST tokens with abstract tokens that match only AST kinds, while paths constrain a node’s position in context.
- Supported operations include inserting, deleting, updating, and inserting-before AST nodes.
- Operations construct fresh ASTs from constants and references extracted from matching ancestors or descendants.
- In the CSharpKind example, the operation replaces a selected location with an IsKind call using extracted receiver and right-hand-side ASTs.
B. Synthesis algorithm
The synthesis algorithm infers rewrite rules from input-output AST examples by identifying, clustering, and generalizing concrete edits. It uses deductive backpropagation with domain-specific witness functions.
- Given an example specification, synthesis finds a transformation in LT consistent with every input-output example.
- Backpropagation reduces synthesis of a transformation to constraints on its rewrite rules.
- The synthesized transformation applies rewrite rules at applicable locations and produces a list of edits for an input AST.
- The algorithm computes tree edit distance, groups connected node edits, clusters components with DBSCAN, and constructs operation examples for rewrite rules.
- A connected component groups node edits representing one subtree edit because LT operations manipulate whole subtrees.
C. Ranking
REFAZER ranks many transformations consistent with examples by favoring transformations likely to remain robust on unseen ASTs, balancing false positives against false negatives.
- C. Ranking: The ranking function selects transformations expected to be robust on unseen ASTs, avoiding false-positive and false-negative matches.It disambiguates among potentially thousands of transformations consistent with an example-based specification.
- C. Ranking: It favors reusing nodes from the input AST over constructing constant AST nodes, because reuse is more likely to match the intended transformation.
- C. Ranking: It favors patterns with non-root paths so surrounding context helps select locations and reduces false-positive matches.
- C. Ranking: Among contextual patterns, it favors shorter contexts because large contexts can overfit and produce false-negative matches.
IV. EVALUATION
The evaluation examines REFAZER in two empirical studies: fixing introductory Python programming submissions and applying repetitive edits to open-source C# projects.
- IV. EVALUATION: REFAZER is evaluated on learning transformations that fix student submissions to introductory Python programming assignments.
- IV. EVALUATION: REFAZER is also evaluated on learning transformations that apply repetitive edits to open-source C# projects.
A. Fixing introductory programming assignments
This study evaluates whether transformations learned from student edits can fix other submissions, including across assignments, and examines their usefulness and limitations in introductory programming education.
- Research questions: The study asks whether transformations learned from student edits fix other students’ incorrect code on the same or a different programming assignment.
- Benchmark: The benchmark uses introductory CS61A data, where students submit incorrect programs and eventually correct submissions while checking a black-box test suite.
- Experimental setup: The experimental setup learns transformations from each student’s last incorrect and correct submissions, then applies them to other students’ incorrect submissions.
- Results within assignments: On average, REFAZER found fixes 3.5 submissions before students’ last incorrect submissions, despite training only on their final incorrect-correct pair.The result suggests feedback could be provided before students independently reach a correct solution.
- Qualitative findings: Learned transformations ranged from single AST-node edits to adding statements, replacing iterative solutions with recursive ones, and representing multiple mistakes.
- Results across assignments: Transformations learned from other assignments fixed only 7–9% of students, indicating that most learned transformations are problem-specific.The results support using problem-specific training corpora for different assignments.
- Qualitative feedback: A teaching assistant found fixes generally appropriate but reported that one syntactic transformation can correspond to distinct underlying mistakes, complicating feedback descriptions.Additional tools may be needed to merge or split clusters of student submissions.
B. Applying repetitive edits to open-source C# projects
REFAZER was evaluated on repetitive edits from three large C# open-source projects, learning transformations for nearly all scenarios while sometimes overgeneralizing edits.
- Benchmark: The benchmark covered 59 repetitive-edit scenarios from Roslyn, Entity Framework, and NuGet, with 3–60 edited locations per scenario.The projects ranged from 150,000 to 1,500,000 lines of code, and each repetitive edit affected more than two locations.
- Experimental setup: REFAZER used diff-described edits as examples, adding varied examples iteratively until all repetitive locations were found.Example selection prioritized different transformation variations.
- Results: 58 of 59 scenarios yielded synthesized transformations.The remaining scenario did not produce a transformation.
- Results: 64% of scenarios matched developers’ edits, while 17% produced incorrect additional edits and exposed DSL limitations.Another 11 scenarios produced additional edits judged correct because developers had missed some edits.
- Limitations: The current DSL lacks data-flow analysis and sufficiently precise tree matching, which can select incorrect locations through over-generalization.The authors propose richer predicates and flow analyses as future extensions.
- Results: REFAZER required an average of 2.8 examples to synthesize all transformations in a diff.The number varied with example selection and ranking functions, whose further investigation remains future work.
V. RELATED WORK
Related work spans example-based transformation, inductive programming, educational feedback, code completion, and automated program repair, with REFAZER emphasizing fully automated transformation synthesis from examples.
- Example-based program transformations: Lase performs repetitive edits from multiple edited methods using clone detection and dependence analysis to identify applicable methods and context.Its abstraction is limited mainly to names of types, variables, and methods.
- Example-based program transformations: Other approaches combine examples with transformation templates, whereas REFAZER is described as fully automated.Related systems also synthesize data-structure transformations or migrate APIs from already migrated clients.
- Code completion: Code-completion and refactoring-assistance methods recommend transformations based on repository data or editing context, but are limited by existing refactorings and datasets.REFAZER is presented as able to automate transformations not previously seen.
- Inductive programming: Inductive programming has been applied to domains including parsers, imperative data structures, network policies, and industrial spreadsheet features.This places REFAZER within a broader Programming-by-Example research area.
- Synthesis for education: AutoGrader requires a predefined error model, while REFAZER generates transformations from examples of student fixes.Other educational systems generate hints from nearby correct solutions or cluster submissions by strategy.
- Program repair: Automated program repair searches for program changes satisfying a desired specification through enumerative, genetic, or data-driven techniques.REFAZER instead focuses on synthesizing transformations from example edits.
VI. CONCLUSIONS
The paper presents REFAZER as an example-driven technique for synthesizing syntactic program transformations and evaluates it on student fixes and repetitive edits in large codebases.
- Conclusions: REFAZER synthesizes syntactic program transformations from program-edit examples using PROSE.Its design includes a transformation DSL, domain-specific search constraints, and robustness-oriented ranking functions.
- Conclusions: REFAZER fixed submissions for 87% of students and learned transformations for 83% of repetitive tasks from three large code repositories.These evaluations covered both educational fixes and repetitive edits in codebases.
- Future work: Future work targets richer tree patterns, control-flow and data-flow analyses, negative examples, and interaction models for applying and debugging synthesized transformations.The education agenda includes personalized feedback based on learned fixes.
- Conclusions: REFAZER extends backpropagation-based Programming-by-Example to software engineering and automates extraction of input-output examples from student and developer data.The authors describe this as progress toward fully unsupervised Programming-by-Example.