9 ms·
Eliminating deadlocks in general isn't possible in a Turing-complete language. What's cool about Rust is that it does statically eliminate a certain subset of r
by kibwen 11y ago
Eliminating deadlocks in general isn't possible in a Turing-complete language. What's cool about Rust is that it does statically eliminate a certain subset of race conditions known as data races. So while deadlocks are still possible in Rust, the typesystem is guaranteed to prevent concurrency errors that would result in corrupted data.
- cwzwarich 11y agoEliminating deadlocks with a type system is just as possible as eliminating data races (albeit maybe a bit more awkward). The question of Turing completeness doesn't really come into it, because you are rejecting some dynamically correct programs with a static type system.
- kibwen 11y agoTo expand on my reply to pcwalton, I consider a deadlock to be anything that causes my program to become unresponsive from which it will never recover, which includes infinite looping (or its ilk, such as infinite (possibly mutual) recursion (and even if that blows the stack eventually in practice, I don't consider that a form of recovery :P )). Can you suggest better terminology for what I mean?
- samth 11y agoThis is what's usually called a "liveness" property: eventually the system will do some particular thing. These two in particular are often called "progress" in some contexts, but that's rarely formal. In general, any of these properties can be checked statically, just like czwarich said. You have to be conservative, but that's not any different than a type system, or Rust's borrow checker. There are certainly languages that enforce termination, and you can design systems that enforce higher-level progress properties (such as absence of deadlock). The major difference between a liveness property and the other kind (called a safety property: at no point does this bad thing happen) is that you can't check for liveness properties dynamically.
- heinrich5991 11y agoStatically checking that progress is made does imply that the language is not Turing-complete if I understand it correctly, which is why Coq, the proof assistant language where all programs have to terminate, is not Turing-complete.
- samth 11y agoThis is not correct. It's possible to write a sound static checker for termination of a Turing complete language. There are some terminating programs on which it will have to say "I don't know", however.
- kibwen 11y agoThis is my understanding as well, and underlies my assertions above. After all, if a compiler can tell you for certain that any given program written in a Turing-complete language will terminate, then you've literally just solved the halting problem. :P
- TheCoelacanth 11y agoOf course, it's true that it can't be proven whether any arbitrary program will halt or not, but in practice most (possibly all) useful programs can be proven to halt or not halt.
- pcwalton 11y ago> Eliminating deadlocks in general isn't possible in a Turing-complete language. It is possible. For example, you could just remove threads and synchronization primitives. :) But it's not easy -- IMO, compared to data races it's much harder to eliminate deadlocks statically without restricting expressiveness too much. It's even harder if you count I/O related deadlocks as deadlocks (e.g. deadlocking reads on Unix pipes).
- kibwen 11y agoBah, I should have been more precise with my terminology. :P I tend to consider an infinite loop a form of deadlock, even if it only involves a single unit of execution.
- acconsta 11y agoThe Rust community makes a car: "Check out our awesome new car! It makes driving 'easy and safe'!" "Does it prevent crashes?" "No, that's impossible! But here, look at our onboard computer that prevents many types of driving errors." I like Rust. I want it to succeed. But I think the rhetoric gets ahead of the language sometimes, and not prioritizing higher level concurrency tools because you have the borrow checker is a mistake.
- steveklabnik 11y ago> not prioritizing higher level concurrency tools because you have the > borrow checker is a mistake. Ahh, but to mix up your analogy here, the borrow checker is the engine, and the higher level tools are like building fancier cars. You have to get your foundations built before you can build higher-level things on top of them. Now that we have a foundation, these things are starting to appear. See https://news.ycombinator.com/item?id=10131429 https://news.ycombinator.com/item?id=10131429, for example.
- acconsta 11y agoIn general, there are many reasons (fragmentation, quality, portability, dependency management, compiler support) it's preferable to have concurrency tools standardized. Standardization is only going to get harder in the future. Specifically, it's great that Rust has a capable atomics library. I'm sure we'll see many good concurrent data structures come from it. But that's not quite what I meant by concurrency tools. The thread primitives Rust offers are the same ones POSIX standardized twenty years ago. It would be very valuable to have something like OpenMP (parallel loops, etc.) and something for concurrent IO (either asynchronous or coroutine-based). There's no reason Rust can't have the performance of C++ and the easy concurrency tools of Go or Erlang.
- Manishearth 11y ago>It would be very valuable to have something like OpenMP (parallel loops, etc.) and something for concurrent IO (either asynchronous or coroutine-based). https://crates.io/crates/mio https://crates.io/crates/mio for the async IO. There was another library out there that provided tons of concurrency utilities, but I can't find it now. Parallel loop-like syntax should be easy with scoped_threadpool and a macro though. Rust tries to avoid stuffing everything into the standard library. So the lack of utilities in the stdlib isn't an artifact of some ignorance of concurrency, it's because Rust doesn't want to keep everything in the stdlib. Rust keeps the basic framework for thread safety in the stdlib (though it doesn't need to, not exactly), but the rest is built upon by the community.
- Veedrac 11y ago"X isn't possible because of Turing completeness" is almost always wrong. GC is another "impossible" task, yet those are everywhere. The real goal is to find a strategy that works well enough, often enough. Dynamic GC gives up perfect collection (aiming to be merely good enough). Rust's data race guarantees prevent safely expressing some subset of correct programs. Whether deadlock prevention can be done nicely enough for general case usage is an open question.
- kibwen 11y agoGC works great in practice, but as you say it isn't provable. Likewise, Rust goes a long way towards preventing deadlocks in practice, but that also isn't provable. All I'm talking about here are guarantees. Rust's type system guarantees that there are no data races; that's firm bedrock that I can rely upon. I can't rely on there being no deadlocks just as I can't rely on a garbage collector actually returning any memory. That doesn't mean these tools aren't useful in practice, only that I have to take their failure modes into consideration if I want to write correct programs.