dafny VS unsafe-code-guidelines

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.

Useful context on the Rust side is this issue [1]. It sounds like some of the author's concerns are addressed already.

[1]: https://github.com/rust-lang/unsafe-code-guidelines/issues/4...

Is this captured by one of the known soundness conflicts? If not then should consider adding it to the list.

There are some competing proposals for different memory models. Stacked borrows is the current proposal, but there are more work in the approproate WG.

Thank you /u/RalfJung for bringing formal methods to Rust, both through models like Stacked Borrows, by developing miri, and by working on unsafe-code-guidelines which aims to specify exactly what is and isn't allowed in unsafe code (surprisingly, it's an open question as 2023!)

You could imagine some way to make this safe for example automatically convert &'short &'long mut T to &'short &'short T, but it's non-trivial to prove they are safe at all, not to mention ensuring this is correctly implemented in the compiler. If you're interested there's also a discussion on whether the opposite (& & T to & &mut T) is sound here.

Agreed! MIRI is so good, it still feels like magic to me. It also comforts me that the Rust team takes improving unsafe semantics seriously, with the past Unsafe Code Guidelines WG and today's operational semantics team (t-opsem).

I think there are some aspects of this rule that are still undecided. See for example:

- https://github.com/rust-lang/unsafe-code-guidelines/issues/8...

- https://github.com/rust-lang/miri/issues/2732

C is much better specified than unsafe Rust. Some things are just not worked out yet in Rust. This may sometimes even bite very experienced devs, such as this issue with Box's aliasing semantics, which tripped up the author of left-right.