24
$\begingroup$

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)
$\endgroup$
  • $\begingroup$ What contradiction do you see between the two statements? To me, they look like they're talking about the same thing, with different emphasis. $\endgroup$ – Gilles 'SO- stop being evil' Jul 23 '12 at 17:59
  • $\begingroup$ @Gilles I don't need runtime code-generation/-compilation in order to delay evaluation of something (see continuables). It may very well be that it is just another emphasis (I admit that option in the question), but I can't really tell. $\endgroup$ – Raphael Jul 23 '12 at 18:04
  • $\begingroup$ You could check out the Julia programming language implementation and metaprogramming documentation on @generated functions: julia.readthedocs.org/en/latest/manual/metaprogramming/… $\endgroup$ – SalchiPapa Dec 5 '15 at 4:04
22
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ As far as I can see, so the difference between staged computation and partial evaluation is the form of $\phi'$? (there is some $\phi'$ that can obtained from staged computation but not from partial evaluation). $\endgroup$ – Ta Thanh Dinh Aug 18 '16 at 15:17
  • $\begingroup$ So what you mean is partial evaluation is an abstraction over multi-staged programming, meaning partial eval does not imply multi-staged programming but multi-staged programming implies partial eval. Whereby partial eval can be done in one or multiple stages since currying in functional languages does not necessarily involve multiple stages and generating code at runtime, right? $\endgroup$ – denis631 Sep 22 '18 at 14:52
  • 1
    $\begingroup$ Not exactly. A partial evaluator compiles an ordinary program to a 2-stage program and then runs its first stage. In staged programming, you write the multi-stage program yourself. $\endgroup$ – Uday Reddy Oct 8 '18 at 18:05
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @Raphael: Here is chapter three with the basics on domains and reuse. Look at even the optimisation you mention. FFT isn't done by staging to make it run faster. It's done so that the programmer doesn't have to calculate the table of values each time by hand, copy them in to the program, and build a big list. It's to minimise work done and reuse the basic steps over. Same with loop unrolling. Doing it by hand repeats info and can't be reused. $\endgroup$ – ex0du5 Jul 26 '12 at 16:25
  • $\begingroup$ This DSL point of view seems to limit staging to one level (one DSL compiler inside the program), right? $\endgroup$ – Raphael Aug 4 '12 at 15:58
  • 1
    $\begingroup$ @Raphael: It really depends on your point of view. Obviously, the concept adds no computational power when viewed simply as the source -> executable translation. We could just build a compiler for the DS language and be done. Where it's strength comes from is in iteration. When building libraries that will be used and expanded by projects in the future, natural stages appear inside the library boundaries. You may have a library that transforms object specifications into source for full serialisation, and then another library that builds the transport layer built on some dispatch spec... $\endgroup$ – ex0du5 Aug 6 '12 at 20:35
  • 1
    $\begingroup$ @Raphael: The staging may more naturally be made with multiple stages. If one piece of code has been having it's requirements change a lot over time, where others are much more stable, it may be appropriate due to "shearing layers" to separate the staging into into layers with more stable interfaces. You can then affect less of the system with changes and honor a staging form of the open-closed principle. Those are practical concerns that don't have mathematical necessity, but it's all based on practicality. We don't want a single compiler language, we want to allow evolution. $\endgroup$ – ex0du5 Aug 6 '12 at 20:40
5
$\begingroup$

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)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.