Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

How to bootstrap it from scratch #2

Open
certik opened this issue Sep 21, 2015 · 3 comments
Open

How to bootstrap it from scratch #2

certik opened this issue Sep 21, 2015 · 3 comments

Comments

@certik
Copy link

certik commented Sep 21, 2015

Anybody who knows C can use your mini-c as the minimal self-hosting subset of C compiler and can implement the whole C compiler or other languages.

What would also be interesting is to bootstrap mini-c from scratch. Currently you require some kind of a C compiler like gcc to be present on the system.

Here is an example of an approach that doesn't require any compiler at all, it starts from a small hand written machine code and then it goes from there to develop a structured programming language called BCC: http://rano.org/bcompiler.html (I made a mirror at github here: https://github.com/certik/bcompiler/blob/master/bcc.bc)

So the goal would be to write a compiler in BCC that can compile mini-c.

@Fedjmike
Copy link
Owner

I actually had a similar idea. I called it the "least fixed point of computing" (a slight abuse of the concept). Cool to see what it looks like in practice!

However mini-c wasn't designed for that and wouldn't really help, I think. I used as little C as possible and only implemented enough to compile itself. If you made something complex enough to compile it, then you've already got as far as mini-c would take you.

However, if there was another system with a slightly higher bar of language features, mini-c could make a good starting point to reach that.

... mini-os?

@certik
Copy link
Author

certik commented Sep 21, 2015

Well so that's the other direction --- use mini-c to build e.g. TinyCC and see if one can bootstrap gcc with TinyCC or something like that. That way all you have to do is to get mini-c working on a system, and then you can bootstrap anything else from source code, without needing any external binaries. I would be interested in that too.

However, to bootstrap mini-c, you still need a C compiler, i.e. some external binary compiler, which e.g. can have a malware in it, and it's pretty hard to make sure that the generated machine code for mini-c doesn't have malware. And even if you don't care about malware, it's still nice to be able to bootstrap from scratch, not relying on any external binary compiler.

I spent some time figuring out how best to do that, and it seems the easiest is to use Forth, or a subset of it, to be precise. Unlike BCC (see above) which is a custom made language, Forth is a well documented language, you can find tons of tutorials online, yet it seems to be very simple to implement directly in assembly, in a similar manner like BCC above. In fact, I think BCC is very close to a Forth subset, it's just that rather than inventing a new language, it's always better to target something that's already widely used.

Here I found such a nice minimal self-hosting implementation of a Forth subset: https://github.com/kragen/stoneknifeforth, just like mini-c, it requires a Forth compiler to be present, and so to bootstrap it, it provides a Forth interpreter written in less than 300 lines of Python. You can use it to create the first binary compiler of Forth. By the nature of it, the generated assembly for the self hosting Forth compiler is actually very small (https://gist.github.com/certik/efa2f3f7e72434576d67), and so it can be inspected that it doesn't contain malware, as well as you can use the assembly as the starting point --- i.e. something that you can write by hand (instead of using Python...) in a manner similar to how BCC was bootstrapped (i.e. the mini Forth compiler has ~1500 assembly lines, and it might be even possible to reduce it using the BCC bootstrapping method).

In other words, if it is possible to write a compiler that can compiler mini-c in that subset of Forth (or possibly develop a little bit more full featured Forth using the subset of Forth first, before writing the C compiler), then that would do what I had in mind.

@tekknolagi
Copy link

For anyone who is interested, I translated stoneknifeforth into C++, so it's even more portable! https://github.com/tekknolagi/stoneknifecpp

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants