Published In Self-Adjusting Programming

This papers proposes techniques for writing self-adjusting programs that can adjust to any change to their data (e.g., inputs, decisions made during the computation) etc. We show that the techniques are efficient by considering a num-ber of applications including several sorting algorithms, and the Graham Scan, and the quick hull algorithm for comput-ing convex hulls. We show that the techniques are flexible by showing that self-adjusting programs can be trivially trans-formed into a kinetic programs that maintain their prop-erty as their input move continuously. We show that the techniques are practical by implementing a Standard ML library for kinetic data structures and applying the library to kinetic convex hulls. We show that the kinetic programs written with the library are more than an order of magni-tude faster than recomputing from scratch. These results rely on a combination of memoization and dynamic depen-dence graphs. We show that the combination is sound by presenting a semantics based on abstraction of memoization via an oracle.