AbstractWe present an integration of modular monadic semantics and generic programming concepts that facilitates the modular development of interpreters. Using modular monadic semantics, the computational structure is obtained as the composition of several monad transformers where each monad transformer adds a new notion of computation. Using generic programming, it is possible to divide the recursive structure of the abstract syntax in several non-recursive pattern functors. For each functor F, it is possible to define an F-algebra over the computational structure. In this way, an interpreter is automatically obtained as a catamorphism.
In this paper we show that it is also possible to use monadic catamorphisms and to combine them with catamorphisms allowing the separation between recursive evaluation from semantic specification. As an example, we define the modular specification of a simple functional programming language with imperative features.
Categories and Subject Descriptors: D.3.4 [Programming Languages]: Processors; F.3.2 [Logics and Meanings of Programs]: Semantics of Programming Languages
Additional Key Words and Phrases: modular monadic semantics, programming languages, interpreters
Selected references
- Mark P. Jones. First-class polymorphism with type inference. In Conference Record of POPL '97: The 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 483-496, Paris, France, 15-17 January 1997.
- Sheng Liang, Paul Hudak, and Mark P. Jones. Monad transformers and modular interpreters. In Conference Record of POPL '95: 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 333-343, San Francisco, California, January 1995.
- Grant Malcolm. Data structures and program transformation. Science of Computer Programming, 14(2-3):255-279, October 1990.
- Philip Wadler. The essence of functional programming. In Conference Record of the Nineteenth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 1-14, Albequerque, New Mexico, January 1992.