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.

Final: "Push-Ups, Push-Downs, and Passing It Around: Exercises in Functional Incrementalization"

We have put up the final copy of our IFL 2009 paper. Here are the PDF and source code.

Abstract Programs in languages such as Haskell are often datatype-centric and make extensive use of folds on that datatype. Incrementalization of such a program can significantly improve its performance by transforming monolithic atomic folds into incremental computations. Functional incrementalization separates the recursion from the application of the algebra in order to reduce redundant computations and reuse intermediate results. In this paper, we motivate incrementalization with a simple example and present a library for transforming programs using upwards, downwards, and circular incrementalization. Our benchmarks show that incrementalized computations using the library are nearly as fast as handwritten atomic functions.

The focus is quite a bit different from the draft submission. We concentrate more on describing how to specify incrementalized computations. We also compare the performance of handwritten atomic functions, specifications written with folds, and incrementalized functions. We found that incrementalization had a relatively small impact on an atomic function's performance. If you have the right needs, of course, the impact on your program time can be profound.

Draft: "Pull-Ups, Push-Downs, and Passing It Around: Exercises in Functional Incrementalization"

Update! The final version is now available.

Andres Löh, Johan Jeuring, and I have submitted a paper to IFL 2009.

Pull-Ups, Push-Downs, and Passing It Around: Exercises in Functional Incrementalization

Abstract Programs in functional programming languages with algebraic datatypes are often datatype-centric and use folds or fold-like functions. Incrementalization of such a program can significantly improve its performance. Functional incrementalization separates the recursion from the calculation and significantly reduces redundant computation. In this paper, we motivate incrementalization with a simple example and present a library for transforming programs using upwards, downwards, and circular incrementalization. We also give a datatype-generic implementation for the library and demonstrate the incremental zipper, a zipper extended with attributes.

This is the result of work that has previously been mentioned on this blog:

1. Smart constructors
2. Incremental fold, a design pattern
3. Incremental attributes
4. Latest on the incremental fold and attributes
5. "Upwards and downwards accumulations on trees" translated into Haskell

We would be happy to have any feedback.

Update! Here's the (completely messy, badly formatted, undocumented, and screwy) code used in the paper if you want to have a go at it.