specialization, the use of staging provides strong guarantees about the structure of the generated code. In this
case, we are guaranteed that specialization will happen for
each value of m (but never for n), statically evaluating tests
on values of m and inserting constants for all occurrences
of m in the generated code.
Other strong guarantees can be achieved by restricting the interface of function definitions. Being of type
Rep[A=>B], the result of lambda is a first-class value in
the generated code that can be stored or passed around
in arbitrary ways. However, we might want to avoid higher
order control flow in generated code for efficiency reasons,
or to simplify subsequent analysis passes. In this case, we
can define a new function constructor fundef as follows:
def fundef[A,B](f: Rep[A] => Rep[B]): Rep[A] =>
(x: Rep[A]) => lambda(f).apply(x)
The use of fundef instead of lambda produces a
restricted function that can only be applied but not passed
around in the generated code (type Rep[A]=>Rep[B]).
At the same time, a result of fundef is still a first class
value in the code generator. If we do not expose lambda
and apply at all to client code, we obtain a guarantee that
each function call site unambiguously identifies the function definition being called and no closure objects will
need to be created at runtime.
4. ReLATeD WoRk
Static program generation approaches include C++ templates, and Template Haskell.
20 Building on C++ templates,
customizable generation approaches are possible through
23 An example of runtime code generation in C++ is the TaskGraph framework. Active libraries
were introduced by Veldhuizen24 and telescoping languages
by Kennedy at al.
11 Specific toolkits using domain-specific
code generation and optimization include FFTW,
This paper draws a lot of inspiration from the work of
Kiselyov et al.
12 on a staged FFT implementation. Performing
symbolic rewritings by defining operators on lifted expressions and performing common subexpression elimination
on the fly is also central to their approach. LMS takes these
ideas one step further by making them a central part of the
staging framework itself.
Immediately related works on embedding typed languages include those of Carette et al.
2 and Hofer et al.
13, 18 describe how LMS is used in the development of
DSLs for high-performance parallel computing on heterogenous platforms.
Multistage Programming Languages such as MetaML22 and
MetaOCaml1 have been proposed as a disciplined approach
to building code generators. These languages provide three
syntactic annotations: brackets, escape, and run, which
together provide a syntactic quasi-quotation facility that
is similar to that found in Lisp but statically scoped and
The development of lightweight modular staging has benefited greatly from the work on Delite in collaboration
with the Stanford Pervasive Parallelism Lab, in particular
Arvind Sujeeth, Hassan Chafi, Kevin Brown, HyoukJoong
Lee and Kunle Olukotun. A number of members of the
authors’ group at EPFL have applied LMS to interesting
use cases and contributed new insights or valuable extensions to the framework.