The number of possible refactorings is unlimited, so no tool vendor will ever be able to provide custom refactorings for all specific user needs. Therefore, we propose a new kind of refactoring tools, which allow users to create, edit and and compose required refactorings just like any other documents. The heart of such a \emph{refactoring editor} is the ability to compose larger refactorings from existing ones. Computing the precondition of the composite refactoring from the preconditions of the composed refactorings is non-trivial since earlier transformations influence the truth of preconditions of later ones. The ability to calculate these effects without referring to a particular program to which the refactorings should be applied is called program-independent composition. It is the prerequisite for creating composite refactorings that are reusable on arbitrary programs. The main contribution of this paper is a formal model for automatic, program-independent composition of conditional program transformations. We show that conditional transformations, including refactorings, can be composed from a limited set of basic operations. Program-independent derivation of a precondition for the composite is based on the notion of ``transformation description'', which can be seen as a simplified, yet equally powerful, variant of Roberts' ``postconditions''. Our approach simplifies the implementation of refactoring tools -- only the basic operations and the ability for composition must be hard coded in a tool. As a proof of concept, we sketch a transformation framework that implements our approach (\jconditioner) and, based on the framework, an experimental refactoring tool (\contract) that includes the editing capabilities that motivated our work.
Date of submission: 17 June 2003
Date of notification: 03 October 2003
Date of 1st revision: 12 January 2004
Date of 2nd revision: 18 February 2004
Date of acceptance: 22 Februar 2004
Abstract:
We present algebraic laws for a language similar to a subset of sequential Java that includes inheritance, recursive classes, dynamic binding, access control, type tests and casts, assignment, but no sharing. These laws are proved sound with respect to a weakest precondition semantics. We also show that they are complete in the sense that they are su±cient to reduce an arbitrary program to a normal form substantially close to an imperative program; the remaining object-oriented constructs could be further eliminated if our language had recursive records. This suggests that our laws are expressive enough to formally derive behaviour preserving program transformations; we illustrate that through the derivation of provably- correct refactorings.
Date of submission: 01 April 2003
Date of notification: 20 September 2003
Date of revision: 20 January 2004
Date of acceptance: 23 January 2004
The structure of monadic functional programs allows the integration of many different features by just changing the definition of the monad and not the rest of the program, which is a desirable feature from a software engineering and software maintenance point of view. We describe an algorithm for the automatic transformation of a group of functions into such a monadic form. We identify two correctness criteria and argue that the proposed transformation is at least correct in the sense that transformed programs yield the results as the original programs modulo monad constructors. The translation of a set of functions into monadic form is in most cases only a first step toward an extension of a program by new features. The extended behavior can be realized by choosing an appropriate monad type and by inserting monadic actions into the functions that have been transformed into monadic form. We demonstrate an approach to the integration of monadic actions that is based on the idea of specifying context-dependent rewritings.
Date of submission: 31 May 2003
Date of notification: 4 September 2003
Date of 1st revision: 08 November 2003
Date of 2nd revision: 06 February 2004
Date of acceptance: 15 February 2004
Transformations of object-oriented methods are a prevalent object-oriented programming technique, but in many languages they are not supported at runtime. Therefore it can be hard to apply method transformations for incremental or experimental software evolution, or other problems that require runtime software behavior adaptation. The goal of the work presented in this paper is to provide a better conceptual and technical support for runtime method transformations. A non-intrusive model for method transformations and a set of runtime method transformation primitives are presented. We also present a pattern language for implementing dynamic method abstractions and combining them with languages that do not support dynamic methods natively. As a case study we introduce a runtime transformation framework for the dynamic configuration and composition language Frag, its connection to Java, and an end user programming example.
Date of submission: 01 April 2003
Date of notification: 17 August 2003
Date of 1st revision: 26 October 2003
Date of 2nd revision: 22 January 2004
Date of acceptance: 22 January 2004
The \emph{distributed data problem} is characterized by the desire to bring together semantically related data from syntactically unrelated portions of a term. A strategic combinator called \emph{transient} and a strategic constant called \emph{skip} is introduced in the context of a higher-order strategic framework. The notion of traversal is lifted to the higher-order as well. The resulting framework allows the manipulation of data to be expressed directly in strategic terms. The impact of this dynamic approach to strategy creation is then explored on several instances of the distributed data problem. Problems considered include three strategic benchmarks as well as two transformations that arise within a class loader for the Java Virtual Machine.
Date of submission: 05 May 2003
Date of notification: 04 August 2003
Date of 1st revision: 12 October 2003
Date of 2nd revision: 19 January 2004
Date of acceptance: 23 January 2004
Software reengineering has been described as being ``about as easy as reconstructing a pig from a sausage''. But the development of program transformation theory, as embodied in the FermaT transformation system, has made this miraculous feat into a practical possibility. This paper describes the theory behind the FermaT system and describes a recent migration project in which over 544,000 lines of assembler ``sausage'' (part of a large embedded system) were transformed into efficient and maintainable structured C code.
Date of submission: 15 April 2003
Date of notification: 28 June 2003
Date of 1st revision: 30 October 2003
Date of 2nd revision: 13 January 2004
Date of acceptance: 23 January 2004
This paper presents a general approach to automatically validate code-improving transformations on low-level program representations. The approach ensures the correctness of compiler and hand-specified optimizations at the machine instruction level. The method verifies the semantic equivalence of the program representation before and after a transformation to determine the validity of the transformation. To verify that the transformation is semantics preserving, the method derives semantic e ects from the instructions that span the execution paths a ected by the transformation. The semantics are preserved if the normalized semantic e ects are unchanged. A validating compilation system was implemented that is able to validate traditional compiler transformations and more powerful transformations that modify the branch structure of a program.
Date of submission: 27 March 2004
Date of notification: 07 August 2003
Date of revision: 06 November 2003
Date of acceptance: 23 December 2004
In a typed language such as Java, inlining of virtual methods does not always preserve typability. The best known solution to this problem is to insert type casts, which may hurt performance. This paper presents a solution that never hurts performance. The solution is based on a transformation that modi es static type annotations and changes some virtual calls into static calls, which can then be safely inlined. The transformation is parameterised by a ow analysis, and for any analysis that satis es certain conditions, the transformation is correct and idempotent. The paper presents the transformation, the conditions on the ow analysis, and proves the correctness properties in the context of a variant of Featherweight Java.
Date of submission: 02 April 2003
Date of notification: 29 July 2003
Date of revision: 09 October 2003
Date of acceptance: 24 January 2004
A program may be transformed by specialising an interpreter for the language in which it is written. Efficiency of the transformed program is determined by the efficiency of the interpreter's dynamic operations; the efficiency of its static operations is irrelevant, since all will be ``specialised away''. This approach is automatic (as automatic as the specialiser is); general, in that it applies to all of the interpreter's input programs; and flexible, in that a wide range of program transformations are achievable since the transformed program inherits the style of the interpreter.
The chief practical challenge is understanding cause and effect: How should one write the interpreter so that specialisation produces efficient transformed programs? The core of this paper is a series of examples, both positive and negative, showing how the way the interpreter is written can influence the removal of interpretational overhead, and thus the efficiency and size of the target programs obtained by specialisation.
In principle this method can speed up source programs by an arbitrary amount; the limit depends only on how efficiently the interpreter can be written. An example shows that a ``memoising'' interpreter can yield asymptotic speedup, transforming an exponential-time program into one running in polynomial time. A final analysis is made of the speed of the output programs in relation to the speed of the interpreter from which they are derived. It is argued that this relative speedup is linear, with a constant coefficient depending on the program being transformed.
Date of submission: 27 April 2003
Date of notification: 04 August 2003
Date of revision: 30 October 2003
Date of acceptance: 23 January 2004
Specialization is an automatic approach to customizing a program with respect to configuration values. In this paper, we present a survey of Tempo, a specializer for the C language. Tempo offers specialization at both compile time and run time, and both program and data specialization. To control the specialization process, Tempo provides the program developer with a declarative language to describe specialization opportunities for a given program.
The functionalities and features of Tempo have been driven by the needs of practical applications. Tempo has been successfully applied to a variety of realistic programs in areas such as operating systems and networking. We give an overview of the design of Tempo and of its use in specializing realistic applications.
Date of submission: 16 April 2003
Date of notification: 28 July 2003
Date of revision: 07 November 2003
Date of acceptance: 22 January 2004