Building interpreters by composing monads

摘要

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.