5 ms·
As I said in another comment, stories like this make people interested in formal methods, and Coq, IMO, would be daunting for most beginners. TLA+ is a good, be
by pron 11y ago
As I said in another comment, stories like this make people interested in formal methods, and Coq, IMO, would be daunting for most beginners. TLA+ is a good, beginner-friendly entry point to formal methods (and you can slowly progress from specification to model-checking and only then proofs), even if you later choose to move to dependent-type approaches and tools like Coq or F*.
> TLA+ is for totally different jobs. Not relevant here.
I beg to differ. TLA+ is commonly (as far as the word "commonly" can be used when formal methods are discussed) used to specify and verify programs in C or any other language.
It is true that Coq has been used to verify compilers more than TLA+, while TLA+ has been used to verify algorithms (esp. concurrent/distributed) more than Coq, but the reason is not because neither could do the other's job, but because of their respective progeny. Coq (as all type-theory tools) is closely associated with PL-theory people, who tend to be more attracted to compilers, while TLA+ originated from the software-verification world (mostly Pnueli's temporal logic), and created and promoted by Leslie Lamport, most certainly an "algorithms" (specifically distributed/concurrent) guy rather than a "PL" guy.
BTW, Isabelle is one of the proof engines used by the TLA+ proof system.
- nickpsecurity 11y ago" stories like this make people interested in formal methods, and Coq, IMO, would be daunting for most beginners. TLA+ is a good, beginner-friendly entry point to formal methods (and you can slowly progress from specification to model-checking and only then proofs), even if you later choose to move to dependent-type approaches and tools like Coq or F*." TLA+ is an easier intro to verification. However, the verification of C programs to any strong degree will require tools like Coq, possibly esoterica like separation logic, tough specs, tough proofs, and so on. There's no easy route for it for beginners except to straight up learn the necessary knowledge with Chlipala's book, Software Foundations, or something similar. Then plenty of practice and study of how successful work was done. There's a reason we celebrate every time someone comes close to specifying or verifying a significant chunk of C language. It's because it's Just That Hard (TM). ;) "I beg to differ. TLA+ is commonly (as far as the word "commonly" can be used when formal methods are discussed) used to specify and verify programs in C or any other language." Hmm. Interesting. I should probably do another survey of TLA+ to see what uses it's had in sequential, low-level algorithms like the OP post is on. May be more going on than I was previously aware. All the top results are using Coq and Isabelle/HOL, though.
- pron 11y ago> There's no easy route for it for beginners And if this post had appeared on a Coq forum, a verification forum or even LtU, I would have said nothing. However, as this is HN, and there are probably many beginners reading this, I thought it very relevant to point out a more beginner-friendly tool as a foray into this interesting subject. > what uses it's had in sequential, low-level algorithms This is a fairly recent paper that describes a tool that translates C to TLA+ for verification: http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/MLBHB-ftscs15.pdf http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/MLBHB-ftscs15... It works for concurrent C programs as well as sequential ones. This is an old (old) spec by Lamport of the Win32 Threads API: http://research.microsoft.com/en-us/um/people/lamport/tla/threads/threads.html http://research.microsoft.com/en-us/um/people/lamport/tla/th... And again, the choice of TLA+/Coq often has much more to do with the community the author belongs to (PL/conc-dist algorithms) rather than some specific strengths of the tool.
- nickpsecurity 11y agoAppreciate the paper as I didn't have that interesting work. Once again, though, they're focused on the details of concurrent (eg protocol-like) work instead of verifying concrete, sequential programs. They claim in the paper to be able to prove absence of runtime errors but don't give much detail. They also aim to do more on that leveraging Frama-C but again no detail. So, your example shows it a work in progress for TLA+ rather than work done several times over as in Coq or Isabelle work. It does support the use of TLA+ for some aspects of C verification or specification along with integrating into the right tool (Frama-C). I'll probably do the re-survey on TLA+ use I mentioned earlier due to this paper.
- OopsCriticality 11y agoI've been wondering for a while, and since this thread seems to have attracted people who may have answers… Can you (or anyone) provide any insight as to why ACL2 doesn't get mentioned much in discussions of formal methods? I'm interested in formal methods and ACL2 seems like a nice tool, but at least on HN all I usually see is Coq this and Coq that, with occasional mentions of TLA+ and Isabelle.