research-article

Sneaking around concatMap: efficient combinators for dynamic programming

Author:

Christian Höner zu SiederdissenAuthors Info & Claims

ICFP '12: Proceedings of the 17th ACM SIGPLAN international conference on Functional programming

Pages 215 - 226

https://doi.org/10.1145/2364527.2364559

Published: 09 September 2012 Publication History

Abstract

We present a framework of dynamic programming combinators that provides a high-level environment to describe the recursions typical of dynamic programming over sequence data in a style very similar to algebraic dynamic programming (ADP). Using a combination of type-level programming and stream fusion leads to a substantial increase in performance, without sacrificing much of the convenience and theoretical underpinnings of ADP.

We draw examples from the field of computational biology, more specifically RNA secondary structure prediction, to demonstrate how to use these combinators and what differences exist between this library, ADP, and other approaches.

The final version of the combinator library allows writing algorithms with performance close to hand-optimized C code.

References

[1]

R. E. Bellman. On the Theory of Dynamic Programming. Proceedings of the National Academy of Sciences, 38 (8): 716--719, 1952.

[2]

A. F. Bompfünewerer, R. Backofen, S. H. Bernhart, J. Hertel, I. L. Hofacker, P. F. Stadler, and S. Will. Variations on RNA folding and alignment: lessons from Benasque. Journal of Mathematical Biology, 56 (1): 129--144, 2008.

[3]

M. M. Chakravarty, G. Keller, and S. Peyton Jones. Associated Type Synonyms. In Proceedings of the tenth ACM SIGPLAN international conference on Functional programming, ICFP'05, pages 241--253. ACM, 2005.

Digital Library

[4]

M. M. Chakravarty, R. Leshchinskiy, S. Peyton Jones, G. Keller, and S. Marlow. Data Parallel Haskell: a status report. In Proceedings of the 2007 workshop on Declarative aspects of multicore programming, DAMP'07, pages 10--18. ACM, 2007.

Digital Library

[5]

K. Claessen and J. Hughes. QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs. In Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, ICFP'00, pages 268--279. ACM, 2000.

Digital Library

[6]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT press, 2001.

Digital Library

[7]

D. Coutts, R. Leshchinskiy, and D. Stewart. Stream Fusion: From Lists to Streams to Nothing at All. In Proceedings of the 12th ACM SIGPLAN international conference on Functional programming, ICFP'07, pages 315--326. ACM, 2007.

Digital Library

[8]

R. Durbin, S. Eddy, A. Krogh, and G. Mitchison. Biological sequence analysis. Cambridge Univ. Press, 1998.

[9]

R. Giegerich and C. Höner zu Siederdissen. Semantics and Ambiguity of Stochastic RNA Family Models. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 8 (2): 499--516, 2011.

Digital Library

[10]

R. Giegerich and C. Meyer. Algebraic Dynamic Programming. In Algebraic Methodology And Software Technology, volume 2422, pages 243--257. Springer, 2002.

Digital Library

[11]

R. Giegerich and P. Steffen. Challenges in the compilation of a domain specific language for dynamic programming. In Proceedings of the 2006 ACM symposium on Applied computing, pages 1603--1609. ACM, 2006.

Digital Library

[12]

R. Giegerich, C. Meyer, and P. Steffen. Towards a Discipline of Dynamic Programming. Informatik bewegt, GI-Edition-Lecture Notes in Informatics, pages 3--44, 2002.

Digital Library

[13]

R. Giegerich, C. Meyer, and P. Steffen. A Discipline of Dynamic Programming over Sequence Data. Science of Computer Programming, 51 (3): 215--263, 2004.

Digital Library

[14]

R. Giegerich et al. Algebraic Dynamic Programming Website. http://bibiserv.techfak.uni-bielefeld.de/adp/, 2004.

Digital Library

[15]

D. Grune and C. J. Jacobs. Parsing techniques: a practical guide. Springer-Verlag New York Inc, 2008.

[16]

I. L. Hofacker, W. Fontana, P. F. Stadler, L. S. Bonhoeffer, M. Tacker, and P. Schuster. Fast Folding and Comparison of RNA Secondary Structures. Monatshefte für Chemie/Chemical Monthly, 125 (2): 167--188, 1994.

[17]

C. Höner zu Siederdissen and I. L. Hofacker. Discriminatory power of RNA family models. Bioinformatics, 26 (18): 453--459, 2010.

Digital Library

[18]

C. Höner zu Siederdissen, S. H. Bernhart, P. F. Stadler, and I. L. Hofacker. A folding algorithm for extended RNA secondary structures. Bioinformatics, 27 (13): 129--136, 2011.

Digital Library

[19]

P. Hudak, J. Hughes, S. Peyton Jones, and P. Wadler. A History of Haskell: Being Lazy with Class. In Proceedings of the third ACM SIGPLAN conference on History of programming languages, HOPL III, pages 1--55. ACM, 2007.

Digital Library

[20]

G. Hutton. Higher-order functions for parsing. Journal of Functional Programming, 2 (3): 323--343, 1992.

[21]

M. P. Jones. Type Classes with Functional Dependencies. Programming Languages and Systems, pages 230--244, 2000.

Digital Library

[22]

G. Keller, M. M. Chakravarty, R. Leshchinskiy, S. Peyton Jones, and B. Lippmeier. Regular, Shape-polymorphic, Parallel Arrays in Haskell. In Proceedings of the 15th ACM SIGPLAN international conference on Functional programming, ICFP'10, pages 261--272. ACM, 2010.

Digital Library

[23]

K. Lari and S. J. Young. The estimation of stochastic context-free grammars using the Inside-Outside algorithm. Computer Speech & Language, 4 (1): 35--56, 1990.

[24]

C. Lattner and V. Adve. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation. In Code Generation and Optimization, 2004. CGO 2004. International Symposium on, pages 75--86. IEEE, 2004.

Digital Library

[25]

R. Leshchinskiy. Recycle Your Arrays! Practical Aspects of Declarative Languages, pages 209--223, 2009.

Digital Library

[26]

R. Lorenz, S. H. Bernhart, C. Höner zu Siederdissen, H. Tafer, C. Flamm, P. F. Stadler, and I. L. Hofacker. ViennaRNA Package 2.0. Algorithms for Molecular Biology, 6 (26), 2011.

[27]

M. Mernik, J. Heering, and A. M. Sloane. When and How to Develop Domain-Specific Languages. ACM Computing Surveys, 37 (4): 316--344, 2005.

Digital Library

[28]

M. Nebel and A. Scheid. Evaluation of a sophisticated SCFG design for RNA secondary structure prediction. Theory in Biosciences, 130: 313--336, 2011. ISSN 1431-7613.

[29]

R. Nussinov, G. Pieczenik, J. R. Griggs, and D. J. Kleitman. Algorithms for Loop Matchings. SIAM Journal on Applied Mathematics, 35 (1): 68--82, 1978.

[30]

B. O'Sullivan, D. B. Stewart, and J. Goerzen. Real World Haskell. O'Reilly Media, 2009.

Digital Library

[31]

S. Peyton Jones. Call-pattern Specialisation for Haskell Programs. In Proceedings of the 12th ACM SIGPLAN international conference on Functional programming, ICFP'07, pages 327--337. ACM, 2007.

Digital Library

[32]

E. Rivas, R. Lang, and S. R. Eddy. A range of complex probabilistic models for RNA secondary structure prediction that includes the nearest-neighbor model and more. RNA, 18 (2): 193--212, 2012.

[33]

G. Sauthoff, S. Janssen, and R. Giegerich. Bellman's GAP - A Declarative Language for Dynamic Programming. In Proceedings of the 13th international ACM SIGPLAN symposium on Principles and practices of declarative programming, PPDP'11, pages 29--40. ACM, 2011.

Digital Library

[34]

R. Sedgewick. Algorithms. Addison-Wesley Publishing Co., Inc., 1983.

Digital Library

[35]

P. Steffen. Compiling a domain specific language for dynamic programming. PhD thesis, Bielefeld University, 2006.

[36]

The GHC Team. The Glasgow Haskell Compiler (GHC). http://www.haskell.org/ghc/, 2012.

Cited By

Eggers DHöner zu Siederdissen CStadler P(2022)Accuracy of RNA Structure Prediction Depends on the Pseudoknot GrammarAdvances in Bioinformatics and Computational Biology10.1007/978-3-031-21175-1_3(20-31)Online publication date: 16-Dec-2022
https://doi.org/10.1007/978-3-031-21175-1_3
Gatter TGiegerich RSaule C(2016)Integrating Pareto Optimization into Dynamic ProgrammingAlgorithms10.3390/a90100129:1(12)Online publication date: 27-Jan-2016
https://doi.org/10.3390/a9010012
Riechert MHöner zu Siederdissen CStadler P(2016)Algebraic dynamic programming for multiple context-free grammarsTheoretical Computer Science10.1016/j.tcs.2016.05.032639:C(91-109)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1016/j.tcs.2016.05.032
Show More Cited By

Index Terms

Sneaking around concatMap: efficient combinators for dynamic programming
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language types
        Functional languages

Recommendations

Sneaking around concatMap: efficient combinators for dynamic programming
ICFP '12

We present a framework of dynamic programming combinators that provides a high-level environment to describe the recursions typical of dynamic programming over sequence data in a style very similar to algebraic dynamic programming (ADP). Using a ...
The HERMIT in the stream: fusing stream fusion's concatMap
PEPM '14: Proceedings of the ACM SIGPLAN 2014 Workshop on Partial Evaluation and Program Manipulation

Stream Fusion, a popular deforestation technique in the Haskell community, cannot fuse the concatMap combinator. This is a serious limitation, as concatMap represents computations on nested streams. The original implementation of Stream Fusion used the ...
Rewriting haskell strings
PADL'07: Proceedings of the 9th international conference on Practical Aspects of Declarative Languages

The Haskell String type is notoriously inefficient. We introduce a new data type, ByteString, based on lazy lists of byte arrays, combining the speed benefits of strict arrays with lazy evaluation. Equational transformations based on term rewriting are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICFP '12: Proceedings of the 17th ACM SIGPLAN international conference on Functional programming

September 2012

392 pages

ISBN:9781450310543

DOI:10.1145/2364527

General Chair:
Peter Thiemann
University of Freiburg, Germany
,
Program Chair:
Robby Findler
Northwestern University, USA

ACM SIGPLAN Notices Volume 47, Issue 9
ICFP '12
September 2012
368 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2398856
Issue’s Table of Contents

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 September 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ICFP'12

Sponsor:

SIGPLAN

ICFP'12: ACM SIGPLAN International Conference on Functional Programming

September 9 - 15, 2012

Copenhagen, Denmark

Acceptance Rates

ICFP '12 Paper Acceptance Rate 32 of 88 submissions, 36%;

Overall Acceptance Rate 333 of 1,064 submissions, 31%

Upcoming Conference

ICFP '25

Sponsor:
sigplan

ACM SIGPLAN International Conference on Functional Programming

October 12 - 18, 2025

Singapore , Singapore

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
210
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)2

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Eggers DHöner zu Siederdissen CStadler P(2022)Accuracy of RNA Structure Prediction Depends on the Pseudoknot GrammarAdvances in Bioinformatics and Computational Biology10.1007/978-3-031-21175-1_3(20-31)Online publication date: 16-Dec-2022
https://doi.org/10.1007/978-3-031-21175-1_3
Gatter TGiegerich RSaule C(2016)Integrating Pareto Optimization into Dynamic ProgrammingAlgorithms10.3390/a90100129:1(12)Online publication date: 27-Jan-2016
https://doi.org/10.3390/a9010012
Riechert MHöner zu Siederdissen CStadler P(2016)Algebraic dynamic programming for multiple context-free grammarsTheoretical Computer Science10.1016/j.tcs.2016.05.032639:C(91-109)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1016/j.tcs.2016.05.032
Saule CGiegerich R(2015)Pareto optimization in algebraic dynamic programmingAlgorithms for Molecular Biology10.1186/s13015-015-0051-710:1Online publication date: 7-Jul-2015
https://doi.org/10.1186/s13015-015-0051-7
zu Siederdissen CProhaska SStadler P(2015)Algebraic Dynamic Programming over general data structuresBMC Bioinformatics10.1186/1471-2105-16-S19-S216:S19Online publication date: 16-Dec-2015
https://doi.org/10.1186/1471-2105-16-S19-S2
Siederdissen CHofacker IStadler P(2015)Product grammars for alignment and foldingIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2014.232615512:3(507-519)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1109/TCBB.2014.2326155
Rivas E(2014)The four ingredients of single-sequence RNA secondary structure prediction. A unifying perspectiveRNA Biology10.4161/rna.2497110:7(1185-1196)Online publication date: 27-Oct-2014
https://doi.org/10.4161/rna.24971
Giegerich RTouzet H(2014)Modeling Dynamic Programming Problems over Sequences and Trees with Inverse Coupled Rewrite SystemsAlgorithms10.3390/a70100627:1(62-144)Online publication date: 7-Mar-2014
https://doi.org/10.3390/a7010062
Jonnalagedda MCoppey TStucki SRompf TOdersky M(2014)Staged parser combinators for efficient data processingACM SIGPLAN Notices10.1145/2714064.266024149:10(637-653)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2714064.2660241
Jonnalagedda MCoppey TStucki SRompf TOdersky MBlack AMillstein T(2014)Staged parser combinators for efficient data processingProceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications10.1145/2660193.2660241(637-653)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2660193.2660241
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents