description
Algebraic dynamic programming (ADP) is a style of dynamic
programming that gives rise to a systematic approach to the
development of DP algorithms. It allows one to design, reflect upon,
tune and even test DP algorithms on a more abstract level than the
recurrences that used to be all that was available to deal with
dynamic programming algorithms.
ADP comes with a library for the functional programming language
Haskell, such that an algorithm written in ADP notation can be
directly executed by a Haskell interpreter (such as Hugs), or
compiled by a Haskell compiler (such as GHC). Although this is very
convenient during the development phase of new ADP algorithms, this
approach is problematic in practice. The data volumes in most dynamic
programming application domains (such as bioinformatics) tend to be
very large, and time- and space-efficiency of the algorithms is
critical. Here the high-level implementation in Haskell comes to its
limits.
The ADP implementation project aims at the development of a compiler
suite, which compiles ADP programs into C code. This compiler can
concentrate on the specific properties of ADP programs and can
therefore perform a lot more optimizations than a general Haskell
compiler could.
The planned compiler suite will include tools like a source-to-source
optimization, the generation of dynamic programming recurrences
typeset in LaTeX, and automatic design of the dynamic programming
tables.
This plan considerably exceeds our available manpower, and we are
currently seeking funding for this project.
people
start
2001
|
