Geeky things and other research from a work in progress

2010-03-12

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.

2009-11-05

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.

2009-09-30

"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.

2009-09-09

"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.

2009-08-06

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.

2009-07-10

Fun and generic things to do with EMGM at the London HUG

I just gave a talk about EMGM at the London HUG. The slides can be found on Scribd or on Github.

Thanks to everybody who showed up! I'm very sorry I was so late. Thanks to Neil for filling in until I got there.

2009-06-23

RFC: Extensible, typed scanf- and printf-like functions for Haskell

I recently found myself inspired (and simultaneously frustrated as it usually happens), and I felt there was something truly missing from the collection of available code for Haskell. So, I sought to do something about it. Now, I would like some feedback on that work. But first, the story...

The inspiration came from none other than Oleg Kiselyov. Not too long ago, he sent out an email responding to some comments about a printf with Template Haskell. His safe and generic printf with C-like format string led me to think it would be nice if we had a safe and generic printf and scanf library. So I thought I could do that. I could take Oleg's code and polish it up and publish it.

I did take his code and play around with it for a while. In fact, what I did sits at its current state in Format.hs and FormatTest.hs. It was fun to play around in that area. I created a bunch of different descriptors for a wide variety of formats. And being the researcher of generic programming that I am, I wanted to make it generic. I wanted users to be able to add their own formats. As I got to thinking about it, I realized that this string format approach doesn't scale. There are only so many characters in the alphabet for one thing. And if I wanted to add alignment and spacing for some descriptors, then I need to create parsers for those. This is too much work for users to do for an extension, too.

The frustration then came. How do I improve on this? How do I make it more extensible? So I researched. With Google, of course. Eventually, I came upon Ralf Hinze's function pearl on "Formatting: a class act." That looked good. It's a type-indexed function that provides a safe way to extend for new types using a multiparameter type class with functional dependencies.

More playing with code ensued. I tried the approach using associated type synonyms because I like how they look (superficial, I suppose). Everything worked well enough, but occasionally I would run into a problem and have trouble debugging it. I eventually came to realize that a lot of those problems were due to the lack of visibility in the types. The type family approach hid the types behind unresolved synonyms. Since I couldn't see the final type, I was having trouble figuring out what I should do with the result. I learned that changing my class to use a functional dependency allowed me to see the resolved type. This helped me quite a bit. I still like how associated type synonym looked, but I gained a new appreciation for functional dependencies.

After working on showf, the printf-like function, for a while, I tried my had at a scanf-like function. At first, I tried to make it too much like showf without success. I wanted a variable-sized result for readf in the same way that showf had a variable number of arguments. In fact, that might still be possible. But for now, the input format descriptor directly determines the output's structure.

So, in the end, I came out with xformat. It has one module for showf and one for readf. It also has quite a few format descriptors. To give you an idea of what you can do, let me share a few examples.

Using the Text.XFormat.Show module:


module S where
import Text.XFormat.Show

s1 :: Int -> String
s1 = showf Int

-- Variable number of arguments mixed with constants
s2 :: String
s2 = showf ("Hello, " % String % Char) "World" '!'

-- Use tuples to group a format descriptor
s3 = showf ("The Answer is ", Int, ".") 42

-- Align right in a column width of 37.
s4 = showf (Align R 37 "Hello darkness, my old friend.")

Using the Text.XFormat.Read module:


{-# LANGUAGE TypeOperators #-}
module R where
import Text.XFormat.Read

r1 :: String -> Maybe Int
r1 = readf Int

-- Variable size format and output
r2 :: Maybe (String :%: (String :%: Char))
r2 = readf ("Hello, " % String % Char) "Hello, World!"

-- Use tuples to group a format descriptor
r3 = let Just (_, ans, _) = readf ("The Answer is ", Int, ".") "The Answer is 42."
     in ans

-- Extract the value in parentheses
r4 = readf (Wrap '(' Int ')') "(37)"

Now, finally to my request. I'd like some feedback on this library. Is the basic design reasonable? Can it be improved either aesthetically, performance-wise, or usability-wise? Any other comments on it? I'd like to go through some community improvement before committing it to Hackage.

I greatly appreciate any thoughts you might have.

Update: Soon after I posted this, I realized it didn't make much sense to ask for feedback when it's rather difficult to get access to the library. Thus, you may now find the package on the xformat Hackage page.