Various forms of interpreter

main.rs

#![feature(box_syntax)]

use std::time::Instant;

enum Expr {
    Lit(i64),
    Var(usize),
    Add(Box<Expr>, Box<Expr>),
    Assign(usize, Box<Expr>),
    Then(Box<Expr>, Box<Expr>),
    While(Box<Expr>, Box<Expr>),
}

fn interp_ast(x: Box<Expr>) -> i64 {
    fn f(x: &Expr, slots: &mut Vec<i64>) -> i64 {
        match x {
            Expr::Lit(i) => *i,
            Expr::Var(u) => slots[*u],
            Expr::Add(x, y) => f(x, slots) + f(y, slots),
            Expr::Then(x, y) => {
                f(x, slots);
                f(y, slots)
            }
            Expr::Assign(u, x) => {
                let v = f(x, slots);
                slots[*u] = v;
                v
            }
            Expr::While(a, b) => {
                while f(a, slots) != 0 {
                    f(b, slots);
                }
                0
            }
        }
    }

    let mut slots = vec![0; 10];
    f(&*x, &mut slots)
}

/*
#0 = 1000
#1 = 100
while (#0)
    #1 = #1 + 4 + #1 + 3
    #1 = #1 + 2 + 4
    #0 = #0 + -2
#1
*/

fn program_ast() -> Box<Expr> {
    fn assign(x: usize, y: Box<Expr>) -> Box<Expr> {
        box Expr::Assign(x, y)
    }
    fn thens(mut x: Vec<Box<Expr>>) -> Box<Expr> {
        let mut res = x.pop().unwrap();
        while let Some(v) = x.pop() {
            res = box Expr::Then(v, res);
        }
        res
    }
    fn adds(mut x: Vec<Box<Expr>>) -> Box<Expr> {
        let mut res = x.pop().unwrap();
        while let Some(v) = x.pop() {
            res = box Expr::Add(v, res);
        }
        res
    }
    fn lit(x: i64) -> Box<Expr> {
        box Expr::Lit(x)
    }
    fn while_(x: Box<Expr>, y: Box<Expr>) -> Box<Expr> {
        box Expr::While(x, y)
    }
    fn var(x: usize) -> Box<Expr> {
        box Expr::Var(x)
    }

    thens(vec![
        assign(0, lit(50000000)),
        assign(1, lit(100)),
        while_(
            var(0),
            thens(vec![
                assign(1, adds(vec![var(1), lit(4), var(1), lit(3)])),
                assign(1, adds(vec![var(1), lit(2), lit(4)])),
                assign(0, adds(vec![var(0), lit(-1)])),
            ]),
        ),
        var(1),
    ])
}

type Compiled = Box<dyn Fn(&mut Vec<i64>) -> i64>;

fn compile(x: &Expr) -> Compiled {
    match x {
        Expr::Lit(i) => {
            let i = *i;
            box move |_| i
        }
        Expr::Var(u) => {
            let u = *u;
            box move |slots| slots[u]
        }
        Expr::Add(x, y) => {
            let x = compile(x);
            let y = compile(y);
            box move |slots| x(slots) + y(slots)
        }
        Expr::Then(x, y) => {
            let x = compile(x);
            let y = compile(y);
            box move |slots| {
                x(slots);
                y(slots)
            }
        }
        Expr::Assign(u, x) => {
            let x = compile(x);
            let u = *u;
            box move |slots| {
                let v = x(slots);
                slots[u] = v;
                v
            }
        }
        Expr::While(a, b) => {
            let a = compile(a);
            let b = compile(b);
            box move |slots| {
                while a(slots) != 0 {
                    b(slots);
                }
                0
            }
        }
    }
}

enum Bytecode {
    Assign(u32),  // assign the value at the top of the stack to a slot
    Var(u32),     // push the value in slot to the top of the stack
    Lit(i32),     // push a literal on the stack
    Add,          // Add the top two items on the stack
    Jump(u32),    // Jump to a program counter
    JumpIf0(u32), // Jump to a PC if a value is 0
    Done,
}

fn bytecode() -> Vec<Bytecode> {
    use Bytecode::*;
    let prefix = vec![Lit(50000000), Assign(0), Lit(100), Assign(1)];
    let inner1 = vec![Var(1), Lit(4), Var(1), Lit(3), Add, Add, Add, Assign(1)];
    let inner2 = vec![Var(1), Lit(2), Lit(4), Add, Add, Assign(1)];
    let inner3 = vec![Var(0), Lit(-1), Add, Assign(0)];
    let prefix_len = prefix.len();
    let inner_len = inner1.len() + inner2.len() + inner3.len();

    let mut res = Vec::new();
    res.extend(prefix);
    res.push(Var(0));
    res.push(JumpIf0((res.len() + 1 + inner_len + 1) as u32));
    res.extend(inner1);
    res.extend(inner2);
    res.extend(inner3);
    res.push(Jump(prefix_len as u32));
    res.push(Var(1));
    res.push(Done);
    res
}

fn smaller_bytecode(xs: &[Bytecode]) -> Vec<u8> {
    fn f(x: &Bytecode, pcs: &Vec<usize>, res: &mut Vec<u8>) {
        use Bytecode::*;
        match x {
            Assign(x) => {
                res.push(0);
                res.push(*x as u8);
            }
            Var(x) => {
                res.push(1);
                res.push(*x as u8);
            }
            Lit(x) => {
                if *x == 50000000 {
                    res.push(2);
                } else {
                    res.push(3);
                    res.push(*x as i8 as u8);
                }
            }
            Add => res.push(4),
            Jump(x) => {
                res.push(5);
                res.push(pcs[*x as usize] as u8);
            }
            JumpIf0(x) => {
                res.push(6);
                res.push(pcs[*x as usize] as u8);
            }
            Done => res.push(7),
        }
    }

    let pcs0 = vec![0; xs.len()];
    let mut pcs = Vec::new();
    let mut res = Vec::new();
    let mut pc = 0;
    for x in xs {
        pcs.push(pc);
        res.clear();
        f(x, &pcs0, &mut res);
        pc += res.len();
    }
    res.clear();
    for x in xs {
        f(x, &pcs, &mut res);
    }
    res
}

struct Stack {
    ptr: usize,
    vals: [i64; 100],
}

impl Stack {
    fn new() -> Self {
        Self {
            ptr: 0,
            vals: [0; 100],
        }
    }

    fn pop(&mut self) -> i64 {
        self.ptr -= 1;
        unsafe { *self.vals.get_unchecked(self.ptr) }
    }

    fn push(&mut self, x: i64) {
        unsafe { *self.vals.get_unchecked_mut(self.ptr) = x };
        self.ptr += 1;
    }
}

fn exec_bytecode_bytes(xs: &[u8]) -> i64 {
    let mut pc = 0;
    let mut slots = vec![0; 10];
    let mut stack = Stack::new();

    loop {
        // println!("{} at {} is {:?}", pc, stack.len(), slots);
        unsafe {
            match *xs.get_unchecked(pc) {
                0 => {
                    *slots.get_unchecked_mut(*xs.get_unchecked(pc + 1) as usize) = stack.pop();
                    pc += 2;
                }
                1 => {
                    stack.push(*slots.get_unchecked(*xs.get_unchecked(pc + 1) as usize));
                    pc += 2;
                }
                2 => {
                    stack.push(50000000);
                    pc += 1;
                }
                3 => {
                    stack.push(*xs.get_unchecked(pc + 1) as i8 as i64);
                    pc += 2;
                }
                4 => {
                    let x = stack.pop();
                    let y = stack.pop();
                    stack.push(x + y);
                    pc += 1;
                }
                5 => {
                    pc = *xs.get_unchecked(pc + 1) as usize;
                }
                6 => {
                    if stack.pop() == 0 {
                        pc = *xs.get_unchecked(pc + 1) as usize;
                    } else {
                        pc += 2;
                    }
                }
                7 => return stack.pop(),
                _ => unreachable!(),
            }
        }
    }
}

fn exec_bytecode(xs: &[Bytecode]) -> i64 {
    let mut pc = 0;
    let mut slots = vec![0; 10];
    let mut stack = Stack::new();

    loop {
        use Bytecode::*;
        // println!("{} at {} is {:?}", pc, stack.len(), slots);
        match xs[pc] {
            Assign(x) => slots[x as usize] = stack.pop(),
            Var(x) => stack.push(slots[x as usize]),
            Lit(i) => stack.push(i as i64),
            Add => {
                let x = stack.pop();
                let y = stack.pop();
                stack.push(x + y)
            }
            Jump(pc2) => pc = pc2 as usize - 1,
            JumpIf0(pc2) => {
                if stack.pop() == 0 {
                    pc = pc2 as usize - 1;
                }
            }
            Done => return stack.pop(),
        }
        pc = pc + 1;
    }
}

fn raw() -> i64 {
    let mut x0: i64 = 50000000;
    let mut x1: i64 = 100;
    while x0 != 0 {
        x1 = x1 + 4 + x1 + 3;
        x1 = x1 + 2 + 4;
        x0 = x0 - 1;
    }
    x1
}

fn main() {
    let ast = program_ast();
    let start = Instant::now();
    let res = interp_ast(ast);
    let stop = start.elapsed();
    println!("AST is {} in {:.3}", res, stop.as_secs_f64());

    let compiled = compile(&program_ast());
    let start = Instant::now();
    let mut slots = vec![0; 10];
    let res = compiled(&mut slots);
    let stop = start.elapsed();
    println!("Compiled is {} in {:.3}", res, stop.as_secs_f64());

    let start = Instant::now();
    let res = raw();
    let stop = start.elapsed();
    println!("Raw is {} in {:.3}", res, stop.as_secs_f64());

    let bc = bytecode();
    let start = Instant::now();
    let res = exec_bytecode(&bc);
    let stop = start.elapsed();
    println!("Bytecode is {} in {:.3}", res, stop.as_secs_f64());

    let bc2 = smaller_bytecode(&bc);
    let start = Instant::now();
    let res = exec_bytecode_bytes(&bc2);
    let stop = start.elapsed();
    println!("Bytecode bytes is {} in {:.3}", res, stop.as_secs_f64());
}