Anything recent happening with multi-stage programming?

I remember that 15 years ago, multi-stage programming was new and exciting. It promised simpler implementation of programming languages, better-than-macro support for strongly-typed languages, etc.

These days, I can't find any recent publications on the topic. Am I somehow looking in the wrong place? Has the topic fuzzed out?

In particular, I'm currently working on something extremely close to multi-stage programming, applied to a JavaScript JIT compiler. I'm very surprised that nobody seems to have worked on seriously applying multi-stage programming to JIT compilers. Am I missing something obvious?

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Multi-stage vs fexprs

I remember noticing the stir about multi-stage programming around that time (fifteen years ago), as I was working intensively on what can be fairly described as the exact opposite approach to much the same problem — both eliminating macros (which everyone loves to hate), but one approach multiplying the compilation stage to arbitrary numbers of stages while the other approach collapses the compile-time/run-time distinction to leave, in a sense, zero stages. There was a time I might have been more upset to realize I was apparently headed against a significant current in the mainstream, but back in the late eighties I was told it would be a waste of time to research abstraction because that had already been solved with the answer "object-orientation" — and that was on the cusp of the moment when OOP stopped looking invincible. The lesson I drew from it was that if you believe you're on to something, and it bucks a current fad, don't worry about the current fad because by the time you've developed your idea the current fad may have run its course anyway,

I think the multi-stage concept is inherently complex, hard to think about, which is a disadvantage and would likely limit how popular it could ever become. The trend may have already reached its natural limits by the time I was going public with my fexpr strategy. (I suppose it's possible the decline of the multi-stage approach might have been nudged along a bit, at that point, by recognition, as Kernel appeared on the stage, that there are interesting things to be found in the extreme opposite approach.)

But I too would be interested to hear from someone close to the multi-stage trend (as I am not), what's up with it lately.

Multi-stage programming and Generalized Arrows

Adam Megacz's work c. 2010 is the most recent paper I've studied on the subject, relating staged programs and arrows.

Multi-stage Programs are Generalized Arrows

His other paper generalizes further to multi-level languages - e.g. embedding a language that is smaller than its host.

Multi-Level Languages are Generalized Arrows

Stream fusion, to completeness

Haven't had time to work through it all, but this new paper is great.


Thanks for posting this. I just read through this paper and will have to study it some more but so far like it a lot. This bit makes me think we're not quite there yet:

It requires a non-trivial step: The threading of the state through the loop can be eliminated if the state is mutable.


One other comment I would make is that while the paper is a good source for stream optimization technique, I think the way it is embedded into ML's type system is far from ideal. I suspect this can be done much more cleanly with a representation system and want to revisit this as an example once I get that going.

Since you often mention

Since you often mention processes in relation to your language, this might also be of interest: Type-Specialized Staged Programming with Process Separation.

Multi-stage programming & JIT compilers

> I'm very surprised that nobody seems to have worked on seriously applying multi-stage programming to JIT compilers. Am I missing something obvious?

You might find this paper interesting:

Surgical precision JIT compilers (PLDI'14)
Tiark Rompf, Arvind K. Sujeeth, Kevin J. Brown, HyoukJoong Lee, Hassan Chafi, Kunle Olukotun

We present Lancet, a JIT compiler framework for Java bytecode that enables such a tight, two-way integration with the running program. Lancet itself was derived from a high-level Java bytecode interpreter: staging the interpreter using LMS (Lightweight Modular Staging) produced a simple bytecode compiler. Adding abstract interpretation turned the simple compiler into an optimizing compiler. This fact provides compelling evidence for the scalability of
the staged-interpreter approach to compiler construction.


Indeed, this seems to be very comparable to what we're working on at the moment, except taken from the exact opposite direction.


Lightweight multi-stage via temporal logics

I'm interested in staged programming for performance, i.e. so we can ensure certain functions are specialized at compile time, or that constants in a loop are evaluated only once. I recently received some inspiration from temporal logics, introducing two annotations: (now) and (later).

Annotations in my language are essentially identity functions that provide hints (about type, representation, breakpoints, etc.) to a compiler or interpreter. In this case, (now) indicates an expression should immediately evaluate, without waiting on further arguments. And (later) allows delaying requirement of (now) within a function body (until one argument is provided).

This technique describes intention for partial evaluation, and helps provide compile time warnings when things go wrong. Any models for partial evaluation, e.g. to make it easier to compose, are left to the programmers. Type safety analysis for the body of (later) functions is left as an exercise for a linter.

I believe that the biggest concern with staged programming isn't "getting it right" so much as knowing early when we get it wrong, so we aren't operating under false performance assumptions.

Lots of happening with multi-stage programming

Actually, lots of happening with staged programming. Here are a few recent

dbarbour wrote: "I recently received some inspiration from temporal
logics, introducing two annotations: (now) and (later)."
That is a very old idea: have you seen lambda-circle calculus of
Davies? His old paper has been finally published in the full form:

Finally, I just finished 100-page tutorial on staging and

staging in proof assistants (VeriML)

I enjoyed the VeriML work by Antonis Stampoulis with Zhong Shao in the early 2010s, that put staging as a central building block of a proof assistant. I think that this mode of use of staging may show up again in the future -- my (cursory) understanding of "A Metaprogramming Framework for Formal Verification" by Gabriel Ebner, Sebastian Ullrich, Jared Roesch, Jeremy Avigad, and Leonardo de Moura, 2017 is that Lean uses a form of elaboration-time staged computation for its tactics.

Meta-tracing and Partial evaluation in JITs

(I'm sure David is aware of those, and they are not exactly in-topic, but I thought that a root message to discuss those could be useful.)

While not directly multi-staged programming, there is a fair amount of specialization-related research ongoing within "JIT frameworks" such as Rpython (meta-tracing) and Truffle/Graal (specialized interpreters).

I expect that connections with multi-stage programming will be deepened when this research area becomes better-understood, similarly to the way multi-stage programming has been applied to make traditional partial-evaluation research more predictable.

You're right

You are, of course, right to mention them. But yes, I was aware of them :)