Past Research

From bootstrapping
Revision as of 02:29, 7 July 2022 by 51.9.70.151 (talk) (Content moved from main page)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Past Research[edit]

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[edit]

important: try to summarize lessons learned from each.