rust-np/

[utterances-bot]

Compiling Rust is NP-hard

https://niedzejkob.p4.team/rust-np/

[ModestGoblin]

:feelsgood:

[tuzz]

Nice article!

The compiler also tells you how many satisfying assignments there are:

and 4 more not covered

I suppose that means it's also solving #SAT.

[meithecatte]

Rust is a billion dollar mistake.

@expnkx I disagree. Moreover, I don't see how you'd arrive at that conclusion after reading this article. After all, this is merely an intellectual curiosity with no practical impact. Would you care to elaborate?

[brendanzab]

Hey, really cool post! If you're interested to read more background on this, there's some great documentation for the algorithm used by Rust's pattern matching compiler, along with some extensive comments in the source code. The docs cite Warnings for pattern matching by Maranget as the basis of the algorithm, which covers the complexity result, in turn citing Sekar et al. [1992] as well.

[beepster4096]

@expnkx

unsafe all functions in Linux kernel. YEAH. SOOOOOOOOOOO SAFE!!

You misunderstand rust's safety. Rust allows you to contain unsafe to specific areas where it can be aggressively tested and audited. If you can check that the unsafe portions of the code cannot cause Undefined Behavior, then the safe portions cannot either

everyone who use C or C++ violates human rights

Strawman.

python programmers MUST learn python because you have no jobs.

I don't see how this relates to rust.

Rust believe language will always be political.

Are you angry about Rust's stance on LGBTQ rights?

[meithecatte]

Rust believe language will always be political.

Are you angry about Rust's stance on LGBTQ rights?

Rust is a lovely language (the best actually), and IT IS a shame that it takes a position on political issues. And it is even sadder that is not alone (before the election, a ton of JS libs were advocating BLM).

Sadly, some maintainers do this even though they know that some people don't like to see this. Maybe they think they must enlighten others.

Just imagine what would happen if the crab appears one day using a MAGA hat.

"Everyone deserves to be treated humanely" (which is what both BLM and the issue of LGBTQ+ rights amount to, to be clear here) is not a political issue. Or, rather, it shouldn't be. If you can't see the difference between that and "this particular person should rule our country", I don't know what to tell you. Either way, the comments under a purely technical post are not the place to discuss this. Since this has became a problem, all further blatant off-topic discussion will be deleted on sight.

[BartMassey]

Just saw this post today for some reason. Big fun.

Technically Rust compilation is undecidable, because type-level programming :-). But this is really cool. I used to work on pattern matching algorithms, and it's neat to see Rust's.

One possibility, of course, would be to restrict pattern matching so that it's polytime. But as you say, since it's not a real problem in practice, it seems way better to just take the performance hit in the very unlikely case that it arises in "normal" programming than to have weird restrictions and error messages.

Great article.

[Nadrieril]

Thanks for the delightful article! I'm the maintainer of the rustc exhaustiveness algorithm :D And now you're having me think about adapting DPLL to exhaustiveness checking :3

[SeniorMars]

Thank you on your work on this and the busy beaver. Very cool! I hope to read more of your work in the future.