Building interpreters by composing monads

ABSTRACT

We exhibit a set of functions coded in Haskell that can be used as building blocks to construct a variety of interpreters for Lisp-like languages. The building blocks are joined merely through functional composition. Each building block contributes code to support a specific feature, such as numbers, continuations, functions calls, or nondeterminism. The result of composing some number of building blocks is a parser, an interpreter, and a printer that support exactly the expression forms and data types needed for the combined set of features, and no more. The data structures are organized as pseudomonads, a generalization of monads that allows composition. Functional composition of the building blocks implies type composition of the relevant pseudomonads. Our intent was that the Haskell type resolution system ought to be able to deduce the appropriate data types automatically. Unfortunately there is a deficiency in current Haskell implementations related to recursive data types: circularity must be reflected statically in the type definitions. We circumvent this restriction by applying a purpose-built program simplifier that performs partial evaluation and a certain amount of program algebra. We construct a wide variety of interpreters in the style of Wadler by starting with the building blocks and a page of boiler-plate code, writing three lines of code (one to specify the building blocks and two to (redundantly) specify type compositions), and then applying the simplifier. The resulting code is acceptable Haskell code. We have tested a dozen different interpreters with various combinations of features. In this paper we discuss the overall code structuring strategy, exhibit several building blocks, briefly describe the partial evaluator, and present a number of automatically generated interpreters.

REFERENCES

• 1: Apple Computer, Inc. Inside Maczntosh (five volumes). Addison-Wesley (Reading, Massachusetts, 1985-86).
• 2: Hudak, Paul, Peyton Jones, Simon, and Wadler, Philip, editors. Report on the Programming Language Haskell: A Non-Strict, Purely Functional Language (Version 1.1). Technical Report. Yale University and Glasgow University (New Haven Glasgow (r sp~~tiwly), August 1991).
• 3: Jones, Mark P. Personal communication to Guy Steele, September 1993.
• 4: 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]
• 5: David J. King , Philip Wadler, Combining Monads, Proceedings of the 1992 Glasgow Workshop on Functional Programming, p.134-143, July 06-08, 1992
• 6: Moggi, Eugenio. An Abstract Vzew of Programmint Languages. Technical Report ECS-LFCS-90- 113. Laboratory for Foundations of Computer Science, University of Edinburgh (Edinburgh, Scotland, April 1990). Lecture notes for a course taught at Stanford University, Spring 1989.
• 7: 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]
• 8: Eric S. Raymond, The new hacker's dictionary (3rd ed.), MIT Press, Cambridge, MA, 1996
• 9: Rees, Jonathan. Personal communication to Guy Steele, October 1993.
• 10: John C. Reynolds, Definitional interpreters for higher-order programming languages, Proceedings of the ACM annual conference, p.717-740, August 01-01, 1972, Boston, Massachusetts, United States [doi>10.1145/800194.805852]
• 11: Steele, Guy L., Jr. How to Compose Monads. Technical Report. Thinking Machines Corporation (Cambridge, Massachusetts, July 1993). Unpublished.
• 12: Guy L. Steele, Jr., Common LISP: the language (2nd ed.), Digital Press, Newton, MA, 1990
• 13: Guy L Steele , Gerald J Sussman, The Art of the Interpreter or, The Modularity Complex (Parts Zero, One, and Two), Massachusetts Institute of Technology, Cambridge, MA, 1978
• 14: Gerald J. Sussman , Guy L. Steele, Jr., An Interpreter for Extended Lambda Calculus, Massachusetts Institute of Technology, Cambridge, MA, 1975
• 15: 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]
• 16: 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]
• 17: Philip Wadler, Theorems for free!, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.347-359, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99404]
• 18: Richard C. Waters, XP: A Common Lisp Pretty Printing System, Massachusetts Institute of Technology, Cambridge, MA, 1989
• 19: Wegbreit, Ben, Holloway, Glenn, Spitzen, Jay, and Townley, Judy. ECL Programmer's Manual. Technical Report 23-74. Harvard University Center for Research in Computing Technology (Cambridge, Massachusetts, December 1974).

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Interpreters

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

General Terms:
Languages, Theory