Multi-stage programming (MSP) is a form of metaprogramming where parts of source code are annotated and become available as symbolic expressions. Such staged code can be manipulated within the same program before it is translated at either run-time or compile time.
It is not easy to pinpoint the exact time when multistage programming was formally introduced. But it can be argued that, similar to metaprogramming, the origin can be linked to the LISP language, especially with the introduction of quotes (or Quasiqoutes to be distinguished from string quotes). The word “multi-stage” itself seems to have been first introduced by Jones et al.
In the 1990s, there was a rise in interest in work on creating multistage languages that can support program generation through staging in order to optimize high performance computing programs. This led to the creation of Multistage languages such MetaML, and MetaOcaml (which was later reconstructed by Oleg Kiselyov in 2013).
Staging as a concept can appear naturally in different situations. For example, programs that are compiled usually have two different stages (compilation and execution). This usually happens in two separate processes: one that compiles the code and another that runs the code on the user's machine.
Multistage programming is the paradigm in which different stages, such as generation, compilation, and execution, are done within one process. This means that in MSP the distinction between compile-time and run-time becomes blurry and hard to distinguish.
To generate programs using MSP, some constructs need to be able to control the construction, combination, and execution of expressions. Such control and flexibility are obtained through the use of annotations. Controlling the execution of expressions requires the delay expressions only to be executed at later stages. The constructs for MSP can vary based on the use cases and languages.
The following are the basic constructs that are used in MetaOCaml:
These three constructs, in the order they are presented, are analogous to the LISP's back-quote, comma, and eval respectively. This analogy is not perfect but can explain the relation to LISP.
The most-used example when talking about multistage programming is the power function example which came from Andrei Petrovich Ershov's 1977 paper that begat partial evaluation. The following is the generic power function written in OCaml:
let rec power (n, x) =
match n with
0 -> 1 | n -> x * (power (n-1, x));;
This function can calcaulate xn for any non-negative n. But the problem rises when there is a need to compute a specific power very often, say x cubed (x3). Then using the above function we would write:
let power3 (x) = power(3,x);;
This declaration of the function will always do 3 recursive calls to the power fucntion which is not optimal for runtime. So we might want to automatically generate a function that can do this in a faster way by unfolding the power function.
Using a multistage programming language such as MetaOCaml we can stage the power function using the annotations presented earlier, as follow:
let rec power (n, x) =
match n with
0 -> .<1>. | n -> .<.~x * .~(power (n-1, x))>.;;
The return type of this function is now code int instead of int. The type code int is the code of expressions that compute an int. Inserting brackets around the multiplication expression delays the expression while inserting the Escape around the recursive call to power means that it is performed immediately.
After annotating the power function, we have to also annotate the declaration of the power3 function. We do so as follows:
let power3 = .! .<fun x -> .~(power (3,.<x>.))>.;;
The evaluation of this annotated function would result in fun x -> 1 * x * x * x. Hence this eliminates the overhead of recursively calling the power function at runtime.
Note: The above annotations can also be reused to declare the square function or any other power function.
Using multistage programming to generate code has multiple benefits. The following are some benefits of MSP:
In essence, partial evaluation optimizes a program automatically based on partial information about the program's input and hence creating a specialized version of the program. The main reasons why one would prefer multistage over partial evaluation are as follows:
When using multistage programming it is important to ensure a couple of features such as hygienic code and type safety. Hygenic code is code that doesn't allow the accidenetal capture of identifiers (non-hygenic code causes variable shadowing). For example in MSP, a variable bound in a particular stage should be available in future stages and can't be used in earlier stages. These two features are referred to as cross-stage persistence and cross-stage safety resepctively.
Those features along with renaming go along towards solving the problem of Hygienic code which seems to be first treated by Kohlbecker et al.. In addition, MSP requires that the type safety is not violated. This is the main reason why code in MSP is not represented as a string but as more structured representations such as AST or low-level IR.
The support for multistage programming by languages varies from language to language. OCaml, ML, Common Lisp, Terra, and Zig are some of the languages that provide good support for multistage programming. In addition, some other languages have a lower level of support for multistage. Below are some of those languages"
Scala: According to docs, multistage programming can be enabled for Scala projects.
Groovy: Groovy's operator overloading, semantics, and method parenthesis omission can allow some level of multistaging but the performance cost is large.
Kotlin: Kotlin has some support for multistage programming but it is not optimized.
Template Haskell: Haskell types classes provides support for multistage programming but there are some limits when trying to use more than one class at once.
Java: Java annotations allow users to do MSP. Taha implemented a Java framework called Mint.
C++/C: Multistage programming can be done through templates and C Macros. There are some C++/C frameworks that provide support for multistage programming.
Python: Python decorators can be used to do multistage programming.
In more recent years, there has been an increase in frameworks that support multistage programming for mainstream languages such as Scala's LMS, BuildIt, and Mint (Java framework). Another research direction focus on integrating dependent types or Macros with MSP(Stucki et al.,and Stucki et al. ). In addition, there are some recent works that focus on cross-stage persistence and cross-stage safety.
Walid Taha's Papers on multistage programming and MetaML
Oleg Kiselyov's Article and Annotated slides
Nicolas Stucki, Aggelos Biboudis and Martin Odersky's Article on
MSP and Macros
Bawden's Article on Quasiqoutes in LISP