What are staged functions (conceptually)?

Question

In a recent CACM article [1], the authors present an implementation for staged functions. They use the term as if it was well-known, and none of the references looks like an obvious introduction.

They give a short explanation (emphasis mine and reference number changed; it's 22 in the original)

In the context of program generation, multistage programming (MSP, staging for short) as established by Taha and Sheard [2] allows programmers to explicitly delay evaluation of a program expression to a later stage (thus, staging an expression). The present stage effectively acts as a code generator that composes (and possibly executes) the program of the next stage.

However, Taha and Sheard write (emphasis mine):

A multi-stage program is one that involves the generation, compilation, and execution of code, all inside the same process. Multi-stage languages express multi-stage programs. Staging, and consequently multi-stage programming, address the need for general purpose solutions which do not pay run-time interpretive overheads.

They than go on to several references to older work allegedly showing that staging is effective, which suggests that the concept is even older. They don't give a reference for the term itself.

These statements seem to be orthogonal, if not contradictory; maybe what Rompf and Odersky write is an application of what Taha and Sheard propose, but maybe it is another perspective on the same thing. They seem to agree that an important point is that programs (re)write parts of themselves at runtime, but I do not know whether that is a necessary and/or sufficient ability.

So, what is staging respectively are interpretations of staging in this context? Where does the term come from?

---

1. Lightweight Modular Staging: A Pragmatic Approach to Runtime Code Generation and Compiled DSLs by T. Rompf and M. Odersky (2012)
2. MetaML and multi-stageprogramming with explicit annotations by W. Taha and T. Sheard (2000)

Answer 1

To the best of my knowledge, the term staged computation was first used by Bill Scherlis in this paper. Prior to that, the term "partial evaluation" was used for much the same concept, but the idea of staged computation is subtly different. Both the ideas are related to Kleene's S-m-n theorem.

If you have a function $\phi(m,n)$ of two arguments, but you know one argument, say $m$, then you can perform some of the computation of the function right away using the knowledge of the first argument. What you are then left with is a function $\phi_m(n)$ whose computations only depend on the second, unknown, argument.

The idea of partial evaluation is to compute the specialized function $\phi_m(n)$ automatically. Given the code for the original function $\phi$, partial evaluation does static analysis to determine which bits of the code depend on $m$ and which bits depend on $n$, and transforms it to a function $\phi'$ which, given $m$, constructs $\phi_m$. The second argument $n$ can then be fed to this specialized function.

The idea of staged computation is to think about the function $\phi'$ first. It is called a "staged" function because it works in multiple stages. Once we give it the first argument $m$, it constructs the code for the specialized function $\phi_m$. This is the "first stage." In the second stage, the second argument is provided to $\phi_m$ which does the rest of the job.

So, the job of partial evaluation is to transform the code for an ordinary function $\phi$ to a staged function $\phi'$. Scherlis envisaged that this transformation could be done by more general mechanisms than the earlier partial evaluation methods. The subject of "staged computation" now deals with issues such as:

• How to define staged functions?
• What programming languages and type systems should be used for defining staged functions?
• What is the semantics of such languages?
• How do we ensure the coherence and correctness of staged functions?
• What techniques are useful for automatically or semi-automatically constructing staged functions?
• How do we prove the correctness of such techniques?

Staged computation can be very important in practice. In fact, every compiler is in effect a staged computation. Given a source program, it constructs a translated and optimized target program, which can then take the actual input and calculate the result. It is hard to write staged computation programs in practice because we have to juggle the multiple stages and make sure that the right things are done at the right time. Everybody who has written a compiler has struggled with such issues. It is also hard to write programs that write other programs, may they be machine language programs (compilers), SQL queries (database manipulations) or HTML/Server Pages/Javascript code (web applications) and myriads of other applications. The researchers in staged computation aim to create good languages and tools that make it easier and safer to create such applications.

Answer 2

Although the other answers are technically correct, I don't think they give a correct understanding of why computer scientists are interested in staged functions.

By creating staged functions, you define programs that generate programs. One of the big goals of modern practical language theory is to maximise potential reuse. We want to make it possible to write libraries that are not just useful functions and objects, but which help programmers by providing higher order architectural constructions.

It would be great if we could get rid of all boilerplate code. We should be able to minimise the specification language. If we want an event driven dispatcher, for instance, communicating to other dispatchers with a given thread design, we should be able to specify that compactly, and all IO listeners and queue object and thread connections should be able to be built from that specification.

Domain languages tend to be those compact representations we are looking for. When people work in a domain for a while, the language they use tends to drop most duplication of info and become a lean specification. So this theory of staging tends to become a translation system from domain languages to the execution language.

Compilers are technically stagers, but it misses the goal. The goal of modern staging is to allow building programs that build programs to maximise reuse and automate program construction wherever possible. It would be great if one day functional requirements of a program are the program.

See "Generative Programming" by Czarnecki and Eisenecker (ISBN-13: 978-0201309775).

Answer 3

The answer is given in the technical perspective piece for the article in question [1]. The problem under consideration is the area of tension between general and specific code:

Programs can be written to be either general-purpose or special-purpose. General-purpose code has the advantage of being usable in a variety of situations, whereas special-purpose code might be written in a way that takes advantage of unique characteristics of the execution environment and thus gain efficiency at the cost of reusability.

Of course we want to resolve this tension, that is achieve general code and specific implementation:

We can ask the question: Is it possible to write code so that it is general-purpose but then have it automatically specialize itself to the situation at hand during execution?

This has given rise to the idea of having (general) programs (re)write themselves at runtime to accomodate for a specific situation:

As a result, an important direction of research has involved the search for language and compiler technology that can allow programmers to write general-purpose code that is then correctly and efficiently turned into high-performance specialized code at run-time.

I guess Java's JIT is a good example. One particular idea is multi-stage programming, which Lee explains like this:

In this line of research, one of the core ideas is the concept of staging. We imagine the execution of a program proceeding in a series of stages, each one calculating values that are used by later stages. What we seek, then, is to write the program code so that somehow these stages are made apparent. If this is accomplished, then we can arrange for the later-stage code to be compiled into code generators that optimize against the results of earlier-stage computations.

That is, "staging" is a way of looking at suitable functions/code that identifies phases in the computation/execution which can be simplified knowing the results of former phases. "Delaying" computation as in the first quote in the question may be a necessary side effect in order to separate stages properly, but it is not the point.

Rompf and Odersky mention fast fourier transform as an example which may be instructive.

---

1. The fox and the hedgehog: technical perspective by Peter Lee (2012)