ML 05 START ConferenceManager    

A Library for Self-Adjusting Computation

Umut A. Acar, Guy Blelloch, Matthias Blume, Robert Harper, Kanat Tangwongsan

The 2005 ACM SIGPLAN Workshop on ML (ML 05)
Tallinn, Estonia, September 29, 2005


Abstract

We present a Standard ML library for writing programs that automatically adjust to changes to their data. The library combines dynamic dependence graphs and memoization to achieve efficient updates. We describe an implementation of the library and apply it to the problem of maintaining the convex hull of a dynamically changing set of points. Our experiments show that the overhead of the library is no more than a factor of 7, and average speedups can be more than two orders magnitude. The implementation relies on invariants that could be enforced by a modal type system. We show, using an existing language, an abstract interface to computations that ensures the same safety properties without the use of modal types.


  
START Conference Manager (V2.49.7)
Maintainer: rrgerber@softconf.com