8 ms·
Show HN: “Statements and State”, the next chapter of my book on interpreters
- ChuckMcM 9y agoI vividly remember learning about recursive descent parsing in my compilers class and thinking, "Wow, I can use this everywhere!" Of course in addition to executing an AST you can also generate CODE for it...
- seanmcdirmid 9y agoRecursive descent is still a great way to implement parsers.
- dozzie 9y ago"Recursive descent" is an ancient African expression meaning "I can't write grammars".
- seanmcdirmid 9y agoMost production compilers still depend on recursive descent because (a) it isn't that much harder compared to the generative approach, and (b) it is the best way to work in real error recovery or to support IDE services.
- munificent 9y ago> Of course in addition to executing an AST you can also generate CODE for it... Yes! In the third part of the book [1], we'll do exactly that. The C interpreter's parser generates bytecode as it parses. I haven't written the text yet (that's the hard part...) but you can see the code for it here [2]. [1]: http://www.craftinginterpreters.com/a-bytecode-virtual-machine.html http://www.craftinginterpreters.com/a-bytecode-virtual-machi... [2]: https://github.com/munificent/craftinginterpreters/blob/master/c/compiler.c https://github.com/munificent/craftinginterpreters/blob/mast...
- ChuckMcM 9y agoThat will be awesome.
- bhrgunatha 9y agoI like this book a lot - especially making it available to read free in HTML. It's good to see practical information about parsing and grammar rather than plainly theoretical - although there's room and a for need both. Another similar read is Vidar Hokstad's blog series - Writing a compiler in Ruby [1] which was first submitted here 9 years ago! [2] [1] http://hokstad.com/compiler http://hokstad.com/compiler [2] https://news.ycombinator.com/item?id=319337 https://news.ycombinator.com/item?id=319337
- flavio81 9y ago"In less than two thousand lines of clean Java code, we’ll build a complete interpreter for Lox..." 2000 lines of Java code? I guess 400 of the lines of are just getFoo() setFoo() getBar() setBar() and so on and so on... At the beginning i thought "Why is this tutorial written in Java? Yuck!". Then, in a flash of enlightenment i saw this was a perfect choice: The author, bless him, is showing us how to write an interpreter in Java, so after one is finished, one can stop using Java and start using this brand new language. Jokes aside, i am VERY MUCH looking forward and EXCITED to see that the next chapter is on implementing a bytecode virtual machine. So let's hope the author completes the book soon!! Then I will finally create my ambitious project for an object oriented COBOL, which will be called "ADD 1 TO COBOL GIVING COBOL" (drum fill please...)
- yumaikas 9y agoINCREMENTED
- pvg 9y agoThe repo is here https://github.com/munificent/craftinginterpreters https://github.com/munificent/craftinginterpreters so you could have looked without the need for 'comedic' guessing. It contains exactly zero getX/setX methods.
- flavio81 9y agoMan, what happened to sense of humor in Hacker News? Has it been deprecated in the current version?
- pvg 9y agoI think you'd have to use actual humor for that. Instead you wrote the programmer equivalent of 'BUTTS LOL' (hilarious all-caps included) except longer.
- flavio81 9y agoUmm... You should understand that the use of all-caps in "COBOL", "ADD" and "GIVING" wasn't gratuitous. Historically, programming languages (early 1950s, COBOL, FORTRAN, etc), not only had acronyms as their names (thus the names in all caps) but the keywords themselves (and thus most of the source code) was written (and supposed to be written) as all-caps: "GOTO", "IF", "THEN", "GOSUB", etc.
- ljw1001 9y agoThis is really a wonderful book. Nystrom's writing is clear and entertaining. I look forward to every new chapter.
- panic 9y agoThis is great writing: very clear and easy to understand! I feel that dynamic variable lookup is a mistake, though -- it's just so painful to have to wait until runtime to discover you've made a typo. Is supporting mutual recursion really important enough to offset this pain?
- _pmf_ 9y agoTypography and layout is also very pleasing.
- munificent 9y agoThank you! I put more time into this than most people probably realize.
- wtetzner 9y agoI don't think dynamic variable lookup should be required for mutual recursion. There are plenty of static languages that support mutual recursion.
- panic 9y agoThis topic is covered in a sidebar in the chapter: allowing the top level to be list of statements instead of declarations means that each function definition must happen in order. Otherwise you can end up with troublesome code like this: function f() { g() } f() var x = read_user_input() function g() { print x } Static languages typically don't allow the calls to f() and read_user_input() -- maybe that's the right answer here. There are other answers that come to mind as well. But, either way, I don't think we should perpetuate the mistake of dynamic variable lookup.
- wtetzner 9y agoAh, this is solved in OCaml using the 'and' keyword: let rec even n = match n with | 0 -> true | x -> odd (x-1) and odd n = match n with | 0 -> false | x -> even (x-1) Although personally I've never liked the idiom where everything at the top-level is a statement. Even in OCaml I usually define a 'main' function, and call it at the bottom of the file: let main args = do stuff... ... let () = main Sys.argv
- erikb 9y agoI thought this would be a book in political statement interpretation. Would be really interested in that! Any suggestions?
- dmux 9y agohttps://www.coursera.org/learn/understanding-arguments https://www.coursera.org/learn/understanding-arguments
- erikb 9y agoReally appreciate the attempt. Thanks! Yet, I don't think that will be an answer. A very simple example of political speak: Merkel basically said last Sunday: "We can't trust our overseas partners anymore. I've seen that the last few days. We must take our fate in our own hands." Yet what she meant was: "Trump will let you down. I'm strong enough to defy him. If you want a strong leader that listens, come to me." Another example is how the G7 fought just about phrasing of a final statement for day and night before. What does the result mean? Who won what? How will that influence decision of other people in the political landscape? Really curious to learn about that.
- pravj 9y agoI am loving this book so far, always wanted a resource with such details and a 1:1 session like feeling. Also, to enforce an extra layer of learning, I am writing the interpreter in Go. (book uses Java and C) https://github.com/pravj/glox The "satisfactory" part is, I've started applying the learning to other problems (writing a transpiler, completely different from the book's context), despite being in the middle of the book.
- WalterGR 9y agoto enforce an extra layer of learning That's a very interesting approach. Is that something you usually do when learning, or you just wanted to use Go for this? Anything else you can say about the practice?
- mrmondo 9y agoThanks for taking your time to commit to this, I was wondering if you had an RSS feed rather than the email subscription option? I tried a few feed readers and couldn't discover RSS or ATOM feeds present. (Although I may have missed it as on my phone at present)
- munificent 9y agoI don't. My blog has one, but the hand-rolled static site generator I use for the book doesn't do that. It's pretty minimal. My impression (for better or worse) is that few people use RSS these days, so it didn't seem like a great use of my time to get it set up. If you don't want to join the mailing list for whatever reason (though it is quite low traffic), you could follow me on twitter too (@munificentbob). I tweet whenever a new chapter is up.
- mrmondo 9y agoAh I see, if you use Jekyll or Hugo they will generate the feeds for you so I'm assuming it's something else? Personally I've found that RSS is more popular than ever, especially in the tech space as the number of news sources available these days is so large partly due to the number of individual blogs out there and services like feedly along with wonderful apps like reeder.
- munificent 9y ago> I'm assuming it's something else? Yes, I hand-rolled a little build script tailored specifically to the book.
- mrmondo 9y agoHey that's neat that you rolled your own build for your needs though.
- munificent 9y agoYeah, it was a deliberate choice to hack together something simple. Otherwise, I'd spend countless hours tinkering with frameworks and libraries and never actually write the damn book.
- lozzo 9y agoany reason for not putting this book on github you would hopefully get stars and various encouragements and it would be more transparent to the whole community
- munificent 9y agohttps://github.com/munificent/craftinginterpreters https://github.com/munificent/craftinginterpreters I should probably link to it from the site...
- jnbiche 9y agoI'll add my usual comment in discussions about interpreter/compiler books: I'd really love to read a modern book or in-depth tutorial on creating a statically-typed functional language, with discussions on pattern matching, type inference, tail call elimination, ADTs, etc. There are so many great books out there on how to create a lisp, or a typical mutable object-oriented language, but with one notable exception (that's unfinished), there are no approachable online tutorials/books out there that I've found on building compilers or interpreters for functional languages. Only academic papers, a textbook, and one or two books from 20-30 years ago. Pierce's Types and Programming Languages is a great textbook that covers all of this material, but from an extremely detailed and formal academic perspective. It would be great to see more approachable tutorials or short books online to complement Pierce's text. I've started writing my own in-depth tutorial on this subject using Scala as the implementation language, but would love to see other tutorials/books as well.
- burkaman 9y agoWhat's the notable exception?
- jnbiche 9y agoWrite you a Haskell by Stephen Diehl: http://dev.stephendiehl.com/fun/ http://dev.stephendiehl.com/fun/
- munificent 9y ago> I'd really love to read a modern book or in-depth tutorial on creating a statically-typed functional language, with discussions on pattern matching, type inference, tail call elimination, ADTs, etc I'm interested in that too. I've heard good things about Appel's book [1], but haven't read it yet. > There are so many great books out there on how to create a lisp, or a typical mutable object-oriented language For what it's worth, I haven't found much about creating object-oriented languages. There's a lot on Lispy dynamicall-typed languages, but I haven't seen much on things like method dispatch, vtables, inheritance, etc. One of the reasons I'm writing this book is to try to cover that. Even if you don't like OOP languages, I think it's worth knowing more about how they work under the hood since they are so prevalent in the industry. > I've started writing my own in-depth tutorial on this subject using Scala as the implementation language Interesting! Is it online yet? [1]: https://www.cs.princeton.edu/~appel/modern/ml/ https://www.cs.princeton.edu/~appel/modern/ml/
- yolo77 9y agoBeutiful! What tools do you use for generating HTML ?
- munificent 9y agoA pretty simple hand-cobbled-together chunk of Python: https://github.com/munificent/craftinginterpreters/blob/master/util/build.py https://github.com/munificent/craftinginterpreters/blob/mast... It's more complex than the build script[1] for my previous book[2], but still pretty simple. There's a real luxury in writing a program that literally only has to run on one single set of input data. A whole lot of things get easier. [1]: https://github.com/munificent/game-programming-patterns/blob/master/script/format.py https://github.com/munificent/game-programming-patterns/blob... [2]: http://gameprogrammingpatterns.com/ http://gameprogrammingpatterns.com/
- seibelj 9y agoI haven't had a chance to dive into this book, but I just want to say that Game Programming Patterns[0] is one of the finest programming books I have ever read, 100% worth reading even if you never intend to create a game. Very readable, funny, and full of wisdom. You are the man! [0] http://gameprogrammingpatterns.com/ http://gameprogrammingpatterns.com/
- yoodenvranx 9y agoYes, I can second this! Game Programming Patterns is one of my favorite programming books of the last few years.
- munificent 9y agoMine too! Though some have accused me of bias in that regard...