5 ms·

An Intro to Compilers (2017)

245 points by memexy 6y ago

the_duke 6y ago
While somewhat irrelevant for a majority of developers, it feels great to understand how computers actually work. Even many higher education IT programs often barely cover the underpinnings anymore. I'm currently embarking on a fun little "from first principles" challenge: Imagine a post-apocalyptic world where computers are a relic of the past. You stumble upon a functioning device with a screen and keyboard. When powered on, all you get is a bare metal "assembly interpreter". You can type in riscv64 assembly instructions and they are executed. You can print to the screen via a UART. So you don't even get an assembler/linker to build on. From there you have to build up an entire new software stack, with a proper language with compiler/vm, an operating system, a standard library, basic userspace tools, a UI, ... Simulating the device and console is easy with qemu-system-riscv64 and a a bit of assembly. It's very challenging, but also rewarding to study up/relearn and implement all the basic underpinnings of computers, all the way from hardware (CPU, memory, IO devices, ISAs) up to a GUI stack. Hacking together a simple OS isn't actually all that hard when your hardware is constrained to a specific device. And writing a very simple language in assembly also isn't that bad. You can build progressively better languages on top of that. I'd love to turn this into a somewhat guided, interactive learning experience that runs in the browser via tinyemu [1] or similar, but I won't have time for that. [1] https://bellard.org/tinyemu/ https://bellard.org/tinyemu/
- p4bl0 6y ago
  > Even many higher education IT programs often barely cover the underpinnings anymore. Really? A compiler course seems quite standard in any licence/bachelor CS degree.
  - the_duke 6y ago
    I've seen some "practice oriented" bachelor degrees like "Software Development" that don't cover these topics at all. I think more common is to have a few courses on it, but as a small part of the curriculum; which is largely forgotten by graduation time. I guarantee that asking the average application developer about IO ports, out of order execution, cache misses, AST passes, stack machines, how a GC works, or even just how to implement a hash table or tradeoffs between arrays and linked lists will earn you mostly blank, confused stares.
    - BossingAround 6y ago
      > which is largely forgotten by graduation time Let's be honest, 90% of everything you "learn" at university is largely forgotten during graduation time. I've seen folks fresh out of uni who couldn't even run a Java program without an IDE, or who forgot how to write a switch statement. I find it fascinating how inefficient the brain is, and how though it spends huge amount of our resources, it's actually not extremely good at picking up new complex information.
      - chrisseaton 6y ago
        'run a Java program without an IDE' is not a learning outcome of a computer science degree, though.
        BossingAround 6y ago
        Is it not? If the programme teaches Java, "learning how to compile and execute Java programs" would surely be one of the top priorities of such a course.
        chrisseaton 6y ago
        Ok but you said they could do that using an IDE - why isn't that enough?
        rehemiau 6y ago
        Maybe because there are no IDEs on servers
        chrisseaton 6y ago
        Is it the job of a computer scientist to run programs on servers though? That seems like specific technical training, not the subject of a computer science degree.
  - deleted 6y ago
    [deleted]
  - hazz99 6y ago
    I go to a pretty good uni (not elite, but global top 30) and they don’t have a compilers course, which I was very disappointed by. It’s even a theory heavy degree!
    - p4bl0 6y ago
      Well, at least that says a lot about whatever is called "elite" and "global top N": it doesn't have any relevant meaning.
      - hazz99 6y ago
        To be fair, they’ve given me a great education and very valuable opportunities. I’m very appreciative! I just wish I didn’t have to self teach compilers.
    - chrisseaton 6y ago
      This really surprises me - looking down the THE and QS global rankings, I know that at least all the universities outside the Far East teach compilers. I guess you're not saying which university you're at to keep it anonymous, but I'd be interested to hear which it was.
      - derangedHorse 6y ago
        Which universities are you looking at? Mine technically had a compilers course but it wasn't required coursework and was generally offered every 2-3 years or so
        chrisseaton 6y ago
        The top 30 in QS and THE. Most of them have major compiler research groups, even.
  - kyawzazaw 6y ago
    It is an advanced elective. So totally optional. Some smaller colleges (like mine) don’t even offer it.
  - rustybolt 6y ago
    A compiler course is standard, but it didn't teach me about linkers, relocation, loading, and all that stuff. So I see p4bl0's point.
- bloodorange 6y ago
  I have a feeling you might like this: https://www.nand2tetris.org/ https://www.nand2tetris.org/ It's a popular course about building a computer from nand gates and eventually building a Tetris like game on it. All of this is done on a hardware simulator of course. If you are keen on real hardware, you might find this interesting: https://www.youtube.com/watch?v=HyznrdDSSGM&list=PLowKtXNTBypGqImE405J2565dvjafglHU https://www.youtube.com/watch?v=HyznrdDSSGM&list=PLowKtXNTBy... It's a series of videos where Ben Eater explains how to build an 8-bit computer using breadboards and basic elements of circuits. I find that his explanations are quite good as well.
- kgoutham93 6y ago
  Hey, I am really intrigued about the idea. Do you follow any specific learning path? Any resources would also help a lot.
parenthesis 6y ago
Even if you never write or work on a compiler in the sense of a program that turns source code text into assembly, many programs (or parts thereof) are compilers in the sense of turning data or code in one form into another form.
- lou1306 6y ago
  This is especially true of "code generators" or "source-to-source" transformation tools. I did write one of each recently, and often had to look up the compiler literature to go forward.
shpongled 6y ago
I'm currently working on a compiler from scratch for fun/learning. Currently just compiling Standard ML without modules because it presents an interesting challenge, compilation-wise. I'm self taught (but have been programming 10+ years) so it's been a really interesting experience - I've gotten exposure/actual use of some different data structures and algorithms that I've never used before. If you're into this kinda thing, I suggest checking out the ProgrammingLanguages subreddit, there's a discord server as well.
deleted 6y ago
[deleted]
perfect5th 6y ago
I took a couple of compiler courses in university, and I think for the most part it made me a better programmer, mainly because it enforced understanding of how specific programming concepts and constructs are generally implemented. That, and a more intense look at the "heap of abstractions" you're generally working with when you write a higher-level language. I've always advocated that, if you want to really understand the tools you are using, you need to understand at least one level below the "surface abstraction" that you are working if. Even better if you can understand two or three levels down. There's a great talk from game developer Jonathan Blow [1] that describes how knowledge is lost "generationally" due to our lack of understanding of the black boxes we build things on top of. Not sure I 100% agree with his thoughts, but it's an interesting take. [1] https://www.youtube.com/watch?v=pW-SOdj4Kkk https://www.youtube.com/watch?v=pW-SOdj4Kkk
peacefulhat 6y ago
I spent a couple days writing a compiler for a custom shader language. It's a very simple lisp with minimal features, but enough to do everything I use in graphics. I compile this into glsl + a struct and functions for cpu side. A lot faster to prototype when I only have to modify my shader, and I can switch out the backend between webgl and opengl. Should be quick to add support for vulkan/metal/dx12 when I need that. I never would have thought to do this solution if I didn't already know how to write compilers. Somebody might say "oh, you could have used ____" - maybe, but it wasn't much effort and I can make it work in a convenient way for me. (in position f2) (in uv f2) (all sprite tex) (all color f4) (vert (position 0.0 1.0)) (frag (* (sprite uv) color))
stevekemp 6y ago
That's pretty topical for me, last week I challenged myself to write a brainfuck compiler in 24 hours or less. The end result worked out pretty well, and took less time than I expected: https://github.com/skx/bfcc/ https://github.com/skx/bfcc/
dang 6y ago
Discussed at the time: https://news.ycombinator.com/item?id=15005031 https://news.ycombinator.com/item?id=15005031
exdsq 6y ago
I’m writing a simple Lisp compiler with Bash at the moment. It’s fun to find all the things you really miss from other languages!

245 points by memexy 6y ago

While somewhat irrelevant for a majority of developers, it feels great to understand how computers actually work. Even many higher education IT programs often barely cover the underpinnings anymore. I'm currently embarking on a fun little "from first principles" challenge: Imagine a post-apocalyptic world where computers are a relic of the past. You stumble upon a functioning device with a screen and keyboard. When powered on, all you get is a bare metal "assembly interpreter". You can type in riscv64 assembly instructions and they are executed. You can print to the screen via a UART. So you don't even get an assembler/linker to build on. From there you have to build up an entire new software stack, with a proper language with compiler/vm, an operating system, a standard library, basic userspace tools, a UI, ... Simulating the device and console is easy with qemu-system-riscv64 and a a bit of assembly. It's very challenging, but also rewarding to study up/relearn and implement all the basic underpinnings of computers, all the way from hardware (CPU, memory, IO devices, ISAs) up to a GUI stack. Hacking together a simple OS isn't actually all that hard when your hardware is constrained to a specific device. And writing a very simple language in assembly also isn't that bad. You can build progressively better languages on top of that. I'd love to turn this into a somewhat guided, interactive learning experience that runs in the browser via tinyemu [1] or similar, but I won't have time for that. [1] https://bellard.org/tinyemu/ https://bellard.org/tinyemu/

p4bl0 6y ago
> Even many higher education IT programs often barely cover the underpinnings anymore. Really? A compiler course seems quite standard in any licence/bachelor CS degree.
- the_duke 6y ago
  I've seen some "practice oriented" bachelor degrees like "Software Development" that don't cover these topics at all. I think more common is to have a few courses on it, but as a small part of the curriculum; which is largely forgotten by graduation time. I guarantee that asking the average application developer about IO ports, out of order execution, cache misses, AST passes, stack machines, how a GC works, or even just how to implement a hash table or tradeoffs between arrays and linked lists will earn you mostly blank, confused stares.
  - BossingAround 6y ago
    > which is largely forgotten by graduation time Let's be honest, 90% of everything you "learn" at university is largely forgotten during graduation time. I've seen folks fresh out of uni who couldn't even run a Java program without an IDE, or who forgot how to write a switch statement. I find it fascinating how inefficient the brain is, and how though it spends huge amount of our resources, it's actually not extremely good at picking up new complex information.
    - chrisseaton 6y ago
      'run a Java program without an IDE' is not a learning outcome of a computer science degree, though.
      - BossingAround 6y ago
        Is it not? If the programme teaches Java, "learning how to compile and execute Java programs" would surely be one of the top priorities of such a course.
        chrisseaton 6y ago
        Ok but you said they could do that using an IDE - why isn't that enough?
        rehemiau 6y ago
        Maybe because there are no IDEs on servers
        chrisseaton 6y ago
        Is it the job of a computer scientist to run programs on servers though? That seems like specific technical training, not the subject of a computer science degree.
- deleted 6y ago
  [deleted]
- hazz99 6y ago
  I go to a pretty good uni (not elite, but global top 30) and they don’t have a compilers course, which I was very disappointed by. It’s even a theory heavy degree!
  - p4bl0 6y ago
    Well, at least that says a lot about whatever is called "elite" and "global top N": it doesn't have any relevant meaning.
    - hazz99 6y ago
      To be fair, they’ve given me a great education and very valuable opportunities. I’m very appreciative! I just wish I didn’t have to self teach compilers.
  - chrisseaton 6y ago
    This really surprises me - looking down the THE and QS global rankings, I know that at least all the universities outside the Far East teach compilers. I guess you're not saying which university you're at to keep it anonymous, but I'd be interested to hear which it was.
    - derangedHorse 6y ago
      Which universities are you looking at? Mine technically had a compilers course but it wasn't required coursework and was generally offered every 2-3 years or so
      - chrisseaton 6y ago
        The top 30 in QS and THE. Most of them have major compiler research groups, even.
- kyawzazaw 6y ago
  It is an advanced elective. So totally optional. Some smaller colleges (like mine) don’t even offer it.
- rustybolt 6y ago
  A compiler course is standard, but it didn't teach me about linkers, relocation, loading, and all that stuff. So I see p4bl0's point.
bloodorange 6y ago
I have a feeling you might like this: https://www.nand2tetris.org/ https://www.nand2tetris.org/ It's a popular course about building a computer from nand gates and eventually building a Tetris like game on it. All of this is done on a hardware simulator of course. If you are keen on real hardware, you might find this interesting: https://www.youtube.com/watch?v=HyznrdDSSGM&list=PLowKtXNTBypGqImE405J2565dvjafglHU https://www.youtube.com/watch?v=HyznrdDSSGM&list=PLowKtXNTBy... It's a series of videos where Ben Eater explains how to build an 8-bit computer using breadboards and basic elements of circuits. I find that his explanations are quite good as well.
kgoutham93 6y ago
Hey, I am really intrigued about the idea. Do you follow any specific learning path? Any resources would also help a lot.

parenthesis 6y ago

Even if you never write or work on a compiler in the sense of a program that turns source code text into assembly, many programs (or parts thereof) are compilers in the sense of turning data or code in one form into another form.

lou1306 6y ago
This is especially true of "code generators" or "source-to-source" transformation tools. I did write one of each recently, and often had to look up the compiler literature to go forward.

shpongled 6y ago

I'm currently working on a compiler from scratch for fun/learning. Currently just compiling Standard ML without modules because it presents an interesting challenge, compilation-wise. I'm self taught (but have been programming 10+ years) so it's been a really interesting experience - I've gotten exposure/actual use of some different data structures and algorithms that I've never used before. If you're into this kinda thing, I suggest checking out the ProgrammingLanguages subreddit, there's a discord server as well.

deleted 6y ago

[deleted]

perfect5th 6y ago

I took a couple of compiler courses in university, and I think for the most part it made me a better programmer, mainly because it enforced understanding of how specific programming concepts and constructs are generally implemented. That, and a more intense look at the "heap of abstractions" you're generally working with when you write a higher-level language. I've always advocated that, if you want to really understand the tools you are using, you need to understand at least one level below the "surface abstraction" that you are working if. Even better if you can understand two or three levels down. There's a great talk from game developer Jonathan Blow [1] that describes how knowledge is lost "generationally" due to our lack of understanding of the black boxes we build things on top of. Not sure I 100% agree with his thoughts, but it's an interesting take. [1] https://www.youtube.com/watch?v=pW-SOdj4Kkk https://www.youtube.com/watch?v=pW-SOdj4Kkk

peacefulhat 6y ago

I spent a couple days writing a compiler for a custom shader language. It's a very simple lisp with minimal features, but enough to do everything I use in graphics. I compile this into glsl + a struct and functions for cpu side. A lot faster to prototype when I only have to modify my shader, and I can switch out the backend between webgl and opengl. Should be quick to add support for vulkan/metal/dx12 when I need that. I never would have thought to do this solution if I didn't already know how to write compilers. Somebody might say "oh, you could have used ____" - maybe, but it wasn't much effort and I can make it work in a convenient way for me. (in position f2) (in uv f2) (all sprite tex) (all color f4) (vert (position 0.0 1.0)) (frag (* (sprite uv) color))

stevekemp 6y ago

That's pretty topical for me, last week I challenged myself to write a brainfuck compiler in 24 hours or less. The end result worked out pretty well, and took less time than I expected: https://github.com/skx/bfcc/ https://github.com/skx/bfcc/

dang 6y ago

Discussed at the time: https://news.ycombinator.com/item?id=15005031 https://news.ycombinator.com/item?id=15005031

exdsq 6y ago

I’m writing a simple Lisp compiler with Bash at the moment. It’s fun to find all the things you really miss from other languages!