4 ms·

It was written in B. And B was written in B. To trace the bootstrap up into the high level, you have to go further back than the PDP-11. To bootstrap B on th

by retrac 6y ago

It was written in B. And B was written in B. To trace the bootstrap up into the high level, you have to go further back than the PDP-11. To bootstrap B on the PDP-7 and GE-635 machines he had access too, Ritchie wrote the minimum subset required to compile a compiler in B, in a language known as TMG (in the vein of, and a big influence on, Yacc and similar). This minimal bootstrap was then used to compile a B compiler written in B, and further development was self-hosted. Later, the language would be retargeted to the PDP-11 while on the PDP-7. Various changes, like byte-addressed rather than word-addressed memory, led to it morphing into C after it was moved. There was no clear line between B and C -- the language was self-hosting the whole time as it changed from B into C. Mr. Ritchie wrote a history from his perspective published in 1993. I've mostly just summarized it above. It's available here: https://web.archive.org/web/20150611114355/https://www.bell-labs.com/usr/dmr/www/chist.html https://web.archive.org/web/20150611114355/https://www.bell-...

systemvoltage 6y ago
When people say bootstrapping, is this how all computer languages came to be? Or there has been multiple attempts at bootstrapping? What I’m getting at is whether all languages have a single root.
- retrac 6y ago
  Yes, bootstrapping with regard to languages is the trick of getting that first compiler running so you can compile the rest of the compiler. It has been done many times. The first assemblers were written directly in machine language. The first compilers were written in assembly. Many implementations of FORTRAN, ALGOL, COBOL, etc. As late as the 1970s it was not unknown to write a new high level language directly in machine code. Steve Woz's BASIC for the Apple II was "hand-assembled", as he put it. So, taken literally, certainly not. People still do it today as a hobby or educational project. But if we take the question in a looser sense? Yes kind of, at least in the UNIXish world. No one has implemented a serious high level systems language, except in a high level systems language, for a long time now. Rust, for example, was initially implemented in Ocaml. And normally that's what would be called the first Rust bootstrap. But OCaml was implemented in C, probably compiled by Clang or GCC. GCC was written in C and... so on. Often one finds it does lead back to DMR at a PDP-7. On the other hand, I strongly suspect something like IBM's COBOL compiler for their mainframes (still supported and maintained today!) would not have such a heritage.
  - systemvoltage 6y ago
    Fascinating and inspiring, thank you for taking the time to distill it so clearly.
    - deleted 6y ago
      [deleted]
  - musicale 6y ago
    > Steve Woz's BASIC for the Apple II was "hand-assembled", as he put it. Very cool - so basically (haha) Woz's integer BASIC was bootstrapped by writing it in assembly language and translating it into machine code by hand. I wonder if someone (Woz?) has written a 6502 assembler in integer BASIC to allow it to bootstrap itself?
    - rob74 6y ago
      I'm not an expert, but I guess "bootstrapping" only applies to compilers, and Apple II BASIC was an interpreter. An interpreter doesn't have to compile itself, only run the programs you give it. So on an 8-bit computer the priority is to have an implementation that (a, and most importantly) takes up as little space as possible and (b) is reasonably fast.
      - deleted 6y ago
        [deleted]
      - sn41 6y ago
        There are metacircular interpreters, like in Scheme (see SICP [1]). But this is rare, compared to bootstrapping compilers. [1] https://mitpress.mit.edu/sites/default/files/sicp/full-text/sicp/book/node76.html https://mitpress.mit.edu/sites/default/files/sicp/full-text/...
    - wazoox 6y ago
      The Apple ][ has a monitor in ROM that allows to enter machine code directly. The legend says that for the Apple I, Woz knew the complete integer basic machine code and could type it live into the monitor.
- musicale 6y ago
  Interesting article on how the original CDC 6000 Pascal compilers were bootstrapped (including the scanned source code listings as PDFs!?!): http://pascal.hansotten.com/niklaus-wirth/cdc-6000-pascal-compilers/ http://pascal.hansotten.com/niklaus-wirth/cdc-6000-pascal-co... "The method used to create the first Pascal compiler, described by U. Ammann in The Zurich Implementation, was to write the compiler in a subset of unrevised Pascal itself, then hand-translate the code to SCALLOP, a CDC specific language. The compiler was then bootstrapped, or compiled using the Pascal source code and the SCALLOP based compiler, to get a working compiler that was written in Pascal itself. Then, the compiler was extended to accept the full unrevised Pascal language."
- brianpan 6y ago
  I don't know if I'm stating the obvious, but you only need to bootstrap if you're writing a compiler in the language it's compiling. So any language compiler written in a different language isn't bootstrapped. Even if you're using a loose definition of "root" as in a parent language is any language involved in writing another language, I doubt there is one root. There are certainly have been languages and computer architectures (with assembly languages) that are independent islands.
- pabs3 6y ago
  Some languages have multiple implementations in different languages. The Bootstrappable Builds folks are working on proper bootstrap for everything. https://bootstrappable.org/ https://bootstrappable.org/ https://bootstrapping.miraheze.org/wiki/Main_Page https://bootstrapping.miraheze.org/wiki/Main_Page
- rzzzt 6y ago
  Bootstrapping can also get recursive, eg. GCC and binutils are bootstrapped by compiling their sources with the GCC you already have on your build system; the result of this is an intermediary compiler, which is then used to compile the sources of itself again. (I should look up the following bit, but IIRC, the second generation result compiles the sources a third time, and the last two outputs are compared -- they should be equal, barring any non-deterministic optimizations.)
- yiyus 6y ago
  Chuck Moore is an interesting example of someone who has bootstrapped several languages without touching a C compiler. He has written systems directly in machine code, and has gone as far as designing his own chips to directly run Forth and ColorForth.
pabs3 6y ago
I like that the Bootstrappable Builds folks are working on a bootstrap process that goes from a small amount of machine code (~512 bytes) all the way up to a full Linux distro, including compilers/interpreters for modern languages. https://bootstrappable.org/ https://bootstrappable.org/
- kiwidrew 6y ago
  Nice, I hadn't heard of this project before! In particular BOOTSTRA [1] looks really fun. I have also toyed with the idea of using MS-DOS 3.30 as a guaranteed-ubiquitous build environment. It comes with a filesystem, a text editor (EDLIN.EXE), an object file linker (yup!), a debugger/assembler (DEBUG.EXE is an amazing tool), a programming language with decent string handling (GWBASIC.EXE), and a command interpreter with batch file scripting to glue it all together. Not sure I would write the assembler as batch files though, that is really hardcore. :) That entire build environment would fit on a single 360KB floppy. [1] https://github.com/mniip/BOOTSTRA https://github.com/mniip/BOOTSTRA
  - pabs3 6y ago
    I don't think that BOOTSTRA is in any way involved in the process bootrappable.org are working on, which starts with hex0 (the 512B machine code binary seed), proceeds through a ton of layers and eventually reaches non-interactive bash. https://github.com/fosslinux/live-bootstrap/blob/master/parts.rst https://github.com/fosslinux/live-bootstrap/blob/master/part...
    - gigel82 6y ago
      That repo is very cool. I want to see them build further on it, go through recursive gcc / clang versions, etc. all the way to a kernel.
  - pwdisswordfish0 6y ago
    What is "guaranteed-ubiquitous" about DOS 3.30?

by retrac 6y ago

systemvoltage 6y ago

When people say bootstrapping, is this how all computer languages came to be? Or there has been multiple attempts at bootstrapping? What I’m getting at is whether all languages have a single root.

retrac 6y ago
Yes, bootstrapping with regard to languages is the trick of getting that first compiler running so you can compile the rest of the compiler. It has been done many times. The first assemblers were written directly in machine language. The first compilers were written in assembly. Many implementations of FORTRAN, ALGOL, COBOL, etc. As late as the 1970s it was not unknown to write a new high level language directly in machine code. Steve Woz's BASIC for the Apple II was "hand-assembled", as he put it. So, taken literally, certainly not. People still do it today as a hobby or educational project. But if we take the question in a looser sense? Yes kind of, at least in the UNIXish world. No one has implemented a serious high level systems language, except in a high level systems language, for a long time now. Rust, for example, was initially implemented in Ocaml. And normally that's what would be called the first Rust bootstrap. But OCaml was implemented in C, probably compiled by Clang or GCC. GCC was written in C and... so on. Often one finds it does lead back to DMR at a PDP-7. On the other hand, I strongly suspect something like IBM's COBOL compiler for their mainframes (still supported and maintained today!) would not have such a heritage.
- systemvoltage 6y ago
  Fascinating and inspiring, thank you for taking the time to distill it so clearly.
  - deleted 6y ago
    [deleted]
- musicale 6y ago
  > Steve Woz's BASIC for the Apple II was "hand-assembled", as he put it. Very cool - so basically (haha) Woz's integer BASIC was bootstrapped by writing it in assembly language and translating it into machine code by hand. I wonder if someone (Woz?) has written a 6502 assembler in integer BASIC to allow it to bootstrap itself?
  - rob74 6y ago
    I'm not an expert, but I guess "bootstrapping" only applies to compilers, and Apple II BASIC was an interpreter. An interpreter doesn't have to compile itself, only run the programs you give it. So on an 8-bit computer the priority is to have an implementation that (a, and most importantly) takes up as little space as possible and (b) is reasonably fast.
    - deleted 6y ago
      [deleted]
    - sn41 6y ago
      There are metacircular interpreters, like in Scheme (see SICP [1]). But this is rare, compared to bootstrapping compilers. [1] https://mitpress.mit.edu/sites/default/files/sicp/full-text/sicp/book/node76.html https://mitpress.mit.edu/sites/default/files/sicp/full-text/...
  - wazoox 6y ago
    The Apple ][ has a monitor in ROM that allows to enter machine code directly. The legend says that for the Apple I, Woz knew the complete integer basic machine code and could type it live into the monitor.
musicale 6y ago
Interesting article on how the original CDC 6000 Pascal compilers were bootstrapped (including the scanned source code listings as PDFs!?!): http://pascal.hansotten.com/niklaus-wirth/cdc-6000-pascal-compilers/ http://pascal.hansotten.com/niklaus-wirth/cdc-6000-pascal-co... "The method used to create the first Pascal compiler, described by U. Ammann in The Zurich Implementation, was to write the compiler in a subset of unrevised Pascal itself, then hand-translate the code to SCALLOP, a CDC specific language. The compiler was then bootstrapped, or compiled using the Pascal source code and the SCALLOP based compiler, to get a working compiler that was written in Pascal itself. Then, the compiler was extended to accept the full unrevised Pascal language."
brianpan 6y ago
I don't know if I'm stating the obvious, but you only need to bootstrap if you're writing a compiler in the language it's compiling. So any language compiler written in a different language isn't bootstrapped. Even if you're using a loose definition of "root" as in a parent language is any language involved in writing another language, I doubt there is one root. There are certainly have been languages and computer architectures (with assembly languages) that are independent islands.
pabs3 6y ago
Some languages have multiple implementations in different languages. The Bootstrappable Builds folks are working on proper bootstrap for everything. https://bootstrappable.org/ https://bootstrappable.org/ https://bootstrapping.miraheze.org/wiki/Main_Page https://bootstrapping.miraheze.org/wiki/Main_Page
rzzzt 6y ago
Bootstrapping can also get recursive, eg. GCC and binutils are bootstrapped by compiling their sources with the GCC you already have on your build system; the result of this is an intermediary compiler, which is then used to compile the sources of itself again. (I should look up the following bit, but IIRC, the second generation result compiles the sources a third time, and the last two outputs are compared -- they should be equal, barring any non-deterministic optimizations.)
yiyus 6y ago
Chuck Moore is an interesting example of someone who has bootstrapped several languages without touching a C compiler. He has written systems directly in machine code, and has gone as far as designing his own chips to directly run Forth and ColorForth.

pabs3 6y ago

I like that the Bootstrappable Builds folks are working on a bootstrap process that goes from a small amount of machine code (~512 bytes) all the way up to a full Linux distro, including compilers/interpreters for modern languages. https://bootstrappable.org/ https://bootstrappable.org/

kiwidrew 6y ago
Nice, I hadn't heard of this project before! In particular BOOTSTRA [1] looks really fun. I have also toyed with the idea of using MS-DOS 3.30 as a guaranteed-ubiquitous build environment. It comes with a filesystem, a text editor (EDLIN.EXE), an object file linker (yup!), a debugger/assembler (DEBUG.EXE is an amazing tool), a programming language with decent string handling (GWBASIC.EXE), and a command interpreter with batch file scripting to glue it all together. Not sure I would write the assembler as batch files though, that is really hardcore. :) That entire build environment would fit on a single 360KB floppy. [1] https://github.com/mniip/BOOTSTRA https://github.com/mniip/BOOTSTRA
- pabs3 6y ago
  I don't think that BOOTSTRA is in any way involved in the process bootrappable.org are working on, which starts with hex0 (the 512B machine code binary seed), proceeds through a ton of layers and eventually reaches non-interactive bash. https://github.com/fosslinux/live-bootstrap/blob/master/parts.rst https://github.com/fosslinux/live-bootstrap/blob/master/part...
  - gigel82 6y ago
    That repo is very cool. I want to see them build further on it, go through recursive gcc / clang versions, etc. all the way to a kernel.
- pwdisswordfish0 6y ago
  What is "guaranteed-ubiquitous" about DOS 3.30?