5 ms·

Against Query Based Compilers

83 points by surprisetalk 8mo ago

armchairhacker 8mo ago
> In Zig, every file can be parsed completely in isolation...every name needs to be explicitly declared (there’s no use *)... > In contrast, you can’t really parse a file in Rust...Expanding macros requires name resolution, which, in Rust, is a crate-wide, rather than a file-wide operation...Similarly, the nature of the trait system is such that impl blocks relevant to a particular method call can be found almost anywhere... matklad doesn't even mention dynamic languages, where perfect name resolution is undecidable. "Fast static analysis, easy static analysis, language designed for static analysis - pick two". Rust's IDE integration is fast and deep, and I've heard TypeScript's is too, so "easy static analysis" may not be important today. I believe it will as coding evolves due to LLMs, albeit without evidence and I'm not quite sure how.
- foolswisdom 8mo ago
  I would really appreciate if rust analyzer was faster, actually. It feels even worse with the fact that you need to save the file before it updates the type checking (though I assume it's because it's too slow to feel smooth if you do it while typing?).
  - Rusky 8mo ago
    The reason rust-analyzer doesn't update diagnostics until you save is historical. Originally, people tried to build IDE support by reusing rustc itself, but this proved too slow and cumbersome at the time. Rust-analyzer reimplemented the frontend in a more IDE-friendly architecture, but focused more on name resolution than on type checking. So it delegated diagnostics to literally just running `cargo check`. As parts of rustc get rewritten over time (the trait solver, borrow checker) they have also been made more IDE-friendly and reusable, so rust-analyzer is slowly gaining the ability to surface more type checking diagnostics as you edit, without delegating to `cargo check`.
- rendaw 8mo ago
  > "Fast static analysis, easy static analysis, language designed for static analysis - pick two" Where does this come from and what's the explanation?
  - armchairhacker 8mo ago
    I made it up, although maybe I’m not the first? The third should actually be “language not designed around static analysis” - You can write a static analysis that is fast and straightforward if you design the language around it (fast + easy + !language) - Otherwise, you’ll run into features that prevent that. Ex (stolen from an above comment): name resolution within unqualified imports - For many such features, you can write a brute-force solution. Ex: scan all possible definitions within the unqualified import until you find the target name (!fast + easy + language) - Or you can optimize this solution, using incremental cached lookup tables (fast + !easy + language) Of course, there are languages with features that make most static analyses for them neither fast nor easy (ex: for name resolution, eval or macros). But it holds in many cases, ex: - Parsing: basic syntax (!language), GLR parser or LL parser with big alternatives (!fast), IELR parser or LL parser with smart alternatives (!easy) - Type inference: many type annotations (!language), brute-force enumerate candidates (!fast), Hindley-Milner or bidirectional, possibly extended for features like trait resolution (!easy) - Allocation: manual (!language), put everything on the heap (!fast), heuristics, implicit boxing and unboxing (!easy) There’s a trend (I also don’t know where it originates) that most “data processing” problems can be solved with an easier slower or trickier faster algorithm (hence, competitive programming). Static analyses are this class of problem, but for them (sometimes) there is a third option: simplify the problem by putting hints in the language.
- deleted 8mo ago
  [deleted]
- SkiFire13 8mo ago
  > "Fast static analysis, easy static analysis, language designed for static analysis - pick two" I think you might have meant "language *not* designed for static analysis".
recursivecaveat 8mo ago
Mass unqualified imports is a feature that I really dislike in languages. At least please make it less syntactically convenient so people are not drawn to it. Trawling around to find out where symbols come from has wasted a lot more of my time than unqualified imports have ever saved. Using a very short alias gets you 90% of the way there anyways.
- jiggawatts 8mo ago
  > Trawling around to find out where symbols come from has wasted a lot more of my time than unqualified imports have ever saved. Why aren't you using an IDE with "navigate to definition" conveniently bound to something like middle-click or ctrl-click? I haven't used a language/IDE combination without this feature in decades.
  - jitl 8mo ago
    the difference is "i see this information at a glance" versus "i need to move the cursor to each unknown name to ask my ide a question". i think doing the command-click or even just hovering a bunch of unknown symbols is "trawling around". this goes doubly when doing code reviews; i'd prefer code make sense to my grug brain when i view it outside an ide. (sure, i can pull the code down to do an in-depth review in my ide, but the tax for unqualified names is starting to pile up...)
    - jcgrillo 8mo ago
      similarly, I can step through a program in the debugger and see how it works--or at least that it works--but the whole point of having a programming language in the first place is that (if I use it right) I can understand the program without running it
    - jiggawatts 8mo ago
      > the difference is "i see this information at a glance" versus "i need to move the cursor to each unknown name to ask my ide a question". Is it really "at a glance"? In most languages either by convention or requirement the "import" or "using" statements are collected at the beginning of a file. Once you've scrolled down even a few lines, the context is gone. Also, determining what exactly is bound where is decidedly non-trivial in many languages due to keywords such as "var" and "let", overloaded function/method definitions, etc... Sure, a human can do this with 95% or better accuracy, but that 5% can be a killer during a complex troubleshooting session if you guess wrong. That's why I strongly prefer IDEs and having a purely mechanical process to resolve the dependencies so I can know exactly what things are instead of hoping my intuitions were correct.
jiggawatts 8mo ago
> This is provably impossible to make usefully incremental. The encryption can be implemented as a graph of function calls, and you can apply the general incremental recipe to it. It just won’t be very fast. The specific example is bogus. Merkle trees and their many variants exist to solve precisely this problem. For more compiler-specific scenarios there exist vaguely similar solutions to the issues introduced by incremental compilation such as splitting up monolithic executables into many small dynamically loaded libraries (only during development time), or taking that to the extreme, hot code reloading at the function level. > ... only because Zig language is carefully designed to allow this. Is the key point. Rust wasn't designed for incremental compilation, and most legacy languages like C only allow it in a useful way because they were designed in the era "kilobytes" of system memory and hence they're very frugal in their design. Other than Zig, the only modern language I'm aware of that was "co-designed" for efficient compilation and incremental reload is Jai. > Expanding macros requires name resolution, which, in Rust, is a crate-wide, rather than a file-wide operation. Sure, but macros change infrequently, so that ought to be a highly cacheable pure function for most edits. > The above scheme works only if the language has a property that changing the body of function foo (not touching its signature) can’t introduce type errors into an unrelated function bar. AFAIK Rust and most other statically typed languages have this property. Optimisations such as inlining can mess with the cacheability of code-gen in all languages.
- lostmsu 8mo ago
  No need to go into obscurity. C# and specifically Roslyn are designed for incremental reload.
- skybrian 8mo ago
  Doesn't Go qualify? It has a fast compiler and it was designed that way.
  - orangeboats 8mo ago
    Go is pretty minimalistic as a language though. At least I don't feel that it has the same expressiveness as either Zig or Rust.
jitl 8mo ago
i agree on the whole that query is a good second line of defense versus the primary strategy. however you can do query based strategy and still use a diff/patch approach for some queries, just make the previous state of a query one of its inputs. query based compilers are equivalent to component UI frameworks / signals / self-adjusting computation / spreadsheets. signia signals library implements this idea of using the previous output + diffs to compute the next output (https://signia.tldraw.dev/docs/incremental#using-diffs-in-computed https://signia.tldraw.dev/docs/incremental#using-diffs-in-co...)
zarzavat 8mo ago
> In contrast, you can’t really parse a file in Rust. Rust macros generate new source code, so parsing can’t be finished until all the macros are expanded. Rust needs macros because the language is extremely strict and verbose. Macros are the main escape hatch, allowing you to simplify your code while maintaining memory safety without a GC. Zig doesn't have memory safety as a goal so it seems like an unfair comparison.
- Philpax 8mo ago
  I'm a Rust main, but this argument seems... incorrect? You would not need macros for Rust to remain a usable memory-safe language. They certainly make it easier, but they're not necessary. It would be perfectly possible to design a variant of Rust that gets you to 80-90% of Rust's usability, with the same safety, without macros.
  - kobebrookskC3 8mo ago
    how would you implement https://doc.rust-lang.org/stable/std/pin/macro.pin.html https://doc.rust-lang.org/stable/std/pin/macro.pin.html without macros? a macro is used to shadow the original variable so that you can't move it (safely) after you pin it
    - steveklabnik 8mo ago
      Regular variable definition shadows. Macros expand to regular Rust code, they could always be replaced by the expanded body.
      - kobebrookskC3 8mo ago
        yes, but the code inside is unsafe. the pin macro is like a safe function.
        steveklabnik 8mo ago
        I'm not sure what that has to do with anything. The macro isn't what makes it safe. The unsafe code being properly written is.
Panzerschrek 8mo ago
I have a language server implementation for my programming language. Since it has been developed much later than its compiler, no stuff like query-based redesign was viable to implement. So, I just adopted the compiler codebase for language server needs in a tricky way: on each document change I just redo parsing, but not other compilation steps and use parsing results to perform fetches from name tables built previously - for some older document state. This state is costly to update and it's done only once in a while and only if input document is syntactically-correct. This approach works surprisingly well (it's fast and completion is mostly correct) and doesn't require throwing the whole compiler code away. Even more, I can't imagine how people write language servers with full reprocessing on each document change (even with query-based approach). How do they deal with broken syntax? isn't it generally impossible to recovery syntactic errors, so that the end result is as good as expected?
- armchairhacker 8mo ago
  I know Haskell’s LSP years ago just stopped on broken syntax, so the only diagnostic would be the syntax error and you would lose code actions. That was annoying, especially because the LSP was slow. JetBrains (not an LSP) works up to the syntax error, then recovers and works after. In some cases that are not hard to trigger (e.g. after a closing delimiter), the recovery is wrong and everything after is messed up. But in practice that’s rarely an issue; if I want those later diagnostics and code actions, I fix the delimiters, and the analysis updates quickly.
- norman784 8mo ago
  You need a fault tolerant parser, tree sitter is a good example on how it works in practice, your compiler should have the ability to run a few steps (parsing, symbol resolution, type checking, etc) with an incomplete/invalid AST. > isn't it generally impossible to recovery syntactic errors AFAIK Zig was designed in such way that, in most cases, you can parse each line independently, like their strings by default are single line, you need a special syntax for multiline strings that still are per line basis.
  - Panzerschrek 8mo ago
snthpy 8mo ago
> Similarly, the nature of the trait system is such that impl blocks relevant to a particular method call can be found almost anywhere. For every trait method call, you get a dependency on the impl block that supplies the implementation, *but you also get a dependency on non-existence of conflicting impls in every other file*! The last clause is a great point and one I will try to remember.
smj-edison 8mo ago
It seems like he's not arguing against query-based compilers per se, but rather he's arguing against the thinking that often comes with it. Namely, that you can amortize an expensive compilation process across incremental changes (which often doesn't work in practice because of the avalanche effect).
noelwelsh 8mo ago
The article doesn't mention the other side of the tradeoff, which is that features like Rust's traits or macros make the language more expressive. Given that Rust's LSP server is pretty snappy, these features don't seem to cause problem in practice for incremental compilation.
- gizmondo 8mo ago
  The author is the former lead developer of the Rust's LSP server, so it seems natural to have a preference for languages that would allow him to do a better job. Slow compilation (including incremental) is one of the most common complaints about Rust, despite a lot of effort spent on optimizations there. I think it would be good if more people are aware of the inherent downsides of maximizing expressiveness.
  - speed_spread 8mo ago
    Rust compilation is actually very fast if you keep things Java-esque : No macros, no monomorphization (every Trait dyn). Obviously most the ecosystem isn't built that way, leaning more on the metaprogramming style because the language makes it so convenient.

83 points by surprisetalk 8mo ago

> In Zig, every file can be parsed completely in isolation...every name needs to be explicitly declared (there’s no use *)... > In contrast, you can’t really parse a file in Rust...Expanding macros requires name resolution, which, in Rust, is a crate-wide, rather than a file-wide operation...Similarly, the nature of the trait system is such that impl blocks relevant to a particular method call can be found almost anywhere... matklad doesn't even mention dynamic languages, where perfect name resolution is undecidable. "Fast static analysis, easy static analysis, language designed for static analysis - pick two". Rust's IDE integration is fast and deep, and I've heard TypeScript's is too, so "easy static analysis" may not be important today. I believe it will as coding evolves due to LLMs, albeit without evidence and I'm not quite sure how.

foolswisdom 8mo ago
I would really appreciate if rust analyzer was faster, actually. It feels even worse with the fact that you need to save the file before it updates the type checking (though I assume it's because it's too slow to feel smooth if you do it while typing?).
- Rusky 8mo ago
  The reason rust-analyzer doesn't update diagnostics until you save is historical. Originally, people tried to build IDE support by reusing rustc itself, but this proved too slow and cumbersome at the time. Rust-analyzer reimplemented the frontend in a more IDE-friendly architecture, but focused more on name resolution than on type checking. So it delegated diagnostics to literally just running `cargo check`. As parts of rustc get rewritten over time (the trait solver, borrow checker) they have also been made more IDE-friendly and reusable, so rust-analyzer is slowly gaining the ability to surface more type checking diagnostics as you edit, without delegating to `cargo check`.
rendaw 8mo ago
> "Fast static analysis, easy static analysis, language designed for static analysis - pick two" Where does this come from and what's the explanation?
- armchairhacker 8mo ago
  I made it up, although maybe I’m not the first? The third should actually be “language not designed around static analysis” - You can write a static analysis that is fast and straightforward if you design the language around it (fast + easy + !language) - Otherwise, you’ll run into features that prevent that. Ex (stolen from an above comment): name resolution within unqualified imports - For many such features, you can write a brute-force solution. Ex: scan all possible definitions within the unqualified import until you find the target name (!fast + easy + language) - Or you can optimize this solution, using incremental cached lookup tables (fast + !easy + language) Of course, there are languages with features that make most static analyses for them neither fast nor easy (ex: for name resolution, eval or macros). But it holds in many cases, ex: - Parsing: basic syntax (!language), GLR parser or LL parser with big alternatives (!fast), IELR parser or LL parser with smart alternatives (!easy) - Type inference: many type annotations (!language), brute-force enumerate candidates (!fast), Hindley-Milner or bidirectional, possibly extended for features like trait resolution (!easy) - Allocation: manual (!language), put everything on the heap (!fast), heuristics, implicit boxing and unboxing (!easy) There’s a trend (I also don’t know where it originates) that most “data processing” problems can be solved with an easier slower or trickier faster algorithm (hence, competitive programming). Static analyses are this class of problem, but for them (sometimes) there is a third option: simplify the problem by putting hints in the language.
deleted 8mo ago
[deleted]
SkiFire13 8mo ago
> "Fast static analysis, easy static analysis, language designed for static analysis - pick two" I think you might have meant "language *not* designed for static analysis".

recursivecaveat 8mo ago

Mass unqualified imports is a feature that I really dislike in languages. At least please make it less syntactically convenient so people are not drawn to it. Trawling around to find out where symbols come from has wasted a lot more of my time than unqualified imports have ever saved. Using a very short alias gets you 90% of the way there anyways.

jiggawatts 8mo ago
> Trawling around to find out where symbols come from has wasted a lot more of my time than unqualified imports have ever saved. Why aren't you using an IDE with "navigate to definition" conveniently bound to something like middle-click or ctrl-click? I haven't used a language/IDE combination without this feature in decades.
- jitl 8mo ago
  the difference is "i see this information at a glance" versus "i need to move the cursor to each unknown name to ask my ide a question". i think doing the command-click or even just hovering a bunch of unknown symbols is "trawling around". this goes doubly when doing code reviews; i'd prefer code make sense to my grug brain when i view it outside an ide. (sure, i can pull the code down to do an in-depth review in my ide, but the tax for unqualified names is starting to pile up...)
  - jcgrillo 8mo ago
    similarly, I can step through a program in the debugger and see how it works--or at least that it works--but the whole point of having a programming language in the first place is that (if I use it right) I can understand the program without running it
  - jiggawatts 8mo ago
    > the difference is "i see this information at a glance" versus "i need to move the cursor to each unknown name to ask my ide a question". Is it really "at a glance"? In most languages either by convention or requirement the "import" or "using" statements are collected at the beginning of a file. Once you've scrolled down even a few lines, the context is gone. Also, determining what exactly is bound where is decidedly non-trivial in many languages due to keywords such as "var" and "let", overloaded function/method definitions, etc... Sure, a human can do this with 95% or better accuracy, but that 5% can be a killer during a complex troubleshooting session if you guess wrong. That's why I strongly prefer IDEs and having a purely mechanical process to resolve the dependencies so I can know exactly what things are instead of hoping my intuitions were correct.

jiggawatts 8mo ago

> This is provably impossible to make usefully incremental. The encryption can be implemented as a graph of function calls, and you can apply the general incremental recipe to it. It just won’t be very fast. The specific example is bogus. Merkle trees and their many variants exist to solve precisely this problem. For more compiler-specific scenarios there exist vaguely similar solutions to the issues introduced by incremental compilation such as splitting up monolithic executables into many small dynamically loaded libraries (only during development time), or taking that to the extreme, hot code reloading at the function level. > ... only because Zig language is carefully designed to allow this. Is the key point. Rust wasn't designed for incremental compilation, and most legacy languages like C only allow it in a useful way because they were designed in the era "kilobytes" of system memory and hence they're very frugal in their design. Other than Zig, the only modern language I'm aware of that was "co-designed" for efficient compilation and incremental reload is Jai. > Expanding macros requires name resolution, which, in Rust, is a crate-wide, rather than a file-wide operation. Sure, but macros change infrequently, so that ought to be a highly cacheable pure function for most edits. > The above scheme works only if the language has a property that changing the body of function foo (not touching its signature) can’t introduce type errors into an unrelated function bar. AFAIK Rust and most other statically typed languages have this property. Optimisations such as inlining can mess with the cacheability of code-gen in all languages.

lostmsu 8mo ago
No need to go into obscurity. C# and specifically Roslyn are designed for incremental reload.
skybrian 8mo ago
Doesn't Go qualify? It has a fast compiler and it was designed that way.
- orangeboats 8mo ago
  Go is pretty minimalistic as a language though. At least I don't feel that it has the same expressiveness as either Zig or Rust.

jitl 8mo ago

i agree on the whole that query is a good second line of defense versus the primary strategy. however you can do query based strategy and still use a diff/patch approach for some queries, just make the previous state of a query one of its inputs. query based compilers are equivalent to component UI frameworks / signals / self-adjusting computation / spreadsheets. signia signals library implements this idea of using the previous output + diffs to compute the next output (https://signia.tldraw.dev/docs/incremental#using-diffs-in-computed https://signia.tldraw.dev/docs/incremental#using-diffs-in-co...)

zarzavat 8mo ago

> In contrast, you can’t really parse a file in Rust. Rust macros generate new source code, so parsing can’t be finished until all the macros are expanded. Rust needs macros because the language is extremely strict and verbose. Macros are the main escape hatch, allowing you to simplify your code while maintaining memory safety without a GC. Zig doesn't have memory safety as a goal so it seems like an unfair comparison.

Philpax 8mo ago
I'm a Rust main, but this argument seems... incorrect? You would not need macros for Rust to remain a usable memory-safe language. They certainly make it easier, but they're not necessary. It would be perfectly possible to design a variant of Rust that gets you to 80-90% of Rust's usability, with the same safety, without macros.
- kobebrookskC3 8mo ago
  how would you implement https://doc.rust-lang.org/stable/std/pin/macro.pin.html https://doc.rust-lang.org/stable/std/pin/macro.pin.html without macros? a macro is used to shadow the original variable so that you can't move it (safely) after you pin it
  - steveklabnik 8mo ago
    Regular variable definition shadows. Macros expand to regular Rust code, they could always be replaced by the expanded body.
    - kobebrookskC3 8mo ago
      yes, but the code inside is unsafe. the pin macro is like a safe function.
      - steveklabnik 8mo ago
        I'm not sure what that has to do with anything. The macro isn't what makes it safe. The unsafe code being properly written is.

Panzerschrek 8mo ago

I have a language server implementation for my programming language. Since it has been developed much later than its compiler, no stuff like query-based redesign was viable to implement. So, I just adopted the compiler codebase for language server needs in a tricky way: on each document change I just redo parsing, but not other compilation steps and use parsing results to perform fetches from name tables built previously - for some older document state. This state is costly to update and it's done only once in a while and only if input document is syntactically-correct. This approach works surprisingly well (it's fast and completion is mostly correct) and doesn't require throwing the whole compiler code away. Even more, I can't imagine how people write language servers with full reprocessing on each document change (even with query-based approach). How do they deal with broken syntax? isn't it generally impossible to recovery syntactic errors, so that the end result is as good as expected?

armchairhacker 8mo ago
I know Haskell’s LSP years ago just stopped on broken syntax, so the only diagnostic would be the syntax error and you would lose code actions. That was annoying, especially because the LSP was slow. JetBrains (not an LSP) works up to the syntax error, then recovers and works after. In some cases that are not hard to trigger (e.g. after a closing delimiter), the recovery is wrong and everything after is messed up. But in practice that’s rarely an issue; if I want those later diagnostics and code actions, I fix the delimiters, and the analysis updates quickly.
norman784 8mo ago
You need a fault tolerant parser, tree sitter is a good example on how it works in practice, your compiler should have the ability to run a few steps (parsing, symbol resolution, type checking, etc) with an incomplete/invalid AST. > isn't it generally impossible to recovery syntactic errors AFAIK Zig was designed in such way that, in most cases, you can parse each line independently, like their strings by default are single line, you need a special syntax for multiline strings that still are per line basis.
- Panzerschrek 8mo ago

snthpy 8mo ago

> Similarly, the nature of the trait system is such that impl blocks relevant to a particular method call can be found almost anywhere. For every trait method call, you get a dependency on the impl block that supplies the implementation, *but you also get a dependency on non-existence of conflicting impls in every other file*! The last clause is a great point and one I will try to remember.

smj-edison 8mo ago

It seems like he's not arguing against query-based compilers per se, but rather he's arguing against the thinking that often comes with it. Namely, that you can amortize an expensive compilation process across incremental changes (which often doesn't work in practice because of the avalanche effect).

noelwelsh 8mo ago

The article doesn't mention the other side of the tradeoff, which is that features like Rust's traits or macros make the language more expressive. Given that Rust's LSP server is pretty snappy, these features don't seem to cause problem in practice for incremental compilation.

gizmondo 8mo ago
The author is the former lead developer of the Rust's LSP server, so it seems natural to have a preference for languages that would allow him to do a better job. Slow compilation (including incremental) is one of the most common complaints about Rust, despite a lot of effort spent on optimizations there. I think it would be good if more people are aware of the inherent downsides of maximizing expressiveness.
- speed_spread 8mo ago
  Rust compilation is actually very fast if you keep things Java-esque : No macros, no monomorphization (every Trait dyn). Obviously most the ecosystem isn't built that way, leaning more on the metaprogramming style because the language makes it so convenient.