3 ms·
> Which of course remains an open question. Technically yes, but as Scott Aaronson says, a universe where P=NP would probably look very different from ours (an
by pron 11y ago
> Which of course remains an open question.
Technically yes, but as Scott Aaronson says, a universe where P=NP would probably look very different from ours (and PSPACE is harder than NP). In any event, verifying effectively Turing-complete languages (even total ones) is much harder than EXPTIME (and we know that EXPTIME > P).
> I find it very hard to reason about finite state machines in programs as a human
I didn't mean it like that (programming with explicit states). Just a model of computation where the number of states is bounded. Any program with finite memory is a finite state machine. Every language must support at least that.
> it eliminates the class of errors where one has "implemented" something by an infinite loop. It helps for concrete programs in the same way that it helps for theorems, no?
No, because when you prove a program property A you know that you've really proven "A or no-termination". So being able to prove any property is not an inconsistency. This is not the case for mathematical theorems that don't have running time, and where "no termination" is meaningless. If running time is 0, then A just means A, and if A is a contradiction then you have a real problem.
Now, what about eliminating non-termination from programs? Well, you're not really doing that either, because as far as we're concerned, a program that takes 10^100 steps doesn't really terminate at all. One could claim that people are more likely to accidentally write a function that loops forever than one that loops 2^64 times. This may be true, but this again relies on empirical facts rather than general mathematical properties.
In any case, what makes you think that languages like Idris may make verification easy? The few cases of programs verified in this mostly-manual way took years to prove, even for very small and intentionally "dumbed down" code.
- lmm 11y ago> I didn't mean it like that (programming with explicit states). Just a model of computation where the number of states is bounded. Any program with finite memory is a finite state machine. Every language must support at least that. Any program is (or can be modeled as) a finite state machine, sure. But useful programs are a small subset of the space of possible finite state machines. 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. > One could claim that people are more likely to accidentally write a function that loops forever than one that loops 2^64 times. This may be true, but this again relies on empirical facts rather than general mathematical properties. I am worried about not-terminating-in-reasonable-time (though much less worried than I am about looping forever), but can't we just make that one of the properties we keep track of and prove with the same tools? > In any case, what makes you think that languages like Idris may make verification easy? The few cases of programs verified in this mostly-manual way took years to prove, even for very small and intentionally "dumbed down" code. I guess my experience that keeping track of more properties in the type system doesn't make coding any harder. Compare Rust - writing Rust programs essentially means proving that things have valid lifecycles and are not used outside of them. This is a complex property that mainstream programmers were not previously proving at all - that many had despaired of ever being able to prove. And yet in practice people who write Rust find that not only can they do it, but the additional proof effort quickly becomes barely noticeable. Likewise with Idris you're proving termination in finite (though possibly unreasonable) time and once you get used to doing that it doesn't actually seem noticeably harder than not doing so. So I'm kind of hopeful that we can just keep improving the type systems used by mainstream programming languages until writing a program naturally includes proving the important properties of that program without even noticing.
- 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.