  This paper presents a semantics of self-adjusting computation and proves that
the semantics are correct and consistent. The semantics integrate change
propagation with the classic idea of memoization to enable reuse of
computations under mutation to memory. During evaluation, reuse of a
computation via memoization triggers a change propagation that adjusts the
reused computation to reflect the mutated memory. Since the semantics integrate
memoization and change-propagation, it involves both non-determinism (due to
memoization) and mutation (due to change propagation). Our consistency theorem
states that the non-determinism is not harmful: any two evaluations of the same
program starting at the same state yield the same result. Our correctness
theorem states that mutation is not harmful: self-adjusting programs are
consistent with purely functional programming. We formalize the semantics and
their meta-theory in the LF logical framework and machine check our proofs
using Twelf.
