PLS Lab

Multi-stage Programming

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.

History

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).

Basics of MSP

Staging

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.

Constructs of MSP

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:

  1. Brackets (written as .<...>.) delays the computation of an expression
  2. Escape (written .˜...) used to construct large delayed expressions from smaller subexpressions. Note that escape must be done in the context of a bracket.
  3. Run (written .!...) compiles and executes delayed expressions

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.

Example

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 -> x * x * x * 1. 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.

Why multistage programming?

Using multistage programming to generate code has multiple benefits. The following are some benefits of MSP:

  1. Optimizing code: This is one of the most beneficial uses of MSP. MSP can be helpful in generating code that is optimized. This has been shown with the success of multistage programming in optimizing high performance computing programs. A simple example of code optimization is shown in the next subsection.
  2. Reuseabilty: MSP can help create a lot of abstraction with a lesser amount of code.
  3. DSLs: MSP provides an easy approach for constructing domain specific languages.
  4. Type safety: One of the biggest concerns of code generation is the ability to generate safe code. Multistage languages focus on ensuring that the generated code is safe at any stage.

Mutlistage vs. Partial evaluation

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:

  1. Ease of use and understanding: Partial evaluation systems are harder to be understood for new users. Meanwhile MSP offers an easier way of understanding staging which is helpful for teaching, implementation, and reasoning (one can study annotation in relative isolation without the added complexity of partial evaluation).
  2. Flexibility: Multistage offers control flexibility which is shown to help eliminate non-desirable effects such as infinite unfolding. In addition, the evaluation order in partial evaluation is dependent on the time of arrival of inputs, multistage programming can improve the performance of the programs by controling the evaluation order.

Hygiene and Safety

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.

Languages and Support

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"

  1. Scala: According to docs, multistage programming can be enabled for Scala projects.

  2. Groovy: Groovy's operator overloading, semantics, and method parenthesis omission can allow some level of multistaging but the performance cost is large.

  3. Kotlin: Kotlin has some support for multistage programming but it is not optimized.

  4. 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.

  5. Java: Java annotations allow users to do MSP. Taha implemented a Java framework called Mint.

  6. C++/C: Multistage programming can be done through templates and C Macros. There are some C++/C frameworks that provide support for multistage programming.

  7. Python: Python decorators can be used to do multistage programming.

Recent Works

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.

References