Advanced search
1 file | 409.74 KB

Memoizing a monadic mixin DSL

Author
Organization
Abstract
Modular extensibility is a highly desirable property of a domain-specific language (DSL): the ability to add new features without affecting the implementation of existing features. Functional mixins (also known as open recursion) are very suitable for this purpose. We study the use of mixins in Haskell for a modular DSL for search heuristics used in systematic solvers for combinatorial problems, that generate optimized C++ code from a high-level specification. We show how to apply memoization techniques to tackle performance issues and code explosion due to the high recursion inherent to the semantics of combinatorial search. As such heuristics are conventionally implemented as highly entangled imperative algorithms, our Haskell mixins are monadic. Memoization of monadic components causes further complications for us to deal with.
Keywords
domain-specific language, programming languages, Gecode, mixins, monads, memoization, combinatorial search, Haskell, functional programming, modelling, constraint programming

Downloads

  • paper.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 409.74 KB

Citation

Please use this url to cite or link to this publication:

Chicago
Wuille, Pieter, Tom Schrijvers, Horst Samulowitz, Guido Tack, and Peter Stuckey. 2011. “Memoizing a Monadic Mixin DSL.” In Lecture Notes in Computer Science, ed. Herbert Kuchen, 6816:68–85. Berlin, Germany: Springer.
APA
Wuille, P., Schrijvers, T., Samulowitz, H., Tack, G., & Stuckey, P. (2011). Memoizing a monadic mixin DSL. In H. Kuchen (Ed.), Lecture Notes in Computer Science (Vol. 6816, pp. 68–85). Presented at the 20th International workshop on Functional and (Constraint) Logic Programming (WFLP 2011), Berlin, Germany: Springer.
Vancouver
1.
Wuille P, Schrijvers T, Samulowitz H, Tack G, Stuckey P. Memoizing a monadic mixin DSL. In: Kuchen H, editor. Lecture Notes in Computer Science. Berlin, Germany: Springer; 2011. p. 68–85.
MLA
Wuille, Pieter, Tom Schrijvers, Horst Samulowitz, et al. “Memoizing a Monadic Mixin DSL.” Lecture Notes in Computer Science. Ed. Herbert Kuchen. Vol. 6816. Berlin, Germany: Springer, 2011. 68–85. Print.
@inproceedings{1223472,
  abstract     = {Modular extensibility is a highly desirable property of a domain-specific language (DSL): the ability to add new features without affecting the implementation of existing features. Functional mixins (also known as open recursion) are very suitable for this purpose.
We study the use of mixins in Haskell for a modular DSL for search heuristics used in systematic solvers for combinatorial problems, that generate optimized C++ code from a high-level specification. We show how to apply memoization techniques to tackle performance issues and code explosion due to the high recursion inherent to the semantics of combinatorial search.
As such heuristics are conventionally implemented as highly entangled imperative algorithms, our Haskell mixins are monadic. Memoization of monadic components causes further complications for us to deal with.},
  author       = {Wuille, Pieter and Schrijvers, Tom and Samulowitz, Horst and Tack, Guido and Stuckey, Peter},
  booktitle    = {Lecture Notes in Computer Science},
  editor       = {Kuchen, Herbert},
  isbn         = {9783642225307},
  issn         = {0302-9743},
  keyword      = {domain-specific language,programming languages,Gecode,mixins,monads,memoization,combinatorial search,Haskell,functional programming,modelling,constraint programming},
  language     = {eng},
  location     = {Odense, Denmark},
  pages        = {68--85},
  publisher    = {Springer},
  title        = {Memoizing a monadic mixin DSL},
  url          = {http://dx.doi.org/10.1007/978-3-642-22531-4\_5},
  volume       = {6816},
  year         = {2011},
}

Altmetric
View in Altmetric
Web of Science
Times cited: