Bootstrapping a simple compiler from nothing (2001) | Hacker News Reader

Bootstrapping a simple compiler from nothing (2001)

homepage.ntlworld.com

192 pointsemersonrsantos30 comments

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/programmi...

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/programmi...

I'm glad you enjoyed it! I'm interested to see what you come up with :)

Epic. Scary to recall how many of your 'steps' I've actually been through irl and I wasn't even in a prison cell...

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?

The hard part I think would be the mining. Most if not all of the easily accessible resources have been depleted, so bronze age people had an easier time of it than we do!

Making a bicycle out of bronze would be an interesting exercise. I'd not use ball bearings, but rather babbit bearings and instead of a chain drive I'd use a belt drive (made from cloth).

Bamboo rather than steel or bronze for the frame to keep the amount of metal to a minimum, spokes would be tricky, wheels could be made out of wood.

Inner tubes made out of intestine, outer tubes made out of cloth, bulky but workable.

Something like that?

Now that you have me thinking about this I realize that I'm actually sorely tempted to try this.

Another hard part would be to not (unwittingly) cheat and to work off existing tools and/or raw materials that aren't truly raw.

edit: more thinking about this, the high stress points in the bike would be the spot where the pedals attach (even on my regular bike I can see it flex there), the joint where the tube from the handlebars goes through to the fork, the fork itself and the saddle joint.

Those would probably have to be cast out of bronze and then filed (with what?!) to their precise dimensions, or, alternatively you could first bootstrap a primitive lathe (which would require at least one piece of hardened steel for the bit).

Primitive blast furnaces are fairly easily constructed out of clay, I've seen some in NL that were absolutely doable, depending on what ores you can get your hands at in the end steel might even be easier than bronze.

The belt drive, intestine inner tubes, and bamboo frame are excellent ideas.

That's a good point about the bronze. I think there's still a basically unlimited amount of small deposits of rich iron ore out there (e.g. magnetite sands) and, of course, aluminum, but that's a lot harder to smelt.

I had the impression that Babbitt bearings were too inefficient to make bicycles practical, which is why the bicycle boom didn't happen until the invention of the ball bearing. But I could be mistaken about that. Certainly you could do Babbitt bearings without particularly great metallurgy. (But you need a wider variety of metals.)

I know some people here with bamboo bikes, except for the joints, of course.

Spokes could possibly be made of glass or bamboo, but I'm not sure how you'd pull them tight without being able to thread them. Maybe you could lace the wheel like a circular shoe instead.

I don't think cloth tires will wear for long enough to be useful. You'll probably need at least buna reinforced with carbon black or fumed silica.

As for the working off existing tools: maybe you could make it an iterative process, starting with Dave Gingery tools and materials and working your way down with successive bikes?

Do you think you could do a lathe with a non-metal bit? Corundum, carborundum, diamond, or maybe topaz? I've never turned anything on a lathe, so this might be a stupid question.

I think you can grind some things to precise dimensions rather than filing them, and that might require less materials technology. Knife sharpeners use a particular kind of flint for some of their work.

I definitely, definitely want to know if you end up doing some of this!

Modern lathe bits are ceramic or sintered metal, so it should be possible to use other materials.

Grinding / sanding are good ways to get near perfect shapes (it is typically the last pass after the lathe has done its work if you want extreme precision). Ball bearings are made using an interesting process (using a vibrating drum with abrasive, the resulting minimal surface elements are perfectly spherical by definition...).

Babbit bearings have a higher friction coefficient, but we're talking about making a working bicycle, not the most efficient one, after that it is incremental improvements and of course, ball bearings are better but they may not be the shortest path to success.

You've really done a bad thing here, I can't get this out of my head... :)

Wow, I would never have expected to run into you. Be sure that if I pull it off, I'll brag about it over the whole internet :)

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 ....

And even if he were to write the operating system from scratch, he would still have "cheated" by not designing the hardware. I wonder how long it would take in man-years to recreate the entire chain all the way up to a simple C-like compiler. Still, fascinating work, and most of all a fascinating perspective. I for one haven't the slightest clue about how to program by directly inputting hexadecimal machine code.

Shouldn't take more than a couple of man-years if you got the right people together. A C compiler is still pretty low down on the toolchain, and there is a whole library of literature explaining how the technology below this level works.

I think the big restriction is how much existing technology you'd be allowed to use, and how functional/scalable the technology would have to be when you're done. I/O is a big hurdle. Do you have to design the graphics hardware yourself? Do you have access to modern photolitography? Are you required to create the monitor/keyboard yourself? Other input devices, like disk drives? Do you need presistent storage at all? Display? Etc.

Here's someone who started with the hardware, although he only ported existing software to it:

http://www.homebrewcpu.com/

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.

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/Software/EdsacTG.pdf

This is what I as old beard find so bad in many online forums from young developers.

Back then, most of my peers could understand that implementation != language.

And as consequence, before Java became mainstream the majority of memory safe languages (e.g. Modula-2, Mesa, Algol,Oberon,...) actually had native compilers in most systems.

Nowadays most don't understand this, nor how bootstrapping works, a technique any CS student should be comfortable with.

A lot of us today (including myself) are bootstrapping our own CS education and cannot, in fact, build from bare metal. I, for one, learn more and more when people post things like this and I am also very grateful...and on my way to understanding implementation != language.

Something that would help is to do a lot of computer archaeology.

Many old papers and documents are now scattered around the web.

You would get to learn a lot from the days C was UNIX only, there was a lot of choice in programming languages and OSs to chose from.

Specially the whole explosion of home computers diversity and respective development environments.

Thanks for the comments. I am trying to read less HN and more of the C book. Really, I just need more time than 24 hours in a day.

If you're teaching yourself (what I assume you mean from bootstrapping), you ought to take a Coursera or EdX class on computer architecture or at least get a good textbook on the subject. The class should cover microprocessor architecture, assembly language and how the assembler works. My EE course on the subject at UT Austin used the 6800 micro family, and my CS friends at UT took a similar class that used MIPS.

He also assumed an editor.

I mused on this topic a few years ago (http://boston.conman.org/2009/11/05.1) only I started without an editor (just a command line on an operating system). But past that, it's neat to see he did something similar to what I proposed.

I'm curious to hear what you think about the various bootstrapping threads linked from my comment at http://www.reddit.com/r/programming/comments/9x15g/programmi.... Several of them were inspired by your blog post.

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/

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 ).

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?

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.

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.

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-gar... that put things in a easy to get format.

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

I was doing something like that with https://github.com/darius/tinyhiss but it's really a toy and still far from freestanding.

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.

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.

Reply on news.ycombinator.com