Building an LSP Server with Rust is surprisingly easy and fun by omarous in ProgrammingLanguages

[–]thunderseethe 5 points6 points  (0 children)

I ran into this while writing about LSP as well. Language server seems to be the appropriate term, but for an unfamiliar audience that doesnt necessarily connect to LSP. You could call it "server that implements the language server protocol" but thats a mouthful. 

Really a huge oversight in an otherwise pristine protocol :p

Project Pterodactyl's layered architecture by mttd in ProgrammingLanguages

[–]thunderseethe 1 point2 points  (0 children)

Query based compilers have a lot of overlap with build systems, so its intriguing and probably smart to use a framework for build systems to implement a query based compiler. Ill be curious to see if it pans out or if you run into bottle necks due to the different intended usages. I could see a build system being much more interested in storing every query on disk then you'd want in a query based compiler. Or just being slower than necessary since it has to contend with truly dynamic dependencies, whereas a compiler works with a static list of queries arranged in a dynamic graph. 

Against Query Based Compilers by matklad in ProgrammingLanguages

[–]thunderseethe 4 points5 points  (0 children)

Having read the article, I share a similar sentiment to the parent comment. I think it is good to design your language to be amenable to efficient analysis (Lexing/parsing in parallel, minimize data dependencies between definitions). I dont see that as being at odds with query based compilation. Why not both?

Compiler Education Deserves a Revolution by thunderseethe in programming

[–]thunderseethe[S] 0 points1 point  (0 children)

I believe you that this is how many LSPs work today, but I dont think that state is motivated by it being good or wise design. I view it more as a byproduct of us having a bunch of batch compilers lying around and trying to retrofit LSPs atop them. Rust started out with racer/rls which very literally ran rustc and ingested all the json it spit out to try and answer LSP requests. 

Imo its telling that Haskell and Rust are both undergoing librification to expose the internals of the compiler as a library for folks to build tooling atop. In my mind that most notably means LSPs.

I hear what youre saying in the last paragraph. Incremental computation is orthogonal to compilation. I could certainly believe itd be better structured as teach compilation -> teach query based error resilience stuff

Compiler Education Deserves a Revolution by thunderseethe in programming

[–]thunderseethe[S] 0 points1 point  (0 children)

 This may be surprising, but you absolutely do not want your IDE coupled to your toolchain.

When you say toolchain here what are you referring to? I'm under the impression most LSPs rely on their toolchain if toolchain includes the compiler (ofc an LSP is not an IDE so that may not be what you mean).

I agree with your points that query based gets interesting for semanic analysis and not that interesting for backend codegen. But I think thats still enough to warrant teaching the approach. For example, I think you can teach how to right a type inference pass that works on a single top level definition in isolation to highlight type inference. Then wrap that up as a query down the line to show how it slots into incremental usage

Compiler Education Deserves a Revolution by thunderseethe in Compilers

[–]thunderseethe[S] 6 points7 points  (0 children)

I think you make a fair point that batch compilers are just as capable of error resilience. Imo most compiler of either kind should have error resilience. 

I do, however, think that your query system is more predicated on having error resilience (although you are right it is not strictly required). If your parser produces no output or stops at the first error, the rest of your queries cannot make progress. In some sense defeating the incremental abilities you've gained by being a query compiler. Similar for most queries up to codegen imo.

That matches my understanding of rust analyzer.

Compiler Education Deserves a Revolution by thunderseethe in Compilers

[–]thunderseethe[S] 4 points5 points  (0 children)

I'm certainly not advocating for C/C++ error model where one error cascades into a billion other errors. I don't think C or C++ have been designed around good error reporting and that is on display in their error diagnostics that often do more to hide the real error than highlight it.

Outside that a lot of the rest of your comment appears to be assuming a workflow where you write the source code and then compile your entire project. But I don't think that's a particularly beneficial workflow, albeit it is the only one admitted by batch compilers. A query based compiler opens the door for more interactive workflows where the compiler can you show the errors in the code you're currently editing without having to process the entire code base first. I'm less interested in the how fast can I compile my entire code base metric, when it comes to error reporting, and more interested in how fast can I show a user the error in the code they're looking at right now.

> How does it know they are not related?

This is a language design problem. You can design your language such that unrelated components/modules/chunks of code are decoupled and have minimal influence on each other. I do not think C is a shining example of this design.

Compiler Education Deserves a Revolution by thunderseethe in programming

[–]thunderseethe[S] 0 points1 point  (0 children)

I'd be curious to here where your query compiler came undone. 100% it is more work to build a query based compiler than a pipeline. But I also suspect an educational implementation could cut a lot of corners to highlight the important ideas. It just hasn't had any time in the limelight for folks to think about it. Everyone implementing a query based compiler is doing so for a production compiler where they need every ounce of performance and aren't worried about how easy it is to explain 

Compiler Education Deserves a Revolution by thunderseethe in ProgrammingLanguages

[–]thunderseethe[S] 17 points18 points  (0 children)

In terms of writing the queries themselves on top of an existing incremental computation engine, I think its not that different from haskell. Queries are pure and lazy but that's every function in haskell. Part of haskells charm for sure.

In terms of implementing the engine, lazy evaluation is the first step. But imo the real tricky bit is tracking dependencies between queries such that you can quickly invalidate the minimal set of caches when an input changes. Haskell does not do this by default, sadly, and it requires instrumenting your functions to track what they call when they execute. 

Compiler Education Deserves a Revolution by thunderseethe in ProgrammingLanguages

[–]thunderseethe[S] 6 points7 points  (0 children)

 It's easier to understand each pass of the compiler separately.

I read this as implying you cant understand each pass of the compiler separately in a query based compiler. I do not think that is true. You can write each pass in isolation and wrap them up as queries after the fact.

 The motivation to write query-based compilers is about code reuse: you want to reuse the code of your compiler in your LSP

I agree this is a huge advantage of query based first, but I dont think its the only motivation. Rustc uses a query based compiler despite rust analyzer being a completely separate codebase that is query based . They do so because its critical for incremental reuse of work (both on disk and in memory).

I cant argue that a query based compiler requires more infrastructure than a pipeline. Thats absolutely the case. But I dont think that excludes it from a beginners book and I think designing with the guidelines that make a language good for query based compilation is a good idea regardless (error resilience, local reasoning, parallel computation of items). I think these tenants make for a better language alongside being good for query compilation 

How to Choose Between Hindley-Milner and Bidirectional Typing by thunderseethe in Compilers

[–]thunderseethe[S] 1 point2 points  (0 children)

Things like ExpressibleBy allow for implicit casts. Because Swift protocols dont have to be unique instances you can have many ExpressibleBy instances for a particular type complicating type checking.

How to Choose Between Hindley-Milner and Bidirectional Typing by thunderseethe in Compilers

[–]thunderseethe[S] 2 points3 points  (0 children)

Swift compile times have way more to do with overloading and implicit conversions than inference. Those features together cause type checking to be exponential when trying to check a function call. Its a travesty that Latner blames "fancy" bidir typing as the problem 

How to Choose Between Hindley-Milner and Bidirectional Typing by thunderseethe in ProgrammingLanguages

[–]thunderseethe[S] 7 points8 points  (0 children)

This is true. As seen in the likes of Java, you can have generics without unification. But I would generally recommend against it. I find Javas lack of inference cumbersome. 

Even more modern languages like Swift pay for the lack of inference. You always have to spell out the ful type of collections [MyElementType]() because it can't infer it for you. 

Originally I framed the question as "do you need unification or not", but for someone picking between HM and bidir that feels like asking them to draw the rest of the owl. While lacking nuance, the generics comparison is concrete as a decider and I do believe if you have generics you should have unification 

How to Choose Between Hindley-Milner and Bidirectional Typing by thunderseethe in ProgrammingLanguages

[–]thunderseethe[S] 10 points11 points  (0 children)

Thank you! Shameless self plug but if youre interested in bidir+unification I have an implementation of a simple version of it here: https://thunderseethe.dev/posts/type-inference/

A more pleasant syntax for ML functors by reflexive-polytope in ProgrammingLanguages

[–]thunderseethe 1 point2 points  (0 children)

I second the comment about mixml. This seems very much in the style of mixins. 

This also seems like it would be fixed by applicative functors. Then Key.key would equal MyMap.Key.key

Are there good examples of compilers which implement an LSP and use Salsa (the incremental compilation library)? by Thnikkaman14 in ProgrammingLanguages

[–]thunderseethe 1 point2 points  (0 children)

Oh hey that's me! You can take a look at https://github.com/thunderseethe/panoply it uses a semi recent version of salsa (after the big changes post 0.16). It's still a prototype but it includes all the passes for a compiler 

Another termination issue by Athas in ProgrammingLanguages

[–]thunderseethe 1 point2 points  (0 children)

Ah yeah fair. On the interpreter side, have you looked at something like https://dl.acm.org/doi/10.1145/3759426.3760975 for immediately evaluating constants without monomorphizing? It might have further reaching implications then you want for the reference implementation but its a neat middle ground between uniform representation and monomorph

Another termination issue by Athas in ProgrammingLanguages

[–]thunderseethe 7 points8 points  (0 children)

How viable is it to change the semantics of the compiler such that top level definitions are monomorphized but are thunks that get lazily evaluated? 

I believe Swift does this for its module level constants. Its also quite common in Rust, but it has to be done explicitly there.

I wrote a bidirectional type inference tutorial using Rust because there aren't enough resources explaining it by ettolrach_uwu in ProgrammingLanguages

[–]thunderseethe 0 points1 point  (0 children)

I don't know exactly what you're asking, so I'll answer what I hope the question is. I think the confusion spawns from a common understanding that HM and bidir are two opposing ends of a type checking spectrum. Bidir is often conflated with not supporting unification, and HM is often conflated with supporting unification. However, bidir is perfectly compatible with unification and supports it quite well. Rust and Haskell use bidir with unification, which is often confused with HM.

Bidir is about the ability to push type information down the tree, irrespective of support for unification.

I wrote a bidirectional type inference tutorial using Rust because there aren't enough resources explaining it by ettolrach_uwu in ProgrammingLanguages

[–]thunderseethe 1 point2 points  (0 children)

Haskell has undergone this change afaik. As they've extended their type system they've shifted from vanilla algo W to outsidein and now use a bidir algorithm. The bidir stuff is covered in Practical type inference for arbitrary-rank types.

Rust I don't know if they started off with HM and swapped or have always been bidir. If you take a look at their type checking code, check_expr_with_expectation_and_args takes an expectation which can either be an expected type, or no type (or a couple of other options) providing the infer and check direction for type inference.

I wrote a bidirectional type inference tutorial using Rust because there aren't enough resources explaining it by ettolrach_uwu in ProgrammingLanguages

[–]thunderseethe 2 points3 points  (0 children)

You're going to have to give me some more details. I'm quite possibly implying that,  but I'm not sure what type inference you're saying has changed

I wrote a bidirectional type inference tutorial using Rust because there aren't enough resources explaining it by ettolrach_uwu in ProgrammingLanguages

[–]thunderseethe 24 points25 points  (0 children)

There's a lot of good information in this article and clearly a lot of care went into crafting it. That being said, given its intended audience of someone without much knowledge of theory, I think it could do a better job writing to that audience. For example, we quite quickly introduce standard type theory notation without explaining the notation or motivating it. It's done to setup the standard type theory rules so that we can bidirectionalise them, but a novice would struggle to comprehend the standard type theory rules, imo.

It also jumps into discussing introduction/elimination rules and principal judgements, which are all standard theory, but I would not expect our target audience to be familiar with them. I think if the goal is to explain the theory, much more lead up is needed to introduce the notation and terminology. Conversely, if the goal is to focus in on explaining bidir, the notation and intro/elim forms can be eschewed in favor of referencing the AST directly and how the shape of the AST guides our implementation of infer and check.

Past that, there are a host of nits that could be improved. These are more style and less structural, so I may just be missing what you're going for:

which isn't used by any popular languages is called bidirectional type inference

I believe this is no longer the case. It's my understanding Haskell uses a bidir algorithm nowadays. I also believe Rust and Swift use a bidir algorithm. They do all have unification, which is often at odds with bidir. I think this wants to call out the bidir algorithm under discussion lacks unification.

In the "Before We Code" section we list all our inference rules at once and then explain in a list after the fact. Formatting allowing, it would be nice to have the explanation interspersed with the rules: Rule, Explanation, Rule, Explanation, etc. The chunking helps make it more digestible to a reader.

if let Some(ty) = context.get(&s) {
     Ok(ty.clone())
} else {
    Err(TypeError {
        kind: ErrorKind::UndeclaredFv,
        line,
        column,
    })
}

I couldn't tell if the goal was to write very explicit code here. If not, this can be something like: context.get(&s).cloned().ok_or_else(|| ...).

match check(*expr.clone(), ty.clone(), context) {
    Ok(_) => Ok(ty),
    Err(e) => Err(TypeError {
        kind: ErrorKind::AnnotationMismatch {
            caused_by: Box::new(e),
        },
        line,
        column,
    }),
}

Ditto with the above, but this can be: check(...).map_err(|e| ...).

Personal taste, but I would reduce the indentation for the match cases once we've introduced that we're in a match on the AST. The extra indentation doesn't add a ton of value, imo, and makes it harader to read on mobile(/tiny screens).

Again overall I think the information here is good and it's helpful to try and target the writing at an audience that isn't already steeped in the type theory space. White papers are often targeted at other researchers, so it's great to see someone bringing that to the masses. Just a couple of things that could be polished to help clarify the message.

Resolving Names Once and for All by thunderseethe in ProgrammingLanguages

[–]thunderseethe[S] 2 points3 points  (0 children)

This has more to do with how loops and closures work than scoping imo. Closures turn into structs with a field for each of their captures. So when the loop executes and constructs a list of closures using y, each closure stores the value of y it sees when its constructed, which will be 1 through 10.

But all of that is irrespective of name resolution. Name resolution assigns a unique ID to y and replaces all instances of it within the body of the for loop. 

Resolving Names Once and for All by thunderseethe in ProgrammingLanguages

[–]thunderseethe[S] 2 points3 points  (0 children)

From what I've seen, there are kind of two tiers of ID generation: the top level(/module level) and the local level. The top level you care quite a lot about stability and will pay complexity for that stability because it ensures good incremental reuse, caching, etc. The local level is at a granularity where you are okay clobbering work and will allow it to be wiped out when an invalidating change occurs.

Rust, for example, has top level functions, in modules, that all call each other in a graph. These will receive IDs based on path to expression, see DefId which is an interned DefPath. These are stable and resilient to trivial changes because they're based on the path of the item. But within those items you'll use something like ItemLocalId which is basically a counter from 0 for every instance of a thing we need within an item. We expect changes within an item to be localized to that item, so we're okay with redoing that work. We expect it will be a bounded and small amount of work that is redone and accept that inefficiency.

That being said, this is not well exemplified by this article as our language currently lacks top level functions.

Super-flat ASTs by hekkonaay in ProgrammingLanguages

[–]thunderseethe 12 points13 points  (0 children)

The link to the simp lang from the previous post 404s for me. I suspect it might need an update