Proposal: Nanopass compiler support #668

This is a proposal for adding support for building Nanopass compilers to Langkit (most likely in a fork rather than something that will ever be upstreamed). I'm looking to get some feedback on this from other Langkit users to help refine this idea before I start implementing this. For some background on Nanopass compilers, refer to the following:

• https://andykeep.com/pubs/dissertation.pdf
• https://docs.racket-lang.org/nanopass/index.html

In short, from the second document:

The nanopass framework provides a tool for writing compilers composed of several simple passes that operate over well-defined intermediate languages. The goal of this organization is both to simplify the understanding of each pass, because it is responsible for a single task, and to simplify the addition of new passes anywhere in the compiler.

Currently it is entirely possible to write a Nanopass compiler using Langkit by manually writing a series of transformations, however this involves a lot of boilerplate, especially if one wants to formally define and check intermediate languages. I propose the addition of a set of new Langkit constructs to easily and formally define intermediate languages, pipelines, and transformers. I imagine this would look something like the following:

language parsed_foolang from grammar foolang_grammar;

language flat_foolang extends parsed_foolang {
    remove BlockStatement;
}

pass flatten_blocks : parsed_foolang -> flat_foolang
    with Libfoolang.Nanopass.Passes.Flatten_Blocks;

where Libfoolang.Nanopass.Passes.Flatten_Blocks is an Ada package with a Transform functions which takes some kind of rewriting handle. Langkit would generate the stub for this package.

In addition to remove, which makes a node invalid to have in a language, we would also have add to make a node valid and replace to change the shape of a node. I'm not sure exactly what this would look like yet.

Langkit would also be able to generate a pipeline function which calls a series of passes and checks that the outputs are valid between then.

That's about all I have on this idea for now, I plan to start prototyping it after I finish some other projects. Any ideas on how to design this are welcome.