3 ms·
> 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
by 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.