[loicd]

> Compilers already solve multiple NP-complete problems in the course of compilation after all, for example register allocation.

The NP-complete problem is optimal register allocation (through graph coloring). Register allocation in itself is not NP-complete. You can always use a suboptimal but fast algorithm because optimizations are optional. On the other hand, type checking is not optional, so having to solve a NP-complete problem for that would indeed be problematic.

[tzs]

> On the other hand, type checking is not optional, so having to solve a NP-complete problem for that would indeed be problematic.

Not necessarily. There are plenty of NP-complete problems that can be solved optimally fast enough to be useful for the instances that actually come up in real world applications.

For example the Traveling Salesman Problem (TSP) is NP-complete, but there are exact solvers that run in reasonable time for instances of a few hundred vertices. That's fine if you are say a delivery company trying to plan the day's itinerary for one of your delivery trucks.

[samus]

A less precise borrow checker can usually still be satisfied by adding workarounds, at the cost of performance of course. Adding redundant reference counting or increasing the lifetime of data and the duration of critical regions make the program slower. In this sense, improving the borrow checker is analogous to adding new analyses and optimizations passes to a compiler.

[loicd]

OK, I suppose I have to dig deeper into Rust to determine whether I really disagree with that, or maybe this is too vague. The question is: who applies your workarounds? If this is always the compiler, then I agree, but if the programmer has to do any work, then your analogy fails.