CompCert
coq
Our great sponsors
CompCert | coq | |
---|---|---|
36 | 87 | |
1,761 | 4,602 | |
1.8% | 1.4% | |
7.3 | 10.0 | |
24 days ago | about 20 hours ago | |
Coq | OCaml | |
GNU General Public License v3.0 or later | GNU Lesser General Public License v3.0 only |
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
CompCert
-
Differ: Tool for testing and validating transformed programs
A big problem is that proving that transformations preserve semantics is very hard. Formal methods has huge potential and I believe it will be a big part of the future, but it hasn't become mainstream yet. Probably a big reason why is that right now it's simply not practical: the things you can prove are much more limited than the things you can do, and it's a lot less work to just create a large testsuite.
Example: CompCert (https://compcert.org/), a formally-verified compiler AKA formally-verified sequence of semantics-preserving transformations from C code to Assembly. It's a great accomplishment, but few people are actually compiling their code with CompCert. Because GCC and LLVM are much faster[1], and have been used so widely that >99.9% of code is going to be compiled correctly, especially code which isn't doing anything extremely weird.
But as articles like this show, no matter how large a testsuite there may always be bugs, tests will never provide the kind of guarantees formal verification does.
[1] From CompCert, "Performance of the generated code is decent but not outstanding: on PowerPC, about 90% of the performance of GCC version 4 at optimization level 1"
- So you think you know C?
-
Can the language of proof assistants be used for general purpose programming?
Also a C compiler (https://compcert.org/). I did exaggerate bit in saying that anything non-trivial is "nearly impossible".
However, both CompCert and sel4 took a few years to develop, whereas it would only take months if not weeks to make versions of both which aren't formally verified but heavily tested.
-
A Guide to Undefined Behavior in C and C++
From my experience, while many MCUs have settled for the big compilers (GCC and Clang), DSPs and some FPGAs (not Intel and Xilinx, those have lately settled for Clang and a combination of Clang and GCC respectively) use some pretty bespoke compilers (just running ./ --version is enough to verify this, if the compiler even offers that option). That's not necessarily bad, since many of them offer some really useful features, but error messages can be really cryptic in some cases. Also some industries require use of verified compilers, like CompCert[1], and in such cases GCC and Clang just don't cut it.
[1]: https://compcert.org/
-
Recently I am having too much friction with the borrow checker... Would you recommend I rewrite the compiler in another language, or keep trying to implement it in rust?
CompCert sends its regards
- Rosenpass – formally verified post-quantum WireGuard
-
OpenAI might be training its AI technology to replace some software engineers, report says
But that's fine, because we can do even better with things like the CompCert C compiler, which is formally proven to produce correct asm output for ISO C 2011 source. It's designed for high-reliability, safety-critical applications; it's used for things like Airbus A380 avionics software, or control software for emergency generators at nuclear power plants. Software that's probably not overly sophisticated and doesn't need to be highly optimized, but does need to work ~100% correctly, ~100% of the time.
-
There is such thing called bugfree code.
For context, CompCert is a formally verified compiler. My former advisor helped with a fuzzer called CSmith which found plenty of bugs in GCC and LLVM but not in CompCert.
-
Checked C
Does anybody know how does this compare to https://compcert.org/ ?
-
Proofs about Programs
This is a common property for proof-oriented languages. Coq shares this property for instance, and you can write an optimizing C compiler in Coq: https://github.com/AbsInt/CompCert .
coq
-
Change of Name: Coq –> The Rocq Prover
The page summarizing the considered new names and their pros/cons is interesting: https://github.com/coq/coq/wiki/Alternative-names
Naming is hard...
-
The First Stable Release of a Rust-Rewrite Sudo Implementation
Are those more important than, say:
- Proven with Coq, a formal proof management system: https://coq.inria.fr/
See in the real world: https://aws.amazon.com/security/provable-security/
And check out Computer-Aided Verification (CAV).
-
Why Mathematical Proof Is a Social Compact
To be ruthlessly, uselessly pedantic - after all, we're mathematicians - there's reasonable definitions of "academic" where logical unsoundness is still academic if it never interfered with the reasoning behind any proofs of interest ;)
But: so long as we're accepting that unsoundness in your checker or its underlying theory are intrinsically deal breakers, there's definitely a long history of this, perhaps more somewhat more relevant than the HM example, since no proof checkers of note, AFAIK, have incorporated mutation into their type theory.
For one thing, the implementation can very easily have bugs. Coq itself certainly has had soundness bugs occasionally [0]. I'm sure Agda, Lean, Idris, etc. have too, but I've followed them less closely.
But even the underlying mathematics have been tricky. Girard's Paradox broke Martin-Löf's type theory, which is why in these dependently typed proof assistants you have to deal with the bizarre "Tower of Universes"; and Girard's Paradox is an analogue of Russell's Paradox which broke more naive set theories. And then Russell himself and his system of universal mathematics was very famously struck down by Gödel.
But we've definitely gotten it right this time...
[0] https://github.com/coq/coq/issues/4294
-
In Which I Claim Rich Hickey Is Wrong
Dafny and Whiley are two examples with explicit verification support. Idris and other dependently typed languages should all be rich enough to express the required predicate but might not necessarily be able to accept a reasonable implementation as proof. Isabelle, Lean, Coq, and other theorem provers definitely can express the capability but aren't going to churn out much in the way of executable programs; they're more useful to guide an implementation in a more practical functional language but then the proof is separated from the implementation, and you could also use tools like TLA+.
https://dafny.org/
https://whiley.org/
https://www.idris-lang.org/
https://isabelle.in.tum.de/
https://leanprover.github.io/
https://coq.inria.fr/
http://lamport.azurewebsites.net/tla/tla.html
-
If given a list of properties/definitions and relationship between them, could a machine come up with (mostly senseless, but) true implications?
Still, there are many useful tools based on these ideas, used by programmers and mathematicians alike. What you describe sounds rather like Datalog (e.g. Soufflé Datalog), where you supply some rules and an initial fact, and the system repeatedly expands out the set of facts until nothing new can be derived. (This has to be finite, if you want to get anywhere.) In Prolog (e.g. SWI Prolog) you also supply a set of rules and facts, but instead of a fact as your starting point, you give a query containing some unknown variables, and the system tries to find an assignment of the variables that proves the query. And finally there is a rich array of theorem provers and proof assistants such as Agda, Coq, Lean, and Twelf, which can all be used to help check your reasoning or explore new ideas.
-
Functional Programming in Coq
What ever happened to the effort [1] to rename Coq in order to make it less offensive? There were a number of excellent proposals [2] that seemed to die on the vine.
[1] https://github.com/coq/coq/wiki/Alternative-names
[2] https://github.com/coq/coq/wiki/Alternative-names#c%E1%B5%A3...
-
Mark Petruska has requested 250000 Algos for the development of a Coq-avm library for AVM version 8
Information about the Coq proof assistant: https://coq.inria.fr/ , https://en.wikipedia.org/wiki/Coq
- How are people like Andrew Wiles and Grigori Perelman able to work on popular problems for years without others/the research community discovering the same breakthroughs? Is it just luck?
-
Basic SAT model of x86 instructions using Z3, autogenerated from Intel docs
This type of thing can help you formally verify code.
So, if your proof is correct, and your description of the (language/CPU) is correct, you can prove the code does what you think it does.
Formal proof systems are still growing up, though, and they are still pretty hard to use. See Coq for an introduction: https://coq.inria.fr/
-
What are the current hot topics in type theory and static analysis?
Most of the proof assistants out there: Lean, Coq, Dafny, Isabelle, F*, Idris 2, and Agda. And the main concepts are dependent types, Homotopy Type Theory AKA HoTT, and Category Theory. Warning: HoTT and Category Theory are really dense, you're going to really need to research them.
What are some alternatives?
seL4 - The seL4 microkernel
coc.nvim - Nodejs extension host for vim & neovim, load extensions like VSCode and host language servers.
unbound - Replib: generic programming & Unbound: generic treatment of binders
kok.nvim - Fast as FUCK nvim completion. SQLite, concurrent scheduler, hundreds of hours of optimization.
gcc
FStar - A Proof-oriented Programming Language
corn - Coq Repository at Nijmegen [maintainers=@spitters,@VincentSe]
Agda - Agda is a dependently typed programming language / interactive theorem prover.
vericert - A formally verified high-level synthesis tool based on CompCert and written in Coq.
lean4 - Lean 4 programming language and theorem prover
koika - A core language for rule-based hardware design 🦑
tlaplus - TLC is a model checker for specifications written in TLA+. The TLA+Toolbox is an IDE for TLA+.