[HN Gopher] Why take a compiler course? (2010)
___________________________________________________________________
Why take a compiler course? (2010)
Author : signa11
Score : 156 points
Date : 2023-03-24 05:52 UTC (1 days ago)
(HTM) web link (blog.regehr.org)
(TXT) w3m dump (blog.regehr.org)
| yeetaway1111 wrote:
| It will teach most of the good programming and software
| engineering practices that apply to any nearly any project.
| AstixAndBelix wrote:
| >why the hell should I take an electromagnetism course as a
| physics undergrad? I want to work in fluid dynamics dammit!
|
| unfortunately there are too many people who think a CS curriculum
| should be an advanced coding bootcamp instead of a place where
| you actually explore how your software works
| ramg wrote:
| We use gcc/javac/etc almost daily and having some understanding
| of what your toolchain is likely to be very beneficial. Here are
| a few things I've done with my compiler knowledge:
|
| 1. Wrote a simulator of sorts for a 68xx CPU. User passed in
| assembly files and I simulated the execution and spat out cycle
| counts. The real-time application had a fixed time window it
| could not exceed. I did this in my first year out of college with
| compilers fresh on my mind.
|
| 2. Wrote an automated test tool for a proprietary protocol. The
| protocol had the usual opcodes but they could only be played in a
| certain order (cannot send B before C or can send B any number of
| times and have it be idempotent). The QA engineers were doing
| this by hand. I asked them if they could automated the test case
| generation and they looked at me as though I was an idiot. I
| developed a tool with its own simplified grammar that they could
| use to build test cases which exercised all
| combinations/permutations of the opcodes. Saved us a ton of time
| and made the developers more productive.
|
| 3. My hackiest project was an SGML parser that was used to
| generate hypertext documents. Tech writer wrote docs in
| FrameMaker. My hacky parser found the places where the TOC and
| the Index could be linked and inserted hypertext links. Net
| result is we had a document that could be printed and viewed
| online. Think 1993/1994.
|
| I've sat with a number of engineers who thought the compiler was
| wrong and sat down and looked at the assembly with them and
| mapped it back to C only for them to realize the bug was in their
| code.
|
| Compilers are fun. You should take a compiler course just for
| that!
| saghm wrote:
| Despite the fact that my algorithms course was ostensibly about
| learning how to come up with efficient solutions to various
| problems, the two courses I took that have helped me the most
| with writing performant code in my career were my compilers
| course and my architecture course. The compilers course gave me a
| much stronger understanding of what actually happens when running
| a line of code I wrote and helped me understand better what types
| of optimizations could potentially be performed based on the way
| I write an algorithm, and the architecture course taught me about
| how a modern CPU actually works with regards to caching, out-of-
| order processing, branch prediction, etc.
|
| On the other hand, the types of things we discussed in my
| algorithms course felt very hit-or-miss with regards to whether
| they actually felt useful or not. I'm not just talking about
| high-level abstractions that can miss important details in the
| real world like "memory can be accessed in constant time" either,
| but solving problems that were so contrived to the point of being
| almost implausible. The example I always remember is that in one
| of our problems sets, we were asked to write an algorithm that
| sorted an array of size N with each element within K indices of
| the correct sorted position in O(n*log(k)) time. I can't think of
| any situation where I'd have data so large with a small enough
| strict upper bound on K that such an algorithm would be
| necessary, but even if I did find myself in that situation,
| that's the exact type of input that the naive quicksort
| implementation would perform more efficiently on!
|
| Maybe someday we'll have powerful enough tools that we can
| generate code that's performant without needing to do it
| ourselves, but at least for now, writing code that a computer
| executes efficiently is much easier when you actually understand
| what's being run on the computer and how it runs it, and a
| compilers course is a great way to start learning about the first
| half of that.
| WalterBright wrote:
| While one may not be interested in writing compilers, the
| techniques are applicable elsewhere.
|
| For example, I once wrote a date/time "compiler" that could read
| dates and times in various human formats and construct a time_t
| from it. It's a giant mess if you approach it in an ad-hoc
| fashion. But if you approach it from a lexing then parsing
| standpoint, things work a lot better.
|
| I see too many attempts at reading a textual data format that are
| done ad-hoc. Even worse are the attempts to _design_ a data
| format where the designer clearly had no awareness of lexing and
| parsing - the format is just one ad-hoc kludge after another.
| agiacalone wrote:
| Uni CS lecturer here. One of my mentors in grad school was the
| compiler professor, and I learned a lot from him. I also got a
| chance to actually teach compilers for the fist time last year
| and it was one of the most difficult courses I have ever taught.
| Used the dragon book and had my students create their own
| lexer/parser based on an invented language that I came up with.
|
| Compilers is one of the few topics that none of my colleagues
| seem care about, but IMHO it's so very important to learn how to
| do. In my Uni, the course only gets taught once every few years
| (it didn't help that our last department chair didn't care for
| the course at all and never scheduled it).
|
| I count the day that I finished my LL(1) parser and lexer for my
| own compiler course as a student as the day I "earned" my chops.
|
| Edit: Since there seems to be some discussion on this thread,
| I'll throw in the actual project that I gave my students (warts
| and all). https://github.com/agiacalone/cecs-444-semester-project
| ethicalsmacker wrote:
| Most never "earn their chops" in a traditional sense. These
| days, it would seem earning your chops is done by running
| create react app, cobbling together several dozen random
| javascript libraries and putting out a laughably designed
| website in a few days.
| havblue wrote:
| The Georgia Tech cs2130 class, languages and translation, the
| third required cs class for the major, was notorious as being
| a weeder course around 1999. The professor made it clear that
| there would be no partial credit for code that could be core
| dumped by the teaching assistants. If you weren't good at the
| class you should probably look forward to writing business
| applications for IBM, allegedly. So some people used to be
| hardcore on this subject.
| agiacalone wrote:
| We have a similar course too which focuses specifically on
| language design without the compiler part (they do get a
| bit of compiler theory) which satisfies that "requirement"
| for graduation. It is much more popular than the compiler
| course which is perceived as "harder" (it probably _is_
| when I teach it). ;)
| fsckboy wrote:
| when I use those sites I think, in a very traditional sense
| (the French Revolution and the Reign of Terror), "oooh,
| they've earned their chops!"
| vram22 wrote:
| Veering a bit more off-topic:
|
| - La Guillotine
|
| - Madame Defarge and friends
|
| - etc.
|
| from A Tale of Two Cities.
|
| IIRC (may be wrong, read as a kid), those ladies used to
| signal which aristocrats should be chopped vs. not, by
| signalling with their knitting needles, or a nod or shake
| of the head, or some such - while sitting in the front row
| before the guillotine.
|
| Ghoulish. Of course, as a kid, you (I) lap up and relish
| that stuff, like breakfast cereal.
|
| Edit: Links:
|
| https://en.m.wikipedia.org/wiki/Madame_Defarge
|
| https://en.m.wikipedia.org/wiki/A_Tale_of_Two_Cities
|
| Wow, I did not know before just now seeing the Wikipedia
| article above, that, to quote it:
|
| [ As Dickens's best-known work of historical fiction, A
| Tale of Two Cities is said to be one of the best-selling
| novels of all time. ]
| skitter wrote:
| I'm curious, why focus entirely on parsing? I only read parts
| of the Dragon Book, but it didn't go in much detail about other
| topics, such as types, either. Couldn't you just use a very
| simple syntax such as S-expressions or even start from an AST
| directly?
| mathisfun123 wrote:
| people hyperfocus on parsing because it's far and away the
| easiest part of a compiler - type inference, optimization,
| target codegen are infinitely harder and deeper wells to
| plumb.
| murdoze wrote:
| FORTH ;)
| agiacalone wrote:
| A few reasons, although you are only seeing part of the
| picture with the project. The lectures were all theory-based
| (more along what you would find in the book).
|
| 1. I had a whopping _three weeks_ to prepare this course from
| scratch (welcome to Uni teaching) and it was what I could
| scrape together in that time.
|
| 2. Parsing is highly useful, and I felt my students could
| benefit from it.
|
| 3. It was what I did in undergrad.
|
| 4. It was not _too_ difficult to accomplish, and a project
| like this can easily get out of hand for a semester project.
| markus_zhang wrote:
| I agree with you that parsing, for most people, or even
| most software engineering people, are much more useful then
| the other stages. Code generation is also interesting and
| could be useful too but that's pretty much the two of them.
| All the "interesting" stuffs people spoke about (e.g.
| optimization) actually has very few use cases unless you
| are working on it directly.
| anta40 wrote:
| From a practical standpoint, compiler dev job is very nice-ish,
| not typically in high demand, like developing mobile or web
| apps.
|
| But that's what us, software developers, relied to. No compiler
| means no app.
|
| Which means some folks gotta maintain the GCC, Go, FPC, etc
| etc...
| einpoklum wrote:
| My two answers - based also on personal experience - would be:
|
| 1. If you are ever concerned with code performance, you need to
| know what the compiler (/interpreter) is doing with your code.
| With a compiler course, you'll get a basic understanding - enough
| to later actually look at what the compiler is doing with your
| real-life code.
|
| 2. If you write a software system which can handle computation
| tasks that are not fully known at compile-time - such as user
| queries in some domain-specific language - then you are likely to
| end up implementing a compiler in your software system. If you
| haven't learned about compilers, you'll (a.) may fail to realize
| that and (b.) are likely to do it more poorly than if you have.
|
| ---
|
| My beef with compiler courses, though, is the excessive focus on
| parsing. Text parsing, look-ahead grammars etc may be interesting
| in themselves, but IMHO they're mostly self-contained and not
| what you will be concerned with in the life-scenarios I've
| described above. I would have liked, in hindsight, to have more
| time devoted to optimization selection, passes and what goes in
| each of them, optimization work on the AST vs work on the IR etc.
| pyrolistical wrote:
| Compilers also show an application of pipelines which can be used
| architecturally at all levels.
|
| I'm a happy coder if I can translate my problem to a pipeline
| problem. Each pipeline step can be modelled as a pure function.
| Each artifact between each step can be inspected and cached.
| Pipeline failures can be resumed at the last valid artifact
| saagarjha wrote:
| IMO compilers are a bit like kernel development in that the real
| learning was the friends you made along the way, rather than
| actually being able to understand how a compiler works, which is
| a nice side effect. For example, when you write an OS you learn a
| lot about how code interfaces with hardware. A compiler is many
| people's first and only introduction to soundness and formal
| analysis. Being able to put on the hat of a compiler author can
| be useful in many fields that have nothing to with compiler
| development, and that's even if you go beyond "I just want to see
| what my code is being transformed into".
| UltimateEdge wrote:
| As a Mathematics undergraduate I am not allowed by my university
| to officially take (and receive credit for taking) most non-
| beginner Computer Science courses, including Compilers. At least
| I'm allowed to attend the lectures and cram it in alongside my
| other pure math classes!
| epgui wrote:
| Good on you for being more academically-minded than your
| university, and shame on them for not encouraging more cross-
| disciplinary credits!
|
| I went to a relatively small school in Canada, but they were
| very good about staying out of the way if you tried to take
| extra courses (with credit).
| the_snooze wrote:
| The big value I got from taking compilers as an undergrad was
| that it brought everything together. It's basically where
| computer architecture, theoretical CS, and software engineering
| (and a hint of systems security) collide in a very practical
| manner. Compilers make it very clear how all those seemingly
| disparate topics apply in real non-trivial systems.
| varrock wrote:
| These are precisely the type of "ahas" I hope to experience,
| too, when I begin studying computer science. I've been taking
| introductory college math courses at my community college to
| fulfill some prerequisites, and a way for me to stay
| disciplined in my studies is knowing that concepts like the
| ones you mentioned are coming. Thank you for sharing!
| 908B64B197 wrote:
| > Compilers make it very clear how all those seemingly
| disparate topics apply in real non-trivial systems.
|
| Combined with a proper OS class, it's the first time a student
| can truly understand all the levels of abstraction from the
| language to the logic gate.
|
| And it also helps to recognize and solve parsing problems. How
| many programs end-up containing a parser, even if rudimentary,
| to read non-trivial input of perform validation? No, you can't
| use regex for that...
| josephg wrote:
| I feel the same way about taking Operating Systems. It's a
| revelation seeing how all the pieces fit together!
| forinti wrote:
| I've had the chance to build parsers for work.
|
| Once for a templating engine for SQL (taking values from the
| environment and using them queries). This was really nice for
| productivity and an intern could churn out dozens of reports a
| day. That was written with javacc.
|
| Another time by using a parser (written with Antlr) to extract
| bits of PLSQL packages (procedures, functions) and move them from
| one environment to another without having to send the whole
| package.
|
| Although this type of job is rare, it can be really useful when
| it shows up.
| LtWorf wrote:
| I've written a compiler that people actually use[1]!
|
| Studying compilers at university was highly beneficial. Before
| that course the code was a mess...
|
| [1] https://ltworf.github.io/relational/
| geophile wrote:
| I was in grad school, 77-83. The first year was part time at NYU,
| and then I went back full time elsewhere, for a PhD.
|
| In that one year at NYU, I took two compiler courses, from RBK
| Dewar, of Spitbol and Ada fame. My specialty is not languages or
| compilers, but those courses were incredibly fascinating, and the
| exposure to the topics I learned has been useful throughout my
| career.
|
| - I learned about lexing and parsing. I no longer remember the
| details of LALR, for example. But I understand the basic ideas
| well enough to construct lexing/parsing software whenever I need
| it, often using parser generator tools, but also rolling my own
| on occasion.
|
| - I learned about code optimization, which is a fascinating
| topic. At the time, Dewar was working on SETL, a set-oriented
| language. And I remember the power of having sets as a builtin
| type, and how powerful that was for expressing flow analysis, for
| example. Those ideas combined nicely with what I later learned
| about relational algebra, and query optimization. (Codd's paper
| on the relational model was only seven years old when I started
| grad school!)
|
| - Exposure to the ideas of interpreters and code generators, and
| even more fundamentally, the idea of code as a thing that can be
| manipulated programatically, has been useful throughout my
| career.
|
| - Oh, and by the way, Dewar was a great teacher.
| ethicalsmacker wrote:
| I really enjoy low level development... things like OS and
| compiler design. Emulation, simulation, etc. It's sad there's
| very little place for these "hobbies" anymore, other than that, a
| hobby.
| fear91 wrote:
| You can contribute to open source compilers. It's both fun and
| beneficial.
| namaria wrote:
| And just like child rearing and homemaking, another line of
| work fundamental to the well being of society goes
| unrecognized, underpaid and expected to be done out of love
| while other profit from it.
| jonstewart wrote:
| I did not take a compilers class when I was in college. Many
| years later, feeling the lack, I bought the Dragon book. I didn't
| make it past Chapter 4 because I was inspired to write a new
| library and tool, which then brought me a modicum of career
| success.
|
| Regehr is right on the money here: parsers and interpreters are
| everywhere. Once you learn how approachable and applicable they
| are, you can solve problems faster and better.
|
| I now always recommend to college interns that they take their CS
| department's compilers course their senior year (along with their
| English department's Shakespeare course).
| nt591 wrote:
| I'm currently in a part time masters program for fun and taking
| the compilers course. I'm sure John's experience is different
| than mine, but it seems the question should be put to
| universities. The professor of my course, by his own admission,
| hasn't studied compilers other than his undergrad decades ago and
| as far as I can tell was assigned the course to teach. As a
| result the syllabus is relatively dates. I think I'm 8 weeks in
| and we've only discussed parsing theory. As far as I can tell
| there won't be time for detailed study of code gen,
| optimizations, type checking, etc.
| wolf550e wrote:
| (2010), though as relevant as ever
| frej wrote:
| How can a compiler course not be requeried for a comp.sci degree?
| We had that. And i'm surprised others do not.
| bombolo wrote:
| We didn't have compilers in undergrad, but we had formal
| languages being required.
| HervalFreire wrote:
| Anyone know of any good free courses?
| ajanicij wrote:
| Stanford Compilers course:
| https://learning.edx.org/course/course-v1:StanfordOnline+SOE...
| stefanos82 wrote:
| I currently study https://github.com/DoctorWkt/acwj which is
| quite interesting I have to admit.
|
| I'm interested in this topic, because I want to participate in
| TinyC compiler's development; I use it quite often to run C
| demos of mine and its execution is instant.
|
| The least I can do is to either fix bugs or extend it to
| support more C99, C11, C17 features, and why not even C23 as
| soon as it gets approved?
|
| All I need is to gain the necessary knowledge and experience to
| jump right in and start fixing things.
| erichocean wrote:
| I would do the _Crafting Interpreters_ book to begin with. It
| 's free online.
| KineticLensman wrote:
| Agree! Learned a lot from doing it myself. Now trying out the
| techniques I learned there to write a VM for lisp
| thriftwy wrote:
| See also https://steve-yegge.blogspot.com/2007/06/rich-
| programmer-foo...
| vishnugupta wrote:
| I have done my share of compilers work a long time ago, my
| masters thesis was on this topic.
|
| The article mentioned a very important but not well known aspect
| right at the end which is compilers is not a homogeneous topic
| but has a fairly independent parts. Front end, optimizers, and
| target code generation. I dabbled little bit in optimizers and a
| lot in target code generation. It was quite fun to figure out how
| to produce optimal machine instructions, or use as few registers
| as possible etc. Along the way I also got to learn a bit about
| the OS because one has to know an executable file's layout, how
| to utilize heap, make sure not to over run stack etc.
|
| And some fun algorithms too, such as a smart way to traverse tree
| by pointer reversal to avoid recursion as one can't use recursion
| (extra space) while garbage collection.
| adrianmonk wrote:
| My unexpected side benefit: some compiler error messages became
| comprehensible.
|
| Oh, an lvalue is required? Since I now actually know WTF that
| means, I can deal with it.
|
| It also cleared up a situation that had always confused the hell
| out of me: sometimes I'd compile and get 1 or 2 errors, so I'd
| make corrections and try compiling again, but then I'd get 8 or
| 10 errors! Seeing that whatever I did made everything much worse,
| I'd conclude those most not be the right corrections, and I'd
| feel lost and maybe even get stuck.
|
| After taking compilers, I finally understood why: compilers have
| phases, and my corrections allowed the parsing phase to complete,
| which meant the semantic analysis phase could happen and give me
| errors. So for example, if I finally fix enough syntax errors
| that the compiler can tell I've written a function with some
| variables in it, then it can start giving me errors that they're
| not the right types.
| einpoklum wrote:
| > Oh, an lvalue is required? Since I now actually know WTF that
| means, I can deal with it.
|
| That's not so much a compiler thing as it's a language thing.
| Perhaps even a C (and C++) language thing...
|
| https://en.cppreference.com/w/cpp/language/value_category
| [deleted]
| NineStarPoint wrote:
| Agreed on this, by far the largest benefit from a utility
| standpoint from my programming language design course was
| increased understanding of errors.
| jll29 wrote:
| Compiler construction is a part of practical computer science
| that includes
|
| - formal languages, Chomsky hiearchy and automata (DFAs, NFAs)
|
| - algorithms & data structures (syntax trees, symbol tables &
| hashing)
|
| - parsing algorithms
|
| - asymptotic complexity (of automata recognition/acceptance and
| parsing algorithms)
|
| - software architecture (single pass versus multi-pass,
| abstractions)
|
| - operations research (graph coloring based register allocation)
|
| - assembler & automatic code generation
|
| - virtual machines & interpreters
|
| It is a field where theory and practice come together beautifully
| (and works like the Aho et al. "Dragon Book" or Wirths
| "Compilers" are masterpieces that lucidly lay things out so after
| reading Chapter 2 of the former, or all of the latter short
| volume (barely 100 pages), a compiler is basically demystified to
| any undergrad).
| hardware2win wrote:
| Imo
|
| Formal langs theory is too weird and formal
|
| And dragon book is too focused on formal math
| erichocean wrote:
| If you are interested in modern compiler infrastructure that
| subsumes a lot of recent PhD level research topics, I can highly
| recommend MLIR.
|
| It's under the LLVM Foundation umbrella.
|
| If you just want to deal with lexing, parsing, and interpretation
| (from scratch) for a reasonably complex class-based language, I
| recommend doing the (free) online book _Crafting Interpreters_.
|
| The second half of that book re-implements the same language in C
| with garbage collection and a fast byte code interpreter.
___________________________________________________________________
(page generated 2023-03-25 23:00 UTC)