8 ms·
Bytecode compilers and interpreters
- tekknolagi 8y agoI wrote this to understand bytecode compilers and interpreters. Please let me know what you think!
- Impossible 8y agoI went to the same class and I just wrote a bytecode interpreter for work. This is a nice follow up I might contact you when I start work again (still on PTO).
- tekknolagi 8y agoYes, please do -- I'd be interested to hear more.
- gravypod 8y agoThis is an amazingly comprehensive writeup! Very well done. Do you intend on implementing a JIT or an optimizing compiler pass? I'd be interested in reading those posts if you eventually write them.
- tekknolagi 8y agoIf/when I get around to it, I would quite like to write posts like that. Also posts that address the ideas at the bottom of this post. Also posts that address some of the comments in this thread, like name resolution.
- bakery2k 8y agoIt's a really good article! Nothing too advanced, but concisely explains a lot of the basic concepts of both a compiler and an interpreter.
- atdt 8y agoGreat write-up, thank you! My one suggestion is that you drop the enum meta-programming; it is a distraction. Instead do what you yourself propose: use a simple class with int attributes.
- tekknolagi 8y agoYeah, that is probably the way to go. But you know how it is... I got sucked down a rabbit-hole while trying to figure out the best enum representation in Python.
- lozenge 8y agoFOO, BAR =range(2) if you're assuming python knowledge
- tekknolagi 8y agoWow, that's a pretty good one. Thank you!
- jfoutz 8y agoThis is super neat! i'd encourage anyone who liked this to check out dybvig's thesis[1] - super readable. It's neat to see how you can cleave the runtime system and compile time system. The first two chapters, at least, are pretty cool. [1] http://agl.cs.unm.edu/~williams/cs491/three-imp.pdf http://agl.cs.unm.edu/~williams/cs491/three-imp.pdf
- daxfohl 8y agoI haven't gotten through the whole thing yet but it looks great. The textbook I have now kinda stops at AST generation, so I was assuming the rest would be way more difficult than this. This makes it look manageable!
- rurban 8y agoIt's extremely primitive. Far better tutorials and bytecide designs exist, much better than those perl-, php-, python- alike bytecodes. Unfortunately only such primitive designs get written and used. SICP e.g. starts with this and then goes into its improvements, whilst better lisps or lua start with tighter opcode designs, and do proper closures and lambda lifting. python cannot even do proper lexical blocks/functions, the most important part of a interpreter/compiler design.
- abecedarius 8y agoPython has had lexical closures for many years. They're covered in my article on a bytecode compiler for Python (with code in Python): https://codewords.recurse.com/issues/seven/dragon-taming-with-tailbiter-a-bytecode-compiler https://codewords.recurse.com/issues/seven/dragon-taming-wit... It's true that Lisp is a simpler language and thus better for learning this with if you know it.
- Lerc 8y agoMay I ask how long it took you to write? Since this is the sort of post I like, I have taken to doing technical posts on a topic myself. The thing I have found is just how time consuming it is. Maybe I'm just slow at this.
- tekknolagi 8y agoI wrote it over the course of a three or four sittings, let it sit for a couple of days, then came back and revised it after sending the draft to several people. So in total a week or so?
- ris 8y agoFor part 2, try porting it to rpython and see how hard it is to turn it into a full JIT.
- tomcam 8y agoWeird. I remember the URL as bernstainbear.com...
- replol 8y agoShouldn’t have tried to wing it taking German at the same time. Quit your job and go back to school. Facebook is trash.
- tekknolagi 8y agoWell we clearly went to school together. That's not very nice.
- replol 8y agoYou are clearly passionate about this field, but you’re deceiving yourself if you think industry is where you should be. Make the world a better place.
- webkike 8y agoHaving naming be a bytecode level instruction kinda misses out on a whole level of what makes compiling interesting in my opinion. One of the challenges in compilation is to convert names to offsets representing names. This is an important optimization.
- kodablah 8y agoDepends on what you find interesting. Depending upon what you are targeting, the names can be part of the bytecode and the interesting part becomes conforming to their naming standards, preventing clashes, mangling for needed temps for synthetics/spilling/etc, and name resolution even in recursive situations.
- webkike 8y agoSure, that’s interesting in the sense that it is complicated to deal with, but these are not reasons for adding naming into the bytecode.
- tekknolagi 8y agoHey, Matt. I plan on doing that eventually. It didn't seem interesting or important enough to include in this post.
- webkike 8y agoI understand that, I’m simply pointing out I think it’s important. Great article regardless (I should add)
- tekknolagi 8y agoI'm glad you enjoyed!
- obl 8y agoSince this is intented to be educational I find it a bit unfortunate to implement function calls using the host (python) stack since it's an important part of an interpreter. It means that you can't really add things like stack traces, coroutines, exceptions, single stepping, etc and understand how they work under the hood.
- bakery2k 8y agoIsn't this how Python itself implements function calls, using the host (C) stack? Hence Python's lack of support for stackful coroutines?
- saagarjha 8y agoAren’t Python stack frames allocated on the heap, like everything else?
- ameliaquining 8y agoNo. You can try this at home: import sys sys.setrecursionlimit(2 ** 32 - 1) def recurse(): recurse() recurse() This code attempts to create unboundedly many Python stack frames. If those frames were allocated on the heap, you would expect it to either throw an exception or else display symptoms of memory exhaustion. Instead, it segfaults.
- tedunangst 8y agoDoesn't the fact that python by default has a recursion limit imply its at least doing a little extra work?
- ameliaquining 8y agoYes, but the point is that that extra work is still happening on the stack, not on the heap. Overflowing the C stack results in a segfault; exhausting heap memory doesn't.
- azhenley 8y agoFor those of you that found this interesting, I also highly recommend: Writing An Interpreter in Go [1] and Crafting Interpreters [2]. [1] https://interpreterbook.com/ https://interpreterbook.com/ [2] http://craftinginterpreters.com/ http://craftinginterpreters.com/
- cgag 8y ago+1 for crafting interpreters,I've already found knowing how to write a simple recursive descent parser useful.
- misternugget 8y agoAs the author of [1]: thanks for the shout-out! I appreciate it. And if you’re more interested in the Bytecode/VM than the tree-walking part: I wrote and published a direct sequel to the mentioned book, called Writing A Compiler In Go [0], which — just like the tutorial we’re looking at here — shows how to turn the tree-walking interpreter built in the first book into a bytecode compiler and stack-based virtual machine. [0] https://compilerbook.com https://compilerbook.com
- ainar-g 8y agoI've always wanted to know the answer from someone who actually implemented a VM: Why do people prefer stack-based VMs over register-based? They are obviously a simpler design, but register-based designs are closer to the actual machine, and I've read somewhere that register-based VMs generally perform better.
- misternugget 8y agoI wrote a longer justification for this in the introduction of the second book, but the short version is exactly what you wrote: they're easier to build. Since since the goal of the book(s) is not to show how to build production-ready, industrial-grade interpreters, but rather to learn and to understand, that was a good enough reason for me.
- codezero 8y agoHey Max! Remember drinking beer on Caltrain? Awesome to see your post on HN! Hope all is well :)
- tekknolagi 8y agoHey, John. I do remember! Still kicking around the area, though I don't much take Caltrain these days.
- hyperpallium 8y ago> Bytecode interpreters don’t work on the AST directly. They work on preprocessed ASTs. This simplifies the execution model and can produce impressive speed wins. In comparing a bytecode interpreter with an AST treewalker, and assuming parsing is not counted (i.e. we already have the AST), what makes bytecode interpreter faster? Walking a tree doesn't seem like that much of a performance penality... perhaps the "execution model" includes something else?
- viraptor 8y agoAst will usually include original/runtime names and need recursion where the bytecode is mostly flat. For example for an assignment you'll have ast like (assign (foo 5)). This will have to look up "assign", run it, look up "foo" in the frame, and assign 5 to it. All of that will operate on pointers to different parts of the heap and kill your CPU cache too. With bytecode, a lot of it will be already reduced to (for example) a machine with stack, so the assignment will be closer to: read the op (jump address in an array, so already in cache), dispatch via a small lookup table, put 5 in slot 2 (names already rewritten to stack indices) in the current frame.
- hyperpallium 8y agoThanks, cache locality makes sense. Though for looking up operators/keywords etc, preprocessing this step doesn't feel like cheating to me (though strictly, it's something more than an AST).
- mamcx 8y agoI'm thinking how viable is marry both. Make flattened AST that still allow to keep the easy of an AST walker yet with more dense representation?
- munificent 8y agoThat's basically what bytecode is. :) You can think of a stack-based bytecode as basically an in-order serialization of a tree.
- njn 8y agolol it's so cringy when tech people like this quote completely unrelated fantasy books like ursula k leguin.
- tekknolagi 8y agoOh, God forbid I share a quote I enjoyed from a book I just finished reading.
- yiransheng 8y agoOh nice. I have been writing a BASIC bytecode interpreter (and a compiler for WebAssembly)[1] in Rust. It's a bit slower to get rolling than Python - especially function value representation and dynamic dispatch, unlike Python, could not just make a callable object on the fly. Handling function/procedure calls in a stack VM is definitely a fun exercise, and there seems to be many ways to skin the cat. Shared vs. dedicated data stack across functions, adding registers (unlimited number if required) etc. [1] https://github.com/yiransheng/basic_rs https://github.com/yiransheng/basic_rs
- geocar 8y ago> Bytecode interpreters don’t work on the AST directly. They work on preprocessed ASTs. This simplifies the execution model and can produce impressive speed wins. Just executing off the parser is also a strategy. That's what some people[1] do, since you can get even more impressive speed wins by simply making small/dense programs. [1]: http://www.nsl.com/papers/origins.htm http://www.nsl.com/papers/origins.htm
- lukegru 8y agoI've followed along with the craftinginterpreters book lately, and it's been a blast. My version of clox [1] has multi-threading with a GVL, managed GC heaps, and various bytecode optimization passes. I've looked into the Ruby source code and even understand much of it now :) Future plans are to add a generational copying GC and remove the GVL ;) [1] https://github.com/luke-gru/clox https://github.com/luke-gru/clox
- munificent 8y ago> My version of clox [1] has multi-threading with a GVL, managed GC heaps, and various bytecode optimization passes. Oh, wow, you've really rocketed past the book. That's awesome!