Lambda the Ultimate

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.

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

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

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

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.

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

https://www.cl.cam.ac.uk/%7Ejdy22/papers/staged-generic-programming.pdf


https://github.com/yallop/staged-generic-programming

http://okmij.org/ftp/meta-programming/index.html#SQUR

http://okmij.org/ftp/tagless-final/cookbook.html#simple-staging

http://okmij.org/ftp/meta-programming/calculi.html#refined-classif

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:

https://dl.acm.org/citation.cfm?id=3011069

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

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.

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