Navigation

Wiki

Toolbox

From CUSystems

University: University of Colorado at Boulder

Professors: Amer Diwan

Contents 1 Project Overview 2 Our Approach 3 Our Research 4 Further reading

Project Overview

Modern agile software engineering practices encourage programmers to refactor their code frequently. Consequently, modern integrated development environments incorporate machine support for refactoring; such machine support takes the form of automatic program transformations that atomically preserve program behavior.

This approach to refactoring is useful, but both the approach and its state-of-the-art implementations fall short of their potential utility in several ways:

(1) Atomic transformations must often work harder than they would like to. For example, when inlining a method body, we frequently encounter name clashes. Consider the following (simplified) Python example:

   def f(x):
   	y = x+1
       return y
 
   def g(x):
       y = x*x
       z = f(x)
       return y+x

If we try to inline "f" into "g", we will wind up with two variables of name "y", with different meanings.

Practical systems can choose to simply abort in such situations (thereby restricting their utility), though many sidestep this particular problem by renaming one of the variables. This is a heuristic and may or may not reflect what the user desires; in either case, it complicates the implementation of the refactoring.

Similar (but more involved) issues arise with variables going out of scope and with certain "corner cases" in popular refactorings (such as requiring multiple return types during an "extract method" refactoring in Java).

(2) Many refactorings do not scale. Consider moving two mutually recursive procedures from one module to another: no matter which procedure we move first, we will break the mutual recursion, so the refactoring cannot accommodate our request.

Existing systems either ignore this problem or provide complex special-case handling, thereby increasing the complexity of the refactoring and thereby the risk of bugs and the need for (possibly unintuitive) heuristics.

(3) Purely /behavior-preserving/ transformations fall short of many practical user needs. For example, changing a public method signature is a behavioral change, since external programs may depend on the method. Worse, swapping two parameters often alters the order of side effects.

Practical systems sidestep this problem by heuristically assuming that the behavioral changes introduced by such changes are "irrelevant", which may or may not be correct in any given case.

(4) Existing approaches to refactoring use ad-hoc mechanisms to ensure the guarantees they try to provide. As of today, there exists no refactoring system for a practical programming language (such as Java, C, Python, SML or Haskell) that offers strong correctness guarantees (i.e., rigorous mathematical proofs showing that the refactoring /implementations/ are behavior-preserving).

Our Approach

We are investigating an alternative approach to refactoring, which we call "Program Metamorphosis". Our approach replaces the traditional atomic refactoring mechanism by a more fine-grained, gradual approach utilizing three components:

• fine-grained transformations that may or may not preserve behavior
• A "current program model" that captures an abstraction of the program behavior and is updated every time we transform the program
• A "desired program model" that captures an abstraction of the intended program behavior

Together, these three components allow us to construct traditional refactorings from smaller components: we can refactor by repeatedly applying transformations until we are satisfied with the result, and then "fix up" the resulting program by ensuring that the current and desired program models match. For example, let's say that we inlined a method body:

 class A { // TODO: Make this an interface
     private int count = 0;
 
     // TODO: Eliminate this method or push it down, we only use it
     // in subclass B
     protected int doCount() { return ++count; }
 
     ...
 }

 class B extends A {
     protected int count = C.getInitialCount();
 
     public void f()
     {
         ...
         int x = doCount(); // <- inline here
         ...
     }
 }

Now the inlined "doCount()" will refer to the wrong "count" variable, and this will cause a discrepancy between the current and the desired program model. We can now choose to resolve this in a number of ways (adding accessors to A, moving "count" from A to B whilst either of the count variables, changing the visibility of A's "count" while also renaming it...), and implement these changes by applying further transformations. The program metamorphosis system will carefully track these changes to ensure that behavior is indeed preserved and ultimately allow us to determine whether we have preserved program behavior (within certain limits).

However, we can use this approach for more than just re-building traditional refactorings. By exploiting the above mechanisms the implementation of refactorings, we can allow users to make strategic decisions about how program behavior should be restored, rather than leaving such decisions to a hard-coded refactoring heuristic-- we can even directly expose the transformations and program model for a maximum of flexibility.

This approach also allows us to "extend" or "mutate" program behaviour, by adjusting the /desired/ program model to match the current one, i.e., by changing the expectations that the PM system has of the final result.

Our Research

Following up on a first prototype, we are currently developing two PM systems:

• An Eclipse plugin that allows PM on Java programs. For this plugin, we have limited our behavioral guarantees in order to explore the expressive power we can provide.

• A language-agnostic PM system generator that can construct a PM system from a language specification. We expect to use this system for a "foundational" exploration of PM.

• Using our prototypes, we intend to measure whether and how PM can aid programmers in their every-day tasks.

• We are further investigating means by which the inherent guarantees offered by PM allow us to simplify formal reasoning about our transformations, to give the strongest possible correctness guarantees.

Further reading

Technical Report CU-CS-1036-07, "Program Metamorphosis", Christoph Reichenbach and Amer Diwan

Views

• Article
• Discussion
• Edit
• History