Implementing algebraic dynamic programming in the functional and the imperative programming paradigm

Giegerich R, Steffen P. Implementing algebraic dynamic programming in the functional and the imperative programming paradigm. In: Boiten E, ed. MATHEMATICS OF PROGRAM CONSTRUCTION. Lecture Notes in Computer Science. Vol 2386. Berlin ; Heidelberg ; New York ; Barcelona ; Hong Kong ; London ; Milan ; Paris ; Tokyo: SPRINGER-VERLAG BERLIN; 2002: 1-20.Algebraic dynamic programming is. a new method for developing and reasoning about dynamic programming algorithms. In this approach, so-called yield grammars and evaluation algebras constitute abstract specifications of dynamic programming algorithms. We describe how this theory is put to practice by providing a specification language that can both be embedded in a lazy functional language, and translated into an imperative language. Parts of the analysis required for the latter translation also gives rise to source-to-source transformations that improve the asymptotic efficiency of the functional implementation. The multi-paradigm. system resulting from this approach provides increased programming productivity and effective validation