21
$\begingroup$

For most modern programming languages, an LSP (Language Server Protocol) server needs to be developed, which requires reusing/rewriting some of the existing code that is already used by the compiler. So, how can a compiler be designed to accommodate this need from the start?

Credit to gavinhoward for the idea on Area 51.

$\endgroup$
2
  • 5
    $\begingroup$ 3 close votes but 2 upvotes and no downvotes. Not a single comment. Why? $\endgroup$ Commented May 21, 2023 at 21:34
  • $\begingroup$ And now there’s 3 downvotes without a comment. Yes, I know that you’re allowed to vote however you want and you don’t have to comment but WHOSE DOWNVOTING EVERY GOOD QUESTION LATELY? Please stop $\endgroup$ Commented Jul 3, 2023 at 10:23

3 Answers 3

11
$\begingroup$

That said, after deciding that LSP would essentially be required for my language, I had to figure this out. Here is my list of factors.

Performance

A user expects an LSP server to respond after every keypress. Typing 120 words a minute means that, with five characters per word and one space, they type 12 characters per second. Let's round that down to 10.

This means your server has to respond within 100 milliseconds.

That's a tall order for a compiler.

This is the biggest reason that compiler-based LSP servers don't really happen; making batch-based compilers fast enough to work that fast is hard.

Why? Because LSP is an entirely different use case than compilation. Compilation is batch; LSP is interactive. Compilation is all-at-once; LSP is incremental.

This mismatch is fundamental.

Of course, the compiler doesn't have to do everything it normally does for LSP; it just has to parse and validate. So it is possible, but it's hard.

Often, based on the design of the language, it makes more sense to have a separate program anyway.

Which brings me to...

Language Design

Language design matters a lot.

If your compiler is multi-pass, that's going to hurt in several ways.

First, it's hard to implement incremental compilation in a multi-pass compiler. I tried. My language design changed because of this.

Second, multiple passes means more time taken.

Third, multiple passes means that information is most likely not local.

How to Do It

So let's assume that you are unwilling to change your language design for LSP. What do you do?

Easy: don't do it.

I suggest you actually plan on writing an LSP server that is separate from the compiler. Really. Just plan on it. Their use cases are completely different and require different architectures in most cases.

Save yourself the pain and just write two different programs.

(Edit: Of course, you could still do the 20% effort upfront to get the compiler 80% of the way there and then share code between them. But that work does have to happen upfront.)

But if you plan on changing your language design like I did, here's what to do:

  • Make your language single-pass.
  • Make sure your compiler can continue after parse errors. This means having a way to recover. Usually, this means looking for the next semicolon or right brace and start again from there.
  • Make sure your compiler can generate semantic information, such as labeling what is a function, what is a type, etc.
  • Make sure your compiler stores location and span information for every token.
  • Make it possible for each compilation unit to be standalone and not depend on other compilation units. Yes, this is what C/C++ did better than everyone else. (This has the benefit of preventing your compiler from becoming a build system and making it easier to build in parallel.)
  • Don't require header files; that's slow. Your compiler should be able to take in that information some other way because in LSP mode, it should store that information and use it as-is without touching disk.
  • If you can make it possible to restart parsing from random spots, do it. For example, if you can store the order in which the functions were defined, then your server could figure out what functions came before the location of a change, delete them, and reparse from the change.
$\endgroup$
5
  • 8
    $\begingroup$ I think “make your language single-pass” is actively counterproductive advice. In addition to simply being an unrealistic goal for any serious modern programming language, it makes things harder to incrementalize because you can’t choose to just run some of the passes. You don’t want to be paying for optimization and code generation on every single edit to your program, so it benefits you to split those out into separate passes. That way, you can just run the first few passes (parsing and typechecking) to get results more quickly. $\endgroup$
    – Alexis King
    Commented Jul 2, 2023 at 18:43
  • 1
    $\begingroup$ @AlexisKing by single pass, I mean one parsing pass over the compilation unit, not one pass to get the results. In other words, I meant one pass like C is, not one pass like smashing parsing, code gen, and optimization into one mess. As for why it needs to be one pass like C, well, I have the implementation scars of a long-dead multi-pass version that didn't work. The current version has four passes: parsing, type-checking, optimization, and machine code gen. But it only does one parsing pass unlike a lot of other languages. $\endgroup$ Commented Jul 2, 2023 at 19:04
  • $\begingroup$ No modern C compilers are one-pass in that sense. It is not a realistic way to engineer a serious modern compiler. I can believe that you managed to get one working for a small hobby project, but I don’t think it is good advice to give to other people. $\endgroup$
    – Alexis King
    Commented Jul 2, 2023 at 19:07
  • 1
    $\begingroup$ @AlexisKing I appreciate your knowledge and your blog (I'm a reader), so I'd like you to explain why it's not a realistic way to engineer a serious modern compiler since this is the second compiler I've implemented that way. I assume the answer will take more space than a comment, so I'll post a question within an hour or so. $\endgroup$ Commented Jul 2, 2023 at 19:16
  • 1
    $\begingroup$ Please do! I’d be happy to answer it. $\endgroup$
    – Alexis King
    Commented Jul 2, 2023 at 20:03
8
$\begingroup$

Gavin's answer makes a lot of great points, and I don't disagree with them. Furthermore, I'm going to risk repeating some of his closing advice, but I hope I included at least some context that makes the answer worthwhile to read.

If you end up deciding you want to marry your compiler to the LSP, or if you even just want to make your compiler amenable to being used in editor/IDE tooling, then I would take a look at some of the design and implementation of rust-analyzer. While it isn't actually a compiler itself, it implements a Rust frontend that is both incremental and resilient. These traits are important because when used in conjunction with an editor we always want our tooling to respond as quickly and as completely as possible, as opposed to failing to check/format/build later code for the sole reason of an earlier, unrelated piece of code not being well-formed.

rust-analyzer's dev docs on syntax describe some of the design that make it very resilient for parsing. One of the rust-analyzer maintainers has recently blogged about resilient parser implementations. The same maintainer has also worked on an incremental computation framework for Rust called salsa, which could be interesting to look at. Here is a blog post on query-based compiler architectures that makes reference to both salsa and using a compiler in language server tooling.

$\endgroup$
1
  • $\begingroup$ And thank you so much for the links! I will be reading deep for the next few days. $\endgroup$ Commented May 28, 2023 at 6:44
4
$\begingroup$

One thing you can do to save a lot of time on LSP re-parsing and re-compiling your code on frequent changes: use a parser with memoisation. Packrat, for example, or any other similar approach. This way it'll be very easy to invalidate the parsed region affected by an edit and then reparse the entire unit, whatever it is - your parser should know the boundaries of your units, be it a module, a class, a function, an entire file, etc.

Likewise, you can run further lowering, typing passes, etc., only on things that changed and that depend on what you've changed.

It can all be easily made a part of your compiler, because why would you write two different parsers anyway? A side effect of having syntax highlighting, type hints, pretty-printing and all that as a side effect of compilation is that you can add formatted literate code generation to the compiler.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .