What are staged functions (conceptually)?

Problem Detail: 

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)

Asked By : Raphael

Answered By : Uday Reddy

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2869