Compiling Embedded Languages

Conal Elliott , Sigbjorn Finne, and Oege de Moor,

Microsoft Research

July, 2000


Functional languages are particularly well-suited to the implementation of interpreters for domain-specific embedded languages (DSELs). We describe an implemented technique for producing optimizing compilers for DSELs, based on Kamin's idea of DSELs for program generation. The technique uses a data type of syntax for basic types, a set of smart constructors that perform rewriting over those types, some code motion transformations, and a back-end code generator. Domain-specific optimization results from chains of rewrites on basic types. New DSELs are defined directly in terms of the basic syntactic types, plus host language functions and tuples. This definition style makes compilers easy to write and, in fact, almost identical to the simplest embedded interpreters. We illustrate this technique with a language Pan for the computationally intensive domain of image synthesis and manipulation.

This paper appeared at the Semantics, Applications and Implementation of Program Generation workshop (SAIG 2000) as part of PLI 2000, and is Springer-Verlag.


Superceded by version appearing in JFP.


For more information about the image language discussed in this paper, see the Pan home page.