Skip to main content.

Bellman's GAP

Bellman's GAP is a system for Dynamic Programming (DP) over sequence input. It consists of a Domain Specific Language (GAP-L) and a compiler (GAP-C). GAP-L allows to specify DP algorithms on a high level using declarative constructs and its syntax is Java-like. The compiler generates optimized C++-code for efficiency. The Bellman's GAP Café site contains many interactive examples, a rich bibliography and the compiler for download. GAP-C is open source and it is also available binary packaged for majour linux distributions.

ADP Combinators

ADP Combinators are parser combinators for implementing Algebraic Dynamic Programming as embedded Domain Specific Language (eDSL) in Haskell. I maintain a version controlled repository that includes all the variants of the combinators (we used at our working group).

It also includes several examples of well known dynamic programming algorithms over sequences implemented using these combinators (e.g. various edit distance and RNA secondary structure predictions examples).

These combinators were developed around 1998 and extended up to 2004. They are not optimized for performance, but for educational purposes. They fit well into a lecture session on dynamic programming after the basics of the theory of Algebraic Dynamic Programming (ADP) are established.