The ADPfusion package

[Tags: bsd3, library]

ADPfusion combines stream-fusion (using the stream interface provided by the vector library) and type-level programming to provide highly efficient dynamic programming combinators.

From the programmers' viewpoint, ADPfusion behaves very much like the original ADP implementation http://bibiserv.techfak.uni-bielefeld.de/adp/ developed by Robert Giegerich and colleagues, though both combinator semantics and backtracking are different.

The library internals, however, are designed not only to speed up ADP by a large margin (which this library does), but also to provide further runtime improvements by allowing the programmer to switch over to other kinds of data structures with better time and space behaviour. Most importantly, dynamic programming tables can be strict, removing indirections present in lazy, boxed tables.

As an example, even rather complex ADP code tends to be completely optimized to loops that use only unboxed variables (Int and others).

Completely novel (compared to ADP), is the idea of allowing efficient monadic combinators. This facilitates writing code that performs backtracking, or samples structures stochastically, among others things.

This version is still highly experimental and makes use of multiple recent improvements in GHC. This is particularly true for the monadic interface.

Long term goals: Outer indices with more than two dimensions, specialized table design, a combinator library, a library for computational biology.

If possible, build using the GHC llvm backend, and GHC-7.2.2. GHC-7.4.x produces very bad code on my system, please benchmark using 7.2.2.

Two algorithms from the realm of computational biology are provided as examples on how to write dynamic programming algorithms using this library: http://hackage.haskell.org/package/Nussinov78 and http://hackage.haskell.org/package/RNAfold.


[Skip to ReadMe]

Properties

Versions0.0.1.0, 0.0.1.1, 0.0.1.2, 0.1.0.0, 0.2.0.0, 0.2.0.1, 0.2.0.2, 0.2.0.3, 0.2.0.4, 0.2.1.0, 0.4.0.0, 0.4.0.1, 0.4.0.2, 0.4.1.0, 0.4.1.1 (info)
Change logNone available
Dependenciesbase (==4.*), primitive (==0.4.*), PrimitiveArray (==0.2.1.1), vector (==0.9.*) [details]
LicenseBSD3
CopyrightChristian Hoener zu Siederdissen, 2011-2012
AuthorChristian Hoener zu Siederdissen, 2011-2012
Maintainerchoener@tbi.univie.ac.at
Stabilityexperimental
CategoryAlgorithms, Data Structures, Bioinformatics
Home pagehttp://www.tbi.univie.ac.at/~choener/adpfusion
Source repositoryhead: git clone git://github.com/choener/ADPfusion
UploadedSun Mar 25 01:35:30 UTC 2012 by ChristianHoener
DistributionsNixOS:0.4.1.1
Downloads2981 total (184 in last 30 days)
Votes
0 []
StatusDocs uploaded by user
Build status unknown [no reports yet]

Modules

[Index]

Flags

NameDescriptionDefault
llvmbuild using llvm backendEnabled

Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info

Downloads

Maintainers' corner

For package maintainers and hackage trustees

Readme for ADPfusion-0.0.1.0

ADPfusion (c) 2012, Christian Hoener zu Siederdissen University of Vienna, Vienna, Austria choener@tbi.univie.ac.at LICENSE: BSD3

Introduction

ADPfusion combines stream-fusion (using the stream interface provided by the vector library) and type-level programming to provide highly efficient dynamic programming combinators.

From the programmers' viewpoint, ADPfusion behaves very much like the original ADP implementation http://bibiserv.techfak.uni-bielefeld.de/adp/ developed by Robert Giegerich and colleagues, though both combinator semantics and backtracking are different.

The library internals, however, are designed not only to speed up ADP by a large margin (which this library does), but also to provide further runtime improvements by allowing the programmer to switch over to other kinds of data structures with better time and space behaviour. Most importantly, dynamic programming tables can be strict, removing indirections present in lazy, boxed tables.

As an example, even rather complex ADP code tends to be completely optimized to loops that use only unboxed variables (Int# and others, indexIntArray# and others).

Completely novel (compared to ADP), is the idea of allowing efficient monadic combinators. This facilitates writing code that performs backtracking, or samples structures stochastically, among others things.

This version is still highly experimental and makes use of multiple recent improvements in GHC. This is particularly true for the monadic interface.

Long term goals: Outer indices with more than two dimensions, specialized table design, a combinator library, a library for computational biology.

If possible, build using the GHC llvm backend, and GHC-7.2.2. GHC-7.4.x produces very bad code on my system, please benchmark using 7.2.2.

Two algorithms from the realm of computational biology are provided as examples on how to write dynamic programming algorithms using this library: http://hackage.haskell.org/package/Nussinov78 and http://hackage.haskell.org/package/RNAfold.

Installation

Please use GHC-7.2.2, if possible. GHC-7.4 currently seems to have problems optimizing vector-dependent code: http://hackage.haskell.org/trac/ghc/ticket/5539 (and others?)

If GHC-7.2.2, LLVM and cabal-install are available, you should be all set. I recommend using cabal-dev as it provides a very nice sandbox (replace cabal-dev with cabal otherwise).

If you go with cabal-dev, no explicit installation is necessary and ADPfusion will be installed in the sandbox together with the example algorithms or your own.

For a more global installation, "cabal install ADPfusion" should do the trick.

To run the Quickcheck tests, do an additional "cabal-dev install QuickCheck", then "cabal-dev ghci", ":l ADP/Fusion/QuickCheck.hs", and "allProps". Loading the quickcheck module should take a bit due to compilation. "allProps" tests all properties and should yield no errors.

Notes

If you have problems, find bugs, or want to use this library to write your own DP algorithms, please send me a mail. I'm very interested in hearing what is missing.

One of the things I'll be integrating is an extension to higher dimensions (more than two).

Right now, I am not quite happy with the construction and destruction of the "Box" representations. These will change soon. In addition, an analysis of the actual combinators should remove the need for nested applications of objective functions in many cases.

VERSION HISTORY