Practical And Generic Incrementalization
Stc
Date: 2009-09-17
Time: 11:45
Room: BBL room 471
Speaker: Sean Leather
Title: Practical and Generic Incrementalization
Joint work with Andres Löh and Johan JeuringAbstract
Datatype-centric libraries are popular in purely functional programming languages. Such libraries can be transformed with datatype-generic incrementalization, a process of changing traditionally atomic computations into incremental ones. Incrementalization can improve the efficiency of operations in which the input changes in small ways relative to the entire computation. In this talk, we attempt to provide an intuition for the process of incrementalization as well as how it can be useful to a generic programming library. We transform a typical datatype-centric library,Set, which uses a binary search tree, through several different forms of incrementalization. We then take a generic zipper and demonstrate how to incrementalize it. The second approach complements the first by exploring the transformations to the structure of a datatype-generic library. By the end of the talk, the participant should have a good idea how to incrementalize any datatype-centric library, whether generic or not.