We introduce MetaML, a practically motivated, statically typed multi-stage
programming language. MetaML is a "rear" language. We have built an impleme
ntation and used it to solve multi-stage problems. MetaML allows the progra
mmer to construct, combine, and execute code fragments in a type-safe manne
r. Code fragments can contain free variables, but they obey the static-scop
ing principle. MetaML performs type-checking for all stages once and for al
l before the execution of the first stage. Certain anomalies with our first
MetaML implementation led us to formalize an illustrative subset of the Me
taML implementation. We present both a big-step semantics and type system f
or this subset, and prove the type system's soundness with respect to a big
-step semantics. From a software engineering point of view, this means that
generators written in the MetaML subset never generate unsafe programs. A
type system and semantics for full MetaML is still ongoing work. We argue t
hat multi-stage languages are useful as programming languages in their own
right, that they supply a sound basis for high-level program generation tec
hnology, and that they should support features that make it possible for pr
ogrammers to write staged computations without significantly changing their
normal programming style. To illustrate this we provide a simple three-sta
ge example elaborating a number of practical issues. The design of MetaML w
as based on two main principles that we identified as fundamental for high-
level program generation, namely, cross-stage persistence and cross-stage s
afety. We present these principles, explain the technical problems they giv
e rise to, and how we address with these problems in our implementation. (C
) 2000 Published by Elsevier Science B.V. All rights reserved.