Monad Transformers and Modular Interpreters
📜 Abstract
We show how a set of building blocks can be used to construct programming language interpreters, and present implementations of such building blocks capable of supporting many commonly known features, including simple expressions, three different function call mechanisms (call-by-name, call-by-value and lazy evaluation), references and assignment, nondeterminism, first-class continuations, and program tracing. The underlying mechanism of our system is monad transformers, a simple form of abstraction for introducing a wide range of computational behaviors, such as state, I/O, continuations, and exceptions. Our work is significant in the following respects. First, we have succeeded in designing a fully modular interpreter based on monad transformers that includes features missing from Steele's, Espinosa's, and Wadler's earlier efforts. Second, we have found new ways to lift monad operations through monad transformers, in particular difficult cases not achieved in Moggi's original work. Third, we have demonstrated that interactions between features are reflected in liftings and that semantics can be changed by reordering monad transformers. Finally, we have implemented our interpreter in Gofer, whose constructor classes provide just the added power over Haskell's type classes to allow precise and convenient expression of our ideas. This implementation includes a method for constructing extensible unions and a form of subtyping that is interesting in its own right.
✨ Summary
The paper establishes a modular approach to programming-language interpreter construction in which individual language features are represented by reusable monad transformers. It demonstrates composition of features including environments, state, errors, continuations, nondeterminism, lazy evaluation, references, and tracing, and analyzes how operation lifting and transformer ordering determine feature interactions and semantics. The implementation in Gofer also introduced techniques for extensible unions and type-class-based abstraction.
The work had documented influence on subsequent Haskell development. A history of Haskell identifies it as the first demonstration of a modular interpreter in Haskell using monad transformers and reports that it helped motivate extensions to type classes and the development of the monad transformer library. (cse.msu.edu) The Haskell transformers documentation continues to use a reduced version of the paper’s interpreter architecture as an example of composing I/O, exceptions, environments, and mutable state. (xmonad.github.io) Later research extended the same modular-monadic methodology to static analysis: Galois Transformers and Modular Abstract Interpreters explicitly builds on this approach to compose language-independent analysis abstractions and transport soundness properties through transformer stacks. (arxiv.org) Subsequent work on modular interpreters also credits the paper’s extensible-union technique and interpreter decomposition pattern. (eprints.nottingham.ac.uk)