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.



Fri Dec 19 10:54:56 CET 2014