6 ms·
> Writing a complex program in a very abstract language further away from an engineer's typical problem domain, being fairly limited in types of languages suppo
by naasking 9y ago
> Writing a complex program in a very abstract language further away from an engineer's typical problem domain, being fairly limited in types of languages supported for extraction, and/or still having to have an awful lot of faith in the extractor (which itself is unverified as near as I can tell) are all things that are currently keeping me out of Coq for immediate use cases.
Indeed, which is why I think something like Idris will probably be the future. We need to combine programming and theorem proving, and allow us to move the line incrementally closer to or further away from full verification as the problem evolves, becomes better understood, or new techniques emerge.
Full verification for most programs is still too difficult, but we should be able verify what's feasible and use standard testing techniques for the rest. It will still be a huge leap towards real software engineering.
- pron 9y ago> Indeed, which is why I think something like Idris will probably be the future. I very much doubt it. I think other code-level specification languages (like JML for Java or ACSL for C), are much better suited to the configurable level of verification that you're looking for. The reason their tooling[1] is better than Idris's is not just because they're more mature, but for deeper reasons, too. While working in different formalisms (dependent types or direct logic) doesn't make much of a difference, when you specify in types, the lowest level of confidence you allow is formal proof, which, as you note, is beyond reach for anything but small and simple code. It doesn't make much of a difference whether you need to prove a JML specification or an Idris type, but a JML specification allows you to optionally use weaker but much cheaper forms of verification like concolic testing, regular test generation etc. OTOH, Idris already has test-generation libraries that require yet another form of specification, just because types won't work with anything less than proof. I heard you could achieve the same with types, but that requires enclosing the weakly-verified types in monads, so type T and type `Weak T` is not the same. Idris is one of many (I've lost count) of experiments in code-level formal verification. So far I don't see any indication it is closer to being "the future" than any of the multitude of other experiments. I don't think it's necessarily worse, either (while suffering from the problem I mentioned above, I assume it has advantages, too), but right now if you hear a lot about Idris it mostly means you hang around Haskellers, who have taken a liking to the language because of its similarity to Haskell in both spirit and style. [1]: See here for an example of some automated JML tools http://www.openjml.org/ http://www.openjml.org/, and here for semi-automated tools (using proof assistants) http://krakatoa.lri.fr/ http://krakatoa.lri.fr/
- naasking 9y ago> It doesn't make much of a difference whether you need to prove a JML specification or an Idris type, but a JML specification allows you to optionally use weaker but much cheaper forms of verification like concolic testing, regular test generation etc. I think you're overshooting the target I was aiming at. You can use simple algebraic types in Idris and check your invariants dynamically as you would in any less expressive language, then incrementally move some of these to statically checked invariants where feasible. Specification-tools require a lot more work in separate specification languages, which are often unwieldy. > if you hear a lot about Idris it mostly means you hang around Haskellers, who have taken a liking to the language because of its similarity to Haskell in both spirit and style. To some extent that's true. So take Haskell, remove the default lazy evaluation which trips so many people up, remove all the restrictions around types since it supports full dependent typing (no more whacky type trickery to check some invariants statically!), support for syntax extensions to support EDSLs, and easy integration with C. Welcome to Idris. Frankly, this is pretty much the full wishlist that advanced programmers have been wanting for years, and I've seen a lot of interest in Idris since its recent 1.0 release.
- pron 9y ago> You can use simple algebraic types in Idris and check your invariants dynamically as you would in any less expressive language, then incrementally move some of these to statically checked invariants where feasible. That simply means writing less specifications, or writing specifications in two different ways. Spec languages allow you to decouple the specification from the verification effort. You write some specs (or not), and then you decide whether you want to prove them, generate tests, add assertions etc. > Specification-tools require a lot more work in separate specification languages, which are often unwieldy. They require exactly the same amount of work (whether you write your spec using types or logic doesn't make a difference; the specs are the same), and the language is mostly the object language (i.e. the programming language) with the addition of some quantifiers. The result is usually not much different than a language with a rich type system. > Frankly, this is pretty much the full wishlist that advanced programmers have been wanting for years, and I've seen a lot of interest in Idris since its recent 1.0 release. I think this is the wishlist of programmers who like Haskell... Formal methods people don't agree at all that this is the future.