Alternatives to stack-based VM for an interpreter

Question

When building an interpreter for another language, it's often recommended to create a stack-based virtual machine that can interpret bytecode generated by the actual interpreter. The interpreter would then consist of two parts: the translator, which converts the instructions from the high-level language into bytecode for the virtual machine, and the virtual machine itself.

My question is this: what alternatives exist for interpreted languages? For example, is it possible (and practical) to skip the virtual machine, and implement all instructions using functions in C? Up to a point, it seems to me this should be possible, but maybe you'd end up implementing a minimal VM of some sort anyway for more complex functionality. Are there any other options?

Answer 1

It's recommended to make a stack-based VM because they are simple to make.

The other common type of VM are register-based, where values are stored in in registers instead of on a stack.

There are also many other variants of interpreters and virtual machines. You can have a compiler which generates parse trees, and an interpreter that interprets these (but if it's implemented using recursive functions, it could be argued it's still a stack-based VM).

---

It also not uncommon to make compilers that instead of generating machine-code of some sort (for a VM or for a real machine) to generate code for another language. C is a common destination language for those types of compilers, as the C language and its compilers are ubiquitous. But then you don't have a VM or interpreter anymore, you just have a compiler/translator.

Answer 2

What you suggest is sort of possible. C doesn't really let you manipulate the stack, and when you call a function, it doesn't know about the local variables around it, so you'd need to allocate a block of memory on the heap to keep some fake "stack space" that you use for your scripting language's local variables, and pass that into each function (or stuff it into a thread-global). You'd also need a base pointer for that stack for your scripting language's function calls.

Once you're doing that, you've already done most of what you'd do to get a stack-based language. So you might as well do the rest. To use the actual stack and base pointer for this, you would have to drop down to a machine language level.

If your language is register-based, it still needs a stack for accessing local variables (it just uses it less often), you just don't use it for instruction parameters as much. If I may criminally simplify, 3-address-register-based VMs are kind of a special case of a stack-based VM.

Another approach for bytecode interpreters is to have the instruction contain the instruction ID, which is then used as an index into an array of function pointers, each of which implements one instruction.

Obviously doing this has performance implications. If what your instructions do is simple enough, you can save CPU cycles by implementing them directly in machine code and foregoing the (usually negligible) overhead of a function call, and maybe even use the real stack instead of the fake one.

It all depends on your needs. For most cases, and especially if this is your first parser/interpreter/VM, I'd recommend going with an array of function pointers and a fake stack. It's simple, not too hard to debug, and fast enough on modern machines. You can always later go in and write an optimized version that does things differently.

E.g. one approach is to generate just enough machine code for a function call, and then insert a pointer to such a function in the generated machine code. So each script becomes a block of compiled code, but you don't have to write a full compiler. From there on, you can then improve individual, pivotal instructions by generating the assembler for them, by leaving less often used things as functions. This improves locality of code a bit, which is one tiny micro-optimization that can help. But just one of many.

Oh, about a month ago, I blogged on how one would make a compiler (and bytecode interpreter) from a beginner's point of view, which may be helpful: http://orangejuiceliberationfront.com/how-to-write-a-compiler/