Merge pull request #4 from slothlang/vm-basics

Basic VM

14 files changed, 1052 insertions, 243 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 157650a..b7ccbe0 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -9,12 +9,29 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "14c189c53d098945499cdfa7ecc63567cf3886b3332b312a5b4585d8d3a6a610"
 
 [[package]]
+name = "cfg-if"
+version = "1.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd"
+
+[[package]]
 name = "either"
 version = "1.8.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "90e5c1c8368803113bf0c9584fc495a58b86dc8a29edbf8fe877d21d9507e797"
 
 [[package]]
+name = "getrandom"
+version = "0.2.9"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "c85e1d9ab2eadba7e5040d4e09cbd6d072b76a557ad64e797c2cb9d4da21d7e4"
+dependencies = [
+ "cfg-if",
+ "libc",
+ "wasi",
+]
+
+[[package]]
 name = "itertools"
 version = "0.10.5"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -24,6 +41,24 @@ dependencies = [
 ]
 
 [[package]]
+name = "libc"
+version = "0.2.141"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "3304a64d199bb964be99741b7a14d26972741915b3649639149b2479bb46f4b5"
+
+[[package]]
+name = "once_cell"
+version = "1.17.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "b7e5500299e16ebb147ae15a00a942af264cf3688f47923b8fc2cd5858f23ad3"
+
+[[package]]
+name = "ppv-lite86"
+version = "0.2.17"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5b40af805b3121feab8a3c29f04d8ad262fa8e0561883e7653e024ae4479e6de"
+
+[[package]]
 name = "proc-macro2"
 version = "1.0.54"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -42,6 +77,36 @@ dependencies = [
 ]
 
 [[package]]
+name = "rand"
+version = "0.8.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "34af8d1a0e25924bc5b7c43c079c942339d8f0a8b57c39049bef581b46327404"
+dependencies = [
+ "libc",
+ "rand_chacha",
+ "rand_core",
+]
+
+[[package]]
+name = "rand_chacha"
+version = "0.3.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e6c10a63a0fa32252be49d21e7709d4d4baf8d231c2dbce1eaa8141b9b127d88"
+dependencies = [
+ "ppv-lite86",
+ "rand_core",
+]
+
+[[package]]
+name = "rand_core"
+version = "0.6.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ec0be4795e2f6a28069bec0b5ff3e2ac9bafc99e6a9a7dc3547996c5c816922c"
+dependencies = [
+ "getrandom",
+]
+
+[[package]]
 name = "sloth"
 version = "0.1.0"
 dependencies = [
@@ -54,23 +119,18 @@ name = "sloth_bytecode"
 version = "0.1.0"
 dependencies = [
  "byteorder",
- "sloth_bytecode_macros",
 ]
 
 [[package]]
-name = "sloth_bytecode_macros"
+name = "sloth_vm"
 version = "0.1.0"
 dependencies = [
- "proc-macro2",
- "quote",
- "syn",
+ "once_cell",
+ "rand",
+ "sloth_bytecode",
 ]
 
 [[package]]
-name = "sloth_vm"
-version = "0.1.0"
-
-[[package]]
 name = "syn"
 version = "2.0.12"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -106,3 +166,9 @@ name = "unicode-ident"
 version = "1.0.8"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "e5464a87b239f13a63a501f2701565754bae92d243d4bb7eb12f6d57d2269bf4"
+
+[[package]]
+name = "wasi"
+version = "0.11.0+wasi-snapshot-preview1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9c8d87e72b64a3b4db28d11ce29237c246188f4f51057d65a7eab63b7987e423"
diff --git a/Cargo.toml b/Cargo.toml
index fed9008..57e0bc4 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -2,7 +2,6 @@
 members = [
     "crates/sloth",
     "crates/sloth_bytecode",
-    "crates/sloth_bytecode/macros",
     "crates/sloth_vm",
 ]
 
diff --git a/crates/sloth_bytecode/Cargo.toml b/crates/sloth_bytecode/Cargo.toml
index 76448ee..0de211f 100644
--- a/crates/sloth_bytecode/Cargo.toml
+++ b/crates/sloth_bytecode/Cargo.toml
@@ -6,6 +6,4 @@ version.workspace = true
 edition.workspace = true
 
 [dependencies]
-sloth_bytecode_macros = { path = "./macros" }
-
 byteorder = "1.4.3"
diff --git a/crates/sloth_bytecode/macros/Cargo.toml b/crates/sloth_bytecode/macros/Cargo.toml
deleted file mode 100644
index 649d88a..0000000
--- a/crates/sloth_bytecode/macros/Cargo.toml
+++ /dev/null
@@ -1,15 +0,0 @@
-[package]
-name = "sloth_bytecode_macros"
-
-license.workspace = true
-version.workspace = true
-edition.workspace = true
-
-[dependencies]
-proc-macro2 = "1.0.54"
-quote = "1.0.26"
-syn = "2.0.12"
-
-[lib]
-proc-macro = true
-
diff --git a/crates/sloth_bytecode/macros/src/lib.rs b/crates/sloth_bytecode/macros/src/lib.rs
deleted file mode 100644
index 15a09d0..0000000
--- a/crates/sloth_bytecode/macros/src/lib.rs
+++ /dev/null
@@ -1,164 +0,0 @@
-use proc_macro2::{Ident, TokenStream};
-use quote::quote;
-use syn::parse::Parse;
-use syn::punctuated::Punctuated;
-use syn::{bracketed, parse_macro_input, LitInt, LitStr, Token};
-
-// TODO: Rename args to operands?
-
-struct DslInstructionInput {
-    opcode: LitInt,
-    name: Ident,
-    args: Punctuated<Ident, Token![,]>,
-    description: LitStr,
-}
-
-impl Parse for DslInstructionInput {
-    fn parse(input: syn::parse::ParseStream) -> syn::Result<Self> {
-        let args_content;
-        Ok(Self {
-            opcode: input.parse()?,
-            name: input.parse()?,
-            args: {
-                bracketed!(args_content in input);
-                args_content.parse_terminated(Ident::parse, Token![,])?
-            },
-            description: input.parse()?,
-        })
-    }
-}
-
-struct DslInstructionsInput {
-    name: Ident,
-    instructions: Punctuated<DslInstructionInput, Token![,]>,
-}
-
-impl Parse for DslInstructionsInput {
-    fn parse(input: syn::parse::ParseStream) -> syn::Result<Self> {
-        Ok(Self {
-            name: input.parse()?,
-            instructions: {
-                input.parse::<Token![;]>()?;
-                input.parse_terminated(DslInstructionInput::parse, Token![,])?
-            },
-        })
-    }
-}
-
-fn into_enum_field(instruction: &DslInstructionInput) -> TokenStream {
-    let DslInstructionInput {
-        opcode,
-        name,
-        args,
-        description,
-    } = instruction;
-
-    let args = args.iter();
-
-    if args.len() > 0 {
-        quote! {
-            #[doc = #description]
-            #name ( #( #args ),*  ) = #opcode
-        }
-    } else {
-        quote! {
-            #[doc = #description]
-            #name = #opcode
-        }
-    }
-}
-
-fn into_bytecode_parser(instruction: &DslInstructionInput) -> TokenStream {
-    let DslInstructionInput {
-        opcode,
-        name,
-        args,
-        description: _,
-    } = instruction;
-
-    if args.is_empty() {
-        return quote! {
-            #opcode => Self :: #name
-        };
-    }
-
-    let mut arg_params = Vec::new();
-    for arg in args {
-        let size = match arg.to_string().as_str() {
-            "u128" => 128,
-            "u64" => 64,
-            "u32" => 32,
-            "u16" => 16,
-            "u8" => 8,
-            typ => panic!("Unsupported instruction arg type '{typ}'"),
-        } as usize;
-
-        let bytes = size / 8;
-
-        let mut chunks = Vec::new();
-        for byte in 0..bytes {
-            let shift_amount = size - (byte + 1) * bytes;
-            chunks.push(quote! {
-                ((chunk[*offset + #byte] as #arg) << #shift_amount)
-            });
-        }
-
-        arg_params.push(quote! {
-            let value = #( #chunks )+* ;
-            *offset += #bytes ;
-            value
-        });
-    }
-
-    quote! {
-        #opcode => {
-            Self :: #name (
-                #( { #arg_params } ),*
-            )
-        }
-    }
-}
-
-#[proc_macro]
-pub fn instructions(input: proc_macro::TokenStream) -> proc_macro::TokenStream {
-    let input = parse_macro_input!(input as DslInstructionsInput);
-
-    // Getting values to construct the enum
-    let enum_name = input.name;
-    let enum_fields = input
-        .instructions
-        .iter()
-        .map(into_enum_field)
-        .collect::<Vec<_>>();
-
-    // Getting the values to parse bytecode
-    let bytecode_parsers = input
-        .instructions
-        .iter()
-        .map(into_bytecode_parser)
-        .collect::<Vec<_>>();
-
-    // Building out the expanded code
-    quote! {
-        #[repr(u8)]
-        #[derive(Clone, Debug, Eq, PartialEq)]
-        enum #enum_name {
-            #( #enum_fields ),*
-        }
-
-        impl #enum_name {
-            fn disassemble(chunk: &[u8], offset: &mut usize) -> #enum_name {
-                let opcode = chunk[*offset];
-                *offset += 1;
-
-                let instruction = match opcode {
-                    #( #bytecode_parsers , )*
-                    _ => panic!("Unknown bytecode encountered"),
-                };
-
-                instruction
-            }
-        }
-    }
-    .into()
-}
diff --git a/crates/sloth_bytecode/src/lib.rs b/crates/sloth_bytecode/src/lib.rs
index 3593f3c..2319330 100644
--- a/crates/sloth_bytecode/src/lib.rs
+++ b/crates/sloth_bytecode/src/lib.rs
@@ -7,56 +7,69 @@
     unused_lifetimes
 )]
 
-use sloth_bytecode_macros::instructions;
-
 pub enum Error {
     UnknownOpcode(u8),
     InvalidArguments,
     Eof,
 }
 
-instructions! {
-    Instructions;
+macro_rules! opcodes {
+    ( $( $code:literal $name:ident $docs:literal ),* ) => {
+        #[repr(u8)]
+        #[derive(Debug, Clone, Copy, Eq, PartialEq)]
+        pub enum Opcode {
+            $(
+                #[doc = $docs]
+                $name = $code
+            ),*
+        }
 
-    0x00 Constant   [u64]   "Push a constant value onto the stack",
-    0x01 Load       [u64]   "Load a value from a variable",
-    0x02 Push       [u64]   "Push a value to a variable",
+        impl Opcode {
+            pub fn into_u8(self) -> u8 {
+                self as u8
+            }
 
-    0x10 Dup        []      "Duplicate a value on the stack",
-    0x11 Pop        []      "Pop a value from the stack",
+            pub fn from_u8(value: u8) -> Opcode {
+                match value {
+                    $( $code => Self:: $name , )*
+                    _ => panic!("Invalid opcode"),
+                }
+            }
+        }
+    };
+}
 
-    0x20 Add        []      "Add the last 2 values on the stack",
-    0x21 Sub        []      "Subtract the last 2 values on the stack",
-    0x22 Mul        []      "Multiply the last 2 values on the stack",
-    0x23 Div        []      "Divide the last 2 values on the stack",
-    0x24 Mod        []      "Modulo the last 2 values on the stack",
+opcodes! {
+    0x00 Constant   "Push a constant value onto the stack",
+    0x01 Load       "Load a value from a variable",
+    0x02 Push       "Push a value to a variable",
 
-    0xF0 Print      []      "[DEBUG] Pop value from stack and print it"
-}
+    0x10 Dup        "Duplicate a value on the stack",
+    0x11 Pop        "Pop a value from the stack",
+
+    0x12 GetGlobal  "Get a global value",
+    0x13 SetGlobal  "Set a global value",
+    0x14 GetLocal   "Get a local value",
+    0x15 SetLocal   "Set a local value",
+
+    0x20 Add        "Add the last 2 values on the stack",
+    0x21 Sub        "Subtract the last 2 values on the stack",
+    0x22 Mul        "Multiply the last 2 values on the stack",
+    0x23 Div        "Divide the last 2 values on the stack",
+    0x24 Mod        "Modulo the last 2 values on the stack",
+
+    0x30 Eq         "Check if the last 2 values on the stack are equal",
+    0x31 Ne         "Check if the last 2 values on the stack are not equal",
+
+    0x40 Jump       "Jump to a specific point in the program",
+    0x41 JumpIf     "Jump to a specific point in the program if true is on the stack",
+
+    0x50 Call       "Call function on stack",
+    0x51 CallNative "Call native function",
+    0x52 Return     "Return from function on stack",
+
+    0xE0 Halt       "Halt the program",
 
-#[cfg(test)]
-mod tests {
-    use crate::Instructions;
-
-    #[test]
-    #[rustfmt::skip]
-    fn decompile_basic_instructions() {
-        let code = [
-            // Load constant 0
-            0x00, 0, 0, 0, 0, 0, 0, 0, 0, 
-            // Pop, Dup, Add, Sub, Mul, Div, Mod
-            0x10, 0x11, 0x20, 0x21, 0x22, 0x23, 0x24,
-        ];
-
-        let mut offset = 0;
-
-        assert_eq!(Instructions::disassemble(&code, &mut offset), Instructions::Constant(0));
-        assert_eq!(Instructions::disassemble(&code, &mut offset), Instructions::Dup);
-        assert_eq!(Instructions::disassemble(&code, &mut offset), Instructions::Pop);
-        assert_eq!(Instructions::disassemble(&code, &mut offset), Instructions::Add);
-        assert_eq!(Instructions::disassemble(&code, &mut offset), Instructions::Sub);
-        assert_eq!(Instructions::disassemble(&code, &mut offset), Instructions::Mul);
-        assert_eq!(Instructions::disassemble(&code, &mut offset), Instructions::Div);
-        assert_eq!(Instructions::disassemble(&code, &mut offset), Instructions::Mod);
-    }
+    0xF0 VMReturn   "[DEBUG] Pop value from stack and return it fromthe program",
+    0xF1 VMPrint    "[DEBUG] Print value to console"
 }
diff --git a/crates/sloth_vm/Cargo.toml b/crates/sloth_vm/Cargo.toml
index e71c18d..f484402 100644
--- a/crates/sloth_vm/Cargo.toml
+++ b/crates/sloth_vm/Cargo.toml
@@ -6,3 +6,7 @@ version.workspace = true
 edition.workspace = true
 
 [dependencies]
+sloth_bytecode = { path = "../sloth_bytecode" }
+
+once_cell = "1.17.1"
+rand = "0.8.5"
diff --git a/crates/sloth_vm/src/lib.rs b/crates/sloth_vm/src/lib.rs
index 1dfb191..295827d 100644
--- a/crates/sloth_vm/src/lib.rs
+++ b/crates/sloth_vm/src/lib.rs
@@ -7,24 +7,148 @@
     unused_lifetimes
 )]
 
-const STACK_SIZE: usize = 1024;
+pub mod native;
+pub mod sloth_std;
+pub mod value;
+pub mod vm;
+
+use std::ops::{Index, IndexMut};
+
+use value::{Object, ObjectType};
+
+use crate::value::Primitive;
+pub use crate::vm::VM;
 
 pub struct Chunk {
+    constants: Vec<Primitive>,
     code: Vec<u8>,
-    constants: Vec<u64>,
 }
 
-pub struct VM {
-    stack: [u8; STACK_SIZE],
-    constants: Vec<u8>,
+const STACK_SIZE: usize = 1024;
+
+#[derive(Debug)]
+pub struct Stack {
+    stack: [Primitive; STACK_SIZE],
+    top: usize,
+}
+
+impl Default for Stack {
+    fn default() -> Self {
+        Self {
+            top: Default::default(),
+            stack: [Primitive::Empty; STACK_SIZE],
+        }
+    }
 }
 
-impl VM {
-    //
+impl Stack {
+    #[inline(always)]
+    pub fn push(&mut self, value: Primitive) {
+        if self.top >= STACK_SIZE {
+            panic!("Stack overflow");
+        }
+
+        self.stack[self.top] = value;
+        self.top += 1;
+    }
+
+    #[inline(always)]
+    pub fn pop(&mut self) -> Primitive {
+        if self.top == 0 {
+            panic!("Stack underflow");
+        }
+
+        self.top -= 1;
+        self.stack[self.top]
+    }
+
+    #[inline(always)]
+    pub fn pop2(&mut self) -> (Primitive, Primitive) {
+        (self.pop(), self.pop())
+    }
+
+    #[inline(always)]
+    pub fn peek(&self) -> Primitive {
+        self.stack[self.top - 1]
+    }
+
+    #[inline(always)]
+    pub fn peek_nth(&self, nth: usize) -> Primitive {
+        self.stack[self.top - 1 - nth]
+    }
+}
+
+impl Index<usize> for Stack {
+    type Output = Primitive;
+
+    fn index(&self, index: usize) -> &Self::Output {
+        &self.stack[index]
+    }
 }
 
-#[cfg(test)]
-mod tests {
-    #[test]
-    fn add_program() {}
+impl IndexMut<usize> for Stack {
+    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
+        &mut self.stack[index]
+    }
+}
+
+pub struct ObjectMap {
+    free: usize,
+    heap: Vec<Object>,
+}
+
+impl Default for ObjectMap {
+    fn default() -> Self {
+        Self::with_capacity(32)
+    }
+}
+
+impl From<Vec<Object>> for ObjectMap {
+    fn from(heap: Vec<Object>) -> Self {
+        let mut free = heap.len();
+        for (idx, obj) in heap.iter().enumerate() {
+            if let ObjectType::Free { .. } = obj.typ {
+                free = idx;
+                break;
+            }
+        }
+
+        Self { free, heap }
+    }
+}
+
+impl ObjectMap {
+    pub fn with_capacity(capacity: usize) -> Self {
+        let mut heap = Vec::with_capacity(capacity);
+        for i in 0..capacity {
+            heap.push(Object::new(ObjectType::Free { next: i + 1 }));
+        }
+
+        Self { free: 0, heap }
+    }
+
+    pub fn allocate(&mut self, object: Object) -> usize {
+        let current = self.free;
+        if current >= self.heap.len() {
+            self.heap
+                .push(Object::new(ObjectType::Free { next: current + 1 }))
+        }
+
+        let ObjectType::Free { next } = self.heap[current].typ else {
+            panic!("Allocation failed: Expected free location wasn't free");
+        };
+
+        self.heap[current] = object;
+        self.free = next;
+
+        current
+    }
+
+    pub fn get(&self, idx: usize) -> Option<&Object> {
+        self.heap.get(idx)
+    }
+
+    pub fn get_mut(&mut self, idx: usize) -> Option<&mut Object> {
+        self.heap.get_mut(idx)
+    }
 }
diff --git a/crates/sloth_vm/src/native.rs b/crates/sloth_vm/src/native.rs
new file mode 100644
index 0000000..8790cbd
--- /dev/null
+++ b/crates/sloth_vm/src/native.rs
@@ -0,0 +1,18 @@
+use crate::value::Primitive;
+use crate::VM;
+
+pub type NativeFunctionResult = Result<Primitive, Error>;
+pub type NativeFunctionInput = fn(&mut VM, &[Primitive]) -> NativeFunctionResult;
+
+pub enum Error {
+    InvalidArgument,
+    Unknown(String),
+}
+
+#[allow(clippy::type_complexity)]
+pub struct NativeFunction {
+    pub name: &'static str,
+    pub function: NativeFunctionInput,
+    pub arity: u8,
+    pub returns_value: bool,
+}
diff --git a/crates/sloth_vm/src/sloth_std/mod.rs b/crates/sloth_vm/src/sloth_std/mod.rs
new file mode 100644
index 0000000..86611d7
--- /dev/null
+++ b/crates/sloth_vm/src/sloth_std/mod.rs
@@ -0,0 +1,24 @@
+use std::collections::HashMap;
+
+use once_cell::sync::Lazy;
+
+use crate::native::NativeFunction;
+
+pub mod rand;
+pub mod stdio;
+
+pub static NATIVE_LIBRARY: Lazy<HashMap<&'static str, NativeFunction>> = Lazy::new(|| {
+    let mut map = HashMap::new();
+
+    // rand
+    map.insert("rand$gen", rand::GEN_FUNCTION);
+    map.insert("rand$gen_range", rand::GEN_RANGE_FUNCTION);
+
+    // stdio
+    map.insert("write", stdio::WRITE_FUNCTION);
+    map.insert("read", stdio::READ_FUNCTION);
+
+    // filesystem
+
+    map
+});
diff --git a/crates/sloth_vm/src/sloth_std/rand.rs b/crates/sloth_vm/src/sloth_std/rand.rs
new file mode 100644
index 0000000..bae0606
--- /dev/null
+++ b/crates/sloth_vm/src/sloth_std/rand.rs
@@ -0,0 +1,39 @@
+use rand::Rng;
+
+use crate::native::{self, NativeFunction, NativeFunctionResult};
+use crate::value::Primitive;
+use crate::value::Primitive::{Float, Integer};
+use crate::VM;
+
+fn gen(_vm: &mut VM, _args: &[Primitive]) -> NativeFunctionResult {
+    let value = rand::thread_rng().gen_range(0.0..1.0);
+
+    Ok(Float(value))
+}
+
+pub const GEN_FUNCTION: NativeFunction = NativeFunction {
+    name: "rand$gen",
+    function: gen,
+    arity: 0,
+    returns_value: true,
+};
+
+fn gen_range(_vm: &mut VM, args: &[Primitive]) -> NativeFunctionResult {
+    let min = args.get(0).cloned();
+    let max = args.get(1).cloned();
+
+    let (Some(Integer(min)), Some(Integer(max))) = (min, max) else {
+        return Err(native::Error::InvalidArgument);
+    };
+
+    let value = rand::thread_rng().gen_range(min..max);
+
+    Ok(Integer(value))
+}
+
+pub const GEN_RANGE_FUNCTION: NativeFunction = NativeFunction {
+    name: "rand$gen_range",
+    function: gen_range,
+    arity: 2,
+    returns_value: true,
+};
diff --git a/crates/sloth_vm/src/sloth_std/stdio.rs b/crates/sloth_vm/src/sloth_std/stdio.rs
new file mode 100644
index 0000000..a743ad1
--- /dev/null
+++ b/crates/sloth_vm/src/sloth_std/stdio.rs
@@ -0,0 +1,51 @@
+use std::io::{stdin, BufRead};
+
+use crate::native::{self, NativeFunction, NativeFunctionResult};
+use crate::value::{Object, ObjectType, Primitive};
+use crate::VM;
+
+fn write(vm: &mut VM, args: &[Primitive]) -> NativeFunctionResult {
+    let Some(Primitive::Object(ptr)) = args.get(0).cloned() else {
+        return Err(native::Error::InvalidArgument);
+    };
+
+    let object = vm
+        .objects()
+        .get(ptr as usize)
+        .ok_or(native::Error::InvalidArgument)?;
+
+    let ObjectType::String(str) = &object.typ else {
+        return Err(native::Error::InvalidArgument);
+    };
+
+    println!("{str}");
+
+    Ok(Primitive::Empty)
+}
+
+pub const WRITE_FUNCTION: NativeFunction = NativeFunction {
+    name: "write",
+    function: write,
+    arity: 1,
+    returns_value: false,
+};
+
+fn read(vm: &mut VM, _args: &[Primitive]) -> NativeFunctionResult {
+    let mut line = String::new();
+    stdin()
+        .lock()
+        .read_line(&mut line)
+        .map_err(|it| native::Error::Unknown(it.to_string()))?;
+
+    let object = Object::new(ObjectType::String(line));
+    let ptr = vm.objects_mut().allocate(object);
+
+    Ok(Primitive::Object(ptr as u32))
+}
+
+pub const READ_FUNCTION: NativeFunction = NativeFunction {
+    name: "read",
+    function: read,
+    arity: 0,
+    returns_value: true,
+};
diff --git a/crates/sloth_vm/src/value.rs b/crates/sloth_vm/src/value.rs
new file mode 100644
index 0000000..f149c0e
--- /dev/null
+++ b/crates/sloth_vm/src/value.rs
@@ -0,0 +1,53 @@
+use crate::native::NativeFunction;
+use crate::Chunk;
+
+#[derive(Debug, Clone, Copy, PartialEq)]
+pub enum Primitive {
+    Integer(i128),
+    Float(f64),
+    Bool(bool),
+    /// Pointer to an object living on heap
+    Object(u32),
+    Empty,
+}
+
+pub struct Object {
+    /// If the object has been marked by the VM or not
+    pub(crate) marked: bool,
+    pub(crate) typ: ObjectType,
+}
+
+impl Object {
+    pub fn new(typ: ObjectType) -> Self {
+        Self { marked: false, typ }
+    }
+}
+
+pub enum ObjectType {
+    Box(Primitive),
+    String(String),
+    List(Vec<Primitive>),
+
+    Function(Function),
+    NativeFunction(NativeFunction),
+
+    Free { next: usize },
+}
+
+pub struct Function {
+    pub(crate) name: Option<String>,
+    pub(crate) chunk: Chunk,
+    pub(crate) arity: u8,
+    pub(crate) returns_value: bool,
+}
+
+impl Function {
+    pub(crate) fn root(chunk: Chunk) -> Self {
+        Self {
+            name: None,
+            chunk,
+            arity: 0,
+            returns_value: false,
+        }
+    }
+}
diff --git a/crates/sloth_vm/src/vm.rs b/crates/sloth_vm/src/vm.rs
new file mode 100644
index 0000000..2d58c3d
--- /dev/null
+++ b/crates/sloth_vm/src/vm.rs
@@ -0,0 +1,599 @@
+use std::mem::MaybeUninit;
+
+use sloth_bytecode::Opcode;
+
+use crate::value::{Function, Object, ObjectType, Primitive};
+use crate::{native, ObjectMap, Stack};
+
+#[derive(Clone, Copy)]
+pub struct CallFrame {
+    pointer: usize,
+    stack_offset: usize,
+    function: *const Function, // TODO: Safety
+}
+
+impl CallFrame {
+    fn new(stack_offset: usize, function: &Function) -> Self {
+        Self {
+            pointer: 0,
+            stack_offset,
+            function: function as *const _,
+        }
+    }
+
+    #[inline]
+    fn function(&self) -> &Function {
+        unsafe { &*self.function }
+    }
+}
+
+const CALL_STACK_SIZE: usize = 1024;
+
+pub struct CallStack {
+    top: usize,
+    frames: [MaybeUninit<CallFrame>; CALL_STACK_SIZE],
+}
+
+impl Default for CallStack {
+    fn default() -> Self {
+        Self {
+            top: 0,
+            frames: [MaybeUninit::uninit(); CALL_STACK_SIZE],
+        }
+    }
+}
+
+impl CallStack {
+    fn push(&mut self, frame: CallFrame) {
+        self.frames[self.top].write(frame);
+        self.top += 1;
+    }
+
+    fn pop(&mut self) {
+        self.top -= 1;
+    }
+
+    fn peek(&self) -> &CallFrame {
+        unsafe { self.frames[self.top - 1].assume_init_ref() }
+    }
+
+    fn peek_mut(&mut self) -> &mut CallFrame {
+        unsafe { self.frames[self.top - 1].assume_init_mut() }
+    }
+}
+
+pub struct VM {
+    stack: Stack,
+    call_stack: CallStack,
+    objects: ObjectMap,
+}
+
+impl Default for VM {
+    fn default() -> Self {
+        Self::init(ObjectMap::default())
+    }
+}
+
+impl VM {
+    pub fn init(objects: ObjectMap) -> Self {
+        Self {
+            stack: Stack::default(),
+            call_stack: CallStack::default(),
+            objects,
+        }
+    }
+
+    pub fn new(objects: ObjectMap, mut root: Function) -> Self {
+        let mut this = Self::init(objects);
+
+        // Allocating the root function
+        root.chunk.code.push(Opcode::Halt as u8);
+        this.call_stack.push(CallFrame::new(0, &root));
+        this.objects
+            .allocate(Object::new(ObjectType::Function(root)));
+
+        this
+    }
+
+    pub fn step(&mut self) -> bool {
+        use Primitive::*;
+
+        let opcode = self.read_u8();
+
+        match Opcode::from_u8(opcode) {
+            Opcode::Constant => {
+                let idx = self.read_u16() as usize;
+                let value = self.call_stack.peek().function().chunk.constants[idx];
+
+                self.stack.push(value);
+            }
+
+            Opcode::Dup => {
+                let value = self.stack.pop();
+                self.stack.push(value);
+                self.stack.push(value);
+            }
+            Opcode::Pop => {
+                self.stack.pop();
+            }
+            Opcode::GetLocal => {
+                let idx = self.read_u16() as usize;
+                let value = self.stack[self.call_stack.peek().stack_offset + idx];
+
+                self.stack.push(value);
+            }
+            Opcode::SetLocal => {
+                let idx = self.read_u16() as usize;
+                let value = self.stack.pop();
+
+                self.stack[self.call_stack.peek().stack_offset + idx] = value;
+            }
+
+            Opcode::Add => {
+                let value = match self.stack.pop2() {
+                    (Integer(lhs), Integer(rhs)) => Integer(lhs + rhs),
+                    (Float(lhs), Float(rhs)) => Float(lhs + rhs),
+                    _ => panic!(),
+                };
+
+                self.stack.push(value);
+            }
+            Opcode::Sub => {
+                let value = match self.stack.pop2() {
+                    (Integer(lhs), Integer(rhs)) => Integer(lhs - rhs),
+                    (Float(lhs), Float(rhs)) => Float(lhs - rhs),
+                    _ => panic!(),
+                };
+
+                self.stack.push(value);
+            }
+            Opcode::Mul => {
+                let value = match self.stack.pop2() {
+                    (Integer(lhs), Integer(rhs)) => Integer(lhs * rhs),
+                    (Float(lhs), Float(rhs)) => Float(lhs * rhs),
+                    _ => panic!(),
+                };
+
+                self.stack.push(value);
+            }
+            Opcode::Div => {
+                let value = match self.stack.pop2() {
+                    (Integer(_), Integer(0)) => panic!("Divide by 0"),
+                    (Integer(lhs), Integer(rhs)) => Integer(lhs / rhs),
+                    (Float(lhs), Float(rhs)) => Float(lhs / rhs),
+                    _ => panic!(),
+                };
+
+                self.stack.push(value);
+            }
+            Opcode::Mod => {
+                let value = match self.stack.pop2() {
+                    (Integer(lhs), Integer(rhs)) => Integer(lhs % rhs),
+                    (Float(lhs), Float(rhs)) => Float(lhs % rhs),
+                    _ => panic!(),
+                };
+
+                self.stack.push(value);
+            }
+
+            Opcode::Eq => {
+                let value = match self.stack.pop2() {
+                    (Integer(lhs), Integer(rhs)) => Bool(lhs == rhs),
+                    (Float(lhs), Float(rhs)) => Bool(lhs == rhs),
+                    (Bool(lhs), Bool(rhs)) => Bool(lhs == rhs),
+                    (Object(lhs), Object(rhs)) => Bool(lhs == rhs),
+                    (Empty, Empty) => Bool(true),
+                    _ => Bool(false),
+                };
+
+                self.stack.push(value);
+            }
+            Opcode::Ne => {
+                let value = match self.stack.pop2() {
+                    (Integer(lhs), Integer(rhs)) => Bool(lhs != rhs),
+                    (Float(lhs), Float(rhs)) => Bool(lhs != rhs),
+                    (Bool(lhs), Bool(rhs)) => Bool(lhs != rhs),
+                    (Object(lhs), Object(rhs)) => Bool(lhs != rhs),
+                    (Empty, Empty) => Bool(false),
+                    _ => Bool(false),
+                };
+
+                self.stack.push(value);
+            }
+
+            Opcode::Jump => {
+                let to = self.read_u16();
+                self.call_stack.peek_mut().pointer = to as usize;
+            }
+            Opcode::JumpIf => {
+                let to = self.read_u16();
+                let value = self.stack.pop();
+
+                if let Bool(true) = value {
+                    self.call_stack.peek_mut().pointer = to as usize;
+                }
+            }
+
+            Opcode::Call => {
+                let Primitive::Object(ptr) = self.stack.pop() else {
+                    panic!("Last element on stack was not an object");
+                };
+
+                self.call(ptr as usize);
+            }
+
+            Opcode::Return => {
+                self.call_return();
+            }
+
+            Opcode::Halt => return false,
+
+            opcode => unimplemented!("Opcode {:?} unimplemented", opcode),
+        }
+
+        true
+    }
+
+    pub fn run(&mut self) {
+        while self.step() {}
+    }
+
+    pub fn call(&mut self, ptr: usize) {
+        let Some(obj) = self.objects.get(ptr) else {
+            panic!("Pointer referenced nothing");
+        };
+
+        match &obj.typ {
+            ObjectType::Function(function) => {
+                // Add a callstack entry for the function
+                let offset = self.stack.top - (function.arity as usize);
+                self.call_stack.push(CallFrame::new(offset, function));
+            }
+            ObjectType::NativeFunction(function) => {
+                let mut args = Vec::with_capacity(function.arity as usize);
+                for _ in 0..function.arity {
+                    args.push(self.stack.pop());
+                }
+
+                let name = function.name;
+                let returns_value = function.returns_value;
+
+                let internal = function.function;
+                let result = internal(self, &args);
+
+                match result {
+                    Ok(value) => {
+                        if returns_value {
+                            self.stack.push(value);
+                        }
+                    }
+                    Err(error) => match error {
+                        native::Error::InvalidArgument => {
+                            panic!("Invalid argument provided to '{name}'");
+                        }
+                        native::Error::Unknown(msg) => {
+                            panic!("Native function '{name}' failed due to '{msg}'");
+                        }
+                    },
+                }
+            }
+            _ => panic!("Object was not a function"),
+        }
+    }
+
+    fn call_return(&mut self) {
+        let function = self.call_stack.peek().function();
+        let stack_offset = self.call_stack.peek().stack_offset;
+
+        let return_value = if function.returns_value {
+            Some(self.stack.pop())
+        } else {
+            None
+        };
+
+        self.stack.top = stack_offset;
+
+        if let Some(return_value) = return_value {
+            self.stack.push(return_value);
+        }
+
+        self.call_stack.pop();
+    }
+
+    fn unwind(&mut self) {
+        unimplemented!("Implement unwinding for error handling");
+    }
+
+    #[inline(always)]
+    fn read_u8(&mut self) -> u8 {
+        let frame = self.call_stack.peek_mut();
+        let function = frame.function();
+        let byte = function.chunk.code[frame.pointer];
+        frame.pointer += 1;
+        byte
+    }
+
+    #[inline(always)]
+    fn read_u16(&mut self) -> u16 {
+        let frame = self.call_stack.peek_mut();
+        let chunk = &frame.function().chunk;
+
+        let bytes = (chunk.code[frame.pointer], chunk.code[frame.pointer + 1]);
+
+        frame.pointer += 2;
+
+        ((bytes.0 as u16) << 8) + (bytes.1 as u16)
+    }
+
+    #[inline(always)]
+    pub fn objects(&self) -> &ObjectMap {
+        &self.objects
+    }
+
+    #[inline(always)]
+    pub fn objects_mut(&mut self) -> &mut ObjectMap {
+        &mut self.objects
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::value::{Function, Object, ObjectType, Primitive};
+    use crate::{sloth_std, Chunk, ObjectMap, VM};
+
+    #[test]
+    fn arithmetic_ops() {
+        // Addition
+        let mut vm = VM::new(
+            ObjectMap::default(),
+            Function::root(Chunk {
+                constants: vec![Primitive::Integer(7)],
+                code: vec![
+                    0x00, 0, 0,    // Load constant from 0
+                    0x10, // Duplicate
+                    0x20, // Add
+                    0xE0,
+                ],
+            }),
+        );
+
+        vm.run();
+        assert_eq!(vm.stack.peek(), Primitive::Integer(14));
+
+        let mut vm = VM::new(
+            ObjectMap::default(),
+            Function::root(Chunk {
+                constants: vec![Primitive::Integer(2), Primitive::Integer(11)],
+                code: vec![
+                    0x00, 0, 0, // Load constant from 0
+                    0x00, 0, 1,    // Load constant from 1
+                    0x20, // Add
+                    0xE0,
+                ],
+            }),
+        );
+
+        vm.run();
+        assert_eq!(vm.stack.peek(), Primitive::Integer(13));
+    }
+
+    #[test]
+    fn basic_function() {
+        let mut vm = VM::new(
+            ObjectMap::from(vec![Object::new(ObjectType::Function(Function {
+                name: Some("add".to_string()),
+                chunk: Chunk {
+                    constants: vec![],
+                    code: vec![0x14, 0, 0, 0x14, 0, 1, 0x20, 0x52],
+                },
+                arity: 2,
+                returns_value: true,
+            }))]),
+            Function::root(Chunk {
+                constants: vec![
+                    Primitive::Integer(6),
+                    Primitive::Integer(3),
+                    Primitive::Object(0),
+                    Primitive::Object(1),
+                    Primitive::Object(2),
+                ],
+                code: vec![
+                    0x00, 0, 0, // Load first function parameter from 0
+                    0x00, 0, 1, // Load second function parameter from 1
+                    0x00, 0, 2,    // Load function constant from 2
+                    0x50, // Call function
+                ],
+            }),
+        );
+
+        vm.run();
+
+        assert_eq!(vm.stack.peek(), Primitive::Integer(9));
+    }
+
+    #[test]
+    fn native_function() {
+        let mut vm = VM::new(
+            ObjectMap::from(vec![
+                Object::new(ObjectType::NativeFunction(sloth_std::rand::GEN_FUNCTION)),
+                Object::new(ObjectType::NativeFunction(
+                    sloth_std::rand::GEN_RANGE_FUNCTION,
+                )),
+            ]),
+            Function::root(Chunk {
+                constants: vec![
+                    Primitive::Object(0),
+                    Primitive::Object(1),
+                    Primitive::Integer(5),
+                    Primitive::Integer(10),
+                ],
+                code: vec![
+                    // First part
+                    0x00, 0, 0,    //
+                    0x50, //
+                    0xE0, //
+                    // Second part
+                    0x00, 0, 3, //
+                    0x00, 0, 2, //
+                    0x00, 0, 1,    //
+                    0x50, //
+                ],
+            }),
+        );
+
+        vm.run();
+
+        assert!({
+            let Primitive::Float(i) = vm.stack.peek() else { panic!(); };
+            (0.0..=1.0).contains(&i)
+        });
+
+        vm.run();
+
+        assert!({
+            let Primitive::Integer(i) = vm.stack.peek() else { panic!(); };
+            (5..10).contains(&i)
+        });
+    }
+
+    #[test]
+    fn fibonacci() {
+        #[rustfmt::skip]
+        let mut vm = VM::new(
+            ObjectMap::default(),
+            Function::root(Chunk {
+                constants: vec![
+                    Primitive::Integer(0),
+                    Primitive::Integer(1),
+                    Primitive::Integer(10),
+                ],
+                code: vec![
+                    // Load variables
+                    0x00, 0, 0,  // 0  Index
+                    0x00, 0, 0,  // 3  Me
+                    0x00, 0, 0,  // 6  Parent
+                    0x00, 0, 1,  // 9  Grandparent
+
+                    // Load parent and grandparent, sum them and put the value in me
+                    0x14, 0, 2,  // 12
+                    0x14, 0, 3,  // 15
+                    0x20,        // 16
+                    0x15, 0, 1,  // 19
+                    
+                    // Set grandparent to parent
+                    0x14, 0, 2,  // 22
+                    0x15, 0, 3,  // 25
+                    
+                    // Set parent to me
+                    0x14, 0, 1,  // 28
+                    0x15, 0, 2,  // 31
+
+                    // Increment Index by 1
+                    0x00, 0, 1,  // 34
+                    0x14, 0, 0,  // 37 Index
+                    0x20,        // 40
+                    0x15, 0, 0,  // 41 Index
+
+                    // Load me
+                    0x14, 0, 1,  // 44
+                    0xE0,        // 47
+                    0x11,        // 48
+
+                    // Repeat until Index is 9
+                    0x00, 0, 2,  // 49 
+                    0x14, 0, 0,  // 52 Index
+                    0x31,        // 55
+                    0x41, 0, 12, // 56
+                ],
+            }),
+        );
+
+        let mut values = Vec::new();
+        for _ in 0..10 {
+            vm.run();
+            values.push(vm.stack.peek());
+        }
+
+        assert_eq!(&values, &[
+            Primitive::Integer(1),
+            Primitive::Integer(1),
+            Primitive::Integer(2),
+            Primitive::Integer(3),
+            Primitive::Integer(5),
+            Primitive::Integer(8),
+            Primitive::Integer(13),
+            Primitive::Integer(21),
+            Primitive::Integer(34),
+            Primitive::Integer(55),
+        ]);
+    }
+
+    #[test]
+    fn fibonacci_recursive() {
+        #[rustfmt::skip]
+        let mut vm = VM::new(
+            ObjectMap::from(vec![Object::new(ObjectType::Function(Function {
+                name: Some("fib".to_owned()),
+                chunk: Chunk {
+                    constants: vec![
+                        Primitive::Object(0),
+                        Primitive::Integer(0),
+                        Primitive::Integer(1),
+                        Primitive::Integer(2),
+                    ],
+                    code: vec![
+                        0x14, 0, 0,  // 0
+                        0x00, 0, 1,  // 3
+                        0x31,        // 6
+                        0x41, 0, 14, // 7
+                        0x00, 0, 1,  // 10
+                        0x52,        // 13
+
+                        0x14, 0, 0,  // 14
+                        0x00, 0, 2,  // 17
+                        0x31,        // 20
+                        0x41, 0, 28, // 21
+                        0x00, 0, 2,  // 24
+                        0x52,        // 27
+
+                        // fib(n - 1)
+                        0x00, 0, 2,  // 28
+                        0x14, 0, 0,  // 31
+                        0x21,        // 34
+                        0x00, 0, 0,  // 35
+                        0x50,        // 38
+                        
+                        // fib(n - 2)
+                        0x00, 0, 3,  // 39
+                        0x14, 0, 0,  // 42
+                        0x21,        // 45
+                        0x00, 0, 0,  // 46
+                        0x50,        // 49
+
+                        // add & return
+                        0x20,        // 50
+                        0x52,        // 51
+                    ],
+                },
+                arity: 1,
+                returns_value: true,
+            }))]),
+            Function::root(Chunk {
+                constants: vec![
+                    Primitive::Object(0),
+                    Primitive::Integer(10),
+                ],
+                code: vec![
+                    // Load n and the function and call it
+                    0x00, 0, 1, // 0
+                    0x00, 0, 0, // 3
+                    0x50,       // 6
+                ],
+            }),
+        );
+
+        vm.run();
+
+        assert_eq!(Primitive::Integer(55), vm.stack.peek());
+    }
+}