Skip to content

Instantly share code, notes, and snippets.

@ndmitchell
Created April 28, 2020 20:47
Show Gist options
  • Save ndmitchell/084bb1a8dd30188492fcd0b8b8c70c6e to your computer and use it in GitHub Desktop.
Save ndmitchell/084bb1a8dd30188492fcd0b8b8c70c6e to your computer and use it in GitHub Desktop.
Various forms of interpreter
#![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());
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment