5 ms·

I haven't read the Nanopass Framework paper, but... The idea of doing tons of compiler passes works well in a functional context, where functional separation i

• pilingual 11y ago
  Its purpose is for education. It's a great course, and I wish Dybvig would create a Coursera.
• sklogic 11y ago
  It is much more memory-efficient than thrashing a single graph over and over again. Rewriting and compacting trees is good for cache locality. Also, for the trivial rewrites (e.g., variable renaming) your compiler can safely choose to replace a cooying rewrite with a destructive update.
  • cbsmith 11y ago
    > It is much more memory-efficient than thrashing a single graph over and over again. Rewriting and compacting trees is good for cache locality. To be clear: if you are thrashing a single graph over-and-over again, you are doing many passes. Rewriting and compacting trees is just a way to make the multiple passes a bit less painful.
    • sklogic 11y ago
      > if you are thrashing a single graph over-and-over again, you are doing many passes. A single "pass" can be thrashing a graph many times too, think of the things like instcombine (in LLVM parlance) or ADCE. Essentially, compilation is rewriting of a source AST into the target machine code. It is up to you how to structure this rewrite, but the amount of work to be done remains the same. For a human it is much easier to structure such a rewrite as a sequence of very trivial changes. And a "sufficiently smart" compiler must realise that it can be done in less steps.
      • vidarh 11y ago
        > Essentially, compilation is rewriting of a source AST into the target machine code. While that is true of most modern compilers, do consider that there's the whole Wirth school of compilers that don't use an AST at all but generate machine code directly during parsing. > For a human it is much easier to structure such a rewrite as a sequence of very trivial changes. I'm not convinced, as I've written elsewhere, because while the changes may be trivial, you need to keep track of what a program is expected to look like in between each stage, and that becomes harder the more stages you introduce. E.g. my forever-in-progress Ruby compiler has a stage where it makes closures explicit: It allocates an environment to store variables in and rewrites variable accesses accordingly. For following stages the language I'm working on is different: I can no longer use closures. The more stages you have, the more language dialects you need to manage to mentally separate when working on the stages. And if you decide you need to reorder stages, you often have painful work to adapt the rewrites to their new dialects. The end result looks very simple. But try to make changes and it's not necessarily nearly as simple.
        • sklogic 11y ago
          > that don't use an AST at all but generate machine code directly during parsing It is not any different. A "sufficiently smart" compiler must be capable of fusing the lowering passes straight into a parser. Parsing is not that different from the other kinds of passes. > that becomes harder the more stages you introduce My usual trick is to have a "unit test" simple AST which, when building in a certain mode, is fed into the compilation pipeline and displayed with all the annotations. It helps a lot to understand what exactly each pass is doing. In the next version of my DSL for building compilers (currently a work in progress) it will even be a part of an IDE. > the more language dialects you need to manage to mentally separate when working on the stages Ideally, one pass = one language. Nanopass handles it nicely. I am using this approach for pretty much all kinds of languages, and never had any issues with too many IRs. In my book, the more distinct IRs, the better.
          • vidarh 11y ago
            > A "sufficiently smart" compiler must be capable of fusing the lowering passes straight into a parser. Given the state of compiler-generation tools (i.e. they're not even viable for generating parsers for production quality compilers), I have little hope of seeing a tool like that in the next couple of decades at least. Probably longer. At least in a form I'll be able to use for anything. > Ideally, one pass = one language. Nanopass handles it nicely. That was exactly what I see as a nightmare of a maintenance problem. Even with half a dozen or so variations at most, I find it annoying.
• cbsmith 11y ago
  I always notice how badly the phone mucked it up after the edit rule passes... That should be: "The idea of doing tons of compiler passes works well in a functional programming context, where functional separation is the preferred method of abstraction, and you can use composition to effectively transform all your passes into a single pass."
• exDM69 11y ago
  Doing many passes seems to be working very well in LLVM, which is definitely not targeted at or implemented with functional languages and is not a toy compiler framework for educational purposes but a full-blown industrial strength compiler framework. Yes, you need to take care of garbage collection (in one way or another) when you're manipulating tree and graph structures. I can't share your opinion about "ending badly". This has been shown to be a good strategy in practice.
• mamcx 11y ago
  Any example on how do nano-pass with F# or oCalm?