3 ms·
> It's not beyond hope that we could find a subset that allowed us to write most useful programs but was easier to reason about. It is beyond hope that we find
by pron 11y ago
> It's not beyond hope that we could find a subset that allowed us to write most useful programs but was easier to reason about.
It is beyond hope that we find a subset that's generally easier to reason about. Verifying one line programs of this sort:
if (a && ~b || c || ~d && e ...)
crash()
is already NP-complete (SAT). Adding some loops that are of depth 2 makes it PSPACE-complete (TQBF, aka QSAT). I can't think of a useful programming language that doesn't have even small-constant-depth loops (which makes it finite state) and simple boolean algebra. Software verification is about verifying some subsets of programs that humans happen to write. It is categorically impossible to write a general-purpose language where all programs are easier to verify than PSPACE.
> but can't we just make that one of the properties we keep track of and prove with the same tools?
Sure, with super-exponential complexity :) But again, this is in the worst case. We hope that humans usually write programs that are simpler.
> I guess my experience that keeping track of more properties in the type system doesn't make coding any harder.
If you mean H-M types as in Haskell, then the properties those types enforce are either trivial (i.e. true for all programs, e.g. function returns Int), or a result of a finite state machine (that's the proving strength of H-M types). You cannot prove even a single bit of a program's output that's a result of non-constant-depth recursion (there's a special case for recursion which is of depth that's a constant multiple of the input length, like `map`). If we take Haskell, you can replace each of your functions with constant-depth recursion (0 or 1 would suffice in virtually all circumstances) and the program will still typecheck yet will be completely wrong.
As for Rust's linear types, that is precisely what I'm talking about. A certain class of bugs (memory errors) that humans are known to make and that verifying with abstract interpretation is easy. That's what software verification aims to do. We cannot hope of proving general programs generally correct, regardless of the language they're written in.
BTW, thinking of type systems muddles understanding in this case, because type systems are just notation. The verification taking place in most sound type systems is abstract interpretation. Yes, we can find more important properties to verify with abstract interpretation, but it has been proven that some properties will forever elude abstraction.
The way abstract interpretation works is that it translates the program into an "abstract" program which is just a finite state machine, with the number of states equal to the number of concrete types, and running an exhaustive model checker on that; this means that the complexity of inferring this kind of types is Ω(|S|), namely, linear in the number of concrete types. As abstract types can multiply the number of concrete types, the inference can become exponential in the worst-case, but it usually doesn't. Once you introduce dependent types, the algorithm is still Ω(|S|) -- linear in the number of state, i.e. types -- but now the number of types is unbounded, and so the problem becomes undecidable.
> until writing a program naturally includes proving the important properties of that program without even noticing.
You're right, but this entirely depends on which properties are found to be important (and has little to do with type systems specifically; again, this is mostly notation[1]), and that, in turn, is rather empirical.
[1]: Not entirely, though, but mostly.
- lmm 11y ago> I can't think of a useful programming language that doesn't have even small-constant-depth loops (which makes it finite state) and simple boolean algebra. Software verification is about verifying some subsets of programs that humans happen to write. It is categorically impossible to write a general-purpose language where all programs are easier to verify than PSPACE. Eh. Again, I don't think we necessarily need arbitrary boolean algebra - something that's hard enough to reason about as a human - and may be able to capture the valuable use cases in a simpler model. Fundamentally if we have any hope of doing verification at all, surely we can characterize the constraints we need for verification and then push them back to the programming language level. > If we take Haskell, you can replace each of your functions with constant-depth recursion (0 or 1 would suffice in virtually all circumstances) and the program will still typecheck yet will be completely wrong. Could you expand on this / give an example? I don't think I follow. And I take it from what you're saying that this doesn't apply if we permit dependent types? > BTW, thinking of type systems muddles understanding in this case, because type systems are just notation. The verification taking place in most sound type systems is abstract interpretation. Yes, we can find more important properties to verify with abstract interpretation, but it has been proven that some properties will forever elude abstraction. Properties that are important for real-world programs? Abstract interpretation sounds very similar to how we reason about programs as humans. It just seems like to the extent that we understand how to do something at all we should be able to formalize that understanding. If we're talking about using programs to address open questions - a best-effort at the travelling salesman problem, say - then I can see how you might end up with a program that had a pile of heuristics that seemed to work but with no concrete understanding of how or if it worked - except that even then you'd probably use a well-known, formally validated heuristic rather than using the program as a medium for mathematical research. I just think (empirically) it would be very rare as a business requirement to need to do something completely unproven, and therefore it might be possible to have a useful general-purpose programming language that didn't allow doing that.
- pron 11y ago> Fundamentally if we have any hope of doing verification at all, surely we can characterize the constraints we need for verification and then push them back to the programming language level. That is not what the verification community is trying to do at all, because trying to find a language that is not even NP-complete to verify and is still generally is absolutely impossible (explanation later). What the verification community is trying to do is to come up with approaches that make it possible/easy to verify some code, which is hopefully the majority of code. As far as languages go, the hope is that a language can make some verification of some code easier than in other languages. A general-purpose language that is at least useful in some cases, and in which all programs are easily verifiable can only exist if P=NP. The reason is this: at best, you can hope that the proof of correctness is checkable in polynomial time. This puts it in NP. If constructing a proof of correctness is possible in polynomial time, so is coming up with the solution in the first place. Namely, such a language wouldn't even need to be programmed. It will be a constraint solver (that somehow is in P). SQL minus boolean expressions might be the best you could do. Possibly useful, but certainly not general-purpose. > Properties that are important for real-world programs? Yes, and they are quite common in distributed algorithms. > It just seems like to the extent that we understand how to do something at all we should be able to formalize that understanding. Yet we can't because when we reason about something we assume a certain regularity of the state-space, that is often wrong in practice. That link I showed you where there are visualizations of state spaces, shows the one for the CAN bus protocol. It is the most complicated example on that page, and it is the very real protocol used by different components in your car that need to communicate. > I just think (empirically) it would be very rare as a business requirement to need to do something completely unproven That depends a lot on what you do. If you design schedulers for OS kernels, concurrent data structures, or distributed algorithms you see that these difficult cases are the rule rather than the exception. I work on concurrent and distributed algorithms, and I do formal verification (TLA+ is my current tool of choice) most day every day. TLA+ offers both a theorem prover (a la Isabelle/Coq/Agda) as well as a model checker. Manual deductive proofs are virtually never worth the trouble (that would take me years), and even with a model checker -- where you just press a button and if there's a bug, any bug, you get a full trace of the execution that led to the bug -- it's still a lot of work, because distributed algorithms are just essentially complex.