Strategic polymorphism requires just two combinators!

Author

Ralf Lämmel and Joost Visser

Paper abstract

In previous work, we introduced the notion of functional strategies: first-class generic functions that can traverse terms of any type while mixing uniform and type-specific behaviour. Functional strategies transpose the notion of term rewriting strategies (with coverage of traversal) to the functional programming paradigm. Meanwhile, a number of Haskell-based models and combinator suites were proposed to support generic programming with functional strategies.

In the present paper, we provide a compact and matured reconstruction of functional strategies. We capture strategic polymorphism by just two primitive combinators. This is done without commitment to a specific functional language. We analyse the design space for implementational models of functional strategies. For completeness, we also provide an operational reference model for implementing functional strategies (in Haskell). We demonstrate the generality of our approach by reconstructing representative fragments of the Strafunski library for functional strategies.

Download paper

• [.ps]
• [.pdf]
• The paper's page @ arXiv.

Bibtex entry

@techreport{LV02-JUST-TWO,
 author = "Ralf L{\"a}mmel and Joost Visser",
 title  = "{Strategic polymorphism requires just two combinators!}",
 institution = "arXiv",
 number = "cs.PL/0212048",
 year   = 2002,
 month  = dec,
 pages  = "15~pages"
}

An early version of this paper has been published in the informal preproceedings of the IFL 2002 workshop.