Modular and generic programming with interpreterlib

ABSTRACT

Modular monadic semantics (MMS) is a well-known technique for structuring modular denotational semantic definitions. Families of language constructs are independently defined using syntactic functors and semantic algebras that can be combined in a mix-and-match fashion to create complete language definitions. We introduce InterpreterLib, a Haskell library that implements and extends MMS techniques for writing composable analyses. In addition to modular analyses composition, InterpreterLib provides algebra combinators, explicit algebra semantics, preprocessors for boiler plate generation and generic programming techniques adapted to language analysis. The key benefits of these features are reliability, increased code reuse via modularity and the ability to rapidly retarget component analyses.

REFERENCES

• 1: Perry Alexander, System Level Design with Rosetta (Systems on Silicon), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2006
• 2: L. Duponcheel. Using catamorphisms, subtypes and monad transformers for writing modular functional interpreters., 1995.
• 3: David A. Espinosa, Semantic Lego, Columbia University, New York, NY, 1995
• 4: J. A. Goguen , J. W. Thatcher , E. G. Wagner , J. B. Wright, Initial Algebra Semantics and Continuous Algebras, Journal of the ACM (JACM), v.24 n.1, p.68-95, Jan. 1977 [doi>10.1145/321992.321997]
• 5: Graham Hutton, Fold and unfold for program semantics, Proceedings of the third ACM SIGPLAN international conference on Functional programming, p.280-288, September 26-29, 1998, Baltimore, Maryland, United States
• 6: Patrik Jansson , Johan Jeuring, PolyP—a polytypic programming language extension, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.470-482, January 15-17, 1997, Paris, France [doi>10.1145/263699.263763]
• 7: J. E. Labra Gayo, MC. Luengo Díez, JM. Cueva Lovelle, and A. Cernuda del Río. LPS: A language prototyping system using modular monadic semantics. In Mvan der Brand and DParigot, editors, Proceedings 1st Workshop on Language Descriptions, Tools and Applications, LDTA'01, Genova, Italy, 7 Apr 2001, volume 44(2). Elsevier, Amsterdam, 2001.
• 8: Ralf Lämmel , Simon Peyton Jones, Scrap your boilerplate: a practical design pattern for generic programming, ACM SIGPLAN Notices, v.38 n.3, March 2003
• 9: Ralf Lämmel , Joost Visser, Design patterns for functional strategic programming, Proceedings of the 2002 ACM SIGPLAN workshop on Rule-based programming, p.1-14, October 05, 2002, Pittsburgh, Pennsylvania [doi>10.1145/570186.570187]
• 10: Ralf Lämmel , Joost Visser, A Strafunski Application Letter, Proceedings of the 5th International Symposium on Practical Aspects of Declarative Languages, p.357-375, January 13-14, 2003
• 11: R. Lämmel, J. Visser, and J. Kort. Dealing with large bananas. In J. Jeuring, editor, Workshop on Generic Programming, 2000.
• 12: Sheng Liang , Paul Hudak , Mark Jones, Monad transformers and modular interpreters, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.333-343, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199528]
• 13: Eelco Visser, Stratego: A Language for Program Transformation Based on Rewriting Strategies, Proceedings of the 12th International Conference on Rewriting Techniques and Applications, p.357-362, May 22-24, 2001
• 14: Philip Weaver , Garrin Kimmell , Nicolas Frisby , Perry Alexander, Constructing language processors with algebra combinators, Proceedings of the 6th international conference on Generative programming and component engineering, October 01-03, 2007, Salzburg, Austria [doi>10.1145/1289971.1289997]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.13 Reusable Software
            Subjects: Reusable libraries

General Terms:
Languages

Keywords:
generative programming, generic programming, modular monadic semantics