5 ms·

Bootstrapping a simple compiler from nothing (2001)

192 points by emersonrsantos 13y ago

mamcx 13y ago
This was great. Exist sometime like this but more high level? For example, I wonder how start with python, lua or obj-c, create my own syntax and continue the development with them after a while. I think nimrod & julia (and certainly freepascal) do this but wonder how they do that.
- maaaats 13y ago
  You could read the dragon book for a detailed introduction to compilers, but at a higher level since it's not about bootstrapping but using tools to do some of the tedious work.
  - mamcx 13y ago
    Yeah I could do that (In fact I'm building resources around this) but I'm thinking more about a simple sample like this, than a full of things before get to the point. Like this post and http://journal.stuffwithstuff.com/2013/12/08/babys-first-garbage-collector/ http://journal.stuffwithstuff.com/2013/12/08/babys-first-gar... that put things in a easy to get format.
- hhm 13y ago
  You can bootstrap with any language. So yes, the process that you are describing is also considered bootstrap. http://en.wikipedia.org/wiki/Bootstrapping#Computing http://en.wikipedia.org/wiki/Bootstrapping#Computing
- abecedarius 13y ago
  I was doing something like that with https://github.com/darius/tinyhiss https://github.com/darius/tinyhiss but it's really a toy and still far from freestanding. https://github.com/darius/ichbins https://github.com/darius/ichbins did get to the point of compiling itself, but it was a little too limited to make a good start on growing into a system I'd like to use.
PythonicAlpha 13y ago
When you program with today's tools and all that we have, you forget very fast, how it was in the beginning and how difficult it is to start from scratch. Today you always have some sort of compiler or cross compiler. Starting totally with nil (not even an assembler) is really not so simple. This little article shows nicely, how bootstrapping can work. Pulling myself out of the mud on my own hair (like the Baron Muenchhausen from literature). But don't forget: He still had the operating system not bootstrapped ... so repeating the whole computer history would need some more bootstrapping to do ....
- stormbrew 13y ago
  Kind of on the contrary I feel like this is a great reminder of how possible doing very complicated things with much more rudimentary tools than we have available now is, and that we're really not so far from the 'ancient' ways than we like to think. And though the product would be quite limited, if you're willing to rely on the BIOS doing this from a raw kernel implemented in itself wouldn't be that bad (and having a VM to do so faster would help, but booting off a floppy would still be possible). If anything it might make things a little simpler since you wouldn't have to even use a syscall to get memory, if you set up the pagetables to map to physical memory 1:1 you've got free reign. And that would definitely be an interesting process to try to take this through.
  - rst 13y ago
    The funny thing is that the EDSAC, one of the first functioning computers (perhaps the first, depending on how you define "functioning" and "computer") had a boot loader (the "initial orders") which was capable of manipulating single-letter address labels in a manner at least reminiscent of HEX2. (Or perhaps the reverse?) And in fact, this "annotated machine code" was how programs were generally written for the machine. There are a lot of fine paywalled descriptions of the system. One that's generally available is in the documentation for the EDSAC simulator here (Tutorial Guide, chapter 3): http://www.dcs.warwick.ac.uk/~edsac/ http://www.dcs.warwick.ac.uk/~edsac/ http://www.dcs.warwick.ac.uk/~edsac/Software/EdsacTG.pdf http://www.dcs.warwick.ac.uk/~edsac/Software/EdsacTG.pdf
- 13y ago
fiorix 13y ago
In 2002 Fabrice Bellard (author of ffmpeg, kvm, etc) won The International Obfuscated C Code Contest with a tiny obfuscated C compiler, which later became tcc, the tiny c compiler: http://bellard.org/otcc/ http://bellard.org/otcc/
neotek 13y ago
This reminds me of an interesting question posed on reddit in /r/programming a few years ago: if you were stuck in a room with a blank PC with only a floppy drive and disk, what's the bare minimum that would need to be on the disk for you to eventually write a full-fledged operating system[1]? The whole thread is a fascinating read, and features a cameo from lutusp. [1] http://www.reddit.com/r/programming/comments/9x15g/programming_thought_experiment_stuck_in_a_room/ http://www.reddit.com/r/programming/comments/9x15g/programmi...
- agumonkey 13y ago
  I bookmarked this[1] a dozen times. I wanna try that ASAP. The whole monitor > forth > lisp is a nerd dream [1] especially kragensitaker's comment http://www.reddit.com/r/programming/comments/9x15g/programming_thought_experiment_stuck_in_a_room/c0ewj2c http://www.reddit.com/r/programming/comments/9x15g/programmi...
  - kragen 13y ago
    I'm glad you enjoyed it! I'm interested to see what you come up with :)
    - jacquesm 13y ago
      Epic. Scary to recall how many of your 'steps' I've actually been through irl and I wasn't even in a prison cell...
      - kragen 13y ago
        If I'm not mistaken, you've bootstrapped a substantial fraction of an industrial economy. Now that is epic. To me, a software development environment is small potatoes compared to your windmill. Here's a question I've often thought about that you might have insight on: what would be the shortest path from raw materials and an unlimited amount of information to, say, a reasonable bicycle? For example: bronze, despite its scarcity, is easier to make from raw materials than steel, but I don't know if it's hard enough for ball bearing races, and I think you need ball bearings for a ridable bicycle. You can probably make a tiny blast furnace with leather bellows and ceramic (or can you?), but then you need to form the bearing balls and the races. Would you cut grindstones from stone? Perhaps electrolyze seawater to get magnesium oxychloride to bind together quartz sand?
dasmithii 13y ago
Interesting. This is a great example of the power in abstraction. By continually building upon available tools, we're able to develop new, higher level toolkits that can be used to further the process. Ironically, this project steps back, abandoning modern utilities in favor of a more educational/interesting process (which is good, sometimes). I too enjoy passion-projects such as this.
userbinator 13y ago
Going even "deeper", you could try starting with ROM BASIC on a PC and building the beginnings of an OS from there ( http://en.wikipedia.org/wiki/IBM_BASIC http://en.wikipedia.org/wiki/IBM_BASIC ). I have written a simple assembler (that supported labels) using the DOS DEBUG utility, but never had enough time to go through the levels of abstraction beyond that. If I did, my next steps would've been a text editor, followed by a simple C-like compiler. Another interesting "bootstrapping" problem I've heard of is this: Suppose you rm-rf'd a *nix system, and all that was left was the kernel and shell process running in memory. How much of the system could you "rebuild" with only that?
maxmojo 13y ago
I put bootstraps on my bootstraps so I could bootstrap my bootstraps while I bootstrap.

192 points by emersonrsantos 13y ago

mamcx 13y ago

This was great. Exist sometime like this but more high level? For example, I wonder how start with python, lua or obj-c, create my own syntax and continue the development with them after a while. I think nimrod & julia (and certainly freepascal) do this but wonder how they do that.

maaaats 13y ago
You could read the dragon book for a detailed introduction to compilers, but at a higher level since it's not about bootstrapping but using tools to do some of the tedious work.
- mamcx 13y ago
  Yeah I could do that (In fact I'm building resources around this) but I'm thinking more about a simple sample like this, than a full of things before get to the point. Like this post and http://journal.stuffwithstuff.com/2013/12/08/babys-first-garbage-collector/ http://journal.stuffwithstuff.com/2013/12/08/babys-first-gar... that put things in a easy to get format.
hhm 13y ago
You can bootstrap with any language. So yes, the process that you are describing is also considered bootstrap. http://en.wikipedia.org/wiki/Bootstrapping#Computing http://en.wikipedia.org/wiki/Bootstrapping#Computing
abecedarius 13y ago
I was doing something like that with https://github.com/darius/tinyhiss https://github.com/darius/tinyhiss but it's really a toy and still far from freestanding. https://github.com/darius/ichbins https://github.com/darius/ichbins did get to the point of compiling itself, but it was a little too limited to make a good start on growing into a system I'd like to use.

PythonicAlpha 13y ago

When you program with today's tools and all that we have, you forget very fast, how it was in the beginning and how difficult it is to start from scratch. Today you always have some sort of compiler or cross compiler. Starting totally with nil (not even an assembler) is really not so simple. This little article shows nicely, how bootstrapping can work. Pulling myself out of the mud on my own hair (like the Baron Muenchhausen from literature). But don't forget: He still had the operating system not bootstrapped ... so repeating the whole computer history would need some more bootstrapping to do ....

stormbrew 13y ago
Kind of on the contrary I feel like this is a great reminder of how possible doing very complicated things with much more rudimentary tools than we have available now is, and that we're really not so far from the 'ancient' ways than we like to think. And though the product would be quite limited, if you're willing to rely on the BIOS doing this from a raw kernel implemented in itself wouldn't be that bad (and having a VM to do so faster would help, but booting off a floppy would still be possible). If anything it might make things a little simpler since you wouldn't have to even use a syscall to get memory, if you set up the pagetables to map to physical memory 1:1 you've got free reign. And that would definitely be an interesting process to try to take this through.
- rst 13y ago
  The funny thing is that the EDSAC, one of the first functioning computers (perhaps the first, depending on how you define "functioning" and "computer") had a boot loader (the "initial orders") which was capable of manipulating single-letter address labels in a manner at least reminiscent of HEX2. (Or perhaps the reverse?) And in fact, this "annotated machine code" was how programs were generally written for the machine. There are a lot of fine paywalled descriptions of the system. One that's generally available is in the documentation for the EDSAC simulator here (Tutorial Guide, chapter 3): http://www.dcs.warwick.ac.uk/~edsac/ http://www.dcs.warwick.ac.uk/~edsac/ http://www.dcs.warwick.ac.uk/~edsac/Software/EdsacTG.pdf http://www.dcs.warwick.ac.uk/~edsac/Software/EdsacTG.pdf
13y ago

fiorix 13y ago

In 2002 Fabrice Bellard (author of ffmpeg, kvm, etc) won The International Obfuscated C Code Contest with a tiny obfuscated C compiler, which later became tcc, the tiny c compiler: http://bellard.org/otcc/ http://bellard.org/otcc/

neotek 13y ago

This reminds me of an interesting question posed on reddit in /r/programming a few years ago: if you were stuck in a room with a blank PC with only a floppy drive and disk, what's the bare minimum that would need to be on the disk for you to eventually write a full-fledged operating system[1]? The whole thread is a fascinating read, and features a cameo from lutusp. [1] http://www.reddit.com/r/programming/comments/9x15g/programming_thought_experiment_stuck_in_a_room/ http://www.reddit.com/r/programming/comments/9x15g/programmi...

agumonkey 13y ago
I bookmarked this[1] a dozen times. I wanna try that ASAP. The whole monitor > forth > lisp is a nerd dream [1] especially kragensitaker's comment http://www.reddit.com/r/programming/comments/9x15g/programming_thought_experiment_stuck_in_a_room/c0ewj2c http://www.reddit.com/r/programming/comments/9x15g/programmi...
- kragen 13y ago
  I'm glad you enjoyed it! I'm interested to see what you come up with :)
  - jacquesm 13y ago
    Epic. Scary to recall how many of your 'steps' I've actually been through irl and I wasn't even in a prison cell...
    - kragen 13y ago
      If I'm not mistaken, you've bootstrapped a substantial fraction of an industrial economy. Now that is epic. To me, a software development environment is small potatoes compared to your windmill. Here's a question I've often thought about that you might have insight on: what would be the shortest path from raw materials and an unlimited amount of information to, say, a reasonable bicycle? For example: bronze, despite its scarcity, is easier to make from raw materials than steel, but I don't know if it's hard enough for ball bearing races, and I think you need ball bearings for a ridable bicycle. You can probably make a tiny blast furnace with leather bellows and ceramic (or can you?), but then you need to form the bearing balls and the races. Would you cut grindstones from stone? Perhaps electrolyze seawater to get magnesium oxychloride to bind together quartz sand?

dasmithii 13y ago

Interesting. This is a great example of the power in abstraction. By continually building upon available tools, we're able to develop new, higher level toolkits that can be used to further the process. Ironically, this project steps back, abandoning modern utilities in favor of a more educational/interesting process (which is good, sometimes). I too enjoy passion-projects such as this.

userbinator 13y ago

Going even "deeper", you could try starting with ROM BASIC on a PC and building the beginnings of an OS from there ( http://en.wikipedia.org/wiki/IBM_BASIC http://en.wikipedia.org/wiki/IBM_BASIC ). I have written a simple assembler (that supported labels) using the DOS DEBUG utility, but never had enough time to go through the levels of abstraction beyond that. If I did, my next steps would've been a text editor, followed by a simple C-like compiler. Another interesting "bootstrapping" problem I've heard of is this: Suppose you rm-rf'd a *nix system, and all that was left was the kernel and shell process running in memory. How much of the system could you "rebuild" with only that?

maxmojo 13y ago

I put bootstraps on my bootstraps so I could bootstrap my bootstraps while I bootstrap.