Change management in multi-stage program generation systems

A multi-stage program generation (MSPG) system can use programs generated in itself to generate further programs. Such systems can be used for multiple purposes such as increasing run-time program performance, reducing repeated computation, pipelining computation among distributed parties, and ultimately building adaptive programs with little run-time overhead and greater programmer productivity. However, we have seen limited success of MSPG systems due to restrictions in the current theory and design. In this dissertation, we propose some new theory and design towards wider applications of MSPG systems.; One common shortcoming of existing approaches is that a linearly ordered set of stages are predetermined and assigned to every piece of a multi-stage program statically. The linear ordering, however, is often hard to determine beforehand and/or misaligns with run-time conditions. Our first contribution is the introduction of a new theory that does not require a static linear order. Instead, we study how to derive a succinct description of all linear orders that are consistent with a given multi-stage program. This study can lead to new designs such that it is possible to apply a number of different cascading stage sequences of program generation at run-time.; General-purpose multi-stage programming languages are sometimes hard to fit well in specific application domains. In view of this, we propose a framework for incorporating domain-specific multi-stage programming languages into mainstream object-oriented programming languages. This lowers the threshold for programmers to accept multi-stage programming and allows programmers to easily design application domain-aware multi-stage programs.; Stand-alone multi-stage programming languages need to observe the run-time environment and manipulate program objects in itself. For example, it is desirable to have a procedure in a multi-stage programming language to turn a multi-stage program object into one with self-updating capabilities. We introduce a general mechanism called reflection across stages for purposes like that.; Finally, to enable fully automatic MSPG in running a conventional program, we make our initial effort to use online feedback to guide multi-stage run-time program specialization.