A semantics-preserving transformation by Komondoor and Horwitz has been shown to be most effective in the elimination of type-3 clones. The two original algorithms for realizing this transformation, however, are not as efficient as the related (slice-based) transformations. We present an asymptotically-faster algorithm that implements the same transformation via bidirectional reachability on a program dependence graph, and we prove its equivalence to the original formulation.

Program slicing is a useful technique in tools for program understanding and transformation. Computing correct and accurate slices for unstructured programs is particularly difficult. We present a new family of slicing algorithms that are proved correct and are more accurate than the best previous algorithms. An empirical study shows significant improvements of our algorithms on real code.

This short paper is a summary of my doctoral research, which was conducted under Oege de Moor's supervision at the University of Oxford, starting October 2001. The thesis was submitted on September 29, 2006, and defended on January 18, 2007. The final version was submitted, after minor corrections, on June 15, 2007.

Refactorings are behaviour-preserving program transformations, typically for improving the structure of existing code. A few of these transformations have been mechanised in interactive development environments. Many more refactorings have been proposed, and it would be desirable for programmers to script their own refactorings. Implementing such source-to-source transformations, however, is quite complex: even the most sophisticated development environments contain significant bugs in their refactoring tools.We present a domain-specific language for refactoring, named JunGL. It manipulates a graph representation of the program: all information about the program, including ASTs for its compilation units, variable binding, control flow and so on is represented in a uniform graph format. The language is a hybrid of a functional language (in the style of ML) and a logic query language (akin to Datalog). JunGL furthermore has a notion of demand-driven evaluation for constructing computed information in the graph, such as control flow edges. Borrowing from earlier work on the specification of compiler optimisations, JunGL uses so-called `path queries' to express dataflow properties.We motivate the design of JunGL via a number of non-trivial refactorings, and describe its implementation on the.NET platform.