CS143: Compilers (2011)
keithschwarz.com
keithschwarz.com
It is an amazing archive of all kinds of neat algorithms and data structures.
The course was video-recorded and I downloaded and saved most of the lectures (and I gave Keith a DVD with a copy of them.) I still have them, but I don't know if it's okay to put them on YouTube or not.
This midterm exam is open-book, open-note, open-computer, but closed-network. This means that if you want to have your laptop with you when you take the exam, that's perfectly fine, but you must not use a network connection. You should only use your computer to look at notes you've downloaded from online in advance. If you are an SCPD student, you should take this exam in any two-hour period between 11:00 AM Pacific time, July 20 and 11:00 AM Pacific time, July 21 . If you have any questions, please feel free to call me at _ any time in this window except between midnight and 8AM on July 21, Pacific time. You may submit the exam either by faxing it to _ or by scanning and emailing it
I'm not familiar with how these things work in the US - are the students trusted to take the exam away and not use the internet to get help?
"The faculty on its part manifests its confidence in the honor of its students by refraining from proctoring examinations and from taking unusual and unreasonable precautions to prevent the forms of dishonesty mentioned above."
https://communitystandards.stanford.edu/student-conduct-proc...
A professor or grad student walks into the room every 30 minutes or so just to make sure everything looks okay. They otherwise sit outside the exam hall so you can ask them questions, ask to go the bathroom, etc. But it's up to the students to police each other and ultimately themselves.
There are definitely other universities in the US that have this policy, but I would say it's more the exception than the norm.
The exception to this was programming exams for which the department would boot all the lab workstations into a locked-down mode with no internet & new homedir containing only the exam files. At the end of the exam everything got collected and marked by an automated test suite.
They went to quite some effort to ensure that no cheating could take place - http://pubs.doc.ic.ac.uk/Lexis/Lexis.pdf
https://github.com/melling/ComputerLanguages/blob/master/com...
I'll add more as they are posted.
I was lucky enough to buy a used copy on amazon for $8.
http://www.amazon.com/Compiler-Construction-Principles-Kenne...
http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf
It is a very instructive process.
I'm terribly sorry to break the news for you, but no, compilers are not about parsing. Nowhere near that.
There is a followup course, CS243 which focuses on the optimization aspect.
There is another dimension to this. While code gen and optimisations are more interesting than lexing/parsing almost no student will ever again write a code generator, let alone optimisations. OTOH, most programmers need to write little lexers and little parsers for little languages all the time. That's why a bit of facility with lexing/parsing and associated tools is hightly useful.
Incidentally, Scheme has a syntax too, so you need lexing and parsing to handle Scheme. The only advantage is that Scheme's syntax is simple.
Moreover the problem of language representation doesn't go away. You still need to represent programs. The real problem is to understand that there are two level: programs and representations of programs. Avoiding to confuse the two is the real challenge, and it remains a challenge in Scheme.
> Then my students would have been puzzled by Scheme, which they don't know.
Maybe they're not ready for a compilers course then? You could have saved a lot of time and effort for them this way.
> Incidentally, Scheme has a syntax too, so you need lexing and parsing to handle Scheme.
It can have as much syntax as you want. Nobody cares - there is already a parser, ready to use, and you don't have to roll out your own.
> The real problem is to understand that there are two level: programs and representations of programs.
This is the most important takeaway from a compilers course. It makes sense to get there as soon as possible.
Also, I'm a bit skeptical about your assessment of your students, from your words it sounds like you're teaching in a lunatics asylum.
> https://news.ycombinator.com/reply?id=11281976
> you need a platform independent memory model
Sorry, this is a wishful thinking.
A truly efficient concurrent language is always very much platform-specific (think of Occam on one side of the spectrum and OpenCL and Cuda on another).
> nobody really knows what exactly the memory model is
Really? I've seen a number of Coq/HOL/ACL2 precise memory models of certain architectures.
> https://news.ycombinator.com/reply?id=11282014
> idealised compilers have a beautiful pipeline structure
A very practical compiler can also be built as a beautiful and simple pipeline.
> By this reasoning, any computable problem is trivially simple, because I can translate it into ARM/x86/MIPS/... machine code, and machine code is just a linear list of trivial commands, i.e. I can "turn it into a laughably simple chain".
You did not get it at all.
You cannot translate "any code" into a linear trivial sequence with each step being nothing but some primitive form of term rewriting of a single input tree into a single output tree.
A trivial proof for how badly wrong you are: you do not need a Turing-complete language to write a compiler. Now try to apply this to your "any computable problem" reasoning.
> if you chain enough simple things, the result stops being simple.
Incorrect. Such a chain is as simple as its most complex building block. Complexity does not add up.
> Look for example at modern JIT compilers, tracing or otherwise.
Firstly, we're talking about the proper compilers here. JIT is a totally different beast, it got a very severe performance constraint.
Secondly, even JIT can be structured this way, and most of the existing JITs are idiotically, needlessly overcomplicated.
> They are not simple by any stretch of the imagination.
Sorry, but no, they are.
Yes, the non-Turing-complete property breaks there, as well as with any other interpreter, but a Turing-complete subset of a JIT compiler can be very easily isolated.
> https://news.ycombinator.com/reply?id=11279390
> Optimisations are easy only if you can accept the optimisation process to be slow, and/or the resulting code buggy.
And this is nothing but a FUD.
Firstly, nanopass compilers are not any slower than the fused ones. In some cases they're faster, due to some of the nice properties of the immutability. Also, you can fuse some passes automatically, while still keeping your code trivial.
Secondly, the simpler your passes are, the easier it is to reason about their correctness. Compare it to the notoriously shitty instcombine pass in LLVM, as it is an example of the opposite approach (the one you're apparently advocating).
I, too, can't post as many messages as I'd like. Not sure why, or how to change it, or how even to see if there's some limit imposed on me. Maybe < 1000 rep users are throttled?
> Maybe they're not ready for a compilers course then?
We've been teaching compilers to 2nd years ever since the department was founded as far as I'm aware. The 2nd year is the right time to see how the programmer's most important tool works.
> you don't have to roll out your own.
I want students to write their own lexer and parser, and familiarise themselves with lexer/parser generators. This is an important part of a programmer's education. First, it let's them see the purpose of all that formal language theory they had to do in the first year. Second, and more important, working programmers have to design languages and write lexers/parsers all the time. A lot of commercial programming is about transforming data from one representation to another. In contrast, few programmers will ever write a real code generator.
> you're teaching in a lunatics asylum
I teach at a large, well-known and decidedly mediocre university. The kind of place that most working programmers graduate from. Needless to say that this is perfectly compatible with being a lunatics asylum.
> truly efficient concurrent language is always very much > platform-specific
Sure, but so what? That's like saying for truly efficient concurrent programming you need to program in assembly, because that's the only way to exploit all platform specific trickery.
The purpose of high-level languages is to abstract away from the target platform. The additional goal of languages like C is to abstract as little as possible, so as to be platform independent while still allowing fast executables.
In practise compilers for high-performance languages like C/C++ and Rust need to balance 3 contradictory goals.
- Platform independence. - Fast executables. - Low cost of compiler development and evolution.
Note that optimisations are by far the most expensive part of a compiler. Memory models are used in this balance: you want MMs that are platform agnostic, while still enabling powerful compiler optimisations. The CPU vendor has two more objectives (which is closely related to platform agnosticism):
- Not giving away too many CPU internals. - Allowing CPU evolution.
> Coq/HOL/ACL2 precise memory models
Are they low-level models of CPUs that can also be used to reason about read/write reordering? Or are they genuine memory models, coming from the CPU manufacturers?
As far as I'm aware, the construction of memory models these days is an empirical science like zoology, where people run experiments to confirm hypotheses about CPU behaviour. See eg. [1]
> A very practical compiler can also be built as a beautiful and simple pipeline.
Yes, and GHC is probably an example of this. But GHC is not simple by any stretch of the imagination.
M Odersky once gave a talk (sorry, no reference handy) where he said that scalac, the Scala compiler, is no longer a pipeline, but has a database structure. That's because scalac's many stages cannot just live on the data feed by the immediate preceeding stage, and need to go back serveral stages sometime. Interesting.
> you do not need a Turing-complete language to write a compiler.
Type checking / inference in Haskell, Scala and C++ (among others) is Turing complete. Haskell's compile-time meta-programming extension Template Haskell, or scala.meta allow you to perform arbitrary computations as part of the code generation process, and do so by recursively invoking itself.
On top of this, the control of a Turing machine is a finite state automata. So it's very simple too.
Finally, I don't see the significance of Turing completeness here. You can write highly complicated programs in small fragments of Turing complete languages (e.g. Calculus of Constructions). This is the point of "Total Functional Programming" [2]. Indeed almost everything the typical working programmer writes is primitive recursive. Why do we have Turing complete programming languages? Because using just primitive recursion is really inconvenient. Try writing a trivial 4-line program like the ancient algorithm computing the greatest common denominator using just primitive recursion [3]. It's already annoying. So unrestricted recursion is a convenience, making programs more readable and shorter. Imagine you had to write type inferencers, graph-colouring based register allocators or program analyses based on fix-point iteration using just primitive recursion. Ugh!
> some primitive form of term rewriting of a single input tree into a single output tree.
Term rewriting is Turing complete. So yes, you can transform any compiler into a term rewriting system. So what? If you transform a sophisticated, industrial-strength compiler like GHC or scalac into a TRS, you end up with a very complex TRS that is difficult to understand. You cannot hide intrinsic complexity. You can kick the can down the road, and change the form in which the complexity manifests itself.
> Such a chain is as simple as its most complex building block.
Consider the Turing complete language {S, K} of combinators. By your reasoning any program written as SK combinators should be simple, because the building block are trivial.
> JIT is a totally different beast
Not really. In a way, JITs are simpler than AOTs in that the optimisations they run are simpler (eg register alloc by linear scan rather than graph colouring), and tracing JIT optimisations are simpler still since they traces they work on have linear control flow, which drastically simplifies the optimisation. Indeed that's the point of traces. The main complication of JITs is the seamless switching between interpretation and execution of compiled fragments.
> existing JITs are idiotically, needlessly overcomplicated.
Extraordinary claims require extraordinary evidence.
The JIT teams at Oracle, Google, or Microsoft would like to hear from you if you can lower the cost of JIT compiler construction.
> nanopass compilers are ...
I have nothing against nano-pass compilers, and using a lot of immutable datastructures is fine. IIRC ocamlopt is heavily based on immutability, and it's one of the fastest compilers around. Whether nanopass is better for formal reasoning about compiler correctness remains to be seen. In formal reasoning it doesn't actually matter that much if information is passed explicitly by argument, or is global state, since either way, your logic has to keep track of it.
But whether nano- or otherwise, the complexity is intrinsic in the problem of compilation, which is about bridging the semantic gap between two languages. And the bigger the semantic gap, the more complicated the task.
[1] J. Alglave et al., Herding cats: Modelling, Simulation, Testing, and Data-mining for Weak Memory. http://www0.cs.ucl.ac.uk/staff/J.Alglave/papers/toplas14.pdf
[2] D. A. Turner, Total Functional Programming. http://sblp2004.ic.uff.br/papers/turner.pdf
[3] R. Harper, Old neglected theorems are still theorems. https://existentialtype.wordpress.com/2014/03/20/old-neglect...
I see... Yes, I'we been exposed to the quality of the intake of the so-called "new" universities (in the UK). Just did not think they're learning anything beyond Excel.
> I want students to write their own lexer and parser, and familiarise themselves with lexer/parser generators. This is an important part of a programmer's education.
I agree. It should follow the compilers course, once everything of importance there is properly absorbed.
> In contrast, few programmers will ever write a real code generator.
And this is where I cannot agree at all. I believe that everyone must build multiple compilers, routinely, on a daily basis.
The reason to think so is:
1) DSLs are an ultimate answer to a complexity problem. And compilation is the best way to implement them easily.
2) Compilers are often present in where you won't even expect to find anything like a compilation. Protocols, UIs, business logic, databases, whatever. And, given the property of a compiler that it can be reduced to a tiny complexity (we'll get back to it later), it is extremely important to be able to spot such patterns early and convert your architecture to a compiler.
And, of course, all such incidental compilers got absolutely nothing to do with any kind of a parsing. Their source languages are already some data structures (even graphs), almost never a plain boring stream of characters.
> The purpose of high-level languages is to abstract away from the target platform.
Impossible if your target platforms concurrency models are incompatible. You cannot fit message passing into a SPMD, and vice versa.
> Note that optimisations are by far the most expensive part of a compiler.
Not necessarily. For C++, for example, all the optimisations, even with a polyhedral vectorisation, abstract interpretation, partial specialisation and all the bells and whistles, are nothing compared to a mere template expansion. See the clang+llvm profiling data.
> Or are they genuine memory models, coming from the CPU manufacturers?
Not "coming" anywhere, unfortunately. They're all internal models. Not available even under an NDA.
> But GHC is not simple by any stretch of the imagination.
It got quite a few gotchas, to be honest. I'd definitely design it differently. And, Haskell is not the best language for this sort of things - see the "expression problem". A Scrap Your Boilerplate library is sort of fixing part of these issues, but it is not used inside GHC.
> That's because scalac's many stages cannot just live on the data feed by the immediate preceeding stage, and need to go back serveral stages sometime. Interesting.
It is exceptionally over-engineered. But, yes, there is a reason to have a backtracking in a compiler pipeline. While still having a linear pipeline (at the end of the day it is linear, but it may be branching and going back to try out certain hypothesis). I've been experimenting with this approach a lot. It does not increase complexity in any way.
> Type checking / inference in Haskell, Scala and C++ (among others) is Turing complete.
Firstly, for most of your DSLs you don't need such a type system. Secondly, all the implementations I've seen are extremely overengineered, and I've got no idea why.
In fact, any Hindley-Milner like type system is laughably trivial, and the Turing-complete part of it is very much isolated (and you don't have to code it, just use an existing library). Hindley-Milner unification is not any different from Prolog unification, so my way of implementing these type systems is to simply compile your AST into a flat list of Prolog equations (see the recent history of my posts for this method explained in depth).
> So it's very simple too.
It's not. You cannot reason about it.
> This is the point of "Total Functional Programming"
Exactly. You don't need anything beyond a simple total language for your entire compiler (or, if you're implementing some metaprogramming, abstract interpretation or a Turing-complete type system, a 99.99% of your compiler, with the rest being well-isolated and reused over and over again).
> Term rewriting is Turing complete.
You only need a subset of term rewriting, which you can express in a total language.
> In a way, JITs are simpler than AOTs in that the optimisations they run are simpler
Yet, they're interpreters, especially the tracing ones. And interpreters are inherently orders of magnitude more complex than compilers.
> By your reasoning any program written as SK combinators should be simple, because the building block are trivial.
Not really. You're combining them in a deep, horrible tree, not a linear pipeline of isolated things.
> Extraordinary claims require extraordinary evidence.
I do not see anything extraordinary in an obvious notion of corporate coding being thoroughly broken. It's a common knowledge.
> In formal reasoning it doesn't actually matter that much if information is passed explicitly by argument, or is global state, since either way, your logic has to keep track of it.
It matters. If all you have is a language as an input and another language as an output, without any global state, then every chunk of your pipeline is isolated and you can comprehend it without thinking about the rest. That's exactly why the complexity of the passes do not add up, and the total complexity is only a complexity of the worst of the passes.
> the complexity is intrinsic in the problem of compilation
I've never seen anything complex there. After over 20 years in the field.
> which is about bridging the semantic gap between two languages.
It's not a chasm, you don't have to cross it in one step. Just build a hundred of trivial passes in between, one step at a time.
> And the bigger the semantic gap, the more complicated the task.
No, complexity do not grow. Mind giving an example of the opposite?
P.S. Also, one of the nice properties of the compilers is that you can abstract out and reuse a lot of routine stuff. Register allocation? Write it once and reuse everywhere. SSA? Implement it once and reuse for any imaginable IR. Typing? See above. Constant folding, ADCE, inlining, etc? Write it once and reuse for all the possible IRs.
compilers are easy
Modern, industrial-strength compilers are some of the most complicated pieces of technology we have.
Indeed almost every part of the compiler pipeline, in particular parsing, type-inference, and optimisations, are active areas of research.
So, I'd say the industrial ones are as tough as they are because they support hard-to-compile languages with many dark corners while bring implemented in the same languages themselves. Make problem hard for yourself then it's hard. Make it easier then it's... still work but only a tiny fraction of what you alluded to.
And optimizations don't even matter anyway. x86 runs your -O1 program as fast as your -O3, and nobody has put a real accurate model of an x86 into a production compiler for the last decade.
nobody has put a real accurate
model of an x86
Optimisations for parallel processing, e.g. auto-parallelisation are not well developed either.
There are actually numerous performance counters exposed by the CPU too, which are good for dynamic benchmarking, but hardly anyone cares to use them.
BTW, even though the ALU part of the CPU is extremely wide and dynamic, you still have to fit your instructions through the x86 decoder at the front, and it's worth writing a scheduler just to model that part.
I understand that they need to keep the low level details of their CPU secret, but a memory model? All it says is when/how reads and write commute. If a CPU manufacturer were to provide a nice, high-level memory model, this would make the CPU more sellable. Why? Because compiler writers could more aggressively optimise when compiling for the CPU.
I suspect that the reason they don't give out memory models is that they don't know how to do it. That's also the vibe I've been getting when I talked to people who would know.
Of course the language designer can always play it safe and choose a ridiculous memory model like sequential consistency, but that prevents many useful compiler optimisations. At the other extreme you could explicitly state that the memory model is a specific processor, but then
(a) the language becomes too platform dependent and program semantics will change with every processor upgrade.
(b) nobody really knows what exactly the memory model is in any meaningful sense because even the manufacturers don't know (other than saying: it is what the CPU does). That means the semantics of the language is unclear.
What you want is something between the Scylla of inefficiency and the Charybdis of platform dependence. This is a difficult problem, and unsolved even for as simple a language as C, see e.g. [1]. Indeed it is unclear if memory models possessing the required attributes even exist, maybe it's contradictory to assume that they can.
[1] M. Batty et al., The Problem of Programming Language Concurrency Semantics. https://www.cl.cam.ac.uk/~jp622/the_problem_of_programming_l...
If the entire thing is "complicated" (although it should not be), it can still be broken into a chain of laughably trivial passes. This is the most beautiful property of the compilers - an ability to break down complexity all the way down to trivial.
If you do not agree for some reason just name a part of a compiler you perceive as inherently complex, and I will show you how to turn it into a laughably simple chain.
turn it into a laughably simple chain.
My point is: if you chain enough simple things, the result stops being simple.
Look for example at modern JIT compilers, tracing or otherwise. They are not simple by any stretch of the imagination. To see that just look at a program, and predict how long the warm-up will take. Whoops ... unknown [1].
[1] E. Barrett et al., Virtual Machine Warmup Blows Hot and Cold. http://arxiv.org/abs/1602.00602
And backend is not just about optimisations, they're mostly insig igicant. Backend is about translating gradually one semantics to the other. An example of such is compiling a regular expression into a DFA and then a C array and a switch.
(Also, real parsers tend to be hand-written, judging from open source language implementations (some have actually migrated from generated parsers to recursive descent in the past). There must be a reason).
Thanks for pointing to PEGs. I will definitely try them out. But judging from a quick web search, it's obvious that there are perfectly valid reasons not to use a PEG grammar today -- unless someone already designed the grammar for you (and it's PEG!). http://lambda-the-ultimate.org/node/3039#comment-44356 http://stackoverflow.com/questions/1857022/limitations-of-pe...
Those of us who care about syntax (that is optimized for the user, not the programmer), will have to keep thinking about parsers for the foreseeable future.
And, no, there is no single reason not to use PEG. Especially when the choice is between a handwritten parser and a PEG. There is a lot of stupid FUD about PEGs, you should ignore it. Your links are pointing to the ignorant, incompetent mumbling of those who never tried implementing a proper PEG.
And I never met a language for which writing a PEG parser was not totally trivial. A pro tip: use PEG alongside with a Pratt for the binary expressions.
It's absolutely not uncommon for architecture experts to plug into the optimization stage of an existing compiler; expecting them to understand the first stages is not useful at all. They need to understand the AST / IR, but not how to arrive at it.
I actually think many useful languages are mostly syntax. If you compile to another source language (like C or SQL) you might not need much optimization.
Parsing some syntaxes is difficult but that doesn't imply we should just ignore it and let libraries handle everything. Thinking about parsing is an opportunity to learn about tradeoffs and to develop a good taste designing syntaxes which are easy to parse (and, possibly correlated, manipulate) both for computers and humans.
Parsing in most cases should either be trivial, or can be skipped altogether.
How come that they are still teaching only yacc/lex as parsing generators in 2016?!
Niklaus Wirth would probably agree.