7 ms·
I would strongly encourage anyone interested in formal methods (and formal proofs in particular) but may be intimidated by dependent types, which serve as the b
by pron 11y ago
I would strongly encourage anyone interested in formal methods (and formal proofs in particular) but may be intimidated by dependent types, which serve as the basis for Coq (and are foreign not only to software developers but to most mathematicians as well) to give TLA+[1] a look. It is a decade younger than Coq (16 vs. 26), but simpler to use, much more gradual, and has had industry adoption pretty much since its inception.
Instead of dependent types (in fact, TLA+ is untyped[2]) It is based on simple ZF set theory and logic, and should be immediately familiar to anyone who's taken even one logic (or discrete math) course in college. In addition to a proof assistant it has a good model checker, comes bundled in a nice (relatively speaking) IDE, and is easy to learn (with a thorough tutorial written by Leslie Lamport himself).
TLA+ is also more widely used in the industry -- both hardware and software -- perhaps most notably in the software industry by Amazon, who use TLA+ to specify many of their AWS services. TLA+ is a formal specification (and verification) tool designed for engineers and used by engineers. Although, to be fair, neither tool is used by a large portion of the industry.
EDIT: Removed potentially incendiary Lamport quote.
EDIT: Changed an incorrect statement about Coq's use in the industry
[1]: http://research.microsoft.com/en-us/um/people/lamport/tla/tla.html http://research.microsoft.com/en-us/um/people/lamport/tla/tl...
[2]: See Should Your Specification Language Be Typed? by Lamport and Paulson: http://research.microsoft.com/en-us/um/people/lamport/pubs/lamport-types.pdf http://research.microsoft.com/en-us/um/people/lamport/pubs/l...
- fuklief 11y agoCoq is also used in industry, in particular by Airbus with the CompCert C compiler.
- pron 11y agoDo Airbus engineers write Coq specifications or just use CompCert (a C compiler formally verified with Coq in academia)?
- deleted 11y ago[deleted]
- nmrm2 11y agoThis distinction is disingenious (edit: I probably mean spurious). The number of people in industry who use either tool is incredibly small and is likely to remain so; developers spend 20-50% of their time on test suites and STILL don't feel it's cost-effective to write down formal specs, even in TLA+-style specifications. What matters is that important libraries and frameworks can be verified, not that everyone and his brother can use formal methods for every WordPress website they churn out.
- pron 11y ago> The number of people in industry who use either tool is incredibly small and is likely to remain so I agree, but I see some chance of TLA+ of getting wide(r) adoption, precisely because it is rather easy to learn and uses math that most engineers are already familiar with. Also, it allows gradual verification: specification -> model-checking -> proof (with each additional step being completely optional) > not that everyone and his brother can use formal methods for every WordPress website they churn out. I don't know about WordPress websites, but Amazon engineers do use TLA+ to specify many (most?) AWS services.
- nmrm2 11y agoMy point was just that formal methods can have a tremendous positive impact even if academics are the only ones using them, as long as the output from those efforts do get used. So I'm not sure distinguishing between "using formally verified software" and "using a formal methods tool directly" is a helpful distinction when measuring industrial impact. Also, formalizing architectural properties for the world's most popular cloud service is probably even rarer a task than formalizing language specifications.
- jessaustin 11y ago...disingenious. English usage note: if the word you meant to use was "disingenuous", I would suggest "spurious" instead, as it expresses similar feelings about "this distinction", without also attributing unsavory motives to 'pron.
- 11y ago
- pascal_cuoq 11y agoBoth. “They” (and by they I do not necessarily imply a large number of engineers at Airbus, but some people who are engineers at Airbus) use CompCert and “they” also use Coq in order to finish up the correctness arguments for part of the properties that part of the software is supposed to have: https://www.lri.fr/~marche/M2-TIP-Airbus.pdf https://www.lri.fr/~marche/M2-TIP-Airbus.pdf
- feider 11y agoFrom CompCert site: "What sets CompCert C apart from any other production compiler, is that it is formally verified, using machine-assisted mathematical proofs, to be exempt from miscompilation issues." I'm not very into C language - what are these miscompilation issues? What is the practical impact that CompCert C brings?
- witty_username 11y agoMiscompilation issues means bugs in the compiler causing incorrect assembly to be generated.
- feider 11y agoI understood that. Sorry if my question was bit unclear. What I wanted to know was _specifically_ what these bugs are / what causes them / what is practical impact (i.e. probability of application crashing or other serious event due to use of GCC etc)
- sanxiyn 11y agoCheck out "Finding and Understanding Bugs in C Compilers": http://www.cs.utah.edu/~regehr/papers/pldi11-preprint.pdf http://www.cs.utah.edu/~regehr/papers/pldi11-preprint.pdf. The paper explains what-is-bug/what-causes-it/what-is-impact for selected bugs. Complete list of 282 compiler bugs found (79 GCC, 203 LLVM) is also available online: http://embed.cs.utah.edu/csmith/ http://embed.cs.utah.edu/csmith/.
- feider 11y agoThank you, that paper seems to be surprisingly easy to read (being an academic paper that is).
- nickpsecurity 11y agoEspecially see the CompCert section on page 6 of the Csmith PDF to see what a difference formal verification made. Note that compilers don't have to go that far: typed, functional, thoroughly-tested code in something like Ocaml or Haskell can achieve 80-90% of that quality with relatively little effort. Hence, why I promote rewriting and further extending things like LLVM in languages like ML, Ada, or Eiffel that support advanced checks.
- nmrm2 11y agoA note for the unitiated: There is a tension between TLA+ and Coq et al. (typified by statements such as "weird computer-science math") that is similar and maybe even rooted in to the sorts of culture wars that sprout up around programming languages (see [2] of parent's post for a perfect example of what I'm talking about...) The characterization in pron's post is decidedly biased toward TLA+ in a way that I think is unnecessary. A few correctives: * Coq has seen plenty of industry adoption. To say that type-theoretic theorem provers (or the Coq system specifically) are merely academic toys compared to TLA+ is wrong. * "Normal" mathematicians (not just "weird Computer Science-type" mathematicians, whatever that means...) have used and extolled the virtues of Coq as a tool as well as its theoretical foundations. See e.g., the univalent foundations project. Regardless, I'm not sure I understand why "Computer Science-type math" is an unreasonable foundations for a program specification tool, which is what TLA+ is. And if the goal is formalized mathematics, you're probably better off with Coq (and it's not even clear that the TLA+ community is interested in that sort of thing, independnet of results useful in the course of a program specification/verification task.) * If you're familiar with (esp. typed) functional programming, you might find Coq even easier to get into than TLA+. On both sides of the type theory vs sets/axioms divide, people should be careful not to confuse one's predispositions based upon educational background with the actual mental load of learning to use a tool. There is room for both of these tools (and more!) in the world. I don't understand why they have to be in competition. A formalization of the C standard is a HUGE undertaking, independent of what tool was used. Let's celebrate that achievement!
- unboxed_type 11y agoI would like to mention that Coq is also used to extract _verified implementations_ rather than model checking abstract algorithm design (as in TLA+). This property might be very desirable depending on situation. As for me this property looks very appealing.
- pron 11y ago> To say that type-theoretic theorem provers (or the Coq system specifically) are merely academic toys compared to TLA+ is disingenious. I never said that Coq is an academic toy. Some projects done in academia and used in the industry have been verified with Coq, but I am not aware of actual (direct) use of Coq in the industry (but would be interested to learn of any). > I'm not sure I understand why "Computer Science-type math" is an unreasonable foundations for a program specification tool, which is what TLA+ is I've never said it is unreasonable, only that it is foreign to most engineers (as well as most academic CS people), or rather, more foreign than basic logic/set theory. I would say again that if you're comfortable with type theory, you might enjoy Coq better. If not, TLA+ would probably be more approachable. TLA+ has the added advantage of having a model checker, which is very useful when you don't have the resources required for a full proof, but still want a good confidence in the correctness of your algorithm. > A formalization of the C standard is a HUGE undertaking, independent of what tool was used. Let's celebrate that achievement! Oh, absolutely! It's just that stories like this make people interested in formal methods, and Coq, IMO, would be daunting for most. TLA+ is a good entry point to formal methods, even if you later choose to move to dependent-type approaches and tools.
- unboxed_type 11y agoAlso take a look at this thread, were I briefly describe our experience of using all the spectre of verification tools. https://news.ycombinator.com/item?id=10220264 https://news.ycombinator.com/item?id=10220264
- random778 11y agoWould you advise one to start directly with TLA+ or work through some logic/discrete math seperately beforehand?
- nmrm2 11y agoIf you have had the equivalent of an undergraduate course on Discrete Mathematics you are probably fine; an introduction to logic course (covering e.g., soundness and completeness of propositional/first order logics) probably isn't necessary. There is a self-contained book; IMO chapter 1 gives a good overview of what you should be comfortable with: http://research.microsoft.com/en-us/um/people/lamport/tla/book-02-08-08.pdf http://research.microsoft.com/en-us/um/people/lamport/tla/bo...
- agentultra 11y agoNot the author but a recent book I've read on the subject served as a gentle introduction for me: The Little Prover [0]. If you can get past the lisp syntax you can get through this book with an informal and incomplete education in set theory and an intuitive understanding of logic. [0] https://mitpress.mit.edu/index.php?q=books/little-prover https://mitpress.mit.edu/index.php?q=books/little-prover
- pron 11y agoLamport's tutorial (the TLA+ Hyperbook) as well as the old TLA+ book (Specifying Systems) -- both available freely on the TLA+ homepage -- cover all the math you need (which is little more than logical conjunction/disjunction/implication, the quantifiers for all/exists, and set membership/union/intersection). But it is perhaps better to be familiar with those simple concepts beforehand, although note that what you need is very, very basic. As nmrm2 said, there's no need for a full Discrete Math course (or a whole book).
- nickpsecurity 11y agoYour TLA+ comment isn't relevant to this discussion and seems to only promote TLA+. The topic is verification of compilers or imperative programs in C language. I don't know of anyone using TLA+ for that or advocating for it. It's mainly used as a lightweight approach in protocol verification. So, distributed apps not C code or compilers. Now, Coq has plenty of history in certified programming and compilation. There exists formalisms and models of most pieces of the puzzle. There are worked examples of certified compilers whose details and sometimes source are available for re-use. There's even already a verified C compiler other works are building on. It was used in EAL7-class JavaCard interpreters, database structures I believe, web services, and so on. Even outputs to robust Ocaml code. People needing to learn this stuff even have free books like Chlipala's: http://adam.chlipala.net/cpdt/ http://adam.chlipala.net/cpdt/ So, anyone trying to specify or formally verify compilers or algorithms have plenty of reason to choose Coq. It's actually one of the best tools for the job with HOL or Isabelle the other style. Field kind of diverges doing parallel work with them in imperative verification. Coq is possibly easier to use and seems to have more prior work to draw on in this. So, it's either the best or one of best tools for the job. TLA+ is for totally different jobs. Not relevant here.
- throwaway999888 11y ago> Your TLA+ comment isn't relevant to this discussion and seems to only promote TLA+. pron has this habit of being negative and dismissive towards functional programming and related things, recommending non-FP alternatives instead. Which is fine, only that sometimes he's too trigger happy and just gives unsolicited advice without any build up or with weak topical relevance. Like here.
- pron 11y agoI am not dismissive towards Coq (how can anyone be?), and my advice is neither less solicited nor less relevant than many other HN comments. But you are right that I sometimes try to correct what I see as a (strange) imbalance here on HN (which reflects neither the prevailing opinions in academia nor in the industry) regarding PFP and type theory. People unfamiliar with the topic might get the impression that PFP+type-theory is either the only or the most prevalent technique for software verification (or software correctness in general), while neither is the case. In exchange, I get to be the lucky target of various ad hominem attacks, so I guess I've earned my right to speak up :)