Comment by rntz | Hacker News Reader

Comment by rntz | Hacker News Reader

Parent Full thread

No, the proof that the compiled code is "correct" does not depend on the compiler being correct - it can be checked independently.

Of course, if the compiler is incorrect it might generate incorrect code, but then the "proof" that the code is correct would not check.

Mind you, it's very ambiguous to describe what their compiler is doing as producing a proof of "correctness". Any time someone says "correct", you should ask, "correct with respect to what?" In this case, AIUI, their compiler produces: (a) a formal description of what the program does (what they call "a high-level shallow embedding of the program's semantics") (b) a proof that this is in fact what the program does (its "correctness")

The idea being that if you want to show that your program is actually correct with respect to the specification you really care about, you do the proof on the formal description (a), and then (b) automatically guarantees your proof carries over to the actual program.

Yes, that's exactly what I meant. But compare this to CompCert. CompCert itself is verified, which means it doesn't have to output a proof for each program it compiles.

Even if you don't care about the theoretical concerns of for all vs for each, there are two practical concerns with this kind of system. 1) the compiler could just fail to output a valid proof for some program and you're out of luck until the compiler bug is fixed. 2) Proof checking can get pretty time intensive and it'd be better to do it once for the compiler, than every time you run the compiler.

Indeed, but proving a whole compiler correct is really hard. :P

Not if you start with a small compiler

No, it's still hard. The best approach I've seen to this outside CompCert is a project that independently tried my own recommendation of breaking it into stages then using whatever verification works on a per stage basis. So, one prover and approach works best for Stage 1. Then another maybe for Stage 2. Some compositional method to tie them together.

They were making a MIPS compiler. Got pretty far in short time paper covered with a fraction of CompCert's effort. Nonetheless, the untrusted compiler plus trusted checker method has the most supporting evidence in literature for getting the job done and ease of building. So, even my recommendation should take that approach where possible.

It's hard, but I've for awhile thought that developing these tools in a more bottom-up would help. And of course orthogonal components, as you say, is a good idea for just about anything.

I don't agree. Matter of fact, I recommended it here in an answer to the reproducible build meme that pops up. See my conversation with jeffreyrogers here:

https://news.ycombinator.com/item?id=10182282

Looking back at it, I meant to say "I don't disagree. I had made similar recommendations before."

Totally changes meaning of comment till you click the link haha.

Actually, if you take a look at the semantic preservation theorems that CompCert actually proves, you can see that it allows for compilation to fail, even in optimization and code generation:

http://compcert.inria.fr/doc/html/Compiler.html

As one particular example, register allocation is performed by an untrusted oracle that may not even terminate, and then verified a posteriori:

http://compcert.inria.fr/doc/html/Allocation.html

They proved a traditional register allocator correct in a paper (https://www.cs.princeton.edu/~appel/papers/regalloc.pdf), but I guess there are practical reasons why they are not using it in CompCert by default.

Reply on news.ycombinator.com