bootstrapping

Welcome to the bootstrapping wiki!

This wiki is about bootstrapping, i.e., building up compilers and interpreters and tools from nothing.

"Recipe for yogurt: Add yogurt to milk." - Anon.

short sci fi story Coding Machines by Lawrence Kesteloot, January 2009

Also see http://bootstrappable.org, which has pointers to a mailing list and IRC channel.

Simple explanation: bootstrapping is about building a compiler using tools smaller than itself, as opposed to building a compiler using an already built version of itself. The problem with the second is: Where did that prebuilt binary come from?

Current Topics

Past Research

bcompiler by Grimley Evans
This is a detailed log of the process of bootstrapping a series of languages up starting from just a hex assembler written using a hex editor.
The Cuneiform Tablets of 2015 by Long Tien Nguyen, Alan Kay
This discusses methods of long term software preservation. Briefly about hardware that will not degrade over time, but the majority of the paper is about how to design a software stack that can be executed in the far future. In order to achieve this they recommend build everything in terms of a machine with a short simple specification.
jonesforth.S by Richard W.M. Jones
In depth literate programming describing a complete implementation of forth. Bootstrapped from intel 32 bit assembly with lots of assembler macros into a fully self extensible forth. This is a really illuminating read, teaching a lot of details about forth as well as showing just how minimal a runtime it is possible to make a programming language with.
stoneknifeforth by Kragen
Kragen (again) doing amazing bootstrapping/self hosting work. This forth is implemented in a screenful of code, able to emit ELF files directly. Self extensible. Single char word names.
blynn compiler
This is a mini haskell compiler bootstrapped from C.
amber by nineties
These slides outline the developement of rowl and amber. This is a programming language bootstrapped up from assembly. rowl is implemented directly in assembly then parts of the amber vm and compiler are implemented in rowl, then the rest of amber is implemented by self hosting.
Mu by Kartik Agaram
A statement-oriented programming language (docs) that bootstraps up from x86 machine code, using just a handful of Linux syscalls (no libc). The language is memory-safe, and most statements translate 1:1 to x86 machine code. Implemented in 60k lines of a notation for x86 machine code, 40k of which are automated tests.
SCM-Go by pkelcjte
This project builds a SICP-style, Scheme interpreter with a REPL in Go. The blog post describes each phase. They're simple-looking. The Github integrates it into a total of 240 lines of code. Being a simple language, the Go implementation could be ported to anything else in our collection or straight hand-assemblied. Then, more complex stuff built on it like nineties or other LISPers do.
jrp.c by curtism
A very small x86 JIT stack calculator implemented in C. All of the instructions are coded in a clever way to make them each a double word or a quad word.
Yet Another BrainFuck Compiler by cameronswinoga
This is a brainfuck compiler implemented in C. It produces an elf file directly.
qcc
The QCC project: hooking tcc frontend up with qcc's code generator and creating a toybox style set of cc, as, ld tools.
List of Diverse Hardware
A big concern in dealing with trust in hardware is whether it's subverted or not. Intel, AMD, and many other big names have backdoors in their chips for management purposes. Among other things... ;) One cheat to get trustworthy image is to just use a computer you have no reason to believe is subverted. Acquire it under a boring buyer, it itself is a boring tech, do your bootstrapping thing in it air gapped, and use what it produces. It will likely *not* be subverted *by default* since the interdictors and TAO folks have limited resources w/ no reason to target the system. Use several that are different for best results. To help with that, I (Nick P.) put together a list of all kinds of CPU's and execution strategies on Schneier's blog. Something I left off the list are old TI-82 calculators, Palm Pilots, etc. Lots of old stuff lying around you can get in person with cash that is probably unsubverted.
golang talk golang transpiled from c to go
"It's time for the Go compilers to be written in Go, not in C. I'll talk about the unusual process the Go team has adopted to make that happen: mechanical conversion of the existing C compilers into idiomatic Go code". They wrote the compiler in C then translated the source code from C into Go almost automatically (had to do some manual fixing up). This is an interesting approach. Let's name it the transpile approach to self hosting.
asmutils a linux distro/userland implemented in assembly
This is a linux distribution implemented entirely in assembly. It doesn't depend on libc or anything.
COMFY-65 a macro assembler hosted on lisp
Henry G. Baker implements COMFY-65, a macro assembler hosted on lisp.
With the power of the entire Lisp language available for use within COMFY-65 macros, the amount of intelligence one can embed in these macros is limitless
B.Y.O assembler in forth by Brad Rodriguez
This is a teaching document that explains how to make an assembler in forth! It shows a very forth-idiomatic style of programming, and how easy it is to make an advanced assembler once you have a working forth.
mrustc by thepowersgang
This is a rust compiler written in C++, it translates rust to C. it makes the normal self hosted rustc compiler bootstrappable! It neglects the borrow checker but is still able to compile valid input source correctly.
bsdc by Leor Zolman
A C compiler (for CP/M) implemented in assembly. 25k lines of asm.
maru by Ian Piumarta
This is the real deal. Ian Piumarta implemented a fully bootstrappable scheme here starting from C, then self hosting to a compiler that emits binary directly. Very impressive!
CakeML by Myreen et al
CakeML is really really fascinating. They have created a theory of SML programs inside HOL, allowing them to prove properties of SML programs embedded inside HOL. They have created a (serious) compiler from SML down to assembly and proved that it preserves semantics all the way. They are then able to compile the compile simultaneously bootstrapping the proof to create a verified compiler binary for which it is proven that it compiles input programs and preserves their semantics. To my knowledge this is the first such development.
bootstrap by Richard Smith
This is an incredibly well developed bootstrapping project. hex assembler. elf maker. x86 assembler. linker. B compiler. C compiler. Includes implementations of various POSIX style libc functions along the way. It is extremely well written and worth studying!
asmc by Giovanni Mascellani
The asmc project is a small bootable kernel that loads up a payload which. payloads exist for assembly compilers and "G language" compilers. The G language is a low level lang below C which was invented to ease bootstrapping. An assembler (which can build the kernel) has been implemented in G.
blc by Pim Goossens
cmeta - Using ideas from META compiler compiler Pim builds the meta language up from raw hex. blc - binary lambda calculus implementation, capable of computing matt mights factorial program. built using the cmeta system. Incredibly terse. Surprising that the techniques of metacompiler compilers can be applied at such a low level. The amount of leverage may be highest in this project.
pascal-p by Pascal-P Porting Kit
"It compiles and runs a subset of the Revised Pascal language. That subset was designed to be the minimum language required to self compile for a new machine implementation. It was part of a "bootstrapping" kit designed to facilitate porting Pascal to new machines.". The pascal language was implemented with bootstrapping intention in mind. They have a simple "p code" bytecode language that eases the process.
eulex by David Vázquez Púa
This is a forth operating system with emacs like editor and lisp interpreter built in it. It's a 1700 line assembly script for the bootable forth compiler/interpreter and then the whole rest of the system is implemented in forth. I have not tried but apparently it can build itself with the assembler. This is very impressive work.

Past Research / intray

important: try to summarize lessons learned from each.

Groups

Karger-Thompson Attack

Anything related to the karger thompson attack: proof of concept demos, mitigations, theory.

  • multics the original paper explaining the attack (before thompson!)
  • SCM Security by Wheeler (Secure distribution & compilation of source fundamentals; Karger advised mastering it)
  • rotten by rntz (thompson attack demo)
  • rust infection by manishearth (thompson attack demo in the rust compiler)
  • tcc ACSAC by daved wheeler
  • CompCert by Leroy et al (Mathematically-verified, C compiler whose specs and proofs checked with tiny, verified checker)
  • CakeML by Myreen et al (Mathematically-verified, SML compiler whose specs and proofs checked with different, tiny, verified checker)
  • VLISP by Oliva and Wand (Article has links to VLISP which mathematically verified PreScheme and Scheme48)
  • KCC by Rosu et al (Executable, formal semantics for C in rewrite logic; could do that w/ simpler engine)
  • TALC by Cornell (Typed, assembly language to verify safety w/out compiler; checker can be simple; C subset + verified compiler to TALC)
  • CoqASM by Microsoft Research (Bootstrap in verifiably-safe assembly in prover checked by tiny, verified checker)

Ubiquitous Implementations

These are tools written in ubiquitous languages, therefore they can be used in a wide variety of contexts.

  • shasm by Hohensee (x86 assembler written in BASH)
  • AWKLisp by Bacon (LISP written in Awk; includes Perl version from Perl Avenger)
  • Gherkin by Dipert (LISP written in Bash)
  • BASH Infinity by Brzoska (BASH framework/routines that might help write compilers in it)
  • mal "make a lisp" implementing a very basic lisp interpreter in hundreds of languages
  • [4] A new bootstrapping project that is built up to a self host language above assembly from a minimal DOS platform.

Small C Compilers

  • c4 by rswier (incredibly short c compiler)
  • cc500 by edmund grimley-evans (tiny c compiler)
  • CUCU by Zaitsev (Small, C compiler designed for easy understanding)
  • SmallerC by Frunze (Small, single-pass, C compiler for several ISA's)
  • picoc interpreter.
  • C Interpreter by Dr Dobbs (Describes building a C interpreter with source)
  • [5] Small C for I386 (IA-32)
  • Selfie, a tiny self-compiling compiler for a subset of C, a tiny self-executing MIPS emulator, and a tiny self-hosting MIPS hypervisor, all in a single 7kLoC file. HN discussion. Paper.
  • Tiny C expression compiler Written in Forth based on tinyc.c by marc feeley.
  • [6] [7] C compilers by Rui Ueyama blog
  • [8] 10 hour self hosting c compiler

Grammars, Parsing, and Term Rewriting

  • Grammar Executing Machine by McKeeman and He (Incrementally extend languages from simple to complex grammars in interpreter(s))
  • peg by kragen (parsing)
  • PEG-based simple compiler by Ian Piumarta
  • META II by Bayfront Tech (Original meta-compiler w/ live code and detailed tutorial; OMeta was successor)
  • META II implementation by Lugon (Looks like a small implementation of META II; also bootstrapped in META II)
  • OMeta# Intro by Moser (OMeta intro that nicely illustrates the meta approach/advantages)

Virtual Machines, Instruction Sets

  • P-code by Wirth (High-level language & libraries target ultra-simple, portable interpreter)
  • sweet16 by Steve Wozniak
  • Tiny BASIC by Allison (Small BASIC whose original VM took 120, virtual opcodes to implement using 3KB RAM)
  • Klip by Cutting (Compiler & runtime for simple language for students; done in C#; runtime is very readable)

CPU's for Bootstrapping: The Simple, The Verified, and The Necessarily Complex

  • NAND2Tetris by Nisan and Schocken (Guide that teaches hardware step-by-step in fun way with simple CPU emerging)
  • J1 by by Bowman (16-bit Forth CPU in 200 lines of Verilog that does 100MIPS on FPGA's)
  • H2 by Howe (Modified, VHDL version of J1 with detailed description and Howe's code MIT-licensed)
  • RISC-0 by Wirth (Simple, RISC CPU & SOC designed for Oberon language with detailed docs and source online)
  • JOP by Shoeberl et al (Embedded Java processor that takes up 1830 slices on FPGA)
  • Scheme Machine by Burger (Scheme interpreter implemented as CPU using formal methods)
  • ZPU by Zylin AS (Tiny, 32-bit CPU for deep embedded apps in 440 LUT's)
  • J2 by Landley et al (Clone of cost-efficient, SuperH-2 CPU in open-source)
  • VAMP by Beyer et al (Formally-verified, DLX-style processor in 18,000 slices on Xilinx)
  • Leon3 by Gaisler (Industry-grade, 32-bit SPARC w/ auto-configuration of core and GPL license)
  • Rocket by Univ of CA (1.4GHz RISC-V CPU and generator for customization)
  • OpenPITON by Princeton (25-core, shared-memory, SPARC CPU open-sourced and very scalable)

Minimal Operating Systems

  • KolibriOS - lightweight assembly OS.
  • MikeOS - same.
  • Sortix - modern reimplementation of POSIX in C. (Note: No perl port and GCC does not build natively on it. (yet.))
  • ASMLINUX - linux kernel, but the userspace is implemented entirely in assembly.
  • LFS - Guide on building Linux and the GNU userspace.
  • buildroot
  • NetBSD build.sh - Cross-build a complete NetBSD ISO from a foreign OS. There's also a guide in the official NetBSD docs.
  • lh-bootstrap - alternative linux distro, using musl instead of glibc.
  • xv6 - UNIX teaching OS MIT
  • OS/161 - UNIX teaching OS Harvard
  • https://landley.net/toybox/about.html - Toybox, alternative to Busybox by Robert Landley, see also Aboriginal Linux and mkroot by the same author, which are all geared toward a minimal boostrappable system
  • https://github.com/pikhq/bootstrap-linux - Another take at a bootstrappable Linux system
  • Project Oberon - Operating system and programming language Oberon (from the creator of Pascal - Niklaus Wirth)
  • TinyGo Operating system in programming language Go
  • TamaGo - Another operating system in programming language Go
  • seL4 Microkernel - OS kernel in less than 10.000 lines of source code and less than 150 KB binary
  • Ultibo - Unikernel for Raspberry Pi written in FreePascal

Biology/Other?

Helpful Links

Retrieved from "https://bootstrapping.miraheze.org/w/index.php?title=Main_Page&oldid=333"