#vm #frame #register #instructions #meant #builder #function

fn_vm

A lightweight frame based virtual machine, meant as the base for rigz_vm

12 stable releases (4 major)

new 4.0.0 Jul 17, 2024
3.0.1 Jul 17, 2024
2.2.0 Jul 15, 2024
1.5.0 Jul 13, 2024
0.1.0 Jul 1, 2024

#174 in Rust patterns

Download history 355/week @ 2024-06-28 50/week @ 2024-07-05 1339/week @ 2024-07-12

1,744 downloads per month

MIT license

55KB
1K SLoC

fn_vm

A lightweight frame/register based VM that can be used to run functions.

All problems in computer science can be solved by another level of indirection... 
Except for the problem of too many layers of indirection.

Inspired by iridium

How it works

This is based on the idea that if my VM and AST are using the same underlying type for values, but not just a byte array, I'll be able to build a simpler runtime to bridge the gap between the two. Additionally, I didn't want to implement the same instructions I see in most other VMs when all I needed for now is to call a couple of rust functions.

fn_vm can store any value that implements the VMValue trait, there is an implementation for all primitive types.

By default, everything happens in the first frame; each frame is a function definition and can be entered/exited by calling an instruction. Once the value register is used, the register is removed (unless the instruction is meant to provide a register for later steps like COPY)

So all you get are a few types, a builder, and the VM (composed of Frames).

pub type VMFunction<T> = fn(&mut VM<T>, args: Vec<T>) -> Result<Option<T>, VMError>;
pub type HCFFunction<T> = fn(&mut VM<T>) -> Result<(), VMError>;


pub trait LazyCompiler<T: VMValue<T>> {
  fn compile(&self, length: Length) -> Result<Frame<T>, VMError>;
}

#[derive(Clone, Debug, PartialEq)]
pub enum FrameValue<T: VMValue<T>> {
  Value(T),
  Frame(Frame<T>),
}

#[derive(Clone, Debug, PartialEq)]
pub struct Frame<T: VMValue<T>> {
  pub instructions: Vec<u8>,
  pub pc: usize,
  pub locals: IndexMap<String, FrameValue<T>>,
  pub parent: Option<usize>,
}

pub struct VM<T: VMValue<T>> {
    pub fp: usize,
    pub frames: Vec<Frame<T>>,
    pub functions: Vec<VMFunction<T>>,
    pub registers: HashMap<Length, T>,
    pub index_registers: HashMap<Length, Length>,
    pub bit_registers: HashMap<Length, bool>,
    pub stack: Vec<usize>,
    pub lazy_compiler: Option<Box<dyn LazyCompiler<T>>>,
    pub program_data: Bytes,
    pub hcf_trigger: Option<HCFFunction<T>>,
}

pub trait VMValue<T: VMValue<T>>: Display + Debug + Clone + PartialEq + Logical<T> + Add<Output=T> + Mul<Output=T> + Div<Output=T> + PartialOrd + Sub<Output=T> + BitAnd<Output=T> + BitOr<Output=T> + BitXor<Output=T> + Rem<Output=T> + Not<Output=T> + Neg<Output=T> + Shr<Output=T> + Shl<Output=T> {
  
}

Instructions

Key:

  • r is input register, usually output register is the first register passed in
  • a prefix of b or i are the boolean or index registers.
  • f# is a frame index
  • l# is an index to call the lazy compiler with

Variables:

  • let: default immutable variable
  • mut: mutable variable
  • frame: mutable frame that evaluates to a variable

This VM offers the following instructions:

  • NOP: No operation, move the pc to the next instruction. NOP
  • ADD: Add two registers store the output. ADD r1 r2
  • MOD: modulo two registers store the output. MOD r1 r2
  • SUB: subtract two registers store the output. SUB r1 r2
  • MUL: multiply two registers store the output. MUL r1 r2
  • DIV: divide two registers store the output. DIV r1 r2
  • SHR: shift right two registers store the output. SHR r1 r2
  • SHL: shift left two registers store the output. SHL r1 r2
  • XOR: bitxor two registers store the output. XOR r1 r2
  • BAND: boolean and two registers store the output. BAND r1 r2
  • BOR: boolean or two registers store the output. BOR r1 r2
  • BXOR: boolean xor two registers store the output. BXOR r1 r2
  • LXOR: logical xor two registers store the output. LXOR r1 r2
  • LAND: logical and two registers store the output. LAND r1 r2
  • LOR: Add two registers store the output. LOR r1 r2
  • NOT: Not registers store the output. NOT r1
  • BNOT: Boolean not register store the output. BNOT r1
  • NEG: Neg registers store the output. NEG r1
  • AND: Add two registers store the output. AND r1 r2
  • OR: Add two registers store the output. OR r1 r2
  • EQ: compare two registers store the output. EQ r1 r2
  • BEQ: compare two bit registers store the output. BEQ br1 br2
  • IEQ: compare two index registers store the output. IEQ ir1 ir2
  • NEQ: compare two registers store the output. NEQ r1 r2
  • BNEQ: compare two bit registers store the output. BNEQ br1 br2
  • INEQ: compare two index registers store the output. INEQ ir1 ir2
  • REV: reverse value in register store the output. REV r1
  • LT: compare two registers store the output. LT r1 r2
  • LTE: compare two registers store the output. LTE r1 r2
  • GT: compare two registers store the output. GT r1 r2
  • GTE: compare two registers store the output. GTE r1 r2
  • COPY: Copy a value from one register to another, COPY r1 r2
  • CIR: Copy index register from to. CIR ir1 ir2
  • CBR: Copy index register from to. CBR br1 br2
  • CALL: Call a frame, used to call functions. CALL f#
  • CALLR: Call a frame stored in index_register #, used to call frames created by CFR. CALLR ir1
  • RET: Return from a frame, RET <from> <to>
  • GLV: Get local value, GLV r1 <name>
  • MVL: move local value from current frame to fr1 (skips existence check), MVL fr1 <name>
  • CPL: copy local value from current frame to fr1 (skips existence check), CPL fr1 <name>
  • CPM: copy local value from current frame to fr1 (skips existence check), as mutable. CPM fr1 <name>
  • DLV: delete local value from frame, DLV fr1 <name>
  • DFV: delete local value from current frame, DLV <name>
  • SLR: Set local value from a register, SLR r1 <name>
  • SMR: Set local mutable value from a register, SMR r1 <name>
  • SLF: Set local mutable value from frame register, SMF fr1 <name>
  • CFR: Create frame, CFR ir1 <len> [instructions]
  • DFR: Delete frame (soft delete, otherwise all other frame indexes break), resets the Frame and sets instructions to IVF. DFR f#
  • DFI: Delete frame in index register. DFI ir1 , // ir1, delete frame
  • FN: Call provided a function, FN <op> <len> [registers] <out_register>
  • IVF: Invalid frame, not used directly. Result of calling DFR, IVF
  • PSH: push r1 to value_stack, PSH r1
  • PSHV: push r1 to value_stack, PSHV <value>
  • POP: pop from value_stack to r1, POP r1
  • HCF: Halt and catch fire, stop the VM (an optional hcf_trigger can be passed in if this command is received). HCF
  • LZY: Calls out to the lazy compiler to generate a frame with the next set of instructions and moves the fp to that frame, requires lazy_compiler be set. LZY l#
    pub trait LazyCompiler<T: Clone + PartialEq> {
        fn compile(&self, length: Length) -> Result<Frame<T>, VMError>;
    }
    

With IVD as a default command for any invalid command.

FN

This is by far the most complicated instruction since it's really a pass through to you.

Here's an example of calling it with the builder:

NOTE: into() is used to convert to a Length, from small_len to support up to usize args.

fn run() {
    let vm = VMBuilder::new()
            .set_value(5.into(), 42) // store 42 in r5
            .set_value(4.into(), 42) // store 42 in r4
        .add_function_instruction(0, vec![5.into(), 4.into()], 3.into())
        .add_function(move |_, args| {
            let a = args[0];
            let b = args[1];
            Ok(Some(a + b))
        })
        .build();
    vm.run().unwrap();
    assert_eq!(vm.registers[3], 84);
}

Dependencies

~3MB
~50K SLoC