Bootstrapping trust in compilers

I described how to handle this and trustworthy compilers in general here:

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

My replies to "jeffreyrogers" have details and links to examples. You do it bottom-up. I disagree with using Forth as it's a weird language & that reduces number of people that will verify it. One would be better off with P-code given it was successfully used to get Pascal on 70 or so architectures. Wirth and Jurg later used the same approach in Lilith workstation with M-code and Modula-2. They were able to put together a CPU, high-level assembler (M-code), high-level language, compiler, OS, editor, and so on in around 2 years by keeping it simple and consistent. Something like that which maps to what people already know and do.

So, again, here's your model:

1. Portable stack or register VM that's ultra-simple plus similar to language targeting it.

2. Implementations of that diversified by authors, OS's, and HW.

3. Subset of language (or simple HLL like Modula-2) coded in whatever you need to get initial compiler working.

4. That same compiler re-coded in language of trusted VM and run on all targets to ensure same results (equivalence checks).

5. Use that binary to produce an executable from compiler's HLL source and equivalence check again.

Note: Did I word 5 less confusing than most people do at this point? I put effort into avoiding "compile the compiler with compiler etc." ;)

6. Use the binary from No 5 to compile future versions of the compiler written in a subset of its own language. Should continue using a subset for easier understanding and correctness. Check language features with testing suite and sample applications instead of with overly complicated compiler.

So, there you go. Easy stuff already proven by Wirth et al. Not worth another 100 write-ups. Just use what we know. The real problem worth lots of discussion and investigation is certified, secure/robust compilation. That is a difficult problem open to investigation with new, interesting results each year. Bootstrapping compilers for masses? That's so 1971. ;)

Trust is certainly one of the issues when languages migrate to requiring themselves to bootstrap.

However, by far the most infuriating (and one I run into frequently in my line of work, hence the anger) is when you are trying to get the language running on a platform for which binary bootstraps do not yet exist.

Portability matters. If you want your language to be useful and available to as many people as possible, why would you seek to artificially limit the number of platforms it can be built on, just so you can avoid writing the bootstrap in C? I'm sure there is some amount of pride on the part of the language author when their language can bootstrap itself, but it certainly isn't a pragmatic decision.

It's especially frustrating when the bootstrap requirement itself changes so that only very recent versions of the language are sufficient (e.g. GHC), leaving the porter to have to reach back into the archives and carefully plot a path through building multiple versions from the original C-based bootstrap until they finally get to master.

This is painful, painful work, and then has to be done all over again for e.g. 32-bit vs 64-bit. It doesn't have to be like this.

This is one of the discussions we had at the Reproducible Builds Summit last week: https://lists.gnu.org/archive/html/guix-devel/2015-12/msg00107.html ↗ .

In GNU Guix, we don't go as far as the author suggests (starting from a FORTH-like VM, then building a small Lisp, etc.), but we've been thinking about going in that direction: We already have Guile Scheme at the bottom, with which we can implement a range of tools, ranging from HTTP/FTP clients to ELF parsers, and more. We could imagine having (possibly feature-limited) variants of some of the bootstrap tools, written in Scheme, for the purpose of building the "real" tools.

Our current bootstrap looks like this: https://www.gnu.org/software/guix/manual/html_node/Bootstrapping.html ↗ .