Monadification, Memoization and Dynamic Programming

Title:	Monadification, Memoization and Dynamic Programming
Authors:	Simon Wimmer, Shuwei Hu (shuwei /dot/ hu /at/ tum /dot/ de) and Tobias Nipkow
Submission date:	2018-05-22
Abstract:	We present a lightweight framework for the automatic verified (functional or imperative) memoization of recursive functions. Our tool can turn a pure Isabelle/HOL function definition into a monadified version in a state monad or the Imperative HOL heap monad, and prove a correspondence theorem. We provide a variety of memory implementations for the two types of monads. 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 representative dynamic programming problems. A detailed description of our work can be found in the accompanying paper [2].
BibTeX:	@article{Monad_Memo_DP-AFP, author = {Simon Wimmer and Shuwei Hu and Tobias Nipkow}, title = {Monadification, Memoization and Dynamic Programming}, journal = {Archive of Formal Proofs}, month = may, year = 2018, note = {\url{http://isa-afp.org/entries/Monad_Memo_DP.html}, Formal proof development}, ISSN = {2150-914x}, }
License:	BSD License
Depends on:	Show
Used by:	Hidden_Markov_Models, Optimal_BST
Status: [ok]	This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.