See the bootstrap project: https://bootstrappable.org/projects.html
SectorC: A C Compiler in 512 bytes
51–60 of 82 posts
Re: SectorC: A C Compiler in 512 bytes
#52Pretty nifty, nice work! I'll point out to any passerby that this C doesn't support structs, so it's unlikely you'd actually want to build anything in it.
The C Star (C*) language from the selfie project also does not support structs, yet in 12KLOC of code they implemented a C Star compiler that can compile selfie (and outputs ELF files), an emulator that runs RISC-U (RISC-V subset), and a hypervisor.
There was also Small-C[1], which initially only did integers, characters and simple arrays. Formed the basis for quite a few derivates.
Re: SectorC: A C Compiler in 512 bytes
#53This reminded me the idea of compilers bootstrapping ( https://news.ycombinator.com/item?id=35714194 ). That is, now you can code in SectorC some slightly more advanced version of C capable of compiling TCC ( https://bellard.org/tcc/ ), and then with TCC you can go forward to GCC and so on.
Perhaps my favorite thing in all of computing is the authors of Lisp bootstrapping by writing an (academic) interpreter for Lisp in Lisp, and then realizing they could just compile that by hand.
Paper?
I once read a lisp paper that kept defining lisp primitives in terms of simpler lisp primitives until they had only 4-10 primitives. Then the paper started defining those in terms of assembly language (but with parens). In the final step, they just removed the parens. It was so elegant. I can't find the paper though :( Any ideas?
Re: SectorC: A C Compiler in 512 bytes
#54I saw the repeating 'A' at the end of the base64 text and thought "it's not even 512 bytes; it's smaller!" That said, the title is just a little clickbaity --- it's a C-subset compiler, and more accurately a JIT interpreter. There also appears to be no attempt at operator precedence. Nonetheless, it's still an impressive technical achievement and shows the value of questioning common assumptions. Finally, I feel temp…
What does Just In Time mean for an interpreter?
I think in this case that it executes the code as it's being parsed, in a single pass.
Re: SectorC: A C Compiler in 512 bytes
#55Earlier quoted context omitted.
Perhaps my favorite thing in all of computing is the authors of Lisp bootstrapping by writing an (academic) interpreter for Lisp in Lisp, and then realizing they could just compile that by hand.
Paper? I once read a lisp paper that kept defining lisp primitives in terms of simpler lisp primitives until they had only 4-10 primitives. Then the paper started defining those in terms of assembly language (but with parens). In the final step, they just removed the parens. It was so elegant. I can't find the paper though :( Any ideas?
The paper is the original paper on LISP by McCarthy "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I". It has the original definition of LISP in LISP.
Re: SectorC: A C Compiler in 512 bytes
#56I saw the repeating 'A' at the end of the base64 text and thought "it's not even 512 bytes; it's smaller!" That said, the title is just a little clickbaity --- it's a C-subset compiler, and more accurately a JIT interpreter. There also appears to be no attempt at operator precedence. Nonetheless, it's still an impressive technical achievement and shows the value of questioning common assumptions. Finally, I feel temp…
C has a bit of a history with interpreters and reduced implementations (not to devalue SectorC which is absolutely cool). I'm thinking Small C Interpreter for CP/M: http://www.cpm.z80.de/small_c.html an interpreted version of https://en.wikipedia.org/wiki/Small-C
Re: SectorC: A C Compiler in 512 bytes
#57Earlier quoted context omitted.
That's a just-in-time compiler.
An interpreter with a JIT compiler is able to do more optimizations because it has the runtime context to make decisions, while a AOT (ahead of time) compiler will not know anything about what happens at runtime. This is why some JIT'd languages (like Javascript) can be sometimes faster than C.
Can you give some simple example for the folks in the back of how JIT'd languages can be faster than C? I think most people are under the impression that statically compiled languages are "always faster."
Re: SectorC: A C Compiler in 512 bytes
#58really interesting write-up. thanks for sharing!
do you think there are any lessons that can be applied to a "normal" interpreter/compiler written in standard C? i'm always interested in learning how to reduce the size of my interpreter binaries
Re: SectorC: A C Compiler in 512 bytes
#59Earlier quoted context omitted.
An interpreter with a JIT compiler is able to do more optimizations because it has the runtime context to make decisions, while a AOT (ahead of time) compiler will not know anything about what happens at runtime. This is why some JIT'd languages (like Javascript) can be sometimes faster than C.
Can you give some simple example for the folks in the back of how JIT'd languages can be faster than C? I think most people are under the impression that statically compiled languages are "always faster."
> Can you give some simple example for the folks in the back of how JIT'd languages can be faster than C?
If the JIT has instrumentation that analyzes execution traces, then it can notice that a call through a function pointer always goes to the same function. It can then recompile that code to use a static function call instead, which is considerably faster.
Basically, it can perform a similar set of optimizations to a static compiler + profiling information in basic cases. In more advanced scenarios, it specializes the program based on the runtime input, which profiling can't do for all possible inputs, eg. say the above function pointer call only happens for input B but not for input C.
Re: SectorC: A C Compiler in 512 bytes
#60I saw the repeating 'A' at the end of the base64 text and thought "it's not even 512 bytes; it's smaller!" That said, the title is just a little clickbaity --- it's a C-subset compiler, and more accurately a JIT interpreter. There also appears to be no attempt at operator precedence. Nonetheless, it's still an impressive technical achievement and shows the value of questioning common assumptions. Finally, I feel temp…
C has a bit of a history with interpreters and reduced implementations (not to devalue SectorC which is absolutely cool). I'm thinking Small C Interpreter for CP/M: http://www.cpm.z80.de/small_c.html an interpreted version of https://en.wikipedia.org/wiki/Small-C
The book that had the Cain/Hendrix "Small C" compiler, runtime library, assembler and tools was a fantastic resource that taught me C and compiler construction at the same time.
In general, reading (lots of) source code is a good way to learn how to do things in a new language, i.e. to move from the lexical and syntactical level to the level of idioms for problem-solving. On reflection, I find it strange that in programming teaching, larger pieces of existing well-written source code are never discussed/explained/critiqued.