6 ms·

Crafting Interpreters: Calls and Functions

172 points by azhenley 7y ago

munificent 7y ago
Author here. Feels good to be one chapter closer to the end. Only six more to go!
- chrisaycock 7y ago
  I saw from your most recent email that this book will be longer than Moby Dick. I've been following your progress since the beginning and I really appreciate the work you've done. Crafting Interpreters was really helpful for me when I began building my own language.
  - munificent 7y ago
    That's great to hear! I sure as hell wasn't planning to write an epic when I started, but here we are.
    - marai2 7y ago
      "Call me Ishmael..." has to be in the epigraph of this book!
- danso 7y ago
  I love it so far and can't wait to buy it, even as I've gone through what you've posted so far. I was curious about your rate of progress in this phase (and over the past years). Have you found the rate of progress (the demands of job and real life aside) on the book to be relatively constant? Are the final chapters significantly harder to draft and write based on complexity? (as a relative layperson, I'm assuming describing the design and implementation of garbage collection is more involved than for common data structures)
  - munificent 7y ago
    The difficulty of the chapters themselves is almost perfectly flat. I wrote every single line of code for the book and split it out into chapters before I started writing any prose. I can tell you, today, exactly which lines of code need to be explained in the very last chapter, and I could have done that three years ago when I started writing the text for chapter one. (In fact, if you clone the repo and run the build script, you can see for yourself.) Writing did get somewhat harder when I transitioned from part 1 (the Java interpreter) to part 2 (the C VM). C is a more finicky language in a lot of ways. Things like the order of declarations matter. So figuring out which order to introduce snippets of code within a single chapter tends to take a little longer, but it's not a big difference. My rate of progress has generally slowed over the past few years, for a lot of reasons. My initial enthusiasm has naturally waned. There isn't much novelty left in the project for me — writing each chapter is much like writing the previous one. So it's mostly an exercise in discipline now. Meanwhile, of course, I keep stumbling into other new things that I am excited about, so staying focused is hard. The last few years have also been personally difficult for me in a number of ways. My mother got cancer (in remission now!), two family members died, two friends died, my dog (the one on the back cover of my previous book) was in ill health for a long time and then had to be put down. Lots of other personal stuff like that. 2018 was one of the worst years of my life, even though I'm still very fortunate in many ways. But through all of that, I've managed to keep going. I work on the book every day, so I worked on it in the hospital waiting room while my mom got a CAT scan. I wrote a measly 59 words the night after we put down my dog. I wrote in the hotel before my friend's memorial service and on an airplane on the way back from my aunt's funeral. In some ways, the project is a constant comfort in my life, and it's also taught me a lot about the power of perserverance and discipline. I'm really looking forward to it being done and taking a long break. But I'm also looking forward to seeing what I'll be able to do with this discipline next.
    - ekez 7y ago
      As someone who's been working through the book for the last few months, thanks so much for sticking with it. Your prose is excellent and full of really properly funny stuff sometimes. Reading your book has been my weekly dose of programming I know I'll enjoy.
- shortercode 7y ago
  Looking forward to seeing it complete! I got into programming languages after reading Game programming patterns, and I'm absolutely hooked. When I saw you were working on this book I worked through the first half of it in a week using JS, loved it. I started the second half in Rust about a week ago, I don't have enough vacation days to work through it at the pace I did the first half. Finding it a bit harder so far, but I think that's just because I'm still new at Rust. You may have already mentioned this but will you be publishing a physical copy when your done? I'd love to get one for the shelf.
  - munificent 7y ago
    > You may have already mentioned this but will you be publishing a physical copy when your done? Yes. Just like with "Game Programming Patterns", once the chapters are done, I'll put together a print edition, eBook, Kindle, etc. Based on the length, I may end up doing it as two separate volumes, which is crazy to think about.
    - Technetium_Hat 7y ago
      If it is to be 2 separate volumes, would the first volume, ie jlox, be ready to publish already?
      - munificent 7y ago
        It's written, but there's still a lot of work to publish it: copy-editing, page layout, cover design, etc. I don't want to get distracted by that until all of the chapters are done.
- __ryan__ 7y ago
  Very excited to buy the book once it's finished as well. I discovered the series after I stumbled upon Luxe during my Haxe development days. *Off topic: Very excited for Luxe 1.0 and Wren as well.
  - munificent 7y ago
    Me too! The maintainer of Luxe (and now Wren that I've passed the torch) is fantastic and I'm really excited about the future of both of them.
- kyllo 7y ago
  This book is an _epic_ contribution to the field. I've learned a ton from it myself. I had gone through several other tutorials on how to write a parser, but I just wasn't getting how recursive descent works, and yours was the one that finally made me understand it. Thank you so much for writing it!
bbmario 7y ago
I'm excited about the arrays/objects part. :)
codr7 7y ago
I'm all for more people creating their own languages, we've been riding on Lisp for quite a while now and I'm sure that's not the final answer to anything. Didn't read this one, I don't have much time to read these days. But we definitely need more hands on practical information to counter the avalanche of academic fluff out there, and many seem to enjoy Crafting Interpreters. Having spent 34 years writing code and around three years full time designing my own languages, most other kinds of code make me fall asleep sitting up these days. Nothing really compares to controlling your world from the outside. Lately I've been working on a stack machine devkit [0] to use as foundation for new languages, providing convenient access to most of what's needed and an integrated assembler to control it from the outside. The general idea is that you link the library and hook in a custom reader for your syntax, possibly embedded as a separate opcode. It's 5kloc of reasonable MIT-licensed code, small enough to own. Feel free to have a look and I'll try to answer any questions. [0] https://github.com/codr7/cidk https://github.com/codr7/cidk Edit: Was it the academic toes? Because I'm just sharing some code I wrote to help people get started designing their own languages. What did you do for others without expecting anything in return lately?
- sctb 7y ago
  Re your edit: you said that you didn't read the article and then started talking about yourself, which is rude. https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
  - codr7 7y ago
    You're projecting your self-obsession, I was sharing my excitement for the subject and offering a stepping stone for those who still hesitate. Judging is a waste of time, it's always more about you than anything else. And rude, since you have no idea about other people's motivations.
- danso 7y ago
  I upvoted (and vouched, and starred the repo – thanks for sharing!), but I'm guessing you were downvoted because the first 2 grafs are easily misinterpreted as falling into the "I didn't read, but why is this thing necessary?" trope. Deleting the 2nd graf would probably change the perception; it doesn't add any insight, and honestly, no one expects you or any commenter to have read the entire book before remarking on it.
jihadjihad 7y ago
What I love most about this project is that it takes a subject that I've historically thought of as "magic" and plainly lays out the logic behind the curtains. I didn't study computer science in college but have become fascinated by it, and this book is an accessible, well-designed, and well-written resource on a dense and deep topic. Terrific work.
- munificent 7y ago
  Thank you! Dispelling the magic is my primary goal with the book. Like you, I don't have a CS degree and find a number of topics like this to be intimidating. So my hope is that readers will come away from this both knowing more about languages and also less afraid of diving into other topics that seem scary.
  - jchook 7y ago
    Thanks to your book I overcame my fear of formal grammars and wrote three essential LL(1) parsers for my latest project. Where before I haphazardly ignored features like quoted strings or escaped characters, I now have extremely high confidence in my parsers’ completeness and correctness. Also the error reporting rocks and the code is easy to read! Thank you!!!
    - danso 7y ago
      If you are at liberty to share, were these parsers for a specific domain? I'm curious about how to decide when creating a domain-specific grammar/language is worth it for any given project.
      - jchook 7y ago
        In my case I basically just transliterated RFC XXXX grammars from ABNF to code. I ended up really enjoying it. I have seen problems that probably do merit a special DSL or language, though I find it somewhat unfortunate if you need such a thing. One example that comes to mind, Soul lang: https://news.ycombinator.com/item?id=19791154 https://news.ycombinator.com/item?id=19791154
danso 7y ago
Tangent: I was really impressed with how you've made your own book-building script [0], which I assume you found comfortable iterate off of from your previous book [1]. Can't argue with the results, but did you ever look into other bookmaking frameworks (e.g. sphinx, knitpy, knotr, R's bookdown)? Or did your custom script already feel feature-complete for the way you think and work when organizing book content? [0] https://github.com/munificent/craftinginterpreters/blob/master/util/build.py https://github.com/munificent/craftinginterpreters/blob/mast... [1] https://github.com/munificent/game-programming-patterns/blob/master/script/format.py https://github.com/munificent/game-programming-patterns/blob...
- munificent 7y ago
  > I was really impressed with how you've made your own book-building script [0], which I assume you found comfortable iterate off of from your previous book [1]. Yup, though I ended up significantly expanding it over time. This book is a lot more complex because the snippets interact across chapters. Also, I wanted the ability to test the code as it exists at different points in the book. > but did you ever look into other bookmaking frameworks Briefly, yes. But, in general, I'm not much of a "framework" person. I'd rather spend time rolling my own thing than reading docs or fighting with the limitations of some other framework. Of course, doing it from scratch can be a large undertaking, but I think people often overestimate the effort of writing bespoke software. The build script for my book is not a general-purpose build system for generating book sites. It is literally hard-coded to be used for only one single book on Earth. That makes it much simpler. It doesn't need extensibility or configurability. It has nothing like an "API" or even docs or tests. The output is its tests — if I like the resulting HTML, the build script is by definition working correctly. It's also easy to add hacks in there that only make sense for the book, like: # The "(?!-)" is a hack. scanning.md has an inline code sample containing a # "--" operator. We don't want that to get matched, so fail the match if the # character after the "-- " is "-", which is the next character in the code # sample. EM_DASH_PATTERN = re.compile(r'\s+--\s(?!-)') If I was trying to make a general purpose book-building framework, I'd have to design some elegant or extensible solution for escaping or recognizing false positives in the code that converts `--` to em dashes. But because this is just a bespoke script, I can just toss a hack in and be done with it.
ufo 7y ago
I work with programming languages, interpreters and compilers for my PHD and I have to say that this ongoing book is one of the best introductions to the topic that I have seen. It is both well written and knowledgeable. Even if you don't think the whole book is for you, I recommend checking out the introduction sections. Or at least just the discussion on the terminology of "interpreter" vs "compiler". https://craftinginterpreters.com/introduction.html https://craftinginterpreters.com/introduction.html https://craftinginterpreters.com/a-map-of-the-territory.html https://craftinginterpreters.com/a-map-of-the-territory.html
alex_marchant 7y ago
I've tried a couple of other introductions to building a programming language and this is hands down the best. The care and attention to detail that has gone into this book are incredible. Thank you @munificent.
smueller1234 7y ago
"If we store the ip directly in a C local variable and mark it register, there’s a good chance the C compiler will accede to our polite request." Hmm. I may be getting rusty, but do modern compilers actually still pay attention to the "register" keyword? Also, I may have read this too quickly, but if I'm not mistaken you limit the number of parameters to 8, yet the number of arguments passed to 255. Does that make sense? Thank you once again for a brilliant read!
- munificent 7y ago
  > do modern compilers actually still pay attention to the "register" keyword? You know, I'm honestly not sure. If nothing else, it sends a signal to human readers of the code. > if I'm not mistaken you limit the number of parameters to 8, yet the number of arguments passed to 255. You are not mistaken. I changed the limit, but missed that part. Filed an issue to fix this: https://github.com/munificent/craftinginterpreters/issues/468 https://github.com/munificent/craftinginterpreters/issues/46... Thank you!
  - smueller1234 7y ago
    Quick search, first hit: https://stackoverflow.com/questions/10675072/is-the-register-keyword-still-used https://stackoverflow.com/questions/10675072/is-the-register... I know, hardly authoritative. But it matches precisely what I remember from when I was hacking on perl with an eye to performance at the time. Maybe drop that bit regarding 'register'? The rest of that section is still perfectly valid. That is, assuming the compiler doesn't actually perform the local variable/keep in register optimisation itself, but I think it can't do that at least in the general case. I only remember vague things about this. At least aliasing may defeat the compiler optimisation. Caveat: Like yourself, I picked this stuff up without studying it as part of a degree. Anybody with a proper compiler background want to jump in and enlighten maybe?

172 points by azhenley 7y ago

munificent 7y ago

Author here. Feels good to be one chapter closer to the end. Only six more to go!

chrisaycock 7y ago
I saw from your most recent email that this book will be longer than Moby Dick. I've been following your progress since the beginning and I really appreciate the work you've done. Crafting Interpreters was really helpful for me when I began building my own language.
- munificent 7y ago
  That's great to hear! I sure as hell wasn't planning to write an epic when I started, but here we are.
  - marai2 7y ago
    "Call me Ishmael..." has to be in the epigraph of this book!
danso 7y ago
I love it so far and can't wait to buy it, even as I've gone through what you've posted so far. I was curious about your rate of progress in this phase (and over the past years). Have you found the rate of progress (the demands of job and real life aside) on the book to be relatively constant? Are the final chapters significantly harder to draft and write based on complexity? (as a relative layperson, I'm assuming describing the design and implementation of garbage collection is more involved than for common data structures)
- munificent 7y ago
  The difficulty of the chapters themselves is almost perfectly flat. I wrote every single line of code for the book and split it out into chapters before I started writing any prose. I can tell you, today, exactly which lines of code need to be explained in the very last chapter, and I could have done that three years ago when I started writing the text for chapter one. (In fact, if you clone the repo and run the build script, you can see for yourself.) Writing did get somewhat harder when I transitioned from part 1 (the Java interpreter) to part 2 (the C VM). C is a more finicky language in a lot of ways. Things like the order of declarations matter. So figuring out which order to introduce snippets of code within a single chapter tends to take a little longer, but it's not a big difference. My rate of progress has generally slowed over the past few years, for a lot of reasons. My initial enthusiasm has naturally waned. There isn't much novelty left in the project for me — writing each chapter is much like writing the previous one. So it's mostly an exercise in discipline now. Meanwhile, of course, I keep stumbling into other new things that I am excited about, so staying focused is hard. The last few years have also been personally difficult for me in a number of ways. My mother got cancer (in remission now!), two family members died, two friends died, my dog (the one on the back cover of my previous book) was in ill health for a long time and then had to be put down. Lots of other personal stuff like that. 2018 was one of the worst years of my life, even though I'm still very fortunate in many ways. But through all of that, I've managed to keep going. I work on the book every day, so I worked on it in the hospital waiting room while my mom got a CAT scan. I wrote a measly 59 words the night after we put down my dog. I wrote in the hotel before my friend's memorial service and on an airplane on the way back from my aunt's funeral. In some ways, the project is a constant comfort in my life, and it's also taught me a lot about the power of perserverance and discipline. I'm really looking forward to it being done and taking a long break. But I'm also looking forward to seeing what I'll be able to do with this discipline next.
  - ekez 7y ago
    As someone who's been working through the book for the last few months, thanks so much for sticking with it. Your prose is excellent and full of really properly funny stuff sometimes. Reading your book has been my weekly dose of programming I know I'll enjoy.
shortercode 7y ago
Looking forward to seeing it complete! I got into programming languages after reading Game programming patterns, and I'm absolutely hooked. When I saw you were working on this book I worked through the first half of it in a week using JS, loved it. I started the second half in Rust about a week ago, I don't have enough vacation days to work through it at the pace I did the first half. Finding it a bit harder so far, but I think that's just because I'm still new at Rust. You may have already mentioned this but will you be publishing a physical copy when your done? I'd love to get one for the shelf.
- munificent 7y ago
  > You may have already mentioned this but will you be publishing a physical copy when your done? Yes. Just like with "Game Programming Patterns", once the chapters are done, I'll put together a print edition, eBook, Kindle, etc. Based on the length, I may end up doing it as two separate volumes, which is crazy to think about.
  - Technetium_Hat 7y ago
    If it is to be 2 separate volumes, would the first volume, ie jlox, be ready to publish already?
    - munificent 7y ago
      It's written, but there's still a lot of work to publish it: copy-editing, page layout, cover design, etc. I don't want to get distracted by that until all of the chapters are done.
__ryan__ 7y ago
Very excited to buy the book once it's finished as well. I discovered the series after I stumbled upon Luxe during my Haxe development days. *Off topic: Very excited for Luxe 1.0 and Wren as well.
- munificent 7y ago
  Me too! The maintainer of Luxe (and now Wren that I've passed the torch) is fantastic and I'm really excited about the future of both of them.
kyllo 7y ago
This book is an _epic_ contribution to the field. I've learned a ton from it myself. I had gone through several other tutorials on how to write a parser, but I just wasn't getting how recursive descent works, and yours was the one that finally made me understand it. Thank you so much for writing it!

bbmario 7y ago

I'm excited about the arrays/objects part. :)

codr7 7y ago

I'm all for more people creating their own languages, we've been riding on Lisp for quite a while now and I'm sure that's not the final answer to anything. Didn't read this one, I don't have much time to read these days. But we definitely need more hands on practical information to counter the avalanche of academic fluff out there, and many seem to enjoy Crafting Interpreters. Having spent 34 years writing code and around three years full time designing my own languages, most other kinds of code make me fall asleep sitting up these days. Nothing really compares to controlling your world from the outside. Lately I've been working on a stack machine devkit [0] to use as foundation for new languages, providing convenient access to most of what's needed and an integrated assembler to control it from the outside. The general idea is that you link the library and hook in a custom reader for your syntax, possibly embedded as a separate opcode. It's 5kloc of reasonable MIT-licensed code, small enough to own. Feel free to have a look and I'll try to answer any questions. [0] https://github.com/codr7/cidk https://github.com/codr7/cidk Edit: Was it the academic toes? Because I'm just sharing some code I wrote to help people get started designing their own languages. What did you do for others without expecting anything in return lately?

sctb 7y ago
Re your edit: you said that you didn't read the article and then started talking about yourself, which is rude. https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
- codr7 7y ago
  You're projecting your self-obsession, I was sharing my excitement for the subject and offering a stepping stone for those who still hesitate. Judging is a waste of time, it's always more about you than anything else. And rude, since you have no idea about other people's motivations.
danso 7y ago
I upvoted (and vouched, and starred the repo – thanks for sharing!), but I'm guessing you were downvoted because the first 2 grafs are easily misinterpreted as falling into the "I didn't read, but why is this thing necessary?" trope. Deleting the 2nd graf would probably change the perception; it doesn't add any insight, and honestly, no one expects you or any commenter to have read the entire book before remarking on it.

jihadjihad 7y ago

What I love most about this project is that it takes a subject that I've historically thought of as "magic" and plainly lays out the logic behind the curtains. I didn't study computer science in college but have become fascinated by it, and this book is an accessible, well-designed, and well-written resource on a dense and deep topic. Terrific work.

munificent 7y ago
Thank you! Dispelling the magic is my primary goal with the book. Like you, I don't have a CS degree and find a number of topics like this to be intimidating. So my hope is that readers will come away from this both knowing more about languages and also less afraid of diving into other topics that seem scary.
- jchook 7y ago
  Thanks to your book I overcame my fear of formal grammars and wrote three essential LL(1) parsers for my latest project. Where before I haphazardly ignored features like quoted strings or escaped characters, I now have extremely high confidence in my parsers’ completeness and correctness. Also the error reporting rocks and the code is easy to read! Thank you!!!
  - danso 7y ago
    If you are at liberty to share, were these parsers for a specific domain? I'm curious about how to decide when creating a domain-specific grammar/language is worth it for any given project.
    - jchook 7y ago
      In my case I basically just transliterated RFC XXXX grammars from ABNF to code. I ended up really enjoying it. I have seen problems that probably do merit a special DSL or language, though I find it somewhat unfortunate if you need such a thing. One example that comes to mind, Soul lang: https://news.ycombinator.com/item?id=19791154 https://news.ycombinator.com/item?id=19791154

danso 7y ago

Tangent: I was really impressed with how you've made your own book-building script [0], which I assume you found comfortable iterate off of from your previous book [1]. Can't argue with the results, but did you ever look into other bookmaking frameworks (e.g. sphinx, knitpy, knotr, R's bookdown)? Or did your custom script already feel feature-complete for the way you think and work when organizing book content? [0] https://github.com/munificent/craftinginterpreters/blob/master/util/build.py https://github.com/munificent/craftinginterpreters/blob/mast... [1] https://github.com/munificent/game-programming-patterns/blob/master/script/format.py https://github.com/munificent/game-programming-patterns/blob...

munificent 7y ago
> I was really impressed with how you've made your own book-building script [0], which I assume you found comfortable iterate off of from your previous book [1]. Yup, though I ended up significantly expanding it over time. This book is a lot more complex because the snippets interact across chapters. Also, I wanted the ability to test the code as it exists at different points in the book. > but did you ever look into other bookmaking frameworks Briefly, yes. But, in general, I'm not much of a "framework" person. I'd rather spend time rolling my own thing than reading docs or fighting with the limitations of some other framework. Of course, doing it from scratch can be a large undertaking, but I think people often overestimate the effort of writing bespoke software. The build script for my book is not a general-purpose build system for generating book sites. It is literally hard-coded to be used for only one single book on Earth. That makes it much simpler. It doesn't need extensibility or configurability. It has nothing like an "API" or even docs or tests. The output is its tests — if I like the resulting HTML, the build script is by definition working correctly. It's also easy to add hacks in there that only make sense for the book, like: # The "(?!-)" is a hack. scanning.md has an inline code sample containing a # "--" operator. We don't want that to get matched, so fail the match if the # character after the "-- " is "-", which is the next character in the code # sample. EM_DASH_PATTERN = re.compile(r'\s+--\s(?!-)') If I was trying to make a general purpose book-building framework, I'd have to design some elegant or extensible solution for escaping or recognizing false positives in the code that converts `--` to em dashes. But because this is just a bespoke script, I can just toss a hack in and be done with it.

ufo 7y ago

I work with programming languages, interpreters and compilers for my PHD and I have to say that this ongoing book is one of the best introductions to the topic that I have seen. It is both well written and knowledgeable. Even if you don't think the whole book is for you, I recommend checking out the introduction sections. Or at least just the discussion on the terminology of "interpreter" vs "compiler". https://craftinginterpreters.com/introduction.html https://craftinginterpreters.com/introduction.html https://craftinginterpreters.com/a-map-of-the-territory.html https://craftinginterpreters.com/a-map-of-the-territory.html

alex_marchant 7y ago

I've tried a couple of other introductions to building a programming language and this is hands down the best. The care and attention to detail that has gone into this book are incredible. Thank you @munificent.

smueller1234 7y ago

"If we store the ip directly in a C local variable and mark it register, there’s a good chance the C compiler will accede to our polite request." Hmm. I may be getting rusty, but do modern compilers actually still pay attention to the "register" keyword? Also, I may have read this too quickly, but if I'm not mistaken you limit the number of parameters to 8, yet the number of arguments passed to 255. Does that make sense? Thank you once again for a brilliant read!

munificent 7y ago
> do modern compilers actually still pay attention to the "register" keyword? You know, I'm honestly not sure. If nothing else, it sends a signal to human readers of the code. > if I'm not mistaken you limit the number of parameters to 8, yet the number of arguments passed to 255. You are not mistaken. I changed the limit, but missed that part. Filed an issue to fix this: https://github.com/munificent/craftinginterpreters/issues/468 https://github.com/munificent/craftinginterpreters/issues/46... Thank you!
- smueller1234 7y ago
  Quick search, first hit: https://stackoverflow.com/questions/10675072/is-the-register-keyword-still-used https://stackoverflow.com/questions/10675072/is-the-register... I know, hardly authoritative. But it matches precisely what I remember from when I was hacking on perl with an eye to performance at the time. Maybe drop that bit regarding 'register'? The rest of that section is still perfectly valid. That is, assuming the compiler doesn't actually perform the local variable/keep in register optimisation itself, but I think it can't do that at least in the general case. I only remember vague things about this. At least aliasing may defeat the compiler optimisation. Caveat: Like yourself, I picked this stuff up without studying it as part of a degree. Anybody with a proper compiler background want to jump in and enlighten maybe?