Geeky things and other research from a work in progress


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.

1 comment:

  1. Nice work! Reminds me of David F. Place's article "How to refold a map" from issue 11 of The Monad.Reader.