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 incudes 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.

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. W. Appel , T. Jim, Continuation-passing, closure-passing style, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.293-302, January 11-13, 1989, Austin, Texas, United States  [doi>10.1145/75277.75303]
	2	Adrienne Bloss, Paul HudaK and Jonathan Young. Code optimization for lazy evaluation. Lisp and Symbolic Computation, 1(1):147-164,1988.
	3	Robert Cartwright , Matthias Felleisen, Extensible Denotational Language Specifications, Proceedings of the International Conference on Theoretical Aspects of Computer Software, p.244-272, April 19-22, 1994
	4	David Espinosa. Modular denotational semantics. Unpublished manuscript, December 1993.
	5	David Espinosa. Building interpreters by transforming stratified monads. Unpublished manuscript, ftp from altdorf.ai.mit.edu:pub/dae, June 1994.
	6	Andrzej Filinski, Representing monads, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.446-457, January 16-19, 1994, Portland, Oregon, United States  [doi>10.1145/174675.178047]
	7	Paul Hudak , Simon Peyton Jones , Philip Wadler , Brian Boutel , Jon Fairbairn , Joseph Fasel , María M. Guzmán , Kevin Hammond , John Hughes , Thomas Johnsson , Dick Kieburtz , Rishiyur Nikhil , Will Partain , John Peterson, Report on the programming language Haskell: a non-strict, purely functional language version 1.2, ACM SIGPLAN Notices, v.27 n.5, p.1-164, May 1992  [doi>10.1145/130697.130699]
	8	Mark P. Jones. Introduction to gofer 2.20. Ftp from nebula.cs.yale.e#lu in the directory pub/haskell/gofer, September 19911.
	9	Mark P. Jones, A system of constructor classes: overloading and implicit higher-order polymorphism, Proceedings of the conference on Functional programming languages and computer architecture, p.52-61, June 09-11, 1993, Copenhagen, Denmark  [doi>10.1145/165180.165190]
	10	Mark P. Jones #nd Luc Duponcheel Composing monads. Research Report- YALEU/DCS/RR-1004, Yale University Departrhent of Computer Science, New Haven, Connecticut, December 1993.
	11	R. Kelsey , P. Hudak, Realistic compilation by program transformation (detailed summary), Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.281-292, January 11-13, 1989, Austin, Texas, United States  [doi>10.1145/75277.75302]
	12	Amir Kishon , Paul Hudak , Charles Consel, Monitoring semantics: a formal framework for specifying, implementing, and reasoning about execution monitors, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.338-352, June 24-28, 1991, Toronto, Ontario, Canada
	13	Peter Lee, Realistic compiler generation, MIT Press, Cambridge, MA, 1989
	14	Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
	15	Eugenio Mogg#. An abstract view of programming languages. Techni/:al Report ECS-LFCS-90-113, Laboratory for Foundations of Computer Science, University of Edinburgh, Edinburgh, Scotland, 1990.
	16	Peter Mosses, A basic abstract semantic algebra, Proc. of the international symposium on Semantics of data types, p.87-108, July 1984, Sophia-Antipolis, France
	17	Simon L. Peyton Jones , Philip Wadler, Imperative functional programming, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.71-84, March 1993, Charleston, South Carolina, United States  [doi>10.1145/158511.158524]
	18	Guy L. Steele, Jr., Building interpreters by composing monads, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.472-492, January 16-19, 1994, Portland, Oregon, United States  [doi>10.1145/174675.178068]
	19	Joseph E. Stoy, Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory, MIT Press, Cambridge, MA, 1977
	20	Andrew P. Tolmach , Andrew W. Appel, Debugging standard ML without reverse engineering, Proceedings of the 1990 ACM conference on LISP and functional programming, p.1-12, June 27-29, 1990, Nice, France  [doi>10.1145/91556.91564]
	21	Philip Wadler, The essence of functional programming, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-14, January 19-22, 1992, Albuquerque, New Mexico, United States  [doi>10.1145/143165.143169]
	22	Philip Wadler, Comprehending monads, Proceedings of the 1990 ACM conference on LISP and functional programming, p.61-78, June 27-29, 1990, Nice, France  [doi>10.1145/91556.91592]
	23	Mitchell Wand, A semantic prototyping system, ACM SIGPLAN Notices, v.19 n.6, p.213-221, June 1984

• Data structures for quadtree approximation and compression Communications of the ACM   28, 9
  Hanan Samet
  
  
• A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
  Kim S. Lee ,  Huizhu Lu ,  D. D. Fisher
  
  
• The GemStone object database management system Communications of the ACM   34, 10
  Paul Butterworth ,  Allen Otis ,  Jacob Stein
  
  
• Putting innovation to work: adoption strategies for multimedia communication systems Communications of the ACM   34, 12
  Ellen Francik ,  Susan Ehrlich Rudman ,  Donna Cooper ,  Stephen Levine
  
  
• An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE conference on Design automation
  Gwo-Dong Chen ,  Daniel D. Gajski