Draft: "Type-Changing Program Improvement with Type and Transform Systems"

Johan Jeuring, Andres Löh,and I have submitted a paper to ICFP 2011.

Type-Changing Program Improvement with Type and Transform Systems

Structured program improvement is monotonous and error-prone and should be automated whenever possible. Typical approaches such as refactoring are too restrictive, allowing for only minimal changes to types in the program. Other improvement techniques that allow type changes are few and somewhat limited.

We are interested in type-driven program transformations that spread virally throughout code, infecting both function definitions and applications. Such transformations are beneficial for software evolution or migrating a program to a new library interface. An example transformation is the optimization of list-based strings to Hughes' lists, a transformation that can potentially infect every string in a program.

We present type and transform systems, an approach to type-safe, automatic program improvement in which complex transformations can be expressed by simple inference rules that define a relation between source and target programs. In this paper, we describe the relations, their properties, how to design transformations, and a prototype implementation. We also demonstrate automatic string optimization, which, to the best of our knowledge, has not been shown before.

The prototype code is also available for a test drive.