What "compiling Rust is NP-hard" (niedzejkob.p4.team/rust-np/) really shows is that pattern exhaustiveness checking is NP-hard.
To me, this is a good example of "sometimes really useful features are NP-hard, and it's worth accepting this theoretical worst-case complexity".
Conversation
I found the discussion there a bit frustrating, since the complexity result was well-known when Maranget published his paper on this problem 15 years ago, and he cites a paper from 15 years before that.
2
1
25
The Rust team usually knows the relevant literature, but a lot of online discussion of Rust makes it seem like sum types and pattern matching were invented in 2014.
1
3
28
Yeah, reading it I was also a bit sad there was no time put into checking out the background work on pattern matching. It's a constant struggle to expose new people to old useful tools, while making sure that they're aware that this stuff is not new.
The source of Rust's pattern match compiler has references back to “Warnings for pattern matching” at least… I'm guessing that the author of the blog post wasn't aware that it was documented, hence the omission? doc.rust-lang.org/nightly/nightl
1
4
Got around to posting a reply to the blog post with those links, for the benefit of the author and others reading!