mathlib VS dafny

It's been on my mind lately as well. I was trying out `symbolics.jl` (a CAS written in Julia), and it turned out that it didn't support symbolic integration beyond simple linear functions or polynomials (at least back then, things have changed now it seems). Implementing a generic algorithm for finding integrals is hard, but I was expecting more from that CAS since this seems to be implemented in most other CASs. The thing is that every single CAS that covers general maths knowledge will have to implement the same algorithm, while it's hard to do it even once!

I feel like at least a large part of the functionality of a general purpose CAS can be written down once, and every CAS out there could benefit from it, similar to what the Language Server Protocol did for programming tools. They also had to rewrite the same tool for some language multiple times because there are lots of editors out there, and the LSP cut the time investment down a lot. They did have to invest a large amount of time to get LSP up and running, and it'll have to be maintained, but I think it's orders of magnitudes more efficient than having every tool developed and maintained for every single (programming language, editor) pair out there.

Main problem is like you said how to write down mathematical knowledge in a way that all CASs can understand it. I've been learning about Mathlib lately [0], which seems like a great starting point for this. It is as far as I know one of the first machine readable libraries of mathematical knowledge; it has a large community which has been pushing it continuously forward for years into research-level mathematics and covering the entire undergraduate maths curriculum and it's still accelerating. If some kind of protocol can be designed to read from libraries like this and turn it into CAS code, that would be a major step towards making the CAS ecosystem more sustainable I think.

It's not exactly what you were talking about, as in, this would allow multiple CASs to co-exist and benefit from each other, but I think that's better than having one massive CAS that has a monopoly. No software is perfect, but having a diverse set of choices that are open source would be more than enough to satisfy everyone.

(I have posted about this before on the Lean Zulip forum, it's open to everyone to read without an account [1])

[0] https://leanprover-community.github.io/

Kinda agree but Mathlib and its documentation makes for a big corpus to learn by example from. Not ideal but it helps.

https://github.com/leanprover-community/mathlib

https://github.com/leanprover-community/mathlib

https://1lab.dev/

You can watch the next generation, or participate, right now.

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.

For the math that you mention, I would suggest looking at mathlib (https://github.com/leanprover-community/mathlib). I agree that the foundations of Coq are somewhat distanced from the foundations most mathematicians are trained in. Lean/mathlib might be a bit more familiar, not sure. That said, I don't see any obstacles to developing classical real analysis or linear algebra in Coq, once you've gotten used to writing proofs in it.

At this point I would go with Lean because of mathlib. Mathlib's goal is to formalize modern mathematics, so many of the theorems you would need for analysis should already be there for you.

I think about that every day. Lean's mathlib is a gigantic (with respect to this kind of project) code base and each function, each definition has a precise and rigorous natural language counterpart (in a maths book, somewhere).

It's been around since 2013, although there are LLM that interact with Lean to do automated theorem proving. Anyway, you can learn more about Lean here. I enjoyed their natural numbers game (which reminds, me I should finish the last two levels)

Code correctness is a lost art. I requirement to think in abstractions is what scares a lot of devs to avoid it. The higher abstraction language (formal specs) focus on a dedicated language to describe code, whereas lower abstractions (code contracts) basically replace validation logic with a better model.

C# once had Code Contracts[1]; a simple yet powerful way to make formal specifications. The contracts was checked at compile time using the Z3 SMT solver[2]. It was unfortunately deprecated after a few years[3] and once removed from the .NET Runtime it was declared dead.

The closest thing C# now have is probably Dafny[4] while the C# dev guys still try to figure out how to implement it directly in the language[5].

[1] https://www.microsoft.com/en-us/research/project/code-contra...

[2] https://github.com/Z3Prover/z3

[3] https://github.com/microsoft/CodeContracts

[4] https://github.com/dafny-lang/dafny

[5] https://github.com/dotnet/csharplang/issues/105

I don't think something that specific exists. There are a very large number of formal methods tools, each with different specialties / domains.

For verification with proof assistants, [Software Foundations](https://softwarefoundations.cis.upenn.edu/) and [Concrete Semantics](http://concrete-semantics.org/) are both solid.

For verification via model checking, you can check out [Learn TLA+](https://learntla.com/), and the more theoretical [Specifying Systems](https://lamport.azurewebsites.net/tla/book-02-08-08.pdf).

For more theory, check out [Formal Reasoning About Programs](http://adam.chlipala.net/frap/).

And for general projects look at [F*](https://www.fstar-lang.org/) and [Dafny](https://dafny.org/).

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

> I think we can assume it won't be as efficient has hand written code

Actually, surprisingly, not necessarily the case!

If you'll refer to the discussion in https://github.com/dafny-lang/dafny/issues/601 and in https://github.com/dafny-lang/dafny/issues/547, Dafny can statically prove that certain compiler branches are not possible and will never be taken (such as out-of-bounds on index access, logical assumptions about whether a value is greater than or less than some other value, etc). This lets you code in the assumptions (__assume in C++ or unreachable_unchecked() under rust) that will allow the compiler to optimize the codegen using this information.

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.