2 ms·
> are really arguments for sloppiness The model checker verifies this for you whether you're "sloppy" (most mathematicians wouldn't call it sloppy; just those
by pron 11y ago
> are really arguments for sloppiness
The model checker verifies this for you whether you're "sloppy" (most mathematicians wouldn't call it sloppy; just those that work in typed logic systems) or not.
> I'd just carry out the proof by hand.
Except that the most used sorting algorithm in the world has had a real bug for years. It is very hard to prove by hand (see http://www.envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/ http://www.envisage-project.eu/proving-android-java-and-pyth...). And besides Lamport, Zave and many others have shown that a large number of hand-proofs of complex concurrent algorithms are very often wrong. Even ones with Lemmas and proofs and Guy Steele's and Nir Shavit's names on them (Snark), and even ones that win "best paper" and are adopted by the industry (Chord). Those algorithms had proofs, but the proofs were wrong: http://brooker.co.za/blog/2014/03/08/model-checking.html http://brooker.co.za/blog/2014/03/08/model-checking.html
If you could reliable hand-proof complex algorithms, you wouldn't need many of these tools. Lamport has written quite a bit about the difficulty of proofs for modern algorithms.
We are talking about specs that can run to 50 pages or so, and proofs that span hundreds of pages. There's no way people can do it by hand, and there's no way Haskell's type system's help is enough to help you prove it by hand.
> But all of this still seems like a lot effort to me.
It took 30 man years to deductively prove 7500 LOC with a theorem prover! It takes a few days to spec and verify Paxos or fixed Chord.
> if it's too hard to write correct programs that run on it.
There's a Haskell dialect on the JVM and a good (multithreaded!) OCaml implementation.
> All I see when I read those protocols is how to synchronize a single integer or something equally meaningless.
That's because those are the examples that fit in a tutorial. Quite a few real specs for real systems in TLA+/Alloy/Spin are available online. Here's one for Alpha's cache-coherence protocol: http://research.microsoft.com/en-us/um/people/lamport/tla/wildfire-challenge.html http://research.microsoft.com/en-us/um/people/lamport/tla/wi...
And here are all the verification annotations used to find and fix the TimSort bug: http://www.envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/ http://www.envisage-project.eu/proving-android-java-and-pyth...
- catnaroek 11y ago> Except that the most used sorting algorithm in the world has had a real bug for years. It is very hard to prove by hand... If you could reliable hand-proof complex algorithms, you wouldn't need many of these tools. So I just stick to simple data structures and algorithms for the most part. I don't see a real need for something as complex as TimSort, when quicksort and mergesort (or even insertion sort!) are perfectly good algorithms that any high-schooler with a modicum of mathematical talent can understand. It's totally ridiculous to need an automated theorem prover to verify a sorting algorithm. > And besides Lamport, Zave and many others have shown that a large number of hand-proofs of complex concurrent algorithms are very often wrong... Lamport has written quite a bit about the difficulty of proofs for modern algorithms. How often were these proofs formal proofs? By which I mean that the definitions and theorem statements are just pieces of syntax in a formal system, and that the associated proofs are just calculations driven by the formal system's rules? > Even ones with Lemmas and proofs and Guy Steele's and Nir Shavit's names on them (Snark), and even ones that win "best paper" and are adopted by the industry (Chord). I would never assume an algorithm is correct just because it appears on a paper authored by famous people, or because it's widely used in industry. (You wouldn't do drugs just because famous and rich celebrities do, right?) So, unless the proof of correctness of an algorithm is so trivial that I can find the proof on my own given a couple of hints, I will demand fully formal proof. (Yes, this means that the typical CS paper, especially the typical concurrent/distributed computing paper, doesn't convince me of its thesis.) > We are talking about specs that can run to 50 pages or so, and proofs that span hundreds of pages. They're typically that long because they're written in a mix of natural language and mathematical notation, where the former attempts to convey intuition in order to make up for the latter failing to provide rigor. > There's no way people can do it by hand, and there's no way Haskell's type system's help is enough to help you prove it by hand. Agreed. Once we have accepted complexity in our designs, nowhere can salvation be found. So just say no to gratuitous complexity. > There's a Haskell dialect on the JVM Nice. Will check. > and a good (multithreaded!) OCaml implementation. I don't care. OCaml is an ugly language. > Quite a few real specs for real systems in TLA+/Alloy/Spin are available online. Here's one for Alpha's cache-coherence protocol Any examples that a non-hardware person can appreciate? (Preferably databases, but operating systems would also be okay.)
- pron 11y ago> It's totally ridiculous to need an automated theorem prover to verify a sorting algorithm. It's not ridiculous when billions of dollars pass through programs using your sorting algorithm, and any improvement can matter (and there can be big differences). > How often were these proofs formal proofs? Do you know what percentage of algorithms have formal proofs? About 0. > Agreed. Once we have accepted complexity in our designs, nowhere can salvation be found. So just say no to gratuitous complexity. I've been in this industry for 20 years now, and I started out saying this, and now I hear this from others. That is obvious. Sometimes you deal with inherently complex problems. I was in the defense industry for a long time, and air-traffic control is a complex problem. > Any examples that a non-hardware person can appreciate? Sure. Follow the links here: http://brooker.co.za/blog/2014/03/08/model-checking.html http://brooker.co.za/blog/2014/03/08/model-checking.html Also, Amazon specified Dynamo (939 lines in TLA+) and their internal distributed lock manager (mentioned in this report, with the number of lines and the kinds of bugs found: http://glat.info/pdf/formal-methods-amazon-2014-11.pdf http://glat.info/pdf/formal-methods-amazon-2014-11.pdf) but I don't think they've made the actual specs available.