So You Want to Be a Compiler Wizard
belkadan.com
belkadan.com
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.
Besides, it's fun!
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).
Nothing stops you from starting with a language that makes some aspects simpler then average (such as Forth or Scheme), before working on a compiler for a language that does require such things.
Or the succinct version, learn to walk before you run.
Indeed, I'd argue that Forth is best appreciated after you've worked on other compilers for a while. Then you have a basis to appreciate how clever it is.
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.
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.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.
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.
What seems totally useless, though, is to fix bugs! Compiler writing is a very high level field. Fixing bugs on a database server provides equal experience to fixing bugs on a compiler to compiler writing: which is being able to write bug-free code in the given language. So it seems the author is trying to advertise for free labor.
Also, in the first example
Learn regular expressions. This isn’t ... how real compilers work, but regular expressions...
The best advice, which isn't given here, is to read! There are many, many great resources on all of the ins-and-outs of front end, backend, optimization and all the other facets of compiler writing, and there are very few new ideas. Most of the research dates from the 60's and 70's. It's better to be well read on compilers than to have actually written one, depending on the circumstance.
Also, many people always ask for resources on compiler writing, but if you spend even a little time looking for books you will find tons.
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
See the implementation of interpolate in my Assembly-like language: 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
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.
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.
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.
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".
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.
--
On privilege:
I completely disagree with the necessity of being engaged in a community to be a compiler developer or to learn any CS domain.
But stating that free time is a privilege is a bit absurd. You could be a 23-hour a day gardener and still write a compiler. It's not as if there's a time limit.
Dividing by gender is ridiculous---the first computer programmer was a woman.
All that it takes to become a compiler enthusiast is the understanding of languages and computers. Having a pencil and paper is a plus.
Alan Turing was gay but it didn't prevent him from inventing a form of universal computer.
People should be celebrated for their differences, not admonished for not having enough outlying characteristics.
Remember, the first programmers had neither computers nor compilers, and the first compiler writers had punch cards, so who exactly is privileged?
So the discussion of privilege shouldn't necessarily be seen as a negative force trying to tear down white men, but should inform our decision making when we take other people's hardships into account. As a white male myself I understand that I have had better opportunities than a large part of the population. I'd rather take that into account and try to improve the fairness in society, than to look away from it. What to actually do about it is another matter... But acknowledging that it's a problem is the first step.
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.
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.
It would be comical if it wasn't so sad.
Beyond that, I cannot refute an argument when none was presented.
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 :-)
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.
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 (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.
It feels like magic when the product works.
https://github.com/melling/ComputerLanguages/blob/master/com...