6 ms·

Query-Based Compiler Architectures

117 points by matt_d 6y ago

hobo_mark 6y ago
Reminded me of this lecture from last year: Responsive compilers - Nicholas Matsakis - PLISS 2019 https://youtube.com/watch?v=N6b44kMS6OM https://youtube.com/watch?v=N6b44kMS6OM (Of course it's based on Rust, but the same principles would be applicable elsewhere)
- fluffything 6y ago
  The blog post does cite salsa, which is the frame work that was created to create Lark, the language that was created to protoype Rust's implementation of query-based compilation. https://github.com/lark-exploration/lark https://github.com/lark-exploration/lark https://github.com/salsa-rs/salsa https://github.com/salsa-rs/salsa
_bxg1 6y ago
Really interesting ideas, though I think the content is hampered a bit by the use of what I think is Haskell in the examples. It hinders accessibility when you're having to learn two unrelated things in parallel, and I don't think the average audience for this piece can be expected to know Haskell well enough to follow along effectively.
- yingw787 6y ago
  I think the author linked a Rust example of a query-based compiler: https://github.com/salsa-rs/salsa https://github.com/salsa-rs/salsa
- vajrabum 6y ago
  This is from a blog that has 2 posts. Both discuss a compiler for an experimental dependently typed language. That's a fairly specialized topic.
- Ericson2314 6y ago
  They are talking about the idea, and their implementation, which is in Haskell.
foobar_ 6y ago
Can some one build HN filter for these type links. Sick of all the political bike shed.
sly010 6y ago
I have some negative feelings about this trend (of increased integration in compilers), but I can't quite put my finger on the reason. Before the language server idea came along all compilers were pure functions. Dependency management and caching were the responsibility of the build system. A flexible build system could handle things that the language designers haven't though of, like code generation, mixed language projects, linking between different languages etc. Things are very composable and extendable and everything can be modeled as a DAG. With language servers and incremental compilation becoming part of some long running compiler process the responsibilities are blurred, it all leads to increased integration, less flexibility and when things break, you will not be able to tell why. Aren't we giving up too much to get faster recommendations in IDEs?
- deleted 6y ago
  [deleted]
- ratmice 6y ago
  The assertion "all compilers were pure functions", is a strange one, because it is almost entirely backwards. the purity of compilers was abandoned almost immediately (when they started creating a file a.out and writing to that instead of writing binaries to stdout, and in the c-preprocessor when #include was added, and in the assembler with the .incbin directive, If compilers were pure, there would be zero need for Makefile style build systems which stat files to see if they have changed. while Makefiles and their ilk are modeled as a dag is true, The only reason an external file/dag is actually necessary is due to impurity in the compilation process. There have been very few compilers which have even had a relatively pure core (TeX is the only one that I can actually think of), language servers are if anything moving them to a more pure model, simply due to the fact that its sending sources through some file descriptor rather than having to construct some graph out of filenames. Long story short, "purity" in the sense of a compiler is a function from source text -> binary text, "foo.c" is not source text, and a bunch of errors is not binary text. At least language servers take in source text as input.
  - Ace17 6y ago
    > The only reason an external file/dag is actually necessary is due to impurity in the compilation process. No compilation process can know about the parts of your project written in another language.
mshockwave 6y ago
Good...but why does the author think modern compilers / language servers DON'T do caching? Or in another way: why does the author think caching mechanism in modern compiler / language server is insufficient? I think the author is proposing a caching mechanism that has finer granularity and design the whole system around this idea from day one. But first, at least many components in LLVM have been doing caching for a long time (e.g. OrcJIT has a pretty decent caching layer and libTooling also supports incremental parsing with AST caches). Second, what is the memory overhead of this (fine grain caching) design when it's facing some larger input program in real world (e.g. OS kernel)? Does it scale well? I know it's refurbished from an old post so I probably shouldn't be so harsh. But it will be better to compare some old ideas against state-of art works and found some insights rather than doing pure archaeology
- matklad 6y ago
  I am not the author, but work in the same domain. Empirically, existing compilers are impossible to turn into good IDEs, unless the language has header files and forward declarations. Otherwise, you get a decent IDE by doing one of the following: * writing two compilers (C#, Dart, Java(and, in some sense, every major language, supported in JetBrains tooling) * starting with IDE compiler from the start (Kotlin & TypeScript) The two examples where I’ve heard a batch compiler was successfully used to build a language server are C++ and OCaml (haven’t tried these language servers myself though). Curiously, they both use header files, which means that it’s the user who does fine grained caching. I don‘t see how caching in LLVM is relevant to the task of building LSP servers. In terms of prior art, I would suggest studying how IntelliJ works, specifically looking at the stubs: https://www.jetbrains.org/intellij/sdk/docs/basics/indexing_and_psi_stubs.html https://www.jetbrains.org/intellij/sdk/docs/basics/indexing_...
  - seanmcdirmid 6y ago
    There are ways to turn batch compilers into incremental IDE compilers with some tree and effect caching on the periphery of the compiler. You can even go all the way up to the eval level for a full live programming environment. You don’t need module signatures if you are willing to trace dependencies dynamically. See https://www.microsoft.com/en-us/research/publication/programming-with-managed-time/ https://www.microsoft.com/en-us/research/publication/program....

117 points by matt_d 6y ago

Reminded me of this lecture from last year: Responsive compilers - Nicholas Matsakis - PLISS 2019 https://youtube.com/watch?v=N6b44kMS6OM https://youtube.com/watch?v=N6b44kMS6OM (Of course it's based on Rust, but the same principles would be applicable elsewhere)

fluffything 6y ago
The blog post does cite salsa, which is the frame work that was created to create Lark, the language that was created to protoype Rust's implementation of query-based compilation. https://github.com/lark-exploration/lark https://github.com/lark-exploration/lark https://github.com/salsa-rs/salsa https://github.com/salsa-rs/salsa

_bxg1 6y ago

Really interesting ideas, though I think the content is hampered a bit by the use of what I think is Haskell in the examples. It hinders accessibility when you're having to learn two unrelated things in parallel, and I don't think the average audience for this piece can be expected to know Haskell well enough to follow along effectively.

yingw787 6y ago
I think the author linked a Rust example of a query-based compiler: https://github.com/salsa-rs/salsa https://github.com/salsa-rs/salsa
vajrabum 6y ago
This is from a blog that has 2 posts. Both discuss a compiler for an experimental dependently typed language. That's a fairly specialized topic.
Ericson2314 6y ago
They are talking about the idea, and their implementation, which is in Haskell.

foobar_ 6y ago

Can some one build HN filter for these type links. Sick of all the political bike shed.

sly010 6y ago

I have some negative feelings about this trend (of increased integration in compilers), but I can't quite put my finger on the reason. Before the language server idea came along all compilers were pure functions. Dependency management and caching were the responsibility of the build system. A flexible build system could handle things that the language designers haven't though of, like code generation, mixed language projects, linking between different languages etc. Things are very composable and extendable and everything can be modeled as a DAG. With language servers and incremental compilation becoming part of some long running compiler process the responsibilities are blurred, it all leads to increased integration, less flexibility and when things break, you will not be able to tell why. Aren't we giving up too much to get faster recommendations in IDEs?

deleted 6y ago
[deleted]
ratmice 6y ago
The assertion "all compilers were pure functions", is a strange one, because it is almost entirely backwards. the purity of compilers was abandoned almost immediately (when they started creating a file a.out and writing to that instead of writing binaries to stdout, and in the c-preprocessor when #include was added, and in the assembler with the .incbin directive, If compilers were pure, there would be zero need for Makefile style build systems which stat files to see if they have changed. while Makefiles and their ilk are modeled as a dag is true, The only reason an external file/dag is actually necessary is due to impurity in the compilation process. There have been very few compilers which have even had a relatively pure core (TeX is the only one that I can actually think of), language servers are if anything moving them to a more pure model, simply due to the fact that its sending sources through some file descriptor rather than having to construct some graph out of filenames. Long story short, "purity" in the sense of a compiler is a function from source text -> binary text, "foo.c" is not source text, and a bunch of errors is not binary text. At least language servers take in source text as input.
- Ace17 6y ago
  > The only reason an external file/dag is actually necessary is due to impurity in the compilation process. No compilation process can know about the parts of your project written in another language.

mshockwave 6y ago

Good...but why does the author think modern compilers / language servers DON'T do caching? Or in another way: why does the author think caching mechanism in modern compiler / language server is insufficient? I think the author is proposing a caching mechanism that has finer granularity and design the whole system around this idea from day one. But first, at least many components in LLVM have been doing caching for a long time (e.g. OrcJIT has a pretty decent caching layer and libTooling also supports incremental parsing with AST caches). Second, what is the memory overhead of this (fine grain caching) design when it's facing some larger input program in real world (e.g. OS kernel)? Does it scale well? I know it's refurbished from an old post so I probably shouldn't be so harsh. But it will be better to compare some old ideas against state-of art works and found some insights rather than doing pure archaeology

matklad 6y ago
I am not the author, but work in the same domain. Empirically, existing compilers are impossible to turn into good IDEs, unless the language has header files and forward declarations. Otherwise, you get a decent IDE by doing one of the following: * writing two compilers (C#, Dart, Java(and, in some sense, every major language, supported in JetBrains tooling) * starting with IDE compiler from the start (Kotlin & TypeScript) The two examples where I’ve heard a batch compiler was successfully used to build a language server are C++ and OCaml (haven’t tried these language servers myself though). Curiously, they both use header files, which means that it’s the user who does fine grained caching. I don‘t see how caching in LLVM is relevant to the task of building LSP servers. In terms of prior art, I would suggest studying how IntelliJ works, specifically looking at the stubs: https://www.jetbrains.org/intellij/sdk/docs/basics/indexing_and_psi_stubs.html https://www.jetbrains.org/intellij/sdk/docs/basics/indexing_...
- seanmcdirmid 6y ago
  There are ways to turn batch compilers into incremental IDE compilers with some tree and effect caching on the periphery of the compiler. You can even go all the way up to the eval level for a full live programming environment. You don’t need module signatures if you are willing to trace dependencies dynamically. See https://www.microsoft.com/en-us/research/publication/programming-with-managed-time/ https://www.microsoft.com/en-us/research/publication/program....