
\documentclass{scrreprt}
\usepackage{paralist}
\usepackage{graphicx}
\usepackage[final]{hcar}

%include polycode.fmt

\begin{document}

\begin{hcarentry}{ADPfusion}
\report{Christian H\"oner zu Siederdissen}
\status{usable, active development}
%\participants{(PARTICIPANTS OTHER THAN MYSELF)}% optional
\makeheader

ADPfusion combines ideas of Algebraic Dynamic Programming (ADP), established by
Robert Giegerich et al., and stream-fusion by Coutts et al. into a high-level
framework to optimize the run-time performance of algorithms based on
context-free grammars with a special emphasis on applications in computational
biology.

As with ADP, we aim for a separation of concerns. While an algorithm
implementing a, say, context-free grammar (CFG) typically leads to an
intertwining of several ``concerns'' (search space, evaluation, tabulation,
optimization of code), we want to separate them as much as possible to achieve
clarity of code while retaining an efficient implementation.

ADP separates the search space which contains all possible solutions from the
evaluation of each candidate. This idea allows for a very clear description of
an algorithm, to replace evaluation strategies, or even combine them.

Deforestation and stream-fusion are well-established ideas to improve the
performance of (low-level) list- and vector-based algorithms in Haskell.

ADPfusion combines both ideas, allowing for a high-level description of any
CFG, with performance coming close to that of optimized \texttt{C}. The library
can easily be adapted to handle special data structures, and will be extended
to allow for more general grammars than just CFG's, as well as table designs
with more than two dimensions.

A tutorial is in preparation, the library and two examples are available on
hackage.

\FurtherReading

\begin{itemize}
  \item \url{http://www.tbi.univie.ac.at/~choener/adpfusion}
  \item \url{http://hackage.haskell.org/package/ADPfusion}
  \item \url{http://hackage.haskell.org/package/Nussinov78}
  \item \url{http://hackage.haskell.org/package/RNAFold}
\end{itemize}

\end{hcarentry}

\end{document}
