5 ms·
> You are seriously overselling these results. Maybe. Maybe not. No one knows for sure, and no one has anything to suggest that the path forward is now clear.
by pron 10y ago
> You are seriously overselling these results.
Maybe. Maybe not. No one knows for sure, and no one has anything to suggest that the path forward is now clear. Those results provide good enough cause to believe that the problem is very hard. Empirical experience only strengthens the belief in that assumption (suggesting that we cannot easily find an easy-to-categorize subset of programs that is generally useful yet easier enough than the worst-case).
> Here's one way to make termination proofs modular: Take the graph of your function (vertices for each value of the arguments, edges for recursive calls) and take its transitive closure. If you can cover the transitive closure with an arbitrary number of individually well-founded relations, the function terminates.
Sure, that's how abstract interpretation works. But it doesn't always work, and proving termination says absolutely nothing about proving other properties.
> Does the consistency of ZFC "elude the power of math"?
Yes.
> The point of having contextual equivalence or a program logic is that every property you can express in your programming language/logic survives this state reduction.
Then those properties are weak or the reduction is hard. It's a simple consequence of bounded halting and the model checking results (also, I think I've seen Cousot give some simple examples of properties that cannot survive state reduction). In any event, even if you find properties that you can reduce in this way, the "model-checking isn't FPT" result, shows that you won't be able to combine them to prove global results (unless the local property happens to be all that's necessary).
> Right now verifying large programs is possible for a team of experts with a lot of time and money.
No large or even mid-sized program has ever been verified using PLT methods, no matter the size of the team or the effort. A medium sized business program is ~1MLOC. A large one is ~5-10MLOC. Programs that have been formally verified using PLT approaches are hardly within an order of magnitude from 100kLOC (from below, of course). It is also important to know that those verified programs don't employ arbitrary common algorithms, but only the simplest possible algorithms, for the purpose of verification.
> It's very much the goal for PLT. :)
What gives you that impression? My impression is that the goal is to verify important "kernels" for security or other crucial properties, at some acceptable cost given the small size and the great importance. Maybe some people hope that affordable whole-program verification would one day be possible (this is not unique to the PLT approach), but I don't think that's the current goal.
> A decade or two in the future it'll probably be routine and just another tool you use, similar to static analysis or unit tests.
I am not aware of a single researcher who believes that, but I'd like to know who does.
> But there are no fundamental restrictions which would prevent us from verifying, say, the Linux kernel. Apart from it being way too expensive.
I'm not sure what you mean by "apart from it being too expensive". A restriction that sets the complexity of that task at more than the lifespan of the universe would be a fundamental restriction. Anyway, there are no known ones, no. But it's like saying that there are no known fundamental restrictions that prevent us from proving P /= NP or the Goldbach conjecture, but stating confidently that either will be accomplished in some known timeframe is a whole other matter.
> If it was written in a reasonable languages, which encouraged programmers to develop truly sound abstractions it could be orders of magnitude less expensive, though...
We don't know that at all, and there are certainly no known results that suggest this may be the case. No one knows whether "good abstractions" make verification scalable. This may be what some people hope, but it is no more or less promising, and no more or less substantiated than the hope that, say, CEGAR model checkers would be able to verify the Linux kernel. Both are theoretically possible outcomes, both show some promise, but neither makes us confident that it will one day be so. If anything, my money is on CEGAR, or some combined approach where CEGAR would do most of the work.
- fmap 10y ago> Sure, that's how abstract interpretation works. But it doesn't always work, and proving termination says absolutely nothing about proving other properties. Abstract interpretation has nothing to do with disjunctive well-foundedness. The latter is a specific proof method which has pretty much revolutionized automated termination proving in the early 21st century (due to being modular and therefore allowing for easy combination of decision procedures). >> Does the consistency of ZFC "elude the power of math"? > Yes. Yet I can easily show ZFC consistent in CiC with excluded middle at Type. Sets are graphs modulo bisimilarity, choice follows from excluded middle at type. Conversely, classical CiC is consistent relative to ZFC with enough Grothendieck universes. Math doesn't end at ZFC, and no, not even in practice (higher category theory pretty much requires these constructions). > I'm not sure what you mean by "apart from it being too expensive". But it's like saying that there are no known fundamental restrictions that prevent us from proving P /= NP or the Goldbach conjecture, but stating confidently that either will be accomplished in some known timeframe is a whole other matter. One of them requires lots of perspiration, the other requires some fundamental new insight. This is not science fiction. It's not even fiction. You can sit down right now and show the correctness of arbitrary data structures and algorithms in Coq, using, e.g., Charguéraud's CFML. You can even verify arbitrary C programs, using VST, even though I wouldn't recommend it (seeing what guarantees the C semantics really give you, compared to your mental model of C can lead to night terror in adults).
- pron 10y ago> Abstract interpretation has nothing to do with disjunctive well-foundedness. Abstract interpretation has to do with every proof technique regarding computation. > The latter is a specific proof method which has pretty much revolutionized automated termination proving in the early 21st century (due to being modular and therefore allowing for easy combination of decision procedures). That's great, and model checking and abstract interpretation completely revolutionized many kinds of program proofs -- termination, temporal logic, memory safety and many more -- but the fact remains that no one has ever been able to fully verify a large real-world program using any known technique, and no one -- to the best of my knowledge -- seems to think we're on the path that will get us there any time soon. You'll find that the people who use formal methods on a regular basis (like me, if only in the past year or so) are the ones that are most cautious about pie-in-the-sky promises. Yes, some things will get easier; yes some properties will become easy to prove. But full, affordable program verification? Probably not in the foreseeable future, if ever. People like Xavier Leroy, who are experts in deductive verification methods are always very cautious about making such optimistic promises. Leroy, e.g. believes that deductive methods are suitable only for smallish programs. In fact, when it comes to manual formal verification, I am not aware of anyone who claims they will become generally affordable any time soon. Automated methods (model checkers and SMT solvers) are used almost exclusively for real-world programs, with only a small smattering of manual deduction, usually to tie together automated results. Right now, the goal for manual deduction is to match the cost of current high-assurance development (which is too expensive for ordinary programs, if possible at all, due to size). Manual deduction also seems especially sensitive to algorithm complexity (not computational complexity, but "conceptual" complexity, which may be related (perhaps to space complexity more than time complexity)), but really the potential effectiveness of various methods to affordable whole-program verification is no more than a personal affinity at this point. No one has anything definitive to claim. What I do find interesting is that it is PLT fans (maybe not the researchers themselves who are usually more cautious) who make the most outlandish claims despite the fact that when it comes to verification, PLT has had less real-world success than pretty much any other approach. Perhaps it's because those techniques are least put to the test, so there are no disappointments. > Yet I can easily show ZFC consistent in CiC with excluded middle at Type. I don't understand. Then the same result applies to CoC. There is nothing intrinsically special about ZFC as a formal foundation, it's just what most people take as the foundation. If you want to base math on another foundation go ahead, but an unprovable program exists in whatever foundation suits your taste, too. > One of them requires lots of perspiration, the other requires some fundamental new insight. You've just thrown all of complexity theory out the window. "Lots of perspiration" can mean (provably!) more resources than the entire universe can afford. Theoretically winning at Go also required little insight; actually winning required a lot of insight (namely, restricting the problem to facing human opponents and studying their behavior). If anything, it is the difference between decidability and undecidability that is of lesser importance than difference in "perspiration".