Compiling Embedded Languages

Conal Elliott, Sigbjorn Finne, and Oege de Moor,

Abstract:

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.


Appeared in Journal of Functional Programming, 13(2), 2003.  Based on a paper that appeared at the SAIG 2000 (Semantics, Applications, and Implementation of Program Generation) workshop as part of PLI 2000.

Formats:

For more information about the image language discussed in this paper, see the Pan home page.  This work was done while the first and second authors were at Microsoft Research.

BibTeX:

@Article{Elliott03:CompileDSEL-JFP,
  author       = {Conal Elliott and Sigbj\o{}rn Finne and Oege de Moor},
  title        = {Compiling Embedded Languages},
  url          = {http://conal.net/papers/jfp-saig/},
  journal      = {Journal of Functional Programming},
  year         = 2003,
  volume       = 13,
  number       = 2,
  note         = {Updated version of paper by the same name that appeared in SAIG '00 proceedings.}
}