Small correction: cpython (the python interpreter) is indeed a bytecode interpreter, so there is a compilation step that goes from AST to a bespoke bytecode instruction set. Old versions of ruby and perl are a better example for tree walking interpreters, as they run directly on the parsed AST (even though I believe modern versions also compile to bytecode for efficiency reasons)
This was really fun, personally I'd love if you added more "best practices" / convenience crates like camino etc. as I feel a lot of the educational value comes from seeing how to do things well. E.g. all the work on the Iterator that uses references to the source string is much more useful to see than just cloning the string as you go character by character.
Very cool! You inspired me to try the CodeCrafters challenge myself, and just completed the whole thing... Alas, the CodeCrafters site only goes up through basic statement evaluation with global variables, and doesn't cover the rest of the book. I suppose nothing is stopping me from continuing on myself, though. Thanks for doing this! It's fun to see how different our approaches were.
Super cool, thank you for making this! Can't wait to get through the video. I took a crack at Crafting Interpreters in Rust earlier this year, it was a lot of fun. Now I'm setting an early new year resolution to build a Hindley-Milner, LLVM based language (in Rust, of course).
Regarding the first Q&A part (about 20 minutes in), the way I'd explain bytecode is that it's machine code for an ISA that doesn't physically exist, but instead is implemented in software, and that implementation can then be through e.g. an interpreter or a JIT compiler.
Pratt parsing for statements seems like huge overkill. Just match on the first item, if it's a keyword handle that particular form, if it's not, go to (Pratt) parsing expressions. Pratt parsing's win is handling all the nesting and recursion and you have none of that at the statement or block level. Notably, there is no binding power at the expression or block level, so you don't need to pass around r_bp everywhere.
I've been playing around with a parser style where the state machine is more explicit, e.g. with immutable state and functions LexerState -> Result, and where you combine and compose those functions with monad language. Which is really cool, but then I took uncomfortably long to write out a sexp parser, and I decided I wanted to get back to the basics for a bit. Good old ~linear parsing, no big lookahead/backtracking, but still with good type safety, healthy memory idioms and good error reporting. Plus I haven't touched Rust in a while, so this video is the perfect excuse. Thanks for the videos as always, they rock -- hope we get a part 2 for this one!
What you are doing is called a parser combinator. It work and it's probably a standard to create your own parser theses days. Like most generic interface it can be tough to understand what's going on at some point. And painfull to maintain - especially when it come to error message. Bare function call with a side-effect parser is the opposite, like Jon did. They are dual to each others. I have no real preference tbh, both work equally well and have advantage/disadvantage. Using parser generator is also a solution, like yacc/bison.
@@resb64 youtube keeps deleting my comment, I think perhaps because I was linking to it. It's a short course of supplementary skills that one might not develop during an ordinary CS education but which are very useful.
The reason that the book includes the original string in every token is basically only for error reporting. With miette you handle all of the necessary state to track that during iteration, so it would probably be reasonable to only save anything for idents, numbers, and strings. With that you could keep everything in TokenKind. Actually on second thought, that doesn't really work until you get to the compile-as-you go bytecode interpreter, you lose your original place with runtime errors in the tree-walk interpreter. It could be an interesting exercise in how to make it more "rusty" if you get to the bytecode section, I guess.
The link to matklads article in the desription seems broken, I get a 404 on github pages. I think youtube parses the parenthesis as part of the link, the irony!
Around 5:00:00; parsing things like ‘for’ and function calls as a special type of operator reminds me of a more general idea from some functional programming languages - particularly interactive theorem provers like Agda and Coq - called *mixfix* operators. In that setting, you can have an operator like ‘if_then_else_’ which is a prefix operator with two ‘internal arguments’, with the positions of the arguments specified by the _’s. This isn’t something that can be handled by basic Pratt parsing though, and most of the implementations out there go the extra step of allowing user defined operators too, so it’s definitely overkill for this project!
I started reading crafting interpreters in december 2023 and I've been working on my language off and on ever since. I've parted ways with Lox ever since I read that all nimbers are floats. Still it's super helpful to see you approach the challenge and see how you do things differently. It's also amazing to see you do something perfectly from the beginning that took me miltiple attempts to get right.
@@ilyapopov823 Though it looks like it will be disabled by default for now and currently doesn't do a whole lot of optimizations yet. But definitely opens up a lot of possible performance improvements.
A really small query: when Jon said, "... as you get characters from the input you produce tokens from the output...", at ~52:22 did he mean you produce tokens for the output? Just new to this and want to make sure I haven't missed something about how input/output interact.
Yep. Tokens could be enum variants, references to the original input, etc. Maybe he meant “from” as a pipe side. Characters are taken _from_ the input and tokens are produced _from_ the output in an iterator.
1:00:29 I always thought you couldn't have multicursor in nvim? Is this a plugin? I've been using multiline selection with :s/find/replace in these cases.
It's a standard vim feature: type Ctrl-V -> select lines -> insert mode -> change the text -> Esc, after that the change is applied to all the selected lines.
Not showing a website because it’s bright and “people don’t like that” is the STUPIDEST thing I’ve heard all week. At what point did we start caring about what some small group of small-minded people prefer when they’re watching videos at 3am?
Why are you adding so much unnecessary boilerplate and being so fancy? One of the reasons I started liking zig more than rust is because I've seen in a lot of rust projects with crazy amounts of abstractions, unnecessary type wrappers and misdirections where I can barely follow the code.
4 hours in, don't see what you were talking about... I mean I personally disliked the ginormous TokenKind - I thought it may've been useful to break it up (e.g. have the MaybeEqual tokens as a separate subtype, which in turn is a variant of TokenKind), but that would actually be an _additional_ level of abstraction that I though was missing. So what exactly are you talking about?
Wtf do you even mean? There's no abstraction here, just separation of concern. Instead of just blindly complaining, give us an explaination, so we can try to figure things out. Now to the part where i state my opinion, i don't think you at the level where you can follow these kind of codes, that's why you couldn't follow it.
