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.

Call for Papers: IFL 2010

I'm involved with planning IFL 2010, the 22nd Symposium on Implementation and Applications of Functional Languages, held in Alphen aan den Rijn in the Netherlands. Of course, I think you should consider submitting something to the conference. Note that submissions are reviewed after the symposium for the proceedings, so it's easy to use the venue as a way to refine incomplete/unfinished products. The call for papers follows.

---

22nd Symposium on Implementation and Applications of Functional Languages (IFL 2010)
September 1-3, 2010
Utrecht University
Alphen aan den Rijn, The Netherlands
http://www.cs.uu.nl/wiki/IFL2010

After a first successful visit to the USA, the Symposium on Implementation and Applications of Functional Languages returns to Europe for its 22nd edition. The hosting institution is Utrecht University in the Netherlands, although the conference itself will take place in the ornithological theme park Avifauna in Alphen aan den Rijn, situated conveniently close to Schiphol (Amsterdam Airport). The symposium dates are September 1-3, 2010.

The goal of the IFL symposia is to bring together researchers actively engaged in the implementation and application of functional and function-based programming languages. IFL 2010 will be a venue for researchers to present and discuss new ideas and concepts, work in progress, and publication-ripe results related to the implementation and application of functional languages and function-based programming.

Following the IFL tradition, IFL 2010 will use a post-symposium review process to produce formal proceedings which will be published by Springer Verlag in the Lecture Notes in Computer Science series. All participants in IFL 2010 are invited to submit either a draft paper or an extended abstract describing work to be presented at the symposium. At no time may work submitted to IFL be simultaneously submitted to other venues. Here we follow the ACM Sigplan republication policy. The submissions will be screened by the program committee chair to make sure they are within the scope of IFL, and will appear in the draft proceedings distributed at the symposium. Submissions appearing in the draft proceedings are not peer-reviewed publications. After the symposium, authors will be given the opportunity to incorporate the feedback from discussions at the symposium and will be invited to submit a revised full article for the formal review process. These revised submissions will be reviewed by the program committee using prevailing academic standards to select the best articles, which will appear in the formal proceedings.

INVITED SPEAKER

Johan Nordlander of Lulea University, the designer and developer of the Timber language, is the invited speaker at IFL 2010. Timber is a functional programming language that draws some of its concepts from object-oriented programming, and has built-in facilities for concurrent execution. The language is specifically targeted at implementing real-time embedded systems.

TOPICS

IFL welcomes submissions describing practical and theoretical work as well as submissions describing applications and tools. If you are not sure that your work is appropriate for IFL 2010, please contact the PC chair at jur@cs.uu.nl. Topics of interest include, but are not limited to:

• language concepts
• type checking
• contracts
• compilation techniques
• staged compilation
• runtime function specialization
• runtime code generation
• partial evaluation
• (abstract) interpretation
• generic programming techniques
• automatic program generation
• array processing
• concurrent/parallel programming
• concurrent/parallel program execution
• functional programming and embedded systems
• functional programming and web applications
• functional programming and security
• novel memory management techniques
• runtime profiling and performance measurements
• debugging and tracing
• virtual/abstract machine architectures
• validation and verification of functional programs
• tools and programming techniques
• industrial applications of functional programming

PAPER SUBMISSIONS

Prospective authors are encouraged to submit papers or extended abstracts to be published in the draft proceedings and to present them at the symposium. All contributions must be written in English, conform to the Springer-Verlag LNCS series format and not exceed 16 pages. The draft proceedings will appear as a technical report of the Department of Computer Science of Utrecht University.

PETER LANDIN PRIZE

The Peter Landin Prize is awarded to the best paper presented at the symposium every year. The honored article is selected by the program committee based on the submissions received for the formal review process. The prize carries a cash award equivalent to 150 Euros.

IMPORTANT DATES

Draft proceedings submission deadline	July 25, 2010
Registration deadline	August 1, 2010
IFL 2010 Symposium	September 1-3, 2010
Submission for review process deadline	October 25, 2010
Notification Accept/Reject	December 22, 2010
Camera ready version	February 17, 2011

PROGRAM COMMITTEE

Jost Berthold	University of Copenhagen (DIKU), Denmark
Olaf Chitil	University of Kent, UK
John Clements	California Polytechnic State University, USA
Matthew Fluet	Rochester Institute of Technology, USA
Andy Gill	Kansas University, USA
Jurriaan Hage (Chair)	University of Utrecht, Netherlands
Bastiaan Heeren	Open University, Netherlands
Ralf Hinze	University of Oxford, UK
John Hughes	Chalmers University of Technology, Sweden
Yukiyoshi Kameyama	University of Tsukuba, Japan
Gabriele Keller	University of New South Wales, Australia
Pieter Koopman	Radboud University Nijmegen, Netherlands
Luc Maranget	INRIA, France
Simon Marlow	Microsoft Research, UK
Marco T. Morazan	Seton Hall University, USA
Rex Page	University of Oklahoma, USA
Ricardo Pena	Universidad Complutense de Madrid, Spain
Sven-Bodo Scholz	University of Hertfordshire, UK
Tom Schrijvers	Catholic University of Leuven, Belgium
Don Stewart	Galois, USA
Wouter Swierstra	Vector Fabrics, Netherlands
Don Syme	Microsoft, UK
Peter Thiemann	University of Freiburg, Germany
Phil Trinder	Heriott-Watt University, Scotland
Janis Voigtlaender	University of Bonn, Germany
Viktoria Zsok	Eotvos Lorand University, Hungary

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.

"Extensibility and type safety in formatting: the design of xformat" at the Dutch HUG

I'm finally getting around to posting the slides for my talk at the Dutch HUG on 11 September. After that, I was preparing my talk for IFL on incrementalization of datatype-centric programs. I arrived back in Utrecht yesterday morning and crashed mid-day.

You can find the slides on Scribd and on Github. Enjoy!

Update: Thanks to Tom Lokhorst, my talk is also on video.

"Upwards and downwards accumulations on trees" translated into Haskell

I was reading "Upwards and downwards accumulations on trees" by Jeremy Gibbons, and it's written in the Bird-Meertens formalism (a.k.a. Squiggol) of yesteryear. Not that I have anything against people who can write and understand this stuff (in fact, I have a lot of respect for them), but for me, the inconsistent and seemingly arbitrary notation leaves something to be desired. In an attempt to understand what was actually being done, I translated most of the equations to Haskell code. If you plan on reading this paper, here's hoping I could jump-start your comprehension with this contribution.

The only real issue that I ran into while performing this translation is in the function s_fork_sl2. The second component of the catamorphism, ((⊙ ↟ ≪) ∘ ≪²), does not have the expected type (b, b) -> a -> (b, b) -> (b, b). After attempting to puzzle through how to unify the two, I eventually gave up and just came up with a function that seemed to do what I thought it should do, pairs g (x, _) _ (y, _) = (g x y, x) where g :: b -> b -> b is ⊙. But I'm not sure whether there's a bug in the definition in the paper or the one in my code. The code seems to work for a few tests. If you've already read this paper or you're at all interested in debugging Squiggol, I would be happy to learn how this works.

Sharing on Google Reader

I share things regularly on Google Reader. They tend to be eclectic but sometimes technical and sometimes PLT- or Haskell-related. I would like to find out who else uses Reader. If you're interested in letting me and other people know about your own shared items, please post the link in the comments. We can perhaps create a cozy little Reader community.