I occasionally watch streams so far it was very helpful to observe how he makes design decisions, thought process and implementations.

> 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.

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

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?

The language in the book is a little scripting language, so the VM implements both allocating memory for new objects and reclaiming memory for them when no longer needed.

If you were writing something like a bytecode Pascal VM, then the VM itself wouldn't need to allocate memory outside of, say, the built in "New()" function.

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...

"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.

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.

Now, you could argue that writing to a part of the finite tape that's so far clear is "allocating memory" - but at the same time that could be a single section of statically allocated memory from the perspective of the Os that runs your vm...

For some related fun, I still think the nim "howistart" is great (but I haven't tried to follow along in a while, not sure if the code works straight away with up to date nim (but I see there's a notice mentioning a 2018 update, so I hope it's still /again working!)):

http://howistart.org/posts/nim/1/

https://github.com/howistart/howistart/pull/50/files

http://soft-dev.org/events/vmss16/

I forget what the different names he used. He distinguished between runtimes like the JVM and runtimes like Xen, which emulate an operating system too. A CPU emulator seems closer to Xen than the JVM.

-----

EDIT: The names were "system" and "process" VMs, mentioned here:

https://news.ycombinator.com/item?id=16777564

So I think you are talking about a "system VM", where this book is more about "process" VMs. They are related, but distinct -- it even says so in that book's title!

It's definitely true that in something like Xen you would want to avoid allocating memory more than in something like a JavaScript VM. (And it would be easier to avoid allocating, too.)

I don't like that terminology, but it's a useful distinction.

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.

:)

When it's finished, I'll buy a copy.

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.

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=11229975720599781...

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]

      [0x4bcf00][REG_A][2]
      [0x4bcf10][REG_A][REG_B]
      [0x4bca05]

      goto *ip;

[1] https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html

https://news.ycombinator.com/item?id=16777516

that is, "system" VMs vs. "process" VMs. I don't really like those terms, but the distinction is a good one. I think the author must have been at the VM summer school I linked there.

-----

BTW this 2015 paper is saying that the labeled gotos technique isn't a big deal on Haswell:

Branch prediction and the performance of interpreters -- Don't trust folklore

https://scholar.google.com/scholar?cluster=20257610669850946...

In other words the branch predictors improved enough on Intel such that it's not a big optimization. But I don't like how they didn't mention other CPU architectures. Intel is not all we care about!

Also, it would be nice to have an update on this 2015 paper to account for 2017-2018 Spectre/Meltdown mitigations...

on x64, token threading is

    ; goto tokens[program[ip]]
    mov r0, [program_instructions + ip]
    jmp [tokens + r0]

    ; goto program[ip]
    jmp [program_instructions + ip]

Nehalem shows a few outstanding speedups (in the 30 %– 40 % range), as well as Sandy Bridge to a lesser extent, but the average speedups (geomean of individual speedups) for Nehalem, Sandy Bridge, and Haswell are respectively 10.1 %, 4.2 %, and 2.8 % with a few outstanding values for each microarchitecture. The benefits of threaded code decreases with each new generation of microarchitecture.

but looking at the graphic, it seems a few benchmarks still had a +5% speed boost on Haswell.

It would also have been interesting if the paper provided the generated code by gcc for the switch statement. If the switch statement's cases are linear (0, 1, 2, 3, ...) and if there are more than 4 cases, then gcc token threads the code.[2]

[1] https://hg.python.org/cpython/file/v3.3.2/Python/ceval.c#l82... [2] https://godbolt.org/g/yRjFto

Thank you for the great work and can't wait for the next

Yeah. It's a real "blessing and a curse" kind of thing. :-/

I find your writing extremely clear :)

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

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_v...

Although I think they are overgeneralizing the results... you probably still want it for other architectures.

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.

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-...

Though, if you want to do this yourself, consulting those might be considered cheating. :)

Love it. Thanks.