4 ms·

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 wheth

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.
    - flyinghamster 6y ago
      Also, the monitor on pre-][+ machines with integer BASIC also had a mini-assembler, so short assembly programs could be typed in as such instead of keying in the bytes. Both versions of the monitor had a mini-disassembler. On the other hand, I still remember at least a few 6502 hex opcodes, not that I have any use for that information anymore. The instruction set is small enough that it doesn't surprise me that Woz would have it memorized.
  - compiler-guy 6y ago
    I’m not aware of any basic that is implemented in itself. There must be one or two somewhere, but typically for systems like the apple ii or Commodore PET, basic was implemented always in assembly. So most weren’t exactly bootstrapped the way we are talking here.
- divs1210 6y ago
  > No one has implemented a serious high level systems language, except in a high level systems language, for a long time now. LuaJIT is a prominent counterexample. The base interpreter in written in assembly for performance. It comes with its own tradeoffs, especially portability.
  - wahern 6y ago
    LuaJIT uses it's DynASM library for both static and JIT code generation. DynASM is implemented in a mixture of Lua and C, and Lua is of course implemented using C. So LuaJIT actually depends on a C compiler to generate assembly. Plus, not all of LuaJIT is implemented using assembly, only some critical hotspots (e.g. the bytecode interpreter loop). The rest is just C. DynASM is actually really cool. I almost forgot: apropos bootstrapping, because LuaJIT requires Lua to build, it includes a single-file, stripped down version of PUC Lua 5.1 which it can build to bootstrap itself if the host lacks a Lua interpreter.
    - jashmatthews 6y ago
      LuaJIT 1.x uses DynASM for JIT but LuaJIT 2.x doesn't and instead uses the IR to ASM compiler in https://github.com/LuaJIT/LuaJIT/blob/v2.1/src/lj_asm.c https://github.com/LuaJIT/LuaJIT/blob/v2.1/src/lj_asm.c A program using DynASM doesn't depend on Lua or a C compiler to generate assembly at runtime but you need both to build it.
  - deleted 6y ago
    [deleted]
- monkeybutton 6y ago
  IBM's COBOL was implemented in PL/X, which traces its heritage to PL/S. PL/S itself was developed as a replacement for using assembler.
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.

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.
  - flyinghamster 6y ago
    Also, the monitor on pre-][+ machines with integer BASIC also had a mini-assembler, so short assembly programs could be typed in as such instead of keying in the bytes. Both versions of the monitor had a mini-disassembler. On the other hand, I still remember at least a few 6502 hex opcodes, not that I have any use for that information anymore. The instruction set is small enough that it doesn't surprise me that Woz would have it memorized.
- compiler-guy 6y ago
  I’m not aware of any basic that is implemented in itself. There must be one or two somewhere, but typically for systems like the apple ii or Commodore PET, basic was implemented always in assembly. So most weren’t exactly bootstrapped the way we are talking here.
divs1210 6y ago
> No one has implemented a serious high level systems language, except in a high level systems language, for a long time now. LuaJIT is a prominent counterexample. The base interpreter in written in assembly for performance. It comes with its own tradeoffs, especially portability.
- wahern 6y ago
  LuaJIT uses it's DynASM library for both static and JIT code generation. DynASM is implemented in a mixture of Lua and C, and Lua is of course implemented using C. So LuaJIT actually depends on a C compiler to generate assembly. Plus, not all of LuaJIT is implemented using assembly, only some critical hotspots (e.g. the bytecode interpreter loop). The rest is just C. DynASM is actually really cool. I almost forgot: apropos bootstrapping, because LuaJIT requires Lua to build, it includes a single-file, stripped down version of PUC Lua 5.1 which it can build to bootstrap itself if the host lacks a Lua interpreter.
  - jashmatthews 6y ago
    LuaJIT 1.x uses DynASM for JIT but LuaJIT 2.x doesn't and instead uses the IR to ASM compiler in https://github.com/LuaJIT/LuaJIT/blob/v2.1/src/lj_asm.c https://github.com/LuaJIT/LuaJIT/blob/v2.1/src/lj_asm.c A program using DynASM doesn't depend on Lua or a C compiler to generate assembly at runtime but you need both to build it.
- deleted 6y ago
  [deleted]
monkeybutton 6y ago
IBM's COBOL was implemented in PL/X, which traces its heritage to PL/S. PL/S itself was developed as a replacement for using assembler.

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.