8 ms·
A Virtual Machine
- munificent 9y agoAuthor here, and uncomfortably excited to discuss this with any and all who are interested.
- dman 9y agoWho draws the diagrams for the book? They made the book a fun read for me. Are they hand drawn?
- munificent 9y agoYou can watch me draw one of them here: https://www.youtube.com/watch?v=iN1MsCXkPSA https://www.youtube.com/watch?v=iN1MsCXkPSA :)
- dman 9y agoSpotted Lisp in Small Pieces in the background!!
- munificent 9y agoYup! That book was dense. :)
- resource0x 9y agoPossible optimization for step 1 :) http://tommaitland.net/graphpaper/ http://tommaitland.net/graphpaper/
- munificent 9y agoI have thought about doing the initial sketch digitally, but I think it's actually a little faster to do it on paper. I could be wrong.
- jwdunne 9y agoThats an awesome attention to detail. It looks like a lot of work on top of writing a book. It feels like a great debt is owed for the amount of work that's gone into something I can essentially enjoy for free. When it's finished, I'll buy a copy.
- joe_the_user 9y agoOne quick question. You talk about a VM allocating memory. In the process of constructing my own simple-as-possible VM, I figured allocation would be done by the routines involved, with the VM just providing CPU-like facilities for accessing raw memory. What are the advantages of a VM allocating memory?
- chubot 9y agoWe just discussed one aspect of this here: https://www.reddit.com/r/programming/comments/8a9zhz/implementing_a_stackbased_vm_in_c_part_of/dwxg5jp/?context=3 https://www.reddit.com/r/programming/comments/8a9zhz/impleme... There is no real way for the VM to avoid dynamically allocating memory. At the very least, you have to allocate call frames (even if you know their size statically). Maybe the only way around this is if you restrict arbitrary recursion in the language. EDIT: Hm from the reply to that I was somewhat wrong...
- joe_the_user 9y agoThanks for the answer. "No real way" is relative, of course. I happen to have constraints pushing for a VM as small as conceivably possible without code-blow-up, like single-instruction VM but implementing most logic/arithmetic primitives. But which parts are dicier than others is worth considering.
- chubot 9y agoYeah I was a little wrong, and I edited my comment. But I am still confused by your question. There are lots of places where you might need to allocate memory -- it depends on the semantics of your source language, and it depends what you consider part of the VM proper, etc. It sounds like you are describing something with more primitive types, like a CPU emulator or WebAssembly, rather than a dynamic language VM, which is the subject of this book.
- joe_the_user 9y agoSure, that explains it. The VM has to allocate memory if it's interpreting a dynamic language. Sorry if the question was elementary.
- yoodenvranx 9y agoI have nothing to discuss but I wanna say that I loved Game Programming Patterns and I am really looking forward to read Crafting Interpreters!
- munificent 9y agoThank you!
- chubot 9y agoOne thing that popped into my mind recently, as I've been going back and forth between implementing my own stack machine interpreter and forking the Python VM (for the Oil shell). What other books cover bytecode interpreters? (In other words, the part of the book that you are 2 chapters into.) I can't think of any! Many people learn about the front end in a "compilers" class. The Dragon Book and "Modern Compiler Implementation in X" are two of the most popular books, but they don't cover interpreters at all. The other branch people learn about is Lisp interpreters, which are often tree intepreters (as in the first section of your book). And when they are bytecode interpreters, I think they have a compilation process that's fairly different from say Python/Lua/JavaScript. For example the "nanopass" style is somewhat popular for teaching, and pretty different from what I understand. The source language is further from the machine model. It seems like the best sources are the Lua papers you mentioned, but I would call those primary sources. I can't think of any "secondary sources". Terrence Parr's Language Implementation Pattern does part of a bytecode interpreter, but it's in Java, and it leaves out the bytecode compiler as far as I remember. So somewhat surprisingly I think everybody who implements bytecode VMs these days just looks at Lua and Python? I guess Lua was influenced heavily by Scheme, and I don't know where Python got its implementation style, maybe from the ABC precursor. Anyway I'd be interested in hearing about other sources (primary and secondary), but it dawned on me that this is the ONLY full bytecode interpreter I've seen in a textbook. And I have a whole bunch of books and have been doing this for a few years. So if that's the case, then kudos for filling this gap! :) EDIT: A primary source that has been useful for me is The ZINC experiment: an economical implementation of the ML language, which is a description of the predecessor to OCaml (both written by Xavier Leroy). Although OCaml is statically typed and functional, the bytecode interpreter itself has some similarities to Python/Lua. They mention keeping your top-of-stack register in a CPU register, the relationship between runtime values and garbage collection, etc. The book "Real World OCaml" reviews a little of this material. https://scholar.google.com/scholar?cluster=11229975720599781276&hl=en&as_sdt=2005&sciodt=0,5 https://scholar.google.com/scholar?cluster=11229975720599781...
- CodeArtisan 9y agoVirtual Machines: Versatile Platforms for Systems and Processes covers both virtual machines for implementing programming languages and virtual machines for emulating cpu architectures. One of my favorite optimization techniques explained in this book is pre-decoding: After loading the program's instructions, every opcode is replaced by the address of the corresponding routine implementing the instruction. For example, [OP_ADD][REG_A][2] [OP_MUL][REG_A][REG_B] [OP_RET] become [0x4bcf00][REG_A][2] [0x4bcf10][REG_A][REG_B] [0x4bca05] Then, using goto from GNU C[1], decoding is now just goto *ip; I think this is still the state-of-art technique for interpreting instructions. [1] https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html
- coldtea 9y agoThis is probably the clearest programming tutorial I've ever read...
- metaobject 9y agoVery clear presentation. Helpful diagrams. Clean code. This has a very “Linkers and Loaders” (John Levine) feel to it. Very well done.
- carussell 9y agoYou should drop a note on your blog about the new chapter(s). I'm subscribed to your blog's RSS, but not the one for craftinginterpreters.com—because a feed for the latter doesn't actually exist.
- munificent 9y agoI think I used to do that for my first book, ages ago, but these days it seems like not many people are using RSS. Interestingly enough, I did just start using RSS again myself recently. Posting on my blog feels kind of heavyweight for this, though. Do you do email? If so, subscribing to the mailing list is a good way to get notified. I only use the list for new chapters and other "major announcement" stuff like that, so it's not spammy.
- carussell 9y agoI didn't mean to suggest you do this for every chapter. Just something in the vein of, "In case you haven't been following along already, since I last blogged, I've completed several chapters of Crafting Interpreters."
- bogomipz 9y agoI just wanted to say how much I've enjoyed following this. I get excited when there's an update. Looking forward to reading this update over the weekend. PS have you ever considered doing some accompanying video presentation when you the book is completed? Cheers.
- munificent 9y agoI did make a little video showing how the illustration is done, but in general, no. I barely have enough time to write the book, and video production (at least for my perfectionist self) is very time-consuming.
- 323454 9y agoThis is one of the prettiest online books about computing that I've ever seen. I really appreciate how much effort you have put in to making the layout clean and the styling enjoyable to look at. Great visual presentation can really take a load off the reader's brain, leaving more cycles to think about the actual content. Bravo!
- munificent 9y agoThank you! I used to be a graphic designer and web designer before I went more left brain. I put a lot of love and time into the design. It's fully responsive, which is nice, but the part I really like is that the whole page fits into an invisible grid system. All of the columns, line heights, spacing between paragraphs, everything (well, except the illustrations...). It took forever, but I think it helps give the page a harmonious visual cadence. > Great visual presentation can really take a load off the reader's brain, leaving more cycles to think about the actual content. Bravo! Yes, I totally agree. Design is how we get information through our physical senses into our brain. There's no shortcut to skip past the eyes and ears, so you have to put care into the transmission medium if you want the signal to get through effectively.
- acqq 9y agoI was especially glad to see the carefully hand-drawn diagrams. Thanks for that.
- Kagerjay 9y agoWhat are you using to do put the code snippets up? Some parts are greyed out but the most important points stand out Ive been looking for something like hightlightjs that does this, otherwise i intended forking my own version of it and using | | piping to highlight important snippets
- freecodyx 9y agoI follow you on twitter and get excited whenever there is an update. but man you are very perfectionist Thank you for the great work and can't wait for the next
- munificent 9y ago> but man you are very perfectionist Yeah. It's a real "blessing and a curse" kind of thing. :-/
- imdsm 9y agoLooking forward to reading through this. Thoroughly enjoyed Game Programming Patterns, in particular your style of adding comments to the side.
- elderK 9y agoHey Munificient, I just wanted to say that I'm a major fan of your book. I find your writing extremely clear :)
- kiddico 9y agoThis whole book looks like a good read! I'll have to check it out later when I have some time.
- 52-6F-62 9y agoCount me in, too! This goes right along with a lot of stuff I'm working on teaching myself right now.
- runevault 9y agoI'm up to the chapter in part 1 on Classes and it has been a great experience for reminding me how compilers work. Personally I recommend intentionally doing it in a language other than Java just to force the extra step of transliterating in your head, at least for me it has made the learning process much stronger.
- munificent 9y agoYeah, I totally agree with that suggestion. Even handing typing in the code samples yourself instead of just reading them can help you get out of the "skimming" mindset and into really internalizing each step. If you're curious people have ported the code in the book to a lot of languages. Some of them are here: https://github.com/munificent/craftinginterpreters/wiki/Lox-implementations https://github.com/munificent/craftinginterpreters/wiki/Lox-... Though, if you want to do this yourself, consulting those might be considered cheating. :)
- GeertVL 9y agoI am doing the same in Rust (a new language for me) and OCaml (known a little bit). It forces you to find different solutions and you learn new languages at the same time. Love it. Thanks.
- the_arun 9y agoWhat is the software this site is made of? Wordpress? GitHub pages? or Custom? It looks so cool. I am interested to know the details
- ythn 9y agohttps://builtwith.com/ https://builtwith.com/
- colonelxc 9y agoAll source is here. https://github.com/munificent/craftinginterpreters https://github.com/munificent/craftinginterpreters
- the_arun 9y agoThanks!
- munificent 9y agoJust a handful of Python scripts: https://github.com/munificent/craftinginterpreters/tree/master/util https://github.com/munificent/craftinginterpreters/tree/mast... The book is written in Markdown. The code samples are stored in separate files so that I can compile and test them. The code has little comment markers identifying where each chunk of code goes in the book, and the build script weaves it all together.
- UncleEntity 9y ago> Alas, the fastest [dispatching] solutions require either non-standard extensions to C, or hand-written assembly code. I assume gcc's label addresses[0]. I've been planning to try those out the next time I get around to playing with minischeme to see just how much of a speed difference they make -- I'd imagine quite a bit since it could just hop around from opcode to opcode instead of having to go through the loop (which I believe is outside the dispatching function). It's funny, searched the google to see if clang supported this and the top result (from stackoverflow) has the comment "This is terrible coding style. Why don't you use a switch or a function table. If you really want such code, you should goto 70ies/80ies BASIC." [0]https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html
- chubot 9y agoI cited a paper here that says this is of limited value on modern Intel CPUs: https://news.ycombinator.com/item?id=16777564 https://news.ycombinator.com/item?id=16777564 Although I think they are overgeneralizing the results... you probably still want it for other architectures.
- munificent 9y ago> I assume gcc's label addresses[0]. Yes, that's definitely the main one I had in mind. > I've been planning to try those out the next time I get around to playing with minischeme to see just how much of a speed difference they make I added support for computed gotos to my bytecode interpreter for Wren and, if I recall, it gave about a 10% speed boost on my (mostly micro-) benchmarks. YMMV. https://github.com/munificent/wren/blob/master/src/vm/wren_vm.c#L815 https://github.com/munificent/wren/blob/master/src/vm/wren_v...
- morazow 9y agoIf anyone is interested on making compilers / programming languages, there is another recent initiative from Per Vognsen, Bitwise: https://github.com/pervognsen/bitwise https://github.com/pervognsen/bitwise. I occasionally watch streams so far it was very helpful to observe how he makes design decisions, thought process and implementations.
- ryanmccullagh 9y agoHaving been researching process VMs for a few years now, most tutorial miss a crucial piece: the garbage collector.