55 ms·

Mugo, a toy compiler for a subset of Go that can compile itself

180 points by benhoyt 6y ago

dvfjsdhgfv 6y ago
Being able to compile itself is actually a huge milestone, congratulations!
chrfrasco 6y ago
This is so cool. I especially loved the Makefile, it's nice to see "bootstrapping" laid out so plainly. I remember finding the concept quite hard to wrap my head around when I was introduced to it. Seeing this would have made it a lot easier to understand!
- chrfrasco 6y ago
  > I wonder if we could reduce binary size with a dead-simple scheduler and GC For many CLIs I think even a brain-dead bump allocator would work
  - Hello71 6y ago
    musl automatically uses a bump allocator if free is not referenced in the program.
    - KMag 6y ago
      That's really cool! Though, I'm curious... don't a lot of malloc implementations use a bump allocator if a simple fragmentation heuristic is below some limit? Presumably musl down inside malloc() has a static bool (or a static function pointer) it uses to keep track if dlsym() has ever returned the address of free(). How much faster is the musl implementation than an implementation using a simple fragmentation heuristic? Presumably, they're both well-predicted conditional branches (and/or indirect branch targets well predicted by the BTB).
      - saagarjha 6y ago
        Musl's implementation only works for statically linked programs.
    - benhoyt 6y ago
      Interesting. I couldn't find any documentation for how this happens (does it need compiler/linker support to know whether free is used?), but I did find the source code for this __simple_malloc: https://git.musl-libc.org/cgit/musl/tree/src/malloc/lite_malloc.c https://git.musl-libc.org/cgit/musl/tree/src/malloc/lite_mal...
  - tetha 6y ago
    A programming language professor working on interpreters once said - for short-living processes the most effective and efficient garbage processing might be... not to and terminating the process. The OS will collect all garbage at once very quickly. So why bother time spending being smart?
- dane-pgp 6y ago
  If you like well-documented bootstrap processes, I can recommend this: https://github.com/fosslinux/live-bootstrap/blob/master/parts.rst https://github.com/fosslinux/live-bootstrap/blob/master/part... The steps go from a binary seed of a few hundred bytes to (almost) gcc. It is still being actively developed as part of the Bootstrappable Builds project: https://www.bootstrappable.org/ https://www.bootstrappable.org/
  - pabs3 6y ago
    A PDF containing a graph of the process: https://github.com/oriansj/talk-notes/blob/master/live-bootstrap.pdf https://github.com/oriansj/talk-notes/blob/master/live-boots...
iovrthoughtthis 6y ago
great post, this part > For reference, a Python version of this same loop runs in 1 minute and 38 seconds … a dynamically-typed bytecode interpreter is not a good choice for heavy integer arithmetic. made me wonder about other dynamic langs. ruby (3.0.0) and lua (5.4.2) ran it in 1:30 and 1:03 respectively but node (12.22.0) ran it in 0:01. how is node so quick?
- sfifs 6y ago
  Years of Google engineers squeezing performance for JavaScript heavy web pages maybe?
  - iovrthoughtthis 6y ago
    That is certainly how, but why? What have they done that enables it to do that?
    - cdogl 6y ago
      Chrome's V8 engine made quite a stir around the turn of the last decade because it it compiled JavaScript down to native code. It would even watch how code was called (if it couldn't statically figure out a safe way to compile it) and generate native code for the happy paths in hot code paths. I simply assume that all browsers do this now because we take it for granted now that JS is reasonably fast, but I could be wrong. I credit much of Chrome's success to V8. It's a marvel of engineering. Shame that the rest of Chrome hasn't been held to such a high standard.
      - josefx 6y ago
        > I simply assume that all browsers do this now because we take it for granted now that JS is reasonably fast, but I could be wrong. Chrome came out a month after Mozilla published its TraceMonkey JIT. So JITing JavaScript has been the standard thing to do since the end of 2008.
        6y ago
dimes 6y ago
That’s amazing! Congrats. One question: why is var only supported for top level declarations? I’m not a compiler or programming language expert by any means, but I thought the general approach was to define a grammar and write a parser for it. I’m curious how global and local declarations diverged so significantly.
- dahfizz 6y ago
  This is a common simplification in compilers. Even C, until 1999, forced you to declare your variables at the top of the function before any code. Its not a limitation of the parser, but simply that having variable declarations anywhere makes the compiler more complex. Its harder to calculate stack space / stack pointers when the variables are declared all over the place.
  - Joker_vD 6y ago
    To clarify why the stack usage calculation is hard when local variable declarations are allowed everywhere, consider compiling this example code: int a; if (...) { int b; int c; if (...) { int d; } else { int e; int f; } int g; } else { int h; } int i; Let's start assigning offsets to the variables, starting at offset 0. The "a" variable gets 0, "b" gets 1, "c" gets 2, "d" gets 3, "e" gets 4, "f" gets 5, "g" gets 6, "h" gets 7, and "i" gets offset 8, so we need to allocate 9 * sizeof(int) bytes on the stack for the local variables. Wait, there is no complication at all, so what's the problem? Well, the problem is unoptimal stack usage: at any point, only 5 ints at most are alive, so you can alias "b" with "h" and "i", and alias "d" with "e" and "g", and save 4 * sizeof(int) bytes of the stack. But to do this you need to track the nesting levels (so you could reset the current allocated offset back to the one used at the start of the block) -- and if you're writing a one-pass recursive-descent compiler, you get this for (almost) free anyway... huh. Did I miss something? It seems there is actually no complication at all, just unwillingness to implement such a feature.
    - deleted 6y ago
      [deleted]
userbinator 6y ago
Fabrice’s C compiler is implemented in 2048 bytes of obfuscated C, whereas mine is 1600 lines of formatted Go. "It can compile itself" is an interesting benchmark of language complexity, and we now have of C and Go, so I wonder how the other common languages would compare. Of course you can "cheat" by choosing a subset that reduces the complexity of the whole. As you can see, Mugo uses its own very inefficient ABI that’s nothing like the x86-64 ABI – the standard ABI puts the first six “cells” (64-bit values) in registers. Considering that stacking args is the norm for 32-bit x86 and few other architectures, it's not that bad, especially since CPUs have special hardware to handle push/pop.
- pjmlp 6y ago
  Most compiled languages are bootstraped, how come "we now have of C and Go" ?
  - userbinator 6y ago
    Can you point to any other languages' examples of minimal self-compiling compilers?
    - eat_veggies 6y ago
      Here's a (probably non exhaustive) list I found https://en.wikipedia.org/wiki/Self-hosting_(compilers)#List_of_languages_having_self-hosting_compilers https://en.wikipedia.org/wiki/Self-hosting_(compilers)#List_...
jeffrallen 6y ago
This is excellent! And a great way to understand what's the simplest a computer and a programming language can be. Students should puzzle their way through exercises built on systems like this.
deleted 6y ago
[deleted]
jhgb 6y ago
> whereas mine is 1600 lines of formatted Go. I wonder how the whole thing compares with the newest Oberon (which should be at around 2900 lines of code or so). After all, if you drink enough beers, Oberon might look like "a subset of Go that can compile itself" to you.
- benhoyt 6y ago
  Wow, I had no idea the Oberon implementation was so small, thanks. And it looks like it's implemented in a similar way, with parsing and code generation mingled together. It is ~2900 lines of code, though it's very dense. You can see it here: http://www.projectoberon.com/ http://www.projectoberon.com/ ORB - symbol table handling - 430 lines ORG - code generator (for RISC) - 1115 lines ORP - parser (calls scanner and code generator - 997 lines ORS - scanner/lexer - 312 lines

180 points by benhoyt 6y ago

Being able to compile itself is actually a huge milestone, congratulations!

This is so cool. I especially loved the Makefile, it's nice to see "bootstrapping" laid out so plainly. I remember finding the concept quite hard to wrap my head around when I was introduced to it. Seeing this would have made it a lot easier to understand!

chrfrasco 6y ago
> I wonder if we could reduce binary size with a dead-simple scheduler and GC For many CLIs I think even a brain-dead bump allocator would work
- Hello71 6y ago
  musl automatically uses a bump allocator if free is not referenced in the program.
  - KMag 6y ago
    That's really cool! Though, I'm curious... don't a lot of malloc implementations use a bump allocator if a simple fragmentation heuristic is below some limit? Presumably musl down inside malloc() has a static bool (or a static function pointer) it uses to keep track if dlsym() has ever returned the address of free(). How much faster is the musl implementation than an implementation using a simple fragmentation heuristic? Presumably, they're both well-predicted conditional branches (and/or indirect branch targets well predicted by the BTB).
    - saagarjha 6y ago
      Musl's implementation only works for statically linked programs.
  - benhoyt 6y ago
    Interesting. I couldn't find any documentation for how this happens (does it need compiler/linker support to know whether free is used?), but I did find the source code for this __simple_malloc: https://git.musl-libc.org/cgit/musl/tree/src/malloc/lite_malloc.c https://git.musl-libc.org/cgit/musl/tree/src/malloc/lite_mal...
- tetha 6y ago
  A programming language professor working on interpreters once said - for short-living processes the most effective and efficient garbage processing might be... not to and terminating the process. The OS will collect all garbage at once very quickly. So why bother time spending being smart?
dane-pgp 6y ago
If you like well-documented bootstrap processes, I can recommend this: https://github.com/fosslinux/live-bootstrap/blob/master/parts.rst https://github.com/fosslinux/live-bootstrap/blob/master/part... The steps go from a binary seed of a few hundred bytes to (almost) gcc. It is still being actively developed as part of the Bootstrappable Builds project: https://www.bootstrappable.org/ https://www.bootstrappable.org/
- pabs3 6y ago
  A PDF containing a graph of the process: https://github.com/oriansj/talk-notes/blob/master/live-bootstrap.pdf https://github.com/oriansj/talk-notes/blob/master/live-boots...

iovrthoughtthis 6y ago

great post, this part > For reference, a Python version of this same loop runs in 1 minute and 38 seconds … a dynamically-typed bytecode interpreter is not a good choice for heavy integer arithmetic. made me wonder about other dynamic langs. ruby (3.0.0) and lua (5.4.2) ran it in 1:30 and 1:03 respectively but node (12.22.0) ran it in 0:01. how is node so quick?

sfifs 6y ago
Years of Google engineers squeezing performance for JavaScript heavy web pages maybe?
- iovrthoughtthis 6y ago
  That is certainly how, but why? What have they done that enables it to do that?
  - cdogl 6y ago
    Chrome's V8 engine made quite a stir around the turn of the last decade because it it compiled JavaScript down to native code. It would even watch how code was called (if it couldn't statically figure out a safe way to compile it) and generate native code for the happy paths in hot code paths. I simply assume that all browsers do this now because we take it for granted now that JS is reasonably fast, but I could be wrong. I credit much of Chrome's success to V8. It's a marvel of engineering. Shame that the rest of Chrome hasn't been held to such a high standard.
    - josefx 6y ago
      > I simply assume that all browsers do this now because we take it for granted now that JS is reasonably fast, but I could be wrong. Chrome came out a month after Mozilla published its TraceMonkey JIT. So JITing JavaScript has been the standard thing to do since the end of 2008.
      - 6y ago

dimes 6y ago

That’s amazing! Congrats. One question: why is var only supported for top level declarations? I’m not a compiler or programming language expert by any means, but I thought the general approach was to define a grammar and write a parser for it. I’m curious how global and local declarations diverged so significantly.

dahfizz 6y ago
This is a common simplification in compilers. Even C, until 1999, forced you to declare your variables at the top of the function before any code. Its not a limitation of the parser, but simply that having variable declarations anywhere makes the compiler more complex. Its harder to calculate stack space / stack pointers when the variables are declared all over the place.
- Joker_vD 6y ago
  To clarify why the stack usage calculation is hard when local variable declarations are allowed everywhere, consider compiling this example code: int a; if (...) { int b; int c; if (...) { int d; } else { int e; int f; } int g; } else { int h; } int i; Let's start assigning offsets to the variables, starting at offset 0. The "a" variable gets 0, "b" gets 1, "c" gets 2, "d" gets 3, "e" gets 4, "f" gets 5, "g" gets 6, "h" gets 7, and "i" gets offset 8, so we need to allocate 9 * sizeof(int) bytes on the stack for the local variables. Wait, there is no complication at all, so what's the problem? Well, the problem is unoptimal stack usage: at any point, only 5 ints at most are alive, so you can alias "b" with "h" and "i", and alias "d" with "e" and "g", and save 4 * sizeof(int) bytes of the stack. But to do this you need to track the nesting levels (so you could reset the current allocated offset back to the one used at the start of the block) -- and if you're writing a one-pass recursive-descent compiler, you get this for (almost) free anyway... huh. Did I miss something? It seems there is actually no complication at all, just unwillingness to implement such a feature.
  - deleted 6y ago
    [deleted]

userbinator 6y ago

Fabrice’s C compiler is implemented in 2048 bytes of obfuscated C, whereas mine is 1600 lines of formatted Go. "It can compile itself" is an interesting benchmark of language complexity, and we now have of C and Go, so I wonder how the other common languages would compare. Of course you can "cheat" by choosing a subset that reduces the complexity of the whole. As you can see, Mugo uses its own very inefficient ABI that’s nothing like the x86-64 ABI – the standard ABI puts the first six “cells” (64-bit values) in registers. Considering that stacking args is the norm for 32-bit x86 and few other architectures, it's not that bad, especially since CPUs have special hardware to handle push/pop.

pjmlp 6y ago
Most compiled languages are bootstraped, how come "we now have of C and Go" ?
- userbinator 6y ago
  Can you point to any other languages' examples of minimal self-compiling compilers?
  - eat_veggies 6y ago
    Here's a (probably non exhaustive) list I found https://en.wikipedia.org/wiki/Self-hosting_(compilers)#List_of_languages_having_self-hosting_compilers https://en.wikipedia.org/wiki/Self-hosting_(compilers)#List_...

jeffrallen 6y ago

This is excellent! And a great way to understand what's the simplest a computer and a programming language can be. Students should puzzle their way through exercises built on systems like this.

deleted 6y ago

[deleted]

jhgb 6y ago

> whereas mine is 1600 lines of formatted Go. I wonder how the whole thing compares with the newest Oberon (which should be at around 2900 lines of code or so). After all, if you drink enough beers, Oberon might look like "a subset of Go that can compile itself" to you.

benhoyt 6y ago
Wow, I had no idea the Oberon implementation was so small, thanks. And it looks like it's implemented in a similar way, with parsing and code generation mingled together. It is ~2900 lines of code, though it's very dense. You can see it here: http://www.projectoberon.com/ http://www.projectoberon.com/ ORB - symbol table handling - 430 lines ORG - code generator (for RISC) - 1115 lines ORP - parser (calls scanner and code generator - 997 lines ORS - scanner/lexer - 312 lines