Automating and Testing Program Transformations using Program Synthesis

Опубликовано 12 мая 2017, 16:43

Automatic program transformation tools can be valuable for programmers to help them with refactoring tasks, and for Computer Science students in the form of tutoring systems that suggest repairs to programming assignments. However, manually implementing and testing catalogs of transformations is complex and time-consuming. In this talk, I will present two program synthesis-based techniques for automating these tasks.

First, I will present Refazer, a technique for synthesizing program transformations from examples. Refazer builds on the observation that code edits performed by developers can be used as input-output examples for learning program 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 efficiently synthesizing transformations in the DSL, and (c) functions for ranking the synthesized transformations. We evaluated Refazer on two applications: synthesizing bug fixes for Python programming assignments and synthesizing transformations that apply repetitive edits to large C# codebases. Our technique learned transformations that automatically fixed the program submissions of 87% of the students participating in a large UC Berkeley class and it learned the transformations necessary to apply the correct code edits for 84% of the repetitive tasks we extracted from three large code repositories.

Next, I will talk about the challenge of testing refactoring tools. Refactorings must preserve the behavior of a program. Usually, compilation errors and behavioral changes are avoided by preconditions. However, defining and implementing preconditions is non-trivial. In practice, tool developers may not be aware of all preconditions. I will present a technique for testing refactoring tools. Its main novelties are its technique for synthesizing input programs as test inputs and the use of test oracles for checking behavioral preservation based on dynamic analysis. It has been useful for identifying more than 100 bugs in state-of-the-art Java and C refactoring engines.

See more on this video at microsoft.com/en-us/research/v...