10.1184/R1/6609395.v1 Umut A. Acar Umut A. Acar Guy E. Blelloch Guy E. Blelloch Matthias Blume Matthias Blume Robert Harper Robert Harper Self-Adjusting Programming Carnegie Mellon University 1994 computer sciences 1994-03-01 00:00:00 Journal contribution https://kilthub.cmu.edu/articles/journal_contribution/Self-Adjusting_Programming/6609395 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.