8 ms·

I'm a big Steve Yegge fan and I like most of his articles. I like this one too. But, some of them, like this one, leave me feeling a bit disheartened. Okay, co

• danpalmer 10y ago
  I recommend "Understanding Computation" from O'Reilly - it's pretty straightforward, teaches through examples and exercises, and uses Ruby, to build toy compilers from first principles. It's not going to give you the mathematical basis that you'd get in a uni course, (it was actually 3 separate classes over 2 years at my uni), but it should help develop the practical _feel_ for when these things might help solve real engineering problems, which I think is what matters.
  • paloaltokid 10y ago
    Thanks for the recommendation!
• rspivak 10y ago
  Sorry for the shameless plug, but about a year ago I started a series of articles on how to write a simple interpreter called "Let's Build A Simple Interpreter." Take a look, it might be something that you may like: Part 1: https://ruslanspivak.com/lsbasi-part1/ https://ruslanspivak.com/lsbasi-part1/ ... Part 9: https://ruslanspivak.com/lsbasi-part9/ https://ruslanspivak.com/lsbasi-part9/
  • sklogic 10y ago
    Interpreters are inherently very complex, far more complicated than compilers. It is a bit harsh to start learning this subject with an interpreter.
    • striking 10y ago
      I'd say interpreters are less complex than compilers. Even compiling down to byte code and interpreting that isn't as difficult as writing something that actually outputs optimized code that runs on bare metal. There are some very complex interpreters out there, but they have different goals than simple interpreters or optimizing compilers (see: Erlang, LuaJIT, Ruby, etc.)
      • sklogic 10y ago
        > something that actually outputs optimized code Optimisations might be difficult (some of them, not all). Yet, a straightforward compilation is trivial, far simpler than the simplest of possible interpreters. And an unoptimised compiler is by far more simple than even an unoptimised interpreter.
    • SomeCallMeTim 10y ago
      Sorry, but no. Writing an interpreter is strictly a subset of writing a compiler. Instead of spitting out machine instructions, you can use your source language to execute actions directly.
      • sklogic 10y ago
        > Sorry, but no. Mind proving? > Writing an interpreter is strictly a subset of writing a compiler. What?!? You can write a compiler in a non-Turing-complete language. This is impossible for an interpreter. So, how is it a "strict subset" now? Also, interpreters must provide much more functionality than compilers. Compilers simply rewrite the code from one representation into another. Interpreters must take care about the runtime, about the operational semantics. It's much harder than a simple rewriting. > Instead of spitting out machine instructions, you can use your source language to execute actions directly. And the latter is many times more complicated than "spitting out machine instructions".
• sklogic 10y ago
  Start by building simple DSLs that can make your work easier, ideally on top of Racket or any other similarly powerful framework. Learn by following the simple examples.
  • paloaltokid 10y ago
    Do you have a link to some examples? Learning Racket has been on my to-do list for some time, this might be just the excuse I need!
    • sklogic 10y ago
      This one is nice and clean: https://github.com/soegaard/minipascal https://github.com/soegaard/minipascal
• jaggederest 10y ago
  The tradition in the lisp world is to write a metacircular evaluator, which is approximately the most braindead thing that you could actually call a 'compiler'. Similar concepts apply in day to day work, if you want to have some fun with compilers. You can almost certainly use a parser in your day to day work. You've got log files, config files, some sort of routine tedious job that involves taking free text and turning it into useful data structures of some kind. They don't have to be complex - it's entirely possible to write a few-line validator and transformer for (say) CSV user input.
• dionidium 10y ago
  "But, some of them, like this one, leave me feeling a bit disheartened." I think this is a common reaction. Look, he basically starts these articles by saying you're going to be disheartened by this. For some reason, this makes a lot of people want to find a way to A) not have to learn the stuff that they feel disheartened for not knowing; and B) not feel disheartened. Nobody is saying that you have to learn this stuff to make Steve happy. But I think there's a reason that you feel disheartened for not knowing it. Deep down, you know that you really should learn something about it. And that's why you feel disheartened. That's a good sign! But I don't think there are any shortcuts to making that feeling go away.
• wilburTheDog 10y ago
  Jack Crenshaw has a nice series called Let's Build a Compiler. http://compilers.iecc.com/crenshaw/ http://compilers.iecc.com/crenshaw/. It was written many years ago and posted to the comp.compilers usenet group, so the formatting is old-school, but the content is still useful. There's also a wikibook on the subject. https://en.wikibooks.org/wiki/Compiler_Construction https://en.wikibooks.org/wiki/Compiler_Construction
• volkadav 10y ago
  #1) I was in the very same boat and though it is NOT EASY, it is POSSIBLE and possibly VERY REWARDING to go back to school later in your career. I did end up taking compilers in part because of this post and it was awesome. Looking back over the course of my education, there are some classes that are simply head and shoulders above the rest in terms of intellectual impact. You come out of every lecture feeling almost punch-drunk from the impact of the ideas that were just imparted to you, as if your head was ringing and your double vision is seeing through the very framework of the universe itself(1). Compilers was one of those classes for me. #2) Coursera may be an option if you can't swing an in-person class. I've taken a handful of classes that way and always found the time well-invested based on how it helped me grow as an engineer. (1) "When Lawrence understood, it was as if the math teacher had suddenly played the good part of Bach's Fantasia and Fugue in G Minor on a pipe organ the size of the Spiral Nebula in Andromeda-the part where Uncle Johann dissects the architecture of the Universe in one merciless descending ever-mutating chord, as if his foot is thrusting through skidding layers of garbage until it finally strikes bedrock. In particular, the final steps of the organist's explanation were like a falcon's dive through layer after layer of pretense and illusion, thrilling or sickening or confusing depending on what you were. The heavens were riven open. Lawrence glimpsed choirs of angels ranking off into geometrical infinity." http://www.npr.org/templates/story/story.php?storyId=14877676 http://www.npr.org/templates/story/story.php?storyId=1487767...
• xigency 10y ago
  If you really want the full understanding of compilers, you should write a simple compiler. 1. Design your own programming language, or equally, pick a language and remove virtually every feature. In fact, there's no rule that this input language needs to be Turing complete. For simplicity, you should limit yourself to one datatype, integers, and one library call, print. Now, write a set of valid and invalid programs. Write a program to convert this text into tokens. As said, this can be regular expressions or some hand-coded loops. 2. Look at the language you've defined and sketch it out in a few simple (and recursive) rules. Think in terms of statements, expressions, and tokens (symbols or identifiers). The best experience is to write a recursive descent parser or use YACC, but in some way you should convert the stream of tokens into a tree structure. 3. The next steps can be complicated but it's important to keep your footing. You should have a destination architecture in mind. It should not be x86. Pick something simple like an 8-bit microprocessor (Z80) or something 16-bit like MIPS. Make sure you have a simulator or device to target. You will need to learn some assembly and have the skills to convert programs to assembly language by hand. 4. Now, in as many stages or passes as you like, convert the program into machine instructions. You can go over statements and split them into shorter ones with a fixed number of arguments. You can separate function calls as their own assignment. You can force each statement to have a new assignment with temporary variables. These are the backend steps where you operate on a structure to create new structures to make life easier. Think in terms of generating code for each function, techniques for storing results in registers to use, saving values on the stack between calls, and outputting the code in one giant assembly file. Then test, test, test. That's it. Once you've got it working, congratulations, you're a compiler writer. One benefit of taking this class in school is the textbook, lectures, tests, test cases, and partners to work with, but it's totally possible to achieve on your own if you are motivated enough.
• johan_larson 10y ago
  Writing a compiler for a real language targeting a real processor architecture with meaningful optimizations is a very big job -- far too big to undertake just for fun or just to learn. Simplifying the problem is imperative. I've done a bit of digging into various approaches and guides. There are a lot of them, because every respectable CS curriculum needs a compilers course. The one I find most intriguing is by Niklaus Wirth, the guy behind Pascal and Modula-2. In his "Compiler Construction" PDF, he guides you through building a compiler as a series of exercises in a bit over a hundred pages. I get the impression you could work through the guide in 2-3 of weeks full time or perhaps a quarter as a side project. http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf
• tomjen3 10y ago
  I had a CS degree. Our compiler course had us design a toy language, then write a compiler for that language which targeted another (eg write a compiler in ruby to target the JVM or ASM). They were all worse than most other compilers you could get, but today I know how to write one. It was still a lot of work, mind you.
• zenogais 10y ago
  It really depends on what you think qualifies as understanding a topic. You can definitely write a basic compiler without much understanding. I've seen a lot of programmers do this, and I think it's great. The unfortunate reality though is that at some point you'll have to learn the foundational mathematics of compilers to really build them. Without that foundation you'll be manipulating symbols and using libraries with only a vague idea as to what they really mean or do. This means when things go wrong, you'll often be quite puzzled as to what's happening. It also means your workarounds are likely to be flawed as they'll be based on only partial understanding of the problem they're solving. It's great to have a pragmatic attitude when learning things, but it can also prevent you from gaining the deeper understanding only available through protracted study and practice.
  • yumaikas 10y ago
    What courses form the mathatical basis for writing compilers? Discrete Math and the like?
    • zenogais 10y ago
      Usually discrete math as the absolute bedrock, then a good understanding of automata theory.
  • paloaltokid 10y ago
    I think my definition of understanding would be: I have understood this well enough to write a non-trivial program that solved a problem at my day job. This program should provably (and hopefully obviously) be the most correct, maintainable, and performant solution for the job. I make the day job part a requirement because for me to feel that I've invested my time well, I need to be able to apply my knowledge in service of some other task. Mind you, it only has to work and solve a problem once. If I never use it again in my career, that's fine. But it's that ability to say "well, I never thought I needed to learn compilers until this one time..."
    • zenogais 10y ago
• yoo1I 10y ago
  I found that starting with something simple and useful helped me lot's unerstanding how these things work. So I started writing a JSON parser. The JSON spec is relatively simple, while still retaining enough complexity to learn from some edge cases, and you get to start learning about parsing without having to define what you are parsing at the same time. That's just the parsing part of course, but it already contains lots of interesting bits, and you end up with something that is already useful. Then I wrote a small templating library, similar to jinja. That's already more complicated than just parsing, given that you have to make loops and expressions and so on in it. ... so now I trying to write a JSON parser in assembly to understand how that works so that eventually I can compile my templates to machine code instead of just python. That's maybe not so good for production, but then this is a learning exercise. Computers are pretty fun!
• astrange 10y ago
  Compilers are pretty simple - stuff goes in one side and out the other in easily defined layers. There's plenty of open source examples to learn from, too. Not just compilers, but other things that basically are compilers with different names like DSLs, Coffeescript, etc. One thing to watch out for is that people will tell you to read the Dragon book, which is a total waste of time.
• thyrsus 10y ago
  "The Unix Programming Environment" by Kernighan and Pike, in Chapter 8, builds a compiler for a four function calculator using yacc, to which they then add variables, flow control, and functions. Pretty amazing in a breezy <60 pages. Not familiar with C? They introduce the subset they use (and more) in chapters 6 and 7. Anything in the book you don't already know is also likely to be immediately applicable. Oddly, Amazon doesn't provide the table of contents, but Barnes and Noble does: http://www.barnesandnoble.com/w/books/1113183162 http://www.barnesandnoble.com/w/books/1113183162