Challenges in the compilation of a domain specific language for dynamic programming

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Challenges in the compilation of a domain specific language for dynamic programming

Full text

Pdf (178 KB)

Source

Symposium on Applied Computing archive
Proceedings of the 2006 ACM symposium on Applied computing table of contents

Dijon, France

SESSION: Programming languages (PL) table of contents

Pages: 1603 - 1609

Year of Publication: 2006

ISBN:1-59593-108-2

Authors

Robert Giegerich	Bielefeld University, Bielefeld, Germany
Peter Steffen	Bielefeld University, Bielefeld, Germany

Sponsor

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 43, Citation Count: 2

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1141277.1141653 What is a DOI?

ABSTRACT

Many combinatorial optimization problems in biosequence analysis are solved via dynamic programming. To increase programming productivity and program reliability, a domain specific language embedded in Haskell has been suggested. We point out several shortcomings of this approach, and report on some challenges in the (ongoing) project of migrating this domain specific language from its host language to a directly compiled implementation. Most of these challenges are domain specific optimizations, which not only improve significant constant factors of runtime and space requirements, but also affect asymptotic efficiency. We report on our solutions to some of these problems, and point out others that are still open.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , Jeffrey D. Ullman, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
	2	Patrick Cousot , Radhia Cousot, Systematic design of program analysis frameworks, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.269-282, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567778]
	3	R. Durbin, S. Eddy, A. Krogh, and G. Mitchison. Biological Sequence Analysis. Cambridge University Press, 1998.
	4	David Eppstein , Zvi Galil , Raffaele Giancarlo , Giuseppe F. Italiano, Sparse dynamic programming I: linear cost functions, Journal of the ACM (JACM), v.39 n.3, p.519-545, July 1992 [doi>10.1145/146637.146650]
	5	David Eppstein , Zvi Galil , Raffaele Giancarlo , Giuseppe F. Italiano, Sparse dynamic programming II: convex and concave cost functions, Journal of the ACM (JACM), v.39 n.3, p.546-567, July 1992 [doi>10.1145/146637.146656]
	6	Robert Giegerich , Carsten Meyer , Peter Steffen, A discipline of dynamic programming over sequence data, Science of Computer Programming, v.51 n.3, p.215-263, June 2004 [doi>10.1016/j.scico.2003.12.005]
	7	R. Giegerich, B. Voss, and M. Rehmsmeier. Abstract Shapes of RNA. NAR, 32(16):4843--4851, 2004.
	8	Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
	9	Paul Hudak, Building domain-specific embedded languages, ACM Computing Surveys (CSUR), v.28 n.4es, Dec. 1996 [doi>10.1145/242224.242477]
	10	G. Hutton. Higher order functions for parsing. Journal of Functional Programming, 3(2):323--343, 1992.
	11	Ulrich Möncke , Reinhard Wilhelm, Grammar Flow Analysis, Proceedings on Attribute Grammars, Applications and Systems, p.151-186, June 04-13, 1991
	12	S. Peyton Jones, editor. Haskell 98 Language and Libraries -- The Revised Report. Cambridge University Press, April 2003.
	13	J. Reeder and R. Giegerich. Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. BMC Bioinformatics, 5(104), 2004.
	14	M. Rehmsmeier, P. Steffen, M. Höchsmann, and R. Giegerich. Fast and effective prediction of microRNA/target duplexes. RNA, 10:1507--1517, 2004.
	15	D. Searls. Linguistic approaches to biological sequences. CABIOS, 13(4):333--344, 1997.
	16	T. F. Smith and M. S. Waterman. The identification of common molecular subsequences. J. Mol. Biol., 147:195--197, 1981.
	17	P. Steffen and R. Giegerich. Versatile and declarative dynamic programming using pair algebras. BMC Bioinformatics, 6(224), 2005.
	18	Arie van Deursen , Paul Klint , Joost Visser, Domain-specific languages: an annotated bibliography, ACM SIGPLAN Notices, v.35 n.6, p.26-36, June 2000 [doi>10.1145/352029.352035]
	19	S. Wuchty, W. Fontana, I. L. Hofacker, and P. Schuster. Complete suboptimal folding of RNA and the stability of secondary structures. Biopolymers, 49:145--165, 1999.

CITED BY 2

	Janina Reeder , Robert Giegerich, A graphical programming system for molecular motif search, Proceedings of the 5th international conference on Generative programming and component engineering, October 22-26, 2006, Portland, Oregon, USA
	Suleyman Karabuk , F. Hank Grant, A Common Medium for Programming Operations-Research Models, IEEE Software, v.24 n.5, p.39-47, September 2007