9 ms·
Rich Programmer Food
- saturdayplace 16y agoI'm no programmer, barely a web developer, and have no idea what he's talking about half the time. But jeeze this man can write. I should go learn about compilers. Or improve my typing.
- epochwolf 16y agoI'm in the same boat. I have a degree but I don't know anything about compilers. I'm convinced that being a remotely intelligent programmer means you are going to be feeling stupid most of the time.
- jpeterson 16y agoI'm convinced that being a remotely intelligent programmer means you are going to be feeling stupid most of the time. Yup, which is why if you want to be a good programmer, you have to commit yourself to constant tinkering and learning.
- watmough 16y agoOne of the most useful things you could do at this stage is go write a lexer to split some input file up into lexemes / tokens. As an example, think splitting a CSV file up into numbers, strings, separators and newlines. If you get this right, think how easy it would be just to parse this data into a simple data structure and generate SQL to spit it into a db. Right there, in that one lexing module, you've probably taken the single largest step towards accomplishing the tasks that Steve Yegge talks about. Of course there are tools to generate lexers, but if you're learning something, not much beats getting your hands dirty with real code.
- epochwolf 16y agoI think I've done that already. My first program parsed a network protocol. http://botdom.com/wiki/Dante http://botdom.com/wiki/Dante (The code is nasty but it works)
- johnzabroski 16y agoSo research how to make it less nasty. Check out the Lexer Hack article on wikipedia. It also helps to familiarize yourself with classical pathological syntax issues for languages like ALGOL-68 (requires 'semantic actions' to parse correctly) and early versions of FORTRAN (identifiers could have intermediate whitespace, which meant that a typo could corrupt the meaning of the program) and figure out how to do parse a language with an Offside Rule (and not all offside rules are created equal; Haskell 98 is very complex). Then look at techniques like scannerless/lexerless parsing (SGLR, PEG, etc.), combinatorial parsing, etc. Understand what mathematical properties of a parser algorithm and a parser generator you should look for to ease your job. Understand why naive user of a parser generator tends to result in slower lexing/parsing than hand-coded ones. Understand why for some applications we might be able to not care. Understand how to embed good error messages in a grammar-based approach vs. hand-coded solution. Understand the notion of unparsers, which, IIRC, are not covered in any of the Dragon Book at all.
- thyrsus 16y agoWork all the demonstrations and exercises in Kernighan and Pike's Chapter 8 of "The Unix Programming Environment". Less than 60 pages in a friendly large font. You'll be glad you did.
- mahmud 16y agoThe Unix-way of compiler construction is convoluted, difficult and verbose. Any Lisp book will teach you more about compiler construction in the first two chapters than you can learn from entire texts on the subject that use Lex and Yacc. Chapter 8, at a more leisurely pace, and far more in-depth: http://www.cs.brown.edu/~sk/Publications/Books/ProgLangs/ http://www.cs.brown.edu/~sk/Publications/Books/ProgLangs/
- pjscott 16y agoI've been looking through that book, and it's just what I've always wanted from a compiler book. Though maybe I should have expected that as soon as I saw the name "Shriram Krishnamurthi" on the cover.
- mattmillr 16y agoAs a programmer who didn't take the compiler class in school, what's the best way to go about learning what it takes to write one? A book recommendation? Find a CS dept nearby and take the class?
- alextp 16y agoAppel's series of Modern Compiler Implementation in * is easy enough to ready and apply, and some come with code (IIRC).
- silentbicycle 16y agoHow do the Java and C versions compare to the ML version? I have (and really like!) that one, but Appel's an ML hacker, and I'd be surprised if it translated 100% to C / Java.
- demallien 16y agoI have the C version, and I personally found it easier going than the Dragon Book. As with the other books in the series, the beginning chapters dealing with the lexer an the parser are very mathematical - but the parts actually dealing with emitting bytecode are quite practical in nature. I ended up using the lexx/yacc tutorials to give me a grounding in parsing, without worrying too much about the mathematical basis for it, and then used the Appel book for everything after having derived an AST.
- silentbicycle 16y agoOk, thanks.
- drv 16y agoI took a course based on the Java version, and it felt very clunky to me - the sample project code was very verbose and used the Visitor pattern whenever it could possibly be wedged in, making it a bit of a nightmare to understand the flow of the code as a whole. A good IDE would probably clear up a lot of this confusion, but it always felt like we were fighting the language. Take this with a grain of salt, however, since I'm fairly certain my professor edited the projects quite a bit before handing them to the students; perhaps the original book material is less convoluted.
- asolove 16y agoIf you're interested in improving your skills and you read HN a lot, you're probably saying to yourself: 1. I wish I could improve my Lisp and 2. I wish I knew more about compilers. Read Norvig's "Paradigms of Artificial Intelligence Programming." It proceeds through various early AI problems, which are good motivation. It shows how to solve some of them directly, then moves on to solving them with interpreters for DSLs, and finally shows how to speed up those solutions through compilation. The problem-specific portion of the code gradually gets smaller, more powerful, and faster.
- deleted 16y ago[deleted]
- silverlake 16y agoI've spent 20 years working on various compilers, yet I still don't think it's a big deal. Undergrads just need to work on any type of large systems project: OS, compilers, distributed systems, DBs, whatever. The problem with the compilers/programming languages field is that every idiot with a computer has an opinion. It's frustrating that popular languages are arguing about features that have been analyzed in depth 20+ years ago, e.g. closures really are the greatest thing ever and should be in any modern language.
- peripitea 16y agoCan you expand on why closures are the greatest thing ever? I've heard this from a few places, but I've only run into a handful of real-life situations where they were the perfect solution to a problem I was having. And even then, they weren't solving an otherwise-difficult problem; they were just saving me some lines of code. I feel like I might be missing something.
- drblast 16y agoWriting medium-sized projects in Javascript, I often look toward the sky and thank the originators of that language that they had the foresight to include closures and first class functions. I use them all over and save a significant amount of effort. Because my time is extremely limited, they make things possible I couldn't otherwise do. If there are a handful of problems where they're the perfect solution, then any language should have them, simply because the overhead in implementation and linguistic style is so low.
- tkahn6 16y agoHave you ever used jQuery? $(".someclass").onClick(function() { $(this).doSomething(); }); Notice you're passing in a function to a function and `this` is a free variable. Spend a week programming in a functional language (like Haskell or Clojure) and then go program in Java. You basically feel castrated because a) generics were added to the type system as an afterthought and b) functions are not first class citizens and c) higher order functions are simply not used in Java (they can be somewhat imitated with anonymous inner classes but it's a pain).
- grandalf 16y agoThe logic Steve uses, while true, fails to appreciate the benefit of selective ignorance. It's possible to reason effectively about a system without understanding the turtles all the way down, as long as you understand the limitations of the abstraction you are reasoning in, which is possible to do w/o dissecting turtles. I'd further argue that the "scientist vs engineer" personality distinction is applicable here. The scientist is concerned with solving the primary problem, while the engineer is concerned with optimizing all the turtles. Take a physicist using Mathematica... does she need to know how compilers work to effectively do cutting edge work with the tool? No. So why is any other programming langage any different (unless you're amused by dissecting turtles).
- eru 16y agoYes. And if the physicist is implementing anything on top of Mathematica, she may profit from knowing some things about parsing.
- mahmud 16y agoPretty entertaining, if a bit melodramatic. I really wish people didn't mystify such a basic programming skill. Compiler hacking is something reserved for the wizards only if you take the classic definition of compiler implementation: an expensive engineering project, targeting a new processor, architecture or OS. In that sense, sure. You will be working in a lab with hundreds of developers, and tinkering with a piece of multimillion dollar prototype. In reality, however, "compiler construction" boils down to foundational language theory, along with various tricks and techniques for translating a set of very straightforward algebriac rules, to another set. Anytime you write regexes or XPath to extract a set of fields from a documents and transform to something "readable", you're almost writing a simple one pass assembler, using some implicit "business rules" (i.e. all numbers should be floats, names capitalized, etc.) for productions. Compiler skills will give you the theoretical backbone to discover, refine and assess those implicit rules. Not to mention techniques for transforming them from one form to another. To the list of skills made mystical and magical by people I would add Lisp. It's not magic. I mention it because it just so happens to have compiler construction lore aplenty. The first Lisp exercises you will read in your lisp book of choice (often requiring nothing more than basic English literacy and 6th grade arithmetic) are the expression simplification and evaluation exercises. Transforming your elementary school algebra rules (multiplication and division before addition and subtraction, etc.) to something the machine can execute. The hardest part is just understanding the words: if you have a hunch for what "expression", "term", "rule", "left/right hand-side" and "precedence" might mean, you're good to start. Few chapters of a Lisp book will spare you volumes of traditional compiler construction techniques, taught by rote methods. The first time I attempted to read SICP I had convulsions and physical pain. The whole time I had this inferiority complex nagging at me, telling me this was something for "smart kids" and I was unworthy. But this stopped after I went through the first few parts of chapter 1, and took in the playful tone the text. I felt stupid afterward; like being afraid of a St. Bernard. It looks big, but it's actually bubbly. Don't listen to people when they say something is difficult or not for the faint of heart. Put a saddle on Falkor and go flying!
- kenjackson 16y agoThe problem with SICP as a compiler book is that it doesn't really doesn't teach you much about compilers. At least beyond Lisp compilers. Even something relatively simple, like stack layout isn't really covered, at least that I recall. Or intermediate representations (unless you simpler consider Lisp your IL), or even how different parsing techniques will interplay with what you can parse (easily at least). It's like saying that reading CLR's algorithms text will teach you how to build real databases, because it teaches you about trees and hash functions.
- oiuytghyuj 16y agoWell as a physicst I say you can't understand a computer unless you understand the wavefunction of an electron crossing a potential barrier. So ner-ner-ni-ner-ner.....
- seldo 16y agoI certainly agree that learning to type is the most important skill in programming. It saves you a few milliseconds every time you type anything, which adds up over thousands of keystrokes into a clear competitive advantage. And unlike compiler design, learning to touch-type is easy.
- yanilkr 16y agoMany things in software world are built on abstraction. It's not really possible to know it all and many times it is counter productive to get into any project with a mind set of I have to understand everything here.
- fleitz 16y agoA large part of the problem is people only see the skills for compiler design being useful for compilers. If they would start with something simple they could avoid the compiler design class and write better code by using things like ANTLR from the start. The next time your program consumes text input try writing a grammar for it and processing the AST instead of half baking it with a regex.
- staunch 16y ago(2007) should be added to the submission title.
- mahmud 16y agoCompiler theory operates at mathematical time-frames, not Web 2.0's. Best compiler texts were written before 1985 :-)
- staunch 16y agoIt's just a custom here as I'm sure you know.
- silentbicycle 16y agoSo is "posting the obligatory xkcd comic". So is posting "[citation needed]" or reminding people that "correlation does not imply causation" like a goddamned robot. That doesn't mean you have to do it.
- blasdel 16y agoBut with pg making comments that are just a link to the readability bookmarklet, I think this battle might be lost.
- Goladus 16y agoRight, but Yegge's 2007 audience is likely a big pile of programmers coding in Java, C++, and Perl who have never even heard of Backus Naur Form.
- chrismealy 16y agoHis part about rails made laugh out loud. I get the feeling Steve is teasing us with his magical vaporware just for laughs.
- jules 16y agoI've been thinking about a compiler for Lisp/ML like functional languages. If we take the source program, convert it to continuation passing style, then lambda lift, we have an intermediate form where no closures appear, every call is a tail call and where the stack is represented as data structures explicitly. The next step is to convert every call site f(x) into if(f == FUNCTION1) FUNCTION1(x) else if(f == FUNCTION2) FUNCTION2(x) ... The reason for doing this is that now all function calls are to known functions (there are no calls to function pointers anymore). Because all calls are tail calls we can then convert every call to a jump instruction. (note that this could cause code blowup with a lot of different functions and call sites, so it would probably be better to do this transformation lazily as you analyse what values f could take, and only actually do this transformation if you know that f can take at most 10 different values) What we have now is one giant control flow graph (state machine) representing the entire program. All functions have been eliminated. The only thing left is primitive operations and jumps. Why do I think that such a representation is interesting for a compiler? Because many things that previously had to be coded separately are now one analysis/transformation. Because there are no functions left all analysis and transformations automatically become interprocedural. And for example (loop) unrolling and inlining become the same transformation. So this could possibly make the compiler much simpler. Could something like this work?
- silentbicycle 16y agoHave you read Appel's _Compiling with Continuations_?
- jules 16y agoI have not, but the table of contents sure looks interesting. Am I right that they don't do lambda lifting / closure immediately? They seem to have a lot of optimizations working on lambda expressions, and also optimizations working on records. By lambda lifting immediately I am hoping that the optimizations on records can take care of (some of) the lambda-optimizations.
- silentbicycle 16y ago
- sreque 16y agoI like Steve's PL posts a lot, but I don't understand why he has to hate on static type systems so much. I appreciate and use both dynamic and static languages all the time, and both have their own respective strengths and weaknesses. There are some problems for which a static type system is extremely helpful, and others where no type system can really express the problem well. To say that a whole active branch of CS that affects the most popular languages in current use is worthless is a little presumptuous of him.
- silentbicycle 16y agoIf anything, his analogy between the impracticality of fully deterministic NLP and H-M type inference is weak. You want static typing to be deterministic and quickly resolved, or else you'll get nasty C++-like compile times. (Of course, it also has to be smart and consistent, or you just get something that will just make you go through the motions for little gain. Smart static typing can be very useful, but dumb static typing is a waste of time.) I understand people hating on static typing, though - when most people think of static typing, they think of C++ and Java. I didn't see the point of static typing until I learned OCaml, and that still has room for improvement. (OCaml + Haskell-style typeclasses + error messages that weren't obviously transliterated from French as an afterthought would be a nice start.) There are only a few languages with well-designed static type systems, and the most obvious one insists on being all indie rock about it ("avoid success at all costs").
- frivoal 16y agoerror messages that weren't obviously transliterated from French as an afterthought would be a nice start Don't worry too much about this one. I am French, and the phrasing of OCaml's error messages is just as strange before the transliteration.
- silentbicycle 16y agoHah, nice to know. :)
- blasdel 16y ago
- ww520 16y agoCompiler class was the most fun class I had back in school, though there were a number of things I didn't understand and skimmed over. It was only years late that I re-read the Dragon book in depth that I understood some of the topics. Too bad there aren't too many language or compiler jobs.
- moondowner 16y agoTurns out to be a good PR to taking a course on Compilers on faculty. I'm sold, I'll sign up for it.
- clyfe 16y agoRead this article a couple years ago and recognized it. The best part of it to remember: <<A good friend of mine with a Ph.D. in languages told me recently that it's "very painful" to experience the realization that all those years of slaving over beautiful mathematical purity have more or less zero bearing on the real world.>>
- aycangulez 16y agoI think a better title for this article would be "How monstrosities get written".
- mkramlich 16y agoI want to write a compiler that can take a Steve Yegge post as input and compile it down to a compact, concise form more readily executable by my brain.