Design a generic performant-first interpreter

[ryo33]

Current implementation

The interpreter we are using now evaluates MIR (Mid-level IR) directly. It's easy to understand but may have bad performance.
MIR is a collection of CFG (Control Flow Graph), and each instruction of basic blocks is in A-normal form.

Purpose

The purpose is to create a new interpreter for cases that requires a generic performant interpreter.
Because DeskVM can handle multiple types of interpreters, we don't need to replace the current one.

Design requirements

• It must implement the Interpreter trait.
• It must be generic because we can have many interpreters specialized for a specific domain.
• Performant execution is the first, and performant compile is the second.
• It must have a resource management system such as GC.
• No JIT compilation (the reason is written in the Related notes).
• It should be sound.
• We should keep design and code as simple as possible while performant is first.
• The interpreter must be suspendable and resumable for scheduling.

Related notes

• We'll create an AOT compiler in the future.
• On desktop platform, DeskVM has an ability to run any executable file as a d-process in the VM. It means we can use any executable binary including binaries AOT-Compiled Desk code by just performing a delegation effect in a code. So we don’t need JIT anymore.
• Since Desk-lang has no side effects, the only side-effective opcode is perform-an-effect.
• [Needs proof] Because Desk-lang may have a soundish type system, we don't need to worry about crashes by type problem.
• Desk-lang has no operator other than calling a function.
• Desk-lang doesn't define built-in functions, so we can define ones for this interpreter.
• MIR distinguishes data structures such as arrays and linked lists.
• MIR can contain region-analyzed references.

Related crates

• deskc-mir defines the structure of MIR
• deskvm-miri implements the current de facto interpreter
• deskvm-process defines the process struct like ErlangVM's one and the interpreter trait
• deskvm implements the virtual machine like ErlangVM

References

• BEAM bytecode of Erlang VM
• Ruby bytecode

[ryo33]

I think this should be Wasm.