article · 2005
Staging Dynamic Programming Algorithms
Kedar N. Swadi, Walid Taha, Oleg Kiselyov
Cited by 1Abstract and details only
Abstract
Applications of dynamic programming (DP) algorithms are numerous, and include genetic engineering and operations research problems. At a high level, DP algorithms are specified as a system of recursive equations implemented using memoization. The recursive nature of these equations suggests that they can be written naturally in a functional language. However, the requirement for memoization poses a subtle challenge: memoization can be implemented using monads, but a systematic treatment introduces several layers of abstraction that can have a prohibitive runtime overhead. Inspired by other researchers' experience with automatic specialization (partial evaluation), this paper investigates the feasibility of explicitly staging DP algorithms in the functional setting. We find that the key challenge is code duplication (which is automatically handled by partial evaluators), and show that a key source of code duplication can be isolated and addressed once and for all. The result is a simple combinator library. We use this library to implement several standard DP algorithms including ones in standard algorithm textbooks (e.g.
Cite this paper
Swadi, K. N., Taha, W., & Kiselyov, O. (2005). Staging Dynamic Programming Algorithms.
Swadi, Kedar N., et al. “Staging Dynamic Programming Algorithms.” 2005.
Swadi, Kedar N., Walid Taha, and Oleg Kiselyov. 2005. “Staging Dynamic Programming Algorithms.”
Swadi, K.N., Taha, W. and Kiselyov, O. (2005) ‘Staging Dynamic Programming Algorithms’.
@article{swadi2005staging,
title = {{Staging Dynamic Programming Algorithms}},
author = {Swadi, Kedar N. and Taha, Walid and Kiselyov, Oleg},
year = {2005}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.