10 ms·

Resources for Amateur Compiler Writers

273 points by rspivak 10y ago

PaulHoule 10y ago
Is amateur the right word? I am in it for the money which I guess makes me a pro but I don't have a computer science background and frankly in 2016 I am afraid the average undergrad compiler course is part of the problem as much as the solution. Another big issue is nontraditional compilers of many kinds such as js accelerators and things that compile to JavaScript, domain specific languages, data flow systems, etc. Frankly I want to generate Java source or JVM byte code and could care less for real machine code.
- adrianN 10y ago
  The target language shouldn't make much of a difference, should it?
  - PaulHoule 10y ago
    It makes a huge difference. If you are compiling for x86 you have to think about register allocation. If you are compiling for JVM or an HLL, you don't. A good chunk of what is discussed in that article just is not relevant anymore.
    - Drup 10y ago
      Furthermore, the semantics of a language should be tailored for its target. Some execution pattern works well on the JVM, some don't. Same for javascript and other targets. Inventing whatever semantics you have in mind without considering how it's going to be compiled is a recipe for slow languages.
    - chrisseaton 10y ago
      Isolated anecdote, but I work on a JVM based language and my colleague is having to write a register allocator because our input language is written in SSA form and so has a huge number of locals in methods. We need to map these onto a smaller number of JVM locals (like register) otherwise the JVM frames are huge. Also, if you aren't writing a register allocator because you're using the JVM or LLVM, then someone else needs to on your behalf. We can't forget these skills.
      - drfuchs 10y ago
        Doesn't a modern JIT collapse JVM locals into a smaller actual stack frame already? Compilers have been doing this for local variables with non-overlapping liveness for decades.
        chrisseaton 10y ago
        The JVM can't do this because of debugging. If you attach a JVM debugger and examine a local variable which has had the storage reused what would you see? Junk from some other local variable. It's one cost of always on debugging. Normally the cost isn't too bad and of course they're spilled to the stack not kept in registers, but if the language you are implementing has thousands of locals you may even reach the limit of the frame size. We've seen this in practice in more than one language and application. Also, only some frames are JIT compiled - what about the rest?
        drfuchs 10y ago
        In the JVM, the start_pc/length of each LocalVariableTable entry lets you have more than one name for a given index in the stack frame, exactly so as to be able to reuse indexes for variables that don't overlap in liveness. So the debugging and non-JIT objections don't pertain. But if you're really running into the 64k limit on max_locals even with index reuse, then you're out of luck.
        chrisseaton 10y ago
        But that's my point - the person emitting the bytecode needs to be the one doing the work to re-use local variable indices. And the algorithm for doing that is register allocation. So even if you target the JVM you may still need to know how to do register allocation, and it isn't some historical piece of trivia. For every local variable index, the JVM needs to keep the value live for the duration of the method because that's what the debugger will show. And yes we have seen the 64k limit blown by real programs in the wild that aren't designed to be awkward (I'm in the VM research group at Oracle).
  - mcguire 10y ago
    There are 3 languages you have to understand to write a compiler: * The language you are using to write the compiler. You have to know it well enough to write a complex application. * The language you are compiling. You have to completely understand it. * The language you are compiling to: x86, JVM, etc. You have to understand it well enough to write every complex application.
    - nils-m-holm 10y ago
      I agree, except for the last point. Unless you are writing an optimizing compiler, you just have to understand the target language well enough to write snippets that resemble the operations of your source or intermediate language, which can be pretty little. See: http://t3x.org/subc/cg386.c.html http://t3x.org/subc/cg386.c.html Anecdotally: I have once written an AXP21164 back-end without any prior knowledge, only based on the reference manual. It was not pretty or fast, but it worked.
      - sitkack 10y ago
        Nils has an extraordinary amount of compiler related projects and books, http://www.t3x.org/ http://www.t3x.org/
- reymus 10y ago
  "frankly in 2016 I am afraid the average undergrad compiler course is part of the problem as much as the solution." What do you mean by that?
  - PaulHoule 10y ago
    They are still teaching undergrads how to make compilers that give incomprehensible error messages, etc. Compiler technology has the possibility of making a dent in the essential difficulty of getting computers to solve problem and the compiler class is not oriented towards those needs. There's nothing exciting about coding up a toy version of "Pascal" but it would be exciting if you could add the "unless" construction from Perl to Java in <1000 lines of code. We are just now coming out of a dark ages in compilers that was brought on by gcc. Before gcc you could make a living writing compilers (i.e. Turbo C, Turbo Pascal, Turbo Prolog, ...) at a moderately sized company. Today you have gcc and you have compilers from the likes of Intel and Microsoft. LLVM breathed some life into gcc since it is now modularized so that you can do interesting things on top of gcc.
  - tikhonj 10y ago
    I'm not the OP, but I sympathize. The specific details covered in a "classical" compilers course are heavy weight and not super-relevant right now. These days you don't have to understand LR parsing or touch a parser-generator, you don't have to worry about register coloring... etc. Courses still use the Dragon Book which is older than I am and covers a bunch of stuff only relevant to writing compilers for C on resource-constrained systems. Instead, I figure a course should cover basics of DSL design, types and type inference, working with ASTs, some static analysis and a few other things. That has some overlap with a traditional compilers course, but a pretty different focus.
    - Drup 10y ago
      So, the TAPL ? :) https://www.cis.upenn.edu/~bcpierce/tapl/ https://www.cis.upenn.edu/~bcpierce/tapl/
      - 10y ago
deleted 10y ago
[deleted]
cocoflunchy 10y ago
I recommend http://createyourproglang.com/ http://createyourproglang.com/ too if you want something very simple and you don't know where to start.
- Silhouette 10y ago
  Unfortunately that page seems to make a lot of big claims (and unnecessarily insult a lot of established work in the field) but seems to include literally no useful information about the book at all: no table of contents, no indication of who the target audience is or what prior experience is assumed, not even a summary of the topics it covers.
poseid 10y ago
nice collection - i keep some notes myself here, and was able to generate my own parser with Jison https://github.com/mulderp/mulderp.github.com/issues/13 https://github.com/mulderp/mulderp.github.com/issues/13 Once the parser returns the AST, it is getting more complicated, how to decorate an AST, add actions, etc. still looking to learn more about compiler backends
johan_larson 10y ago
Compiler construction is a big field, so it's easy to get lost in the details. If you are mostly interested in principles rather than the most recent tooling, there's a course by Wirth that makes it tractable. More here: http://short-sharp.blogspot.ca/2014/08/building-compiler-briefly.html http://short-sharp.blogspot.ca/2014/08/building-compiler-bri...
_RPM 10y ago
I wrote a VM, I still can't get recursion to work. It's hard.
- chrisseaton 10y ago
  I never understood why recursion causes anyone any problems, because recursion is the absence of a special case limitation. If I tell you that a function may call any function, then you already know everything you need to know for recursion. If we didn't have recursion, only then would I need to qualify what I just told you with the restriction that a function can only be active once. When I show students recursion I can't understand their confusion. I think to myself 'but I already showed you functions can call any other function, why do you see this case differently?' (Obviously I try to be more patient, understanding and anticipatory in person.)
  - octo_t 10y ago
    I think the issue is it forces people to think about preconditions, postconditions and invariants in a very different way if they've come from imperative programming.
  - _RPM 10y ago
    Yes, but I generate the arguments from converting the AST into the internal byte code, so arguments are just a LOAD_NAME, etc. There seems to be a problem when the arguments are coming from the currently executing function's stack (instead of the AST) As I restore the context from current executing function execute data to the previous execute data, and pop the stack once, and push it into the old context's stack as the return value. Also, just to be clear, I understand how recursion works as a user of a programming language, though implementing it is different than using it.
    - ericbb 10y ago
      I definitely struggled to find a satisfying approach to recursion in my own current language project. What I'm doing right now is passing the closure value of the callee as a hidden first argument to every call. Nonrecursive functions just ignore that argument but recursive functions can always call themselves via that hidden argument. It doesn't allow you to support syntactic mutual recursion but it's easy to do and can be implemented without data modification at any level.
senko 10y ago
IMHO, compiler construction as an advanced excercise for amateurs is at topic that has been beaten to death (as OP suggests, there's tons of available materials and projects ranging from high quality not-so-amateur to quick or fun hacks - I'm guilty of one myself). On the other hand, I would love to see "HTML5 and CSS parsing and rendering for amateurs". Given the state of modern HTML5 and CSS standards, and ignoring compatibility and real-world usage (just like for toy compilers), Let's Build A Browser Engine sounds more tempting than Let's Build a Compiler. (To preempt "contribute to existing actual real-world engine" suggestions -- while that's worthwhile, it's like saying "contribute to LLVM" to someone looking to write a toy compiler, ie. completely misses the point).
- stijlist 10y ago
  There's this great series by mbrubeck which sounds like it might be right up your alley: https://limpet.net/mbrubeck/2014/08/08/toy-layout-engine-1.html https://limpet.net/mbrubeck/2014/08/08/toy-layout-engine-1.h...
  - senko 10y ago
    This looks like a great resource, thanks!
    - creatio 10y ago
      This also might be interestings: http://www.html5rocks.com/en/tutorials/internals/howbrowserswork/ http://www.html5rocks.com/en/tutorials/internals/howbrowsers...
- gsnedders 10y ago
  > Given the state of modern HTML5 and CSS standards, and ignoring compatibility and real-world usage (just like for toy compilers), Let's Build A Browser Engine sounds more tempting than Let's Build a Compiler. FWIW, current HTML and CSS standards should give you compatibility with real-world usage if you implement them accurately. Of course, for a toy, you may well want to simplify things from what the standard does.
Ind007 10y ago
Is there any similar kind of collection for static analysis?
- ericbb 10y ago
  Matt Might's site has some pages on this topic: http://matt.might.net/articles/books-papers-materials-for-graduate-students/#analysis http://matt.might.net/articles/books-papers-materials-for-gr... http://matt.might.net/articles/intro-static-analysis/ http://matt.might.net/articles/intro-static-analysis/ http://matt.might.net/articles/partial-orders/ http://matt.might.net/articles/partial-orders/
barrkel 10y ago
If you're more interested in the front end than the back end, then Crenshaw's Let's Build a Compiler is still worthwhile.
zzzcpan 10y ago
Frankly, I don't see anything interesting in that list, especially for amateurs. As an amateur compiler writer you would probably want to make something useful in a few weeks, not waste a year playing around. And it's a very different story. It's essentially about making a meta DSL, that compiles into another language and plays well with existing libraries, tooling, the whole ecosystem, but also does something special and useful for you. So, you should learn parsing, possibly recursive descend for the code and something else for expressions, a bit about working with ASTs and that's pretty much it.
jfoutz 10y ago
Dybvig's dissertation is great. [1] People might disagree that it's a compiler, it targets a fairly high level vm rather than a native machine. But it's got everything you need. Really, you can fire up dr racket, type it in and have a great framework in an afternoon. Anyway, it's very readable. [1] http://agl.cs.unm.edu/~williams/cs491/three-imp.pdf http://agl.cs.unm.edu/~williams/cs491/three-imp.pdf
qwertyuiop924 10y ago
If you're interested in getting started with interpreters, which are easier, you might want to look into Daniel Holden's excellent Build Your Own Lisp (And Learn C). Although it has been criticized for many reasons, it's a great book, and if you find interpreters and compilers totally magic, it's a good place to start. Also, after reading What every compiler writer should know about programmers, I finally understand why people hate C. Because this just shows definitively that C compiler writers have been in their own little world for the past few decades. Man, now I want a C compiler that wasn't written by a bunch of mindless jerks that will be the first up against the wall when the revolution comes...

273 points by rspivak 10y ago

Is amateur the right word? I am in it for the money which I guess makes me a pro but I don't have a computer science background and frankly in 2016 I am afraid the average undergrad compiler course is part of the problem as much as the solution. Another big issue is nontraditional compilers of many kinds such as js accelerators and things that compile to JavaScript, domain specific languages, data flow systems, etc. Frankly I want to generate Java source or JVM byte code and could care less for real machine code.

adrianN 10y ago
The target language shouldn't make much of a difference, should it?
- PaulHoule 10y ago
  It makes a huge difference. If you are compiling for x86 you have to think about register allocation. If you are compiling for JVM or an HLL, you don't. A good chunk of what is discussed in that article just is not relevant anymore.
  - Drup 10y ago
    Furthermore, the semantics of a language should be tailored for its target. Some execution pattern works well on the JVM, some don't. Same for javascript and other targets. Inventing whatever semantics you have in mind without considering how it's going to be compiled is a recipe for slow languages.
  - chrisseaton 10y ago
    Isolated anecdote, but I work on a JVM based language and my colleague is having to write a register allocator because our input language is written in SSA form and so has a huge number of locals in methods. We need to map these onto a smaller number of JVM locals (like register) otherwise the JVM frames are huge. Also, if you aren't writing a register allocator because you're using the JVM or LLVM, then someone else needs to on your behalf. We can't forget these skills.
    - drfuchs 10y ago
      Doesn't a modern JIT collapse JVM locals into a smaller actual stack frame already? Compilers have been doing this for local variables with non-overlapping liveness for decades.
      - chrisseaton 10y ago
        The JVM can't do this because of debugging. If you attach a JVM debugger and examine a local variable which has had the storage reused what would you see? Junk from some other local variable. It's one cost of always on debugging. Normally the cost isn't too bad and of course they're spilled to the stack not kept in registers, but if the language you are implementing has thousands of locals you may even reach the limit of the frame size. We've seen this in practice in more than one language and application. Also, only some frames are JIT compiled - what about the rest?
        drfuchs 10y ago
        In the JVM, the start_pc/length of each LocalVariableTable entry lets you have more than one name for a given index in the stack frame, exactly so as to be able to reuse indexes for variables that don't overlap in liveness. So the debugging and non-JIT objections don't pertain. But if you're really running into the 64k limit on max_locals even with index reuse, then you're out of luck.
        chrisseaton 10y ago
        But that's my point - the person emitting the bytecode needs to be the one doing the work to re-use local variable indices. And the algorithm for doing that is register allocation. So even if you target the JVM you may still need to know how to do register allocation, and it isn't some historical piece of trivia. For every local variable index, the JVM needs to keep the value live for the duration of the method because that's what the debugger will show. And yes we have seen the 64k limit blown by real programs in the wild that aren't designed to be awkward (I'm in the VM research group at Oracle).
- mcguire 10y ago
  There are 3 languages you have to understand to write a compiler: * The language you are using to write the compiler. You have to know it well enough to write a complex application. * The language you are compiling. You have to completely understand it. * The language you are compiling to: x86, JVM, etc. You have to understand it well enough to write every complex application.
  - nils-m-holm 10y ago
    I agree, except for the last point. Unless you are writing an optimizing compiler, you just have to understand the target language well enough to write snippets that resemble the operations of your source or intermediate language, which can be pretty little. See: http://t3x.org/subc/cg386.c.html http://t3x.org/subc/cg386.c.html Anecdotally: I have once written an AXP21164 back-end without any prior knowledge, only based on the reference manual. It was not pretty or fast, but it worked.
    - sitkack 10y ago
      Nils has an extraordinary amount of compiler related projects and books, http://www.t3x.org/ http://www.t3x.org/
reymus 10y ago
"frankly in 2016 I am afraid the average undergrad compiler course is part of the problem as much as the solution." What do you mean by that?
- PaulHoule 10y ago
  They are still teaching undergrads how to make compilers that give incomprehensible error messages, etc. Compiler technology has the possibility of making a dent in the essential difficulty of getting computers to solve problem and the compiler class is not oriented towards those needs. There's nothing exciting about coding up a toy version of "Pascal" but it would be exciting if you could add the "unless" construction from Perl to Java in <1000 lines of code. We are just now coming out of a dark ages in compilers that was brought on by gcc. Before gcc you could make a living writing compilers (i.e. Turbo C, Turbo Pascal, Turbo Prolog, ...) at a moderately sized company. Today you have gcc and you have compilers from the likes of Intel and Microsoft. LLVM breathed some life into gcc since it is now modularized so that you can do interesting things on top of gcc.
- tikhonj 10y ago
  I'm not the OP, but I sympathize. The specific details covered in a "classical" compilers course are heavy weight and not super-relevant right now. These days you don't have to understand LR parsing or touch a parser-generator, you don't have to worry about register coloring... etc. Courses still use the Dragon Book which is older than I am and covers a bunch of stuff only relevant to writing compilers for C on resource-constrained systems. Instead, I figure a course should cover basics of DSL design, types and type inference, working with ASTs, some static analysis and a few other things. That has some overlap with a traditional compilers course, but a pretty different focus.
  - Drup 10y ago
    So, the TAPL ? :) https://www.cis.upenn.edu/~bcpierce/tapl/ https://www.cis.upenn.edu/~bcpierce/tapl/
    - 10y ago

deleted 10y ago

[deleted]

cocoflunchy 10y ago

I recommend http://createyourproglang.com/ http://createyourproglang.com/ too if you want something very simple and you don't know where to start.

Silhouette 10y ago
Unfortunately that page seems to make a lot of big claims (and unnecessarily insult a lot of established work in the field) but seems to include literally no useful information about the book at all: no table of contents, no indication of who the target audience is or what prior experience is assumed, not even a summary of the topics it covers.

poseid 10y ago

nice collection - i keep some notes myself here, and was able to generate my own parser with Jison https://github.com/mulderp/mulderp.github.com/issues/13 https://github.com/mulderp/mulderp.github.com/issues/13 Once the parser returns the AST, it is getting more complicated, how to decorate an AST, add actions, etc. still looking to learn more about compiler backends

johan_larson 10y ago

Compiler construction is a big field, so it's easy to get lost in the details. If you are mostly interested in principles rather than the most recent tooling, there's a course by Wirth that makes it tractable. More here: http://short-sharp.blogspot.ca/2014/08/building-compiler-briefly.html http://short-sharp.blogspot.ca/2014/08/building-compiler-bri...

_RPM 10y ago

I wrote a VM, I still can't get recursion to work. It's hard.

chrisseaton 10y ago
I never understood why recursion causes anyone any problems, because recursion is the absence of a special case limitation. If I tell you that a function may call any function, then you already know everything you need to know for recursion. If we didn't have recursion, only then would I need to qualify what I just told you with the restriction that a function can only be active once. When I show students recursion I can't understand their confusion. I think to myself 'but I already showed you functions can call any other function, why do you see this case differently?' (Obviously I try to be more patient, understanding and anticipatory in person.)
- octo_t 10y ago
  I think the issue is it forces people to think about preconditions, postconditions and invariants in a very different way if they've come from imperative programming.
- _RPM 10y ago
  Yes, but I generate the arguments from converting the AST into the internal byte code, so arguments are just a LOAD_NAME, etc. There seems to be a problem when the arguments are coming from the currently executing function's stack (instead of the AST) As I restore the context from current executing function execute data to the previous execute data, and pop the stack once, and push it into the old context's stack as the return value. Also, just to be clear, I understand how recursion works as a user of a programming language, though implementing it is different than using it.
  - ericbb 10y ago
    I definitely struggled to find a satisfying approach to recursion in my own current language project. What I'm doing right now is passing the closure value of the callee as a hidden first argument to every call. Nonrecursive functions just ignore that argument but recursive functions can always call themselves via that hidden argument. It doesn't allow you to support syntactic mutual recursion but it's easy to do and can be implemented without data modification at any level.

senko 10y ago

IMHO, compiler construction as an advanced excercise for amateurs is at topic that has been beaten to death (as OP suggests, there's tons of available materials and projects ranging from high quality not-so-amateur to quick or fun hacks - I'm guilty of one myself). On the other hand, I would love to see "HTML5 and CSS parsing and rendering for amateurs". Given the state of modern HTML5 and CSS standards, and ignoring compatibility and real-world usage (just like for toy compilers), Let's Build A Browser Engine sounds more tempting than Let's Build a Compiler. (To preempt "contribute to existing actual real-world engine" suggestions -- while that's worthwhile, it's like saying "contribute to LLVM" to someone looking to write a toy compiler, ie. completely misses the point).

stijlist 10y ago
There's this great series by mbrubeck which sounds like it might be right up your alley: https://limpet.net/mbrubeck/2014/08/08/toy-layout-engine-1.html https://limpet.net/mbrubeck/2014/08/08/toy-layout-engine-1.h...
- senko 10y ago
  This looks like a great resource, thanks!
  - creatio 10y ago
    This also might be interestings: http://www.html5rocks.com/en/tutorials/internals/howbrowserswork/ http://www.html5rocks.com/en/tutorials/internals/howbrowsers...
gsnedders 10y ago
> Given the state of modern HTML5 and CSS standards, and ignoring compatibility and real-world usage (just like for toy compilers), Let's Build A Browser Engine sounds more tempting than Let's Build a Compiler. FWIW, current HTML and CSS standards should give you compatibility with real-world usage if you implement them accurately. Of course, for a toy, you may well want to simplify things from what the standard does.

Ind007 10y ago

Is there any similar kind of collection for static analysis?

ericbb 10y ago
Matt Might's site has some pages on this topic: http://matt.might.net/articles/books-papers-materials-for-graduate-students/#analysis http://matt.might.net/articles/books-papers-materials-for-gr... http://matt.might.net/articles/intro-static-analysis/ http://matt.might.net/articles/intro-static-analysis/ http://matt.might.net/articles/partial-orders/ http://matt.might.net/articles/partial-orders/

barrkel 10y ago

If you're more interested in the front end than the back end, then Crenshaw's Let's Build a Compiler is still worthwhile.

zzzcpan 10y ago

Frankly, I don't see anything interesting in that list, especially for amateurs. As an amateur compiler writer you would probably want to make something useful in a few weeks, not waste a year playing around. And it's a very different story. It's essentially about making a meta DSL, that compiles into another language and plays well with existing libraries, tooling, the whole ecosystem, but also does something special and useful for you. So, you should learn parsing, possibly recursive descend for the code and something else for expressions, a bit about working with ASTs and that's pretty much it.

jfoutz 10y ago

Dybvig's dissertation is great. [1] People might disagree that it's a compiler, it targets a fairly high level vm rather than a native machine. But it's got everything you need. Really, you can fire up dr racket, type it in and have a great framework in an afternoon. Anyway, it's very readable. [1] http://agl.cs.unm.edu/~williams/cs491/three-imp.pdf http://agl.cs.unm.edu/~williams/cs491/three-imp.pdf

qwertyuiop924 10y ago

If you're interested in getting started with interpreters, which are easier, you might want to look into Daniel Holden's excellent Build Your Own Lisp (And Learn C). Although it has been criticized for many reasons, it's a great book, and if you find interpreters and compilers totally magic, it's a good place to start. Also, after reading What every compiler writer should know about programmers, I finally understand why people hate C. Because this just shows definitively that C compiler writers have been in their own little world for the past few decades. Man, now I want a C compiler that wasn't written by a bunch of mindless jerks that will be the first up against the wall when the revolution comes...