Memoizing a monadic mixin DSL

Pieter Wuille, Tom Schrijvers, Horst Samulowitz, Guido Tack, Peter James Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

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.

Original languageEnglish
Title of host publicationProceedings of the 20th International Workshop on Functional and Constraint Logic Programming
EditorsHerbert Kuchen
Place of PublicationBerlin Germany
PublisherSpringer-Verlag London Ltd.
Pages68-85
Number of pages18
ISBN (Print)9783642225307
Publication statusPublished - 2011
Externally publishedYes
EventInternational Workshop on Functional and (Constraint) Logic Programming 2011 - Odense, Denmark
Duration: 1 Jan 2011 → …

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6816 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

ConferenceInternational Workshop on Functional and (Constraint) Logic Programming 2011
CountryDenmark
CityOdense
Period1/01/11 → …

Cite this