A super simple bytecode VM

demo.bytecode

Push 0
Push 0

-- accumulator is 0
-- index is 1

-- adds index to accumulator
Get 0
Get 1
Add
Set 0
Pop

-- adds one to index
Get 1
Push 1
Add
Set 1
-- index is on top of the stack

-- if index is 4, jump back to line 7
Push 100
Sub
JNE 7
Get 0

fib.bytecode

Push 1
Push 1
Push 0
Push 0
-- [a, b, i, buffer], the buffer is the result of sub before JNE
Pop
Get 0
Get 1
-- [a, b, i, a, b]
Set 0
-- [b, b, i, a, b]
Add
-- [b, b, i, a + b]
Set 1
Pop
-- [b, a + b, i]

-- print a
Get 0
Print
Pop

-- Add 1 to index
Get 2
Push 1
Add
Set 2
-- index on top, jump to start of loop if not 30
Push 30
Sub
JNE 5

vm.hs

{-# LANGUAGE OverloadedStrings #-}

import System.Environment
import Data.Maybe
import Data.Either
import Debug.Trace
import qualified Data.Text as T
import qualified Data.Text.Read as R

-- Instruction Codes
data Inst
    = Push Int
    | Pop
    | Add
    | Sub
    | Mul
    | Div
    | Jump Int
    | JE Int
    | JNE Int
    | Get Int
    | Set Int
    | Noop

-- A program is a list of an instructions
type Program = [Inst]

-- The stack is a stack of integers
type Stack   = [Int]

-- The instruction pointer is just an integer
type Pointer = Int

replace :: Pointer -> Int -> Stack -> Stack
replace pos newVal list = take pos list ++ newVal : drop (pos+1) list

interpret :: Pointer -> Program -> Stack -> Int
interpret i code stack = case (code!!i) of
    _ | i >= length code -> head stack
    Noop     -> interpret (i+1) code stack
    --_ | trace ((show i) ++ " " ++ (show stack)) False -> error "unreachable"
    (Push x) -> interpret (i+1) code (x:stack)
    Pop      -> interpret (i+1) code (tail stack)
    Add      -> interpret (i+1) code (a+b:xs) where (a:b:xs) = stack
    Sub      -> interpret (i+1) code (b-a:xs) where (a:b:xs) = stack
    Mul      -> interpret (i+1) code (a*b:xs) where (a:b:xs) = stack
    Div      -> interpret (i+1) code (b `div` a : xs) where (a:b:xs) = stack
    (Jump d) -> interpret  d    code stack
    (JE x)   -> interpret  d    code stack where d = if (head stack) == 0 then x else (i + 1)
    (JNE x)  -> interpret  d    code stack where d = if (head stack) /= 0 then x else (i + 1)
    (Get x)  -> interpret (i+1) code ((stack!!(length stack - x - 1)):stack)
    (Set x)  -> interpret (i+1) code (replace (length stack - x - 1) (head stack) stack)

parseInt :: T.Text -> Int
parseInt = fst . (fromRight (error "bad int")) . R.decimal

parseInst :: T.Text -> Maybe Inst
parseInst l = case spl of
                ["Push", x] -> Just (Push (parseInt x :: Int))
                ["Pop"]     -> Just Pop
                ["Add"]     -> Just Add
                ["Sub"]     -> Just Sub
                ["Mul"]     -> Just Mul
                ["Div"]     -> Just Div
                ["Jump", x]    -> Just (Jump (parseInt x))
                ["JE", x]   -> Just (JE (parseInt x))
                ["JNE", x]  -> Just (JNE (parseInt x))
                ["Get", x]  -> Just (Get (parseInt x))
                ["Set", x]  -> Just (Set (parseInt x))
                _           -> Just Noop
              where spl = T.words l

main = do
    args <- getArgs
    contents <- readFile (head args)
    let insts = map (fromJust . parseInst . T.pack) (lines contents)
    print $ interpret 0 insts []

vm.rs

use std::io::Read;

type Pointer = usize;
type Program<'a> = &'a [Inst];

struct Stack(Vec<isize>);

impl Stack {
    fn push(&mut self, v: isize) {
        self.0.push(v);
    }

    fn pop(&mut self) -> isize {
        self.0.pop().expect("popped an empty stack")
    }

    fn peek(&mut self) -> isize {
        *self.0.last().expect("popped an empty stack")
    }
}

#[derive(Debug)]
enum Inst {
    Push(isize),
    Pop,
    Add,
    Sub,
    Mul,
    Div,
    Jump(Pointer),
    JE(Pointer),
    JNE(Pointer),
    Get(Pointer),
    Set(Pointer),
    Noop,
    Print,
    PrintStack,
}

fn interpret<'a>(program: Program<'a>) -> isize {
    use Inst::*;

    let mut stack: Stack = Stack(Vec::new());
    let mut pointer: Pointer = 0;

    while let Some(instruction) = program.get(pointer) {
        pointer += 1;

        match instruction {
            Push(d) => stack.push(*d),
            Pop => {
                stack.pop();
            }
            Add => {
                let (a, b) = (stack.pop(), stack.pop());
                stack.push(a + b)
            }
            Sub => {
                let (a, b) = (stack.pop(), stack.pop());
                stack.push(b - a)
            }
            Mul => {
                let (a, b) = (stack.pop(), stack.pop());
                stack.push(a * b)
            }
            Div => {
                let (a, b) = (stack.pop(), stack.pop());
                stack.push(b / a)
            }
            Jump(p) => pointer = *p,
            JE(p) => {
                if stack.peek() == 0 {
                    pointer = *p;
                }
            }
            JNE(p) => {
                if stack.peek() != 0 {
                    pointer = *p;
                }
            }
            Get(i) => stack.push(*stack.0.get(*i).expect(&format!(
                "Tried to access index {} with stack of length {}",
                i,
                stack.0.len(),
            ))),
            Set(i) => {
                let t = stack.peek();
                *stack.0.get_mut(*i).unwrap() = t;
            }
            Print => println!("{}", stack.peek()),
            PrintStack => println!("{:?}", stack.0),
            Noop => {}
        }
    }

    stack.pop()
}

fn parse_instruction(s: &str) -> Inst {
    use Inst::*;

    match s.split_whitespace().collect::<Vec<_>>().as_slice() {
        ["Push", x] => Push(x.parse::<isize>().unwrap()),
        ["Pop"] => Pop,
        ["Add"] => Add,
        ["Sub"] => Sub,
        ["Mul"] => Mul,
        ["Div"] => Div,
        ["Jump", x] => Jump(x.parse::<Pointer>().unwrap()),
        ["JE", x] => JE(x.parse::<Pointer>().unwrap()),
        ["JNE", x] => JNE(x.parse::<Pointer>().unwrap()),
        ["Get", x] => Get(x.parse::<Pointer>().unwrap()),
        ["Set", x] => Set(x.parse::<Pointer>().unwrap()),
        ["Print"] => Print,
        ["PrintStack"] => PrintStack,
        [] | ["--", ..] => Noop,
        l => panic!("Invalid instruction: {:?}", l),
    }
}

fn main() -> std::io::Result<()> {
    let args: Vec<String> = std::env::args().collect();
    let mut f = std::fs::File::open(&args[1])?;

    let mut buffer = String::new();
    f.read_to_string(&mut buffer)?;

    let instructions: Vec<Inst> = buffer.split('\n').map(parse_instruction).collect();

    interpret(&instructions[..]);

    Ok(())
}

Haskell version is super slow because it's using linkedlists so variable access and instruction access is O(n) but it keeps the syntax simple.

The Rust version is very fast.

Noop has to stay around for the comments so that Jumps can just reference the line number.