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 number of applications including several sorting algorithms, and the Graham Scan, and the quick hull algorithm for computing convex hulls. We show that the techniques are flexible by showing that self-adjusting programs can be trivially transformed into a kinetic programs that maintain their property 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 magnitude faster than recomputing from scratch. These results rely on a combination of memoization and dynamic dependence graphs. We show that the combination is sound by presenting a semantics based on abstraction of memoization via an oracle.