Multi-Stage Programming : Its Theory and Applications

MetaML is a statically typed functional programming language with special support for programgeneration. In addition to providing the standard features of contemporary programminglanguages such as Standard ML, MetaML provides three staging annotations. These staging annotationsallow the construction, combination, and execution of object-programs.Our thesis is that MetaML's three staging annotations provide a useful, theoretically soundbasis for building program generators. This dissertation reports on our study of MetaML's stagingconstructs, their use, their implementation, and their formal semantics. Our results include anextended example of where MetaML allows us to produce ecient programs, an explanation ofwhy implementing these constructs in traditional ways can be challenging, two formulations ofMetaML's semantics, a type system for MetaML, and a proposal for extending MetaML with atype construct for closedness.The dissertation consolidates a number of previous publications by the author, includingMetaML's type systems and big-step semantics. The presentation is new. The proposed solutionto an implementation problem and the reduction semantics for MetaML's three staging constructsare also new