News for hackers. Stuff that matters.
Re:How Did Software Get So Reliable Without Proof? (1996) [pdf] by lmm on Wednesday March 16, 2016 @09:31AM (#11297101)
Sure. What I'm saying is that you can encode statements about values and statements about types the same way, by using dependent types, and once you do that then you can verify halting of metric-recursive functions using exactly the same approach that you use to verify halting of structurally-recursive functions. So proving halting using a combination of proofs that metric-recursive functions halt and proofs that structurally-recursive functions halt isn't an example of it being useful to use two different approaches for different parts of the proof of correctness of a program, and doesn't make the case for having multiple approaches to verification and bridges between them.
Re:How Did Software Get So Reliable Without Proof? (1996) [pdf] by pron on Wednesday March 16, 2016 @09:46AM (#11297199)
That depends on what you mean by "exactly the same approach". Can the same algorithm construct both proofs? Can it construct both proofs with the same computational complexity? If not, then you're not using the same approach.

Using dependent types is more of a particular notation than a solution to verification. How you prove your type inference/checking is the hard part. Examples of approaches include SAT/SMT solvers, symbolic model checking, manual deduction, explicit model checking, abstract interpretation (which is really abstraction + explicit model checking; H-M inference algorithms can be described in terms of this approach), weakest preconditions, etc. You can use all of these approaches to infer/check dependent types, just as you can use them to verify program logic stated using means other than dependent types.

Re:How Did Software Get So Reliable Without Proof? (1996) [pdf] by lmm on Wednesday March 16, 2016 @11:00AM (#11297837)
> That depends on what you mean by "exactly the same approach". Can the same algorithm construct both proofs? Can it construct both proofs with the same computational complexity?

Yes, because once you're representing the values with dependent types, metric recursion and structural recursion are physically the same thing.