Verified Memoization and Dynamic Programming

Simon Wimmer, Huwei Shu, Tobias Nipkow

We present a lightweight framework in Isabelle/HOL for the automatic verified (functional or imperative) memoization of recursive functions. Our tool constructs a memoized version of the recursive function and proves a correspondence theorem between the two functions. A number of simple techniques allow us to achieve bottom-up computation and space-efficient memoization. The framework's utility is demonstrated on a number of classic dynamic programming problems.

pdf