Self-Adjusting Computation
Dr. Robert Harper
Date:
Time:
Location: 367 Votey
Abstract
A static algorithm is one that computes the result of a query about the output for a single, fixed input. For example, a static sorting algorithm is one that takes as input a set of keys, and permits queries about the relative order of these keys according to some ordering relation. A dynamic, or incremental, algorithm is one that permits queries about the output to be interleaved with operations that incrementally modify the input. For example, a dynamic sorting algorithm is one that would permit insertion or deletion of keys to be interleaved with queries about their relative ordering. Self-adjusting computation is a method for deriving a dynamic algorithm from a static algorithm by applying three main techniques: adaptivity, which permits the output of an algorithm to be adjusted to reflect changes to its input; selective memoization, which permits re-use of results based on accurate control flow information rather than simple call patterns; and adaptive memoization, which permits re-use of incorrect computations by adaptation. These techniques are realized as linguistic mechanisms in a statically typed functional language whose type system guarantees that the effects of an input modification are correctly propagated to their outputs, thereby ensuring that the dynamic algorithm is correct relative to its static counterpart. Using these methods we obtain dynamic versions of several well-known algorithms, including a dynamic version of Quicksort that adapts to insertions and deletions in expected logarithmic time.
This is joint work with Umut A. Acar and Guy E. Blelloch.
(Hosted by Computer Science Student Association)