9 ms·

So You Want to Be a Compiler Wizard

192 points by samsymons 10y ago

_RPM 10y ago
> Write snprintf in C Another application of the `snprintf` function is `PyArg_ParseTuple` from CPython. [0] It's not exactly printing formatted output but parsing the args from the `va_list` based on the format. You pass it pointers and it assigns values to the pointers. [0] https://docs.python.org/2/c-api/arg.html#c.PyArg_ParseTuple https://docs.python.org/2/c-api/arg.html#c.PyArg_ParseTuple
- akkartik 10y ago
  > Write snprintf in assembly See the implementation of interpolate in my Assembly-like language: http://akkartik.github.io/mu/html/070text.mu.html http://akkartik.github.io/mu/html/070text.mu.html (search for 'interpolate'. There's also unit tests: the scenarios after the definition) More details: http://akkartik.name/post/mu http://akkartik.name/post/mu
jbb555 10y ago
This was an ok article before it started ranting on about privilege and bias and codes of conducts for projects. I lost interest then.
- fao_ 10y ago
  Could you quote the parts that you thought were a rant? I'm curious, as I read it in an even tone, and thought it was fine. (I think it would be interesting to see your line of thought)
  - zxexz 10y ago
    I think jbb555 is referring to the 'On "Free Time"' section. I see where they're coming from, and do partially agree that an article on compilers isn't really the place for a section of that sort (I like technical/learning articles to be 'atomic', but that's just personal preference). However, I also fullheartedly agree with with the content of the section in question, and would be hesitant to call it a 'rant'. Does seem like a section that could stand on its own as a post, though. Perhaps even be linked to from this post?
  - ThatGeoGuy 10y ago
    I think it has more to do with the fact that the article starts taking a topic that's completely orthogonal to everything before it. There's some good technical advice beforehand about getting into compiler hacking, but as soon as you break into the "On Free Time" section, the article for some bizarre reason delves into how most compiler hackers are privileged. Sure, like anything in tech most people doing it are likely male and probably white, but I think the entire section is for a different article entirely. Reading it, it appears that the author cares more about making a point about how compiler hackers are mostly "privileged" and how you need to find a code of conduct so you can avoid the assholes (the author admits it won't be a silver bullet, but that's not the point here). In any case, the whole section doesn't really give much advice to people who _already_ want to be compiler wizards, but sounds more like trying to sell becoming one to somebody who is nervous about getting into tech in general. As I mentioned before, it comes off as orthogonal to what the article introduces itself as.
    - breck 10y ago
      I also really liked this article but found that bit orthogonal. Thought that comes to mind is like clean code an essay should ideally do one thing and do it well...but if it has to do more than one thing, it should do what it says. I'd suggest splitting the article into 2 (["So You Want to Be a (Compiler) Wizard", "Contributing to Open Source Compiler Projects"]) or if not that then update the title "So You Want to Be a (Compiler) Wizard; Plus Thoughts on Contributing to Open Source Compiler Projects".
    - sanderjd 10y ago
      I read it as an article aimed at people who want to get into open source for the first time, specifically targeted at compilers, because that's what the author knows. Like it or not, the social aspects of open source communities is very relevant to that target audience.
      - brighteyes 10y ago
        Social aspects matter, however, what the article does is talk about them from one very specific political position. It will look familiar and clear to people sharing that position, but it excludes others with a different political worldview.
- sanderjd 10y ago
  That wasn't ranting, it was cogent and well-structured and made good points. If you disagree with those points, say so, but don't diminish it by calling it a rant. I think those points are extremely relevant for an article targeted at people trying to get involved in open source. The for-pay vs. free-time divide is a fundamental problem with using open source work as an "in" to the industry, and despite being scoff-worthy to some people, it's helpful for people coming into this with fresh eyes (ie. the target audience of the article) to be given some context.
  - brighteyes 10y ago
    It's that the points mentioned are the same old familiar points, and the arguments against them are also the same old familiar ones. For example, the article says "men have more privilege than women", based on the criteria provided, which are > 1. Who don’t have families to take care of (kids, parents, whatever) > 2. who have a good, steady income (i.e. not learning while, say, balancing two part-time jobs) > 3. who live close to work (minimizing a commute) And yes, women are more likely to have people to take care of. However, there are also reasons to say women are more privileged than men in this context. For example, 4. Are in college, as a lot of open source contributors are college students. Women are a lot more likely to get into college than men. 5. Are not in jail or prison. Women are far less likely to be in those situations. In other words, it is horribly simplistic to say "men have more privilege than women" in this context. It's just lazy regurgitating of the familiar talking points. It's not helpful. Yes, it's worth mentioning some people have an easier way into open source. But no, it's a bad idea to turn this into an oversimplified and false matter of "men > women".
    - sanderjd 10y ago
      Firstly, I was responding to the idea that this topic is irrelevant or orthogonal to the rest of the article - you don't seem to disagree with that, but rather disagree with the specific points that were made. Secondly, "the same old familiar points" assumes everyone has the same familiarity with the topic that you do, which of course isn't true in general, and the target audience of the article is actively people who are unlikely to have come across this.
- gjm11 10y ago
  Good news! That was at the end of the article, so you didn't miss things you might have been interested in. But the "ranting" isn't particularly ranty and has (it seems to me) a specific purpose: the author is concerned that some people reading his article might be discouraged from getting into open source software by the biases he describes, and wants to encourage them not to be. "But it can't stop you", he says: that's the point. So I think the author is deliberately making a tradeoff: by inserting that material, he hopes to encourage any readers he has from "less privileged" groups not to give up if things get difficult, even if it means that some people from "more privileged" groups who don't like reading about privilege and bias and codes and conduct are put off. Is it a good tradeoff? I dunno. It doesn't seem obviously bad.
  - teacup50 10y ago
    It comes across as offensive and discouraging to those that believe that "intersectionality" is in itself discriminatory, both towards the racial/gender classifications being infantilized, and the racial/gender classifications who are assumed to be privileged. As an extension, the entire presumption of the necessity of a "code of conduct" is in itself "problematic", in that it ascribes problematic behavior to what are in fact welcoming, professional, pro-actively inclusive communities that simply do not accept at face value the discriminatory precepts (racial, gender, or otherwise) of intersectionality.
    - teacup50 10y ago
      The downvoting demonstrates exactly why the article's well-poisoning is offensive; the tautological ideology of intersectionality leaves no room for dissent in the marketplace of ideas, as any dissent merely proves the original premise of structural discrimination and privilege that applies to blunt categories of people on the basis of gender and race, and thus dissent is not to be considered an invitation to dialog, but damaging ignorance at best, "hate speech" at worst, and worthy of silencing regardless.
      - yoo1I 10y ago
        The marketplace of ideas just, rightly, rejected your elaborate but essentially baseless claim that anti-discrimination victimizes everyone who is not in the group being "de-victimized". It would be comical if it wasn't so sad.
- WalterBright 10y ago
  Having been into compilers for 40 years, I can confidently say that if you need validation, encouragement, support, etc., from others you're going into the wrong field. I'm a white male, and pretty much 100% of people told me I was not good enough to write a compiler, that I was sure to fail, that I could not possibly compete against Big Corporations, etc. The same goes for inventing a new programming language. Meanwhile, I've had a rewarding career doing it :-)
sebg 10y ago
Whenever compilers come up, this Steve Yegge article comes to mind -> http://steve-yegge.blogspot.com/2007/06/rich-programmer-food.html http://steve-yegge.blogspot.com/2007/06/rich-programmer-food... that starts: "Gentle, yet insistent executive summary: If you don't know how compilers work, then you don't know how computers work. If you're not 100% sure whether you know how compilers work, then you don't know how they work."
- Kluny 10y ago
  I saw it on the front page last week, actually. I suspect that's why this article got posted.
- joe_the_user 10y ago
  Gentle, yet insistent executive summary: If you don't know how compilers work, then you don't know how computers work. If you're not 100% sure whether you know how compilers work, then you don't know how they work. As opaque and arrogant as that sounds, the statement is actually fairly accurate. The way I'd try to put nicely is that compiler construction involves some conceptual barriers that make constructing an interpreter or compiler different than other programs, even other complex programs. The main difference is that a programming language is an abstract object on a different logical level than, say, a real world object. I think the best way to understand this is constructing a recursive descent parser. Doing requires one to transform the language you parsing and so get an idea of abstract languages. A lot of the advice people gives, such as using regular expressions, isn't a way to get a complete picture of what's happening in the parser or compiler construction process.
chrisseaton 10y ago
If anyone wants to get involved with an open source Ruby JIT compiler you can join us in #jruby or https://gitter.im/jruby/jruby https://gitter.im/jruby/jruby. Happy to tutor beginners.
jdc0589 10y ago
something about parsing text and generating something meaningful from it is just super gratifying; doesn't even have to be a full blown compiler. Some of most enjoyable programming experiences I have had were working on trivial parsing + transformation; e.g. a css beautifier, html beautifier, and whatever the hell this is https://github.com/jdc0589/jtranslate https://github.com/jdc0589/jtranslate (I wrote it in college, I still have no idea what I meant its purpose to be) I've done a couple things closer to full blown compilers (C-- compiler, hand written pascal subset compiler + one using a parser generator for the same language subset). As fun as those were, the simpler stuff was more enjoyable for me.
- nojvek 10y ago
  I 100% agree with this. Making a computer understand a domain of text and manipulate it in interesting ways is amazing. Similar is web crawlers. It feels like magic when the product works.
  - jdc0589 10y ago
    hah, we have similar preferences for what we consider "fun". The last per project I worked on was basically the same as https://www.kimonolabs.com/ https://www.kimonolabs.com/, but with a different paradigm for writing crawlers/parsers (I hate wysiwyg/point+click interfaces for shit like this). THey launched their product when I was taking a break from mine, and implemented most of my feature set though :(
xigency 10y ago
These are definitely some interesting ideas on breaking into a new discipline. The little projects list is great and it's definitely good motivation to start improving skills. One problem I have with this article though, is not with the idea of becoming a wizard at something, which is a great way at looking at things, but rather the idea of joining a special group. Personally, I have a bit of an issue with using LLVM to get started. Maybe this isn't fair because I have literally no experience with LLVM outside of clang, but I think part of the idea of becoming a "wizard" means starting from scratch. Obviously, it's not helpful to point someone in the direction of impossible tasks to get them motivated, but the direction this heads quickly turns toward not becoming a leading independent thinker but becoming a mindless bug fixer on another project. I don't think you can learn to write compilers by fixing other people's bugs. It turns to: solving bugs, getting involved in open source, jumping on someone else's projects, and most of all projects where others are best suited to gain from the developments. It reminds me of the flowchart "Should I work for free?" which programmers should really pay attention to. It's great to work with others, to collaborate, and to appreciate and understand other's technology; however, computer science and programming are rather miraculous in the amount of distance an individual can travel on their own, and being forced to jump on a bandwagon or join a community seems to be demeaning in the end.
- chrisseaton 10y ago
  What are you suggesting then? Learning about how compilers work with no exposure to any existing compilers?
  - lgas 10y ago
    I'm reminded me of the Sagan quote "If you wish to make apple pie from scratch, you must first create the universe".
  - thwarted 10y ago
    In the Compiler Design class I took 20 years ago, we used the dragon book, which I found to be pretty accessible for someone who already knows how to program (at least in an academic setting). The only production (non-educational) compiler we had easily available source code for was gcc, which is not something appropriate for a beginner to learn compiler design and structure from.
prestonbriggs 10y ago
List seems inadequate. I guess it's enough to get you going working on compilers, but there's not much wizardly on that list. Read papers. Learn about data-flow analysis and optimization. Learn code generation (instruction selection, register allocation, instruction scheduling). Learn about interprocedural data-flow analysis. Learn/build a garbage collector or 2. Parallelization, vectorization, type analysis. Write an optimizer for Go. Write papers or your own.
- xigency 10y ago
  I'm not sure that the author cares very much about CPU registers.
  - prestonbriggs 10y ago
    Sure he does... Anyone advocating for assembly language necessarily cares about registers.
UK-AL 10y ago
Much more useful to learn about constructing NFA/DFA automatons from 'pure' regular expressions, then say just knowing regular expression syntax off by art. This is basically gets you to understand regular grammar, probably the easiest formal grammar to understand. If you understand state machines, you know what you know what regular grammars are capable of. Where all the different types of parsing methods? Recursive Descent, LL Parsers, LR Parsers, LALR parser. Being able to understand production rules? Chomsky hierarchy of the formal grammars? Then converting that into AST -> Optimization(so much stuff here) -> Code emitter.
- unimpressive 10y ago
  Coursera/Stanford Online's compilers course covers all this. https://class.coursera.org/compilers/ https://class.coursera.org/compilers/
melling 10y ago
I've got a collection of resources on compilers and interpreters: https://github.com/melling/ComputerLanguages/blob/master/compilers.org https://github.com/melling/ComputerLanguages/blob/master/com...
- codewritinfool 10y ago
  Excellent resource, thank you!
tbirdz 10y ago
I left this comment on the author's page too, but I've copied it to HN as well: I'd also suggest learning and writing your own Forth. The Forth language is very simple to implement, simpler even than Lisp by a long ways, I'd say. If you know how to make a stack, (well two stacks), then you can make your own Forth Interpreter. Going from the Interpreter to the compiler is also easier than in other languages. There is not really much syntax to speak of, and most of the languages's features, even the comments, can be implemented in the language itself. Of course for speed reasons you'd probably want to put the langauge forms into highly optimized assembly forms or something, but you don't have to do that right away. There also isn't much of a runtime system to implement at all. With Lisp you'll have to write a garbage collector, with Forth, you just need to be able to allocate a slab of memory from the OS, maintain the stacks, and the word (like a function in another language) and variable dictionaries. Oh, and including a copy of the compiler to run in interactive mode, but you'd need to do that in Lisp too. Also, writing a Forth compiler lets you jump right into advanced optimizations. Really even just aggressive inlining and basic optimizations will get you a huge speed increase, which is a great motivational boost. The Reverse Polish Notation style stack form of the language is great for matching optimization patterns with as-is. I know SSA is pretty much THE technique to use for register based languages, but you can get great results from Forth by optimizing as is instead of converting to SSA. I really think Forth is a great language to learn compilers with. It really lets you skip ahead to the interesting parts of compilers, since the language doesn't require complicated parsers, or runtime systems.
- prestonbriggs 10y ago
  I disagree. Forth is cute and you'll learn some stuff, but you won't become a compiler wizard. You _need_ to learn how to do parsers and run-time systems and all the rest. Besides, it's fun!
  - tbirdz 10y ago
    I see what you're saying, but respectfully I disagree. The importance of parsers and run-time systems in compilers really depends on the language you are compiling. There's a big spectrum there. For runtime systems, on one hand you have languages where they are very important, such as runtime garbage collectors in Lisp, Java, and similar languages, Prolog's runtime logic backtracking, runtime exception support for C++ but no garbage collection, down to languages like C with no garbage collection and minimal runtime. Forth is certainly on the lower end of the compiler runtime implementation spectrum. For parsing, there's a similar spectrum. There's languages with hideously complicated grammars, like C++, less complex ones like Lisp, and probably again on the simplest end of the spectrum is Forth. So the requirement of needing to learn to write complex parsers and runtime systems is dependant on the language. I'd certainly classify a C compiler author as a "wizard" even though they wouldn't have to write a garbage collector for their C compiler, and a Lisp compiler author as a "wizard" even though their parser is much less difficult to create than a C++ language parser. Of course, it's not like wizard is an exact term or anything. If you're saying a "compiler wizard" should be able to understand how to implement any language, then of course you need to have in-depth knowledge of parsers and run-time systems. Me personally, I'd say if you can write a compiler for any language you're somewhere on the compiler magician spectrum. Maybe not full wizard, but at least a compiler warlock or enchanter or something (this is getting silly now, I don't really want to argue about the semantics of the term wizard applied to compilers).
ori_b 10y ago
This is... rather awful. I'd suggest taking a look at the reading list here instead: http://c9x.me/compile/bib/ http://c9x.me/compile/bib/ This article goes through a number of unrelated exercises, mentions a few hello-world level introductions, and then skips to a more or less unrelated introduction to open source, with a rather bizarre criticism of people who contribute to open source without getting paid for it. If it was written for 'becoming a C wizard', I would imagine that it would read something along the lines of: - Say 'hello' a few times - Write some words on paper - type 'print "hello"' into a python prompt - Work through the "hello world" program in K&R - You're a terrible person if you learn C without getting paid.
- joe_the_user 10y ago
  Yes, In fact, it's even worse than that. You can become one kind of "C wizard" just by writing a bunch of programs since a lot of programming is fairly clear once someone understands function calls and for-loops. But understand compiler construction at a reasonable level requires some specific set of skills that don't come from just messing around.
- Joof 10y ago
  Your link seems pretty good. SSA, dominators, register allocation (utilizing chordal graphs / SSA I hope). Constant propagation. Optimizations AND parsing.
WalterBright 10y ago
An article I wrote on the same subject: https://www.digitalmars.com/articles/b89.html https://www.digitalmars.com/articles/b89.html
- ori_b 10y ago
  You may want to update your certificates -- Chrome complains when I try to view the page.
  - WalterBright 10y ago
    Yeah, I need to do that. For the moment, use this instead: http://www.digitalmars.com/articles/b89.html http://www.digitalmars.com/articles/b89.html

192 points by samsymons 10y ago

_RPM 10y ago

> Write snprintf in C Another application of the `snprintf` function is `PyArg_ParseTuple` from CPython. [0] It's not exactly printing formatted output but parsing the args from the `va_list` based on the format. You pass it pointers and it assigns values to the pointers. [0] https://docs.python.org/2/c-api/arg.html#c.PyArg_ParseTuple https://docs.python.org/2/c-api/arg.html#c.PyArg_ParseTuple

akkartik 10y ago
> Write snprintf in assembly See the implementation of interpolate in my Assembly-like language: http://akkartik.github.io/mu/html/070text.mu.html http://akkartik.github.io/mu/html/070text.mu.html (search for 'interpolate'. There's also unit tests: the scenarios after the definition) More details: http://akkartik.name/post/mu http://akkartik.name/post/mu

jbb555 10y ago

This was an ok article before it started ranting on about privilege and bias and codes of conducts for projects. I lost interest then.

fao_ 10y ago
Could you quote the parts that you thought were a rant? I'm curious, as I read it in an even tone, and thought it was fine. (I think it would be interesting to see your line of thought)
- zxexz 10y ago
  I think jbb555 is referring to the 'On "Free Time"' section. I see where they're coming from, and do partially agree that an article on compilers isn't really the place for a section of that sort (I like technical/learning articles to be 'atomic', but that's just personal preference). However, I also fullheartedly agree with with the content of the section in question, and would be hesitant to call it a 'rant'. Does seem like a section that could stand on its own as a post, though. Perhaps even be linked to from this post?
- ThatGeoGuy 10y ago
  I think it has more to do with the fact that the article starts taking a topic that's completely orthogonal to everything before it. There's some good technical advice beforehand about getting into compiler hacking, but as soon as you break into the "On Free Time" section, the article for some bizarre reason delves into how most compiler hackers are privileged. Sure, like anything in tech most people doing it are likely male and probably white, but I think the entire section is for a different article entirely. Reading it, it appears that the author cares more about making a point about how compiler hackers are mostly "privileged" and how you need to find a code of conduct so you can avoid the assholes (the author admits it won't be a silver bullet, but that's not the point here). In any case, the whole section doesn't really give much advice to people who _already_ want to be compiler wizards, but sounds more like trying to sell becoming one to somebody who is nervous about getting into tech in general. As I mentioned before, it comes off as orthogonal to what the article introduces itself as.
  - breck 10y ago
    I also really liked this article but found that bit orthogonal. Thought that comes to mind is like clean code an essay should ideally do one thing and do it well...but if it has to do more than one thing, it should do what it says. I'd suggest splitting the article into 2 (["So You Want to Be a (Compiler) Wizard", "Contributing to Open Source Compiler Projects"]) or if not that then update the title "So You Want to Be a (Compiler) Wizard; Plus Thoughts on Contributing to Open Source Compiler Projects".
  - sanderjd 10y ago
    I read it as an article aimed at people who want to get into open source for the first time, specifically targeted at compilers, because that's what the author knows. Like it or not, the social aspects of open source communities is very relevant to that target audience.
    - brighteyes 10y ago
      Social aspects matter, however, what the article does is talk about them from one very specific political position. It will look familiar and clear to people sharing that position, but it excludes others with a different political worldview.
sanderjd 10y ago
That wasn't ranting, it was cogent and well-structured and made good points. If you disagree with those points, say so, but don't diminish it by calling it a rant. I think those points are extremely relevant for an article targeted at people trying to get involved in open source. The for-pay vs. free-time divide is a fundamental problem with using open source work as an "in" to the industry, and despite being scoff-worthy to some people, it's helpful for people coming into this with fresh eyes (ie. the target audience of the article) to be given some context.
- brighteyes 10y ago
  It's that the points mentioned are the same old familiar points, and the arguments against them are also the same old familiar ones. For example, the article says "men have more privilege than women", based on the criteria provided, which are > 1. Who don’t have families to take care of (kids, parents, whatever) > 2. who have a good, steady income (i.e. not learning while, say, balancing two part-time jobs) > 3. who live close to work (minimizing a commute) And yes, women are more likely to have people to take care of. However, there are also reasons to say women are more privileged than men in this context. For example, 4. Are in college, as a lot of open source contributors are college students. Women are a lot more likely to get into college than men. 5. Are not in jail or prison. Women are far less likely to be in those situations. In other words, it is horribly simplistic to say "men have more privilege than women" in this context. It's just lazy regurgitating of the familiar talking points. It's not helpful. Yes, it's worth mentioning some people have an easier way into open source. But no, it's a bad idea to turn this into an oversimplified and false matter of "men > women".
  - sanderjd 10y ago
    Firstly, I was responding to the idea that this topic is irrelevant or orthogonal to the rest of the article - you don't seem to disagree with that, but rather disagree with the specific points that were made. Secondly, "the same old familiar points" assumes everyone has the same familiarity with the topic that you do, which of course isn't true in general, and the target audience of the article is actively people who are unlikely to have come across this.
gjm11 10y ago
Good news! That was at the end of the article, so you didn't miss things you might have been interested in. But the "ranting" isn't particularly ranty and has (it seems to me) a specific purpose: the author is concerned that some people reading his article might be discouraged from getting into open source software by the biases he describes, and wants to encourage them not to be. "But it can't stop you", he says: that's the point. So I think the author is deliberately making a tradeoff: by inserting that material, he hopes to encourage any readers he has from "less privileged" groups not to give up if things get difficult, even if it means that some people from "more privileged" groups who don't like reading about privilege and bias and codes and conduct are put off. Is it a good tradeoff? I dunno. It doesn't seem obviously bad.
- teacup50 10y ago
  It comes across as offensive and discouraging to those that believe that "intersectionality" is in itself discriminatory, both towards the racial/gender classifications being infantilized, and the racial/gender classifications who are assumed to be privileged. As an extension, the entire presumption of the necessity of a "code of conduct" is in itself "problematic", in that it ascribes problematic behavior to what are in fact welcoming, professional, pro-actively inclusive communities that simply do not accept at face value the discriminatory precepts (racial, gender, or otherwise) of intersectionality.
  - teacup50 10y ago
    The downvoting demonstrates exactly why the article's well-poisoning is offensive; the tautological ideology of intersectionality leaves no room for dissent in the marketplace of ideas, as any dissent merely proves the original premise of structural discrimination and privilege that applies to blunt categories of people on the basis of gender and race, and thus dissent is not to be considered an invitation to dialog, but damaging ignorance at best, "hate speech" at worst, and worthy of silencing regardless.
    - yoo1I 10y ago
      The marketplace of ideas just, rightly, rejected your elaborate but essentially baseless claim that anti-discrimination victimizes everyone who is not in the group being "de-victimized". It would be comical if it wasn't so sad.
WalterBright 10y ago
Having been into compilers for 40 years, I can confidently say that if you need validation, encouragement, support, etc., from others you're going into the wrong field. I'm a white male, and pretty much 100% of people told me I was not good enough to write a compiler, that I was sure to fail, that I could not possibly compete against Big Corporations, etc. The same goes for inventing a new programming language. Meanwhile, I've had a rewarding career doing it :-)

sebg 10y ago

Whenever compilers come up, this Steve Yegge article comes to mind -> http://steve-yegge.blogspot.com/2007/06/rich-programmer-food.html http://steve-yegge.blogspot.com/2007/06/rich-programmer-food... that starts: "Gentle, yet insistent executive summary: If you don't know how compilers work, then you don't know how computers work. If you're not 100% sure whether you know how compilers work, then you don't know how they work."

Kluny 10y ago
I saw it on the front page last week, actually. I suspect that's why this article got posted.
joe_the_user 10y ago
Gentle, yet insistent executive summary: If you don't know how compilers work, then you don't know how computers work. If you're not 100% sure whether you know how compilers work, then you don't know how they work. As opaque and arrogant as that sounds, the statement is actually fairly accurate. The way I'd try to put nicely is that compiler construction involves some conceptual barriers that make constructing an interpreter or compiler different than other programs, even other complex programs. The main difference is that a programming language is an abstract object on a different logical level than, say, a real world object. I think the best way to understand this is constructing a recursive descent parser. Doing requires one to transform the language you parsing and so get an idea of abstract languages. A lot of the advice people gives, such as using regular expressions, isn't a way to get a complete picture of what's happening in the parser or compiler construction process.

chrisseaton 10y ago

If anyone wants to get involved with an open source Ruby JIT compiler you can join us in #jruby or https://gitter.im/jruby/jruby https://gitter.im/jruby/jruby. Happy to tutor beginners.

jdc0589 10y ago

something about parsing text and generating something meaningful from it is just super gratifying; doesn't even have to be a full blown compiler. Some of most enjoyable programming experiences I have had were working on trivial parsing + transformation; e.g. a css beautifier, html beautifier, and whatever the hell this is https://github.com/jdc0589/jtranslate https://github.com/jdc0589/jtranslate (I wrote it in college, I still have no idea what I meant its purpose to be) I've done a couple things closer to full blown compilers (C-- compiler, hand written pascal subset compiler + one using a parser generator for the same language subset). As fun as those were, the simpler stuff was more enjoyable for me.

nojvek 10y ago
I 100% agree with this. Making a computer understand a domain of text and manipulate it in interesting ways is amazing. Similar is web crawlers. It feels like magic when the product works.
- jdc0589 10y ago
  hah, we have similar preferences for what we consider "fun". The last per project I worked on was basically the same as https://www.kimonolabs.com/ https://www.kimonolabs.com/, but with a different paradigm for writing crawlers/parsers (I hate wysiwyg/point+click interfaces for shit like this). THey launched their product when I was taking a break from mine, and implemented most of my feature set though :(

xigency 10y ago

These are definitely some interesting ideas on breaking into a new discipline. The little projects list is great and it's definitely good motivation to start improving skills. One problem I have with this article though, is not with the idea of becoming a wizard at something, which is a great way at looking at things, but rather the idea of joining a special group. Personally, I have a bit of an issue with using LLVM to get started. Maybe this isn't fair because I have literally no experience with LLVM outside of clang, but I think part of the idea of becoming a "wizard" means starting from scratch. Obviously, it's not helpful to point someone in the direction of impossible tasks to get them motivated, but the direction this heads quickly turns toward not becoming a leading independent thinker but becoming a mindless bug fixer on another project. I don't think you can learn to write compilers by fixing other people's bugs. It turns to: solving bugs, getting involved in open source, jumping on someone else's projects, and most of all projects where others are best suited to gain from the developments. It reminds me of the flowchart "Should I work for free?" which programmers should really pay attention to. It's great to work with others, to collaborate, and to appreciate and understand other's technology; however, computer science and programming are rather miraculous in the amount of distance an individual can travel on their own, and being forced to jump on a bandwagon or join a community seems to be demeaning in the end.

chrisseaton 10y ago
What are you suggesting then? Learning about how compilers work with no exposure to any existing compilers?
- lgas 10y ago
  I'm reminded me of the Sagan quote "If you wish to make apple pie from scratch, you must first create the universe".
- thwarted 10y ago
  In the Compiler Design class I took 20 years ago, we used the dragon book, which I found to be pretty accessible for someone who already knows how to program (at least in an academic setting). The only production (non-educational) compiler we had easily available source code for was gcc, which is not something appropriate for a beginner to learn compiler design and structure from.

prestonbriggs 10y ago

List seems inadequate. I guess it's enough to get you going working on compilers, but there's not much wizardly on that list. Read papers. Learn about data-flow analysis and optimization. Learn code generation (instruction selection, register allocation, instruction scheduling). Learn about interprocedural data-flow analysis. Learn/build a garbage collector or 2. Parallelization, vectorization, type analysis. Write an optimizer for Go. Write papers or your own.

xigency 10y ago
I'm not sure that the author cares very much about CPU registers.
- prestonbriggs 10y ago
  Sure he does... Anyone advocating for assembly language necessarily cares about registers.

UK-AL 10y ago

Much more useful to learn about constructing NFA/DFA automatons from 'pure' regular expressions, then say just knowing regular expression syntax off by art. This is basically gets you to understand regular grammar, probably the easiest formal grammar to understand. If you understand state machines, you know what you know what regular grammars are capable of. Where all the different types of parsing methods? Recursive Descent, LL Parsers, LR Parsers, LALR parser. Being able to understand production rules? Chomsky hierarchy of the formal grammars? Then converting that into AST -> Optimization(so much stuff here) -> Code emitter.

unimpressive 10y ago
Coursera/Stanford Online's compilers course covers all this. https://class.coursera.org/compilers/ https://class.coursera.org/compilers/

melling 10y ago

I've got a collection of resources on compilers and interpreters: https://github.com/melling/ComputerLanguages/blob/master/compilers.org https://github.com/melling/ComputerLanguages/blob/master/com...

codewritinfool 10y ago
Excellent resource, thank you!

tbirdz 10y ago

I left this comment on the author's page too, but I've copied it to HN as well: I'd also suggest learning and writing your own Forth. The Forth language is very simple to implement, simpler even than Lisp by a long ways, I'd say. If you know how to make a stack, (well two stacks), then you can make your own Forth Interpreter. Going from the Interpreter to the compiler is also easier than in other languages. There is not really much syntax to speak of, and most of the languages's features, even the comments, can be implemented in the language itself. Of course for speed reasons you'd probably want to put the langauge forms into highly optimized assembly forms or something, but you don't have to do that right away. There also isn't much of a runtime system to implement at all. With Lisp you'll have to write a garbage collector, with Forth, you just need to be able to allocate a slab of memory from the OS, maintain the stacks, and the word (like a function in another language) and variable dictionaries. Oh, and including a copy of the compiler to run in interactive mode, but you'd need to do that in Lisp too. Also, writing a Forth compiler lets you jump right into advanced optimizations. Really even just aggressive inlining and basic optimizations will get you a huge speed increase, which is a great motivational boost. The Reverse Polish Notation style stack form of the language is great for matching optimization patterns with as-is. I know SSA is pretty much THE technique to use for register based languages, but you can get great results from Forth by optimizing as is instead of converting to SSA. I really think Forth is a great language to learn compilers with. It really lets you skip ahead to the interesting parts of compilers, since the language doesn't require complicated parsers, or runtime systems.

prestonbriggs 10y ago
I disagree. Forth is cute and you'll learn some stuff, but you won't become a compiler wizard. You _need_ to learn how to do parsers and run-time systems and all the rest. Besides, it's fun!
- tbirdz 10y ago
  I see what you're saying, but respectfully I disagree. The importance of parsers and run-time systems in compilers really depends on the language you are compiling. There's a big spectrum there. For runtime systems, on one hand you have languages where they are very important, such as runtime garbage collectors in Lisp, Java, and similar languages, Prolog's runtime logic backtracking, runtime exception support for C++ but no garbage collection, down to languages like C with no garbage collection and minimal runtime. Forth is certainly on the lower end of the compiler runtime implementation spectrum. For parsing, there's a similar spectrum. There's languages with hideously complicated grammars, like C++, less complex ones like Lisp, and probably again on the simplest end of the spectrum is Forth. So the requirement of needing to learn to write complex parsers and runtime systems is dependant on the language. I'd certainly classify a C compiler author as a "wizard" even though they wouldn't have to write a garbage collector for their C compiler, and a Lisp compiler author as a "wizard" even though their parser is much less difficult to create than a C++ language parser. Of course, it's not like wizard is an exact term or anything. If you're saying a "compiler wizard" should be able to understand how to implement any language, then of course you need to have in-depth knowledge of parsers and run-time systems. Me personally, I'd say if you can write a compiler for any language you're somewhere on the compiler magician spectrum. Maybe not full wizard, but at least a compiler warlock or enchanter or something (this is getting silly now, I don't really want to argue about the semantics of the term wizard applied to compilers).

ori_b 10y ago

This is... rather awful. I'd suggest taking a look at the reading list here instead: http://c9x.me/compile/bib/ http://c9x.me/compile/bib/ This article goes through a number of unrelated exercises, mentions a few hello-world level introductions, and then skips to a more or less unrelated introduction to open source, with a rather bizarre criticism of people who contribute to open source without getting paid for it. If it was written for 'becoming a C wizard', I would imagine that it would read something along the lines of: - Say 'hello' a few times - Write some words on paper - type 'print "hello"' into a python prompt - Work through the "hello world" program in K&R - You're a terrible person if you learn C without getting paid.

joe_the_user 10y ago
Yes, In fact, it's even worse than that. You can become one kind of "C wizard" just by writing a bunch of programs since a lot of programming is fairly clear once someone understands function calls and for-loops. But understand compiler construction at a reasonable level requires some specific set of skills that don't come from just messing around.
Joof 10y ago
Your link seems pretty good. SSA, dominators, register allocation (utilizing chordal graphs / SSA I hope). Constant propagation. Optimizations AND parsing.

WalterBright 10y ago

An article I wrote on the same subject: https://www.digitalmars.com/articles/b89.html https://www.digitalmars.com/articles/b89.html

ori_b 10y ago
You may want to update your certificates -- Chrome complains when I try to view the page.
- WalterBright 10y ago
  Yeah, I need to do that. For the moment, use this instead: http://www.digitalmars.com/articles/b89.html http://www.digitalmars.com/articles/b89.html