Hackage :: [Package]

ADPfusion: Efficient, high-level dynamic programming.

[ algorithms, bioinformatics, bsd3, data-structures, formal-languages, library ] [ Propose Tags ] [ Report a vulnerability ]

generalized Algebraic Dynamic Programming

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

ADPfusion allows writing dynamic programs for single- and multi-tape problems. Inputs can be sequences, or sets. New input types can be defined, without having to rewrite this library thanks to the open-world assumption of ADPfusion.

The library provides the machinery for Outside and Ensemble algorithms as well. Ensemble algorithms combine Inside and Outside calculations.

Starting with version 0.4.1 we support writing multiple context-free grammars (interleaved syntactic variables). Such grammars have applications in bioinformatics and linguistics.

The homepage provides a number of tutorial-style examples, with linear and context-free grammars over sequence and set inputs.

The formal background for generalized algebraic dynamic programming and ADPfusion is described in a number of papers. These can be found on the gADP homepage and in the README.

Note: The core ADPfusion library only provides machinery for linear language over sequences. The add-ons ADPfusionSubword, ADPfusionForest, and others provide specialized machinery for other types of formal languages.

[Skip to Readme]

Flags

Manual Flags

NameDescriptionDefault
debug

Enable bounds checking and various other debug operations at the cost of a significant performance penalty.

Disabled
debugoutput

Enable debug output, which spams the screen full of index information

Disabled
debugdump

Enable dumping intermediate / core files

Disabled
dump-core

Dump HTML for the core generated by GHC during compilation

Disabled
examples

build the examples

Disabled
spectest

build the spec-ctor test case

Disabled
devel

build additional tests

Disabled
btstruc

performance test for backtracking structures

Disabled
llvm

use llvm

Disabled

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

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.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, 0.5.0.0, 0.5.1.0, 0.5.2.0, 0.5.2.2, 0.6.0.0 (info)
Change log changelog.md
Dependencies base (>=4.7 && <5.0), bits (>=0.4), containers, deepseq, DPutils (>=0.1.0 && <0.1.1), ghc-prim, mmorph (>=1.0), mtl (>=2.0), OrderedBits (>=0.0.2 && <0.0.3), primitive (>=0.5.4), PrimitiveArray (>=0.10.0 && <0.10.1), QuickCheck (>=2.7), singletons (>=2.4), strict (>=0.3), template-haskell (>=2.0), th-orphans (>=0.12), transformers (>=0.3), tuple (>=0.3), vector (>=0.11) [details]
Tested with ghc ==8.6.4
License BSD-3-Clause
Copyright Christian Hoener zu Siederdissen, 2011-2019
Author Christian Hoener zu Siederdissen, 2011-2019
Maintainer choener@bioinf.uni-leipzig.de
Category Algorithms, Data Structures, Bioinformatics, Formal Languages
Home page https://github.com/choener/ADPfusion
Bug tracker https://github.com/choener/ADPfusion/issues
Source repo head: git clone git://github.com/choener/ADPfusion
Uploaded by ChristianHoener at 2019-10-01T18:22:22Z
Distributions
Reverse Dependencies 15 direct, 1 indirect [details]
Executables spectest, SmithWaterman, NeedlemanWunsch
Downloads 19631 total (52 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2019-10-01 [all 1 reports]

Readme for ADPfusion-0.6.0.0

[back to package description]

Build Status

ADPfusion

generalized Algebraic Dynamic Programming Homepage

Ideas implemented here are described in a couple of papers:

  1. Christian Hoener zu Siederdissen
    Sneaking Around ConcatMap: Efficient Combinators for Dynamic Programming
    2012, Proceedings of the 17th ACM SIGPLAN international conference on Functional programming
    paper preprint
  2. Andrew Farmer, Christian Höner zu Siederdissen, and Andy Gill.
    The HERMIT in the stream: fusing stream fusion’s concatMap
    2014, Proceedings of the ACM SIGPLAN 2014 workshop on Partial evaluation and program manipulation.
    paper
  3. Christian Höner zu Siederdissen, Ivo L. Hofacker, and Peter F. Stadler.
    Product Grammars for Alignment and Folding
    2014, IEEE/ACM Transactions on Computational Biology and Bioinformatics. 99
    paper
  4. Christian Höner zu Siederdissen, Sonja J. Prohaska, and Peter F. Stadler
    Algebraic Dynamic Programming over General Data Structures
    2015, BMC Bioinformatics
    preprint
  5. Maik Riechert, Christian Höner zu Siederdissen, and Peter F. Stadler
    Algebraic dynamic programming for multiple context-free languages
    2016, Theoretical Computer Science
    preprint

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.

Installation

Follow the gADP examples.

Implementors Notes (if you want to extend ADPfusion)

These have been moved to HACKING.md.

Contact

Christian Hoener zu Siederdissen
Leipzig University, Leipzig, Germany
choener@bioinf.uni-leipzig.de
http://www.bioinf.uni-leipzig.de/~choener/