implement a basic virtual machine

[zerbina]

Summary

Implement a small and simple yet powerful virtual machine. It's a stack machine, with inspiration taken from WebAssembly.

Details

The execution loop is implemented in the vm module, the opcode specification can be found in vmspec.

The instruction set covers:

• integer/float arithmetic
• bit operations
• comparisons
• conversions
• memory operations (read, write, block copy)
• control flow
• basic stack management

In addition, the VM has built-in support for subroutines, to be able to efficiently model more complex control-flow (such as try/finally). Basic exception handling is also supported.

For interfacing with the host, ref-counted foreign refs are and imported procedures (which invoke a callback) are supported. Procedures can be stubs, to facilitate just-in-time compilation.

All memory addresses are in a virtual address space, backed by a single host memory region that can be grown as needed.

In general, the set of operations is meant to not make too many assumptions, while still being efficient.

---

To-Do

• [x] implement the validation layer

[zerbina]

The implementation is based on a not-yet-finished rework of the NimSkull VM, but heavily trimmed down. Removed features include:

• complex RTTI and run-time type checks
• a built-in heap allocator
• built-in instructions for set operations (incl, excl, etc.)

Those are all things that added a lot of complexity to the base VM, and there's no point in having them at the moment. Once needed, they can simply be implemented in bytecode instead.

[zerbina]

Beyond the basic "does it compile" test, there aren't any tests at the moment, though I did do some testing locally to ensure that the basics work.

The next step (implemented in a follow-up PR) is implementing an assembler and using it to implement a test tool that runs VM code provided via text files. Having a simple REPL for one-off testing would also be nice.

[zerbina]

With the validation layer implemented, the first iteration of the VM is complete. Same as with the VM itself, I've ran it through some local testing, but no proper test suite for it exists yet.

Things to look for when reviewing:

• logic errors
• opportunities for simplification
• unclear and or missing documentation
• names that could be better

The validation layer ended up to being somewhat complex. If anyone has an idea - that doesn't involve macros/DSLs - on how to restructure/change the code to be easier to understand, I'd be happy to hear it.

[saem]

starting to review this now

[zerbina]

Thank you for the review, @saem!