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.