Re:The Hare programming language
by zozbot234 on Monday April 25, 2022 @10:32AM
(#31155378)
Formal verification doesn't scale to global properties in the general case. Global properties that are simple and type-like (in that they match the syntactic structure of the program in a fully "compositional" way, like Rust lifetimes) can be checked with comparable ease. Complex properties can often be checked within a single, self-contained, small-enough program module. Trying to do both at the same time - check complex properties globally - is highly problematic. That's why the Rust borrow checker has to make simplifying assumptions, and use 'unsafe' as an escape hatch.
[ Parent
| on HN ]
Re:The Hare programming language
by staticassertion on Monday April 25, 2022 @10:43AM
(#31155574)
I'm not really convinced that this is true. I think you're brushing up against Rice's theorem, which is that proving arbitrary properties about arbitrary programs is equivalent to the halting problem. That's why we constrain languages with type systems, which limits any typed language from expressing arbitrary turing complete programs.
Proof assistance is sort of irrelevant. Types and proofs are related, as denoted by the curry howard correspondance.
The real issue with "throwawaymaths"' point is that they're saying "use proof assistants" to people who are using proof assistants. SEL4 is a terrible example of a success story, as it took ages to complete, and then there was immediately a bug found in a class they weren't looking for - because rice's theorem.
They're clearly advocating for the use of specific and explicit proof assistants, which is fine and a totally reasonable thing to advocate for, but in no way is related to rust or the discussion, which is why I chose not to engage.