Skip to content

Instantly share code, notes, and snippets.

@JarrettBillingsley
Last active December 31, 2015 05:29
Show Gist options
  • Save JarrettBillingsley/7940828 to your computer and use it in GitHub Desktop.
Save JarrettBillingsley/7940828 to your computer and use it in GitHub Desktop.
Just a little toy stack-based interpreter I made playing around with Rust for the first time. I'm sure it's gross code :P
use std::rc::{Rc};
use std::gc::{Gc};
use std::cell::{RefCell};
use std::vec;
use std::iter::range_step;
type ValNum = int;
type ValStr = Rc<~str>;
type ValArray = Gc<RefCell<~[Value]>>;
#[deriving(Clone)]
enum Value
{
Null,
Bool(bool),
Num(ValNum),
String(ValStr),
Array(ValArray)
}
fn printValue(v: Value)
{
match v
{
Null => print!("null"),
Bool(b) => print!("{}", b),
Num(n) => print!("{}", n),
String(ref s) => print!("{}", s.borrow().as_slice()),
Array(a) =>
{
print!("[");
let x = a.borrow().borrow();
let mut first = true;
for val in x.get().iter()
{
if first
{ first = false; }
else
{ print!(", "); }
printValue(val.clone());
}
print!("]");
}
}
}
#[deriving(Clone)]
enum Order
{
LT,
LE,
GT,
GE,
EQ,
NE
}
#[deriving(Clone)]
enum Op
{
// Values
PushNull, // Pushes null.
PushBool(bool), // Pushes an immediate boolean.
PushNum(ValNum), // Pushes an immediate number.
PushString(ValStr), // Pushes an immediate string.
NewArray(uint), // Pops top n slots and makes them into an array (top element is last).
NewArraySize, // Expects number >=0 specifying length at top; replaces it with new array filled with null.
// Stack ops
Pop(uint), // Pops n slots.
Dup(uint), // Dups the nth slot down (0 for top) and push it.
Swap(uint), // Swaps the top with the nth slot down.
Insert(uint), // Inserts the top slot into the nth slot, moving other values up.
ToTop(uint), // Inverse of insert; removes the nth slot, and put it on top.
Reverse(uint), // Reverses the order of the top n slots.
// Math
Add, // Pops top 2 nums, performs operation, pushes result.
Sub, // "
Mul, // "
Div, // "
Mod, // "
Cmp(Order), // Pops top 2 nums, pushes bool according to Order.
// Arrays
Idx(uint), // Indexes array in slot n using top num as index; replaces top with the array element.
Idxa(uint), // Assigns value at top into array in slot n, using index at one below top; pops both index and value.
Len(uint), // Pushes a number of the length of the array in slot n.
// Control flow
SkipIfTrue, // Pops a bool; if the value is true, the next instruction is skipped.
Jump(uint), // Jumps to the Label instruction with the same ID.
Label(uint), // Does nothing, just identifies a program point that can be jumped to with Jump.
Call(uint), // Jumps to the label instruction with the given ID, and pushes the return address on the call stack.
Ret, // Pops the return address off the call stack and jumps to it.
Halt, // Halts execution.
// Misc
Print(uint), // Pops the top n slots and prints them, top slot last.
Println(uint), // Same as above but puts a newline after the items.
}
struct Interpreter
{
stack: ~[Value],
code: ~[Op],
pc: uint,
labels: ~[Option<uint>],
callStack: ~[uint],
}
impl Interpreter
{
fn new() -> Interpreter
{
Interpreter
{
stack: ~[],
code: ~[],
pc: 0,
labels: ~[],
callStack: ~[],
}
}
fn run(&mut self, program: ~[Op])
{
self.code = program;
self.pc = 0;
self.callStack = ~[];
self.findLabels();
self.exec();
}
fn findLabels(&mut self)
{
let mut labels: ~[Option<uint>] = ~[];
for (pc, op) in self.code.iter().enumerate()
{
match *op
{
Label(i) =>
{
if i < labels.len()
{
if labels[i].is_some()
{ self.error(format!("Redefinition of label {}", i)); }
}
else
{
let newLen = i - labels.len() + 1;
labels.grow_fn(newLen, |_| None);
}
labels[i] = Some(pc);
}
_ => {}
}
}
self.labels = labels;
}
fn exec(&mut self)
{
while self.pc < self.code.len()
{
let inst = self.code[self.pc].clone();
self.pc += 1;
match inst
{
PushNull => self.push(Null),
PushBool(b) => self.push(Bool(b)),
PushNum(n) => self.push(Num(n)),
PushString(s) => self.push(String(s)),
NewArray(n) => self.newArray(n),
NewArraySize => self.newArraySize(),
Pop(n) => self.pop(n),
Dup(n) => self.dup(n),
Swap(n) => self.swap(n),
Insert(n) => self.insert(n),
ToTop(n) => self.toTop(n),
Reverse(n) => self.reverse(n),
Add => self.mathOp(|a, b| a + b),
Sub => self.mathOp(|a, b| a - b),
Mul => self.mathOp(|a, b| a * b),
Div => self.mathOp(|a, b| a / b),
Mod => self.mathOp(|a, b| a % b),
Cmp(ord) => self.compare(ord),
Idx(n) => self.idx(n),
Idxa(n) => self.idxa(n),
Len(n) => self.len(n),
SkipIfTrue => self.skipIfTrue(),
Jump(n) => self.jumpToLabel(n),
Label(_) => {}
Call(n) => self.call(n),
Ret => self.ret(),
Halt => return,
Print(n) => self.print(n),
Println(n) => self.println(n)
}
}
}
fn push(&mut self, v: Value)
{
self.stack.push(v);
}
fn newArray(&mut self, n: uint)
{
if n > self.stack.len()
{ self.error(format!("Stack underflow")); }
let arr = Gc::new(RefCell::new(self.stack.slice(self.stack.len() - n, self.stack.len()).to_owned()));
self.pop(n);
self.push(Array(arr));
}
fn newArraySize(&mut self)
{
let size = self.getNum(0);
if(size < 0)
{ self.error(format!("Negative array size")); }
self.stack[self.stack.len() - 1] = Array(Gc::new(RefCell::new(vec::from_elem(size as uint, Null))));
}
fn pop(&mut self, n: uint)
{
if n > self.stack.len()
{ self.error(format!("Stack underflow"));; }
let newSize = self.stack.len() - n;
self.stack.truncate(newSize);
}
fn dup(&mut self, n: uint)
{
let v = self.getSlot(n);
self.stack.push(v);
}
fn swap(&mut self, n: uint)
{
if n == 0
{ return; }
let a = self.getSlot(0);
let b = self.getSlot(n);
self.setSlot(n, a);
self.setSlot(0, b);
}
fn insert(&mut self, n: uint)
{
if n == 0
{ return; }
let idx = self.checkSlot(n);
let a = self.getSlot(0);
self.stack.insert(idx, a);
let newLen = self.stack.len() - 1;
self.stack.truncate(newLen);
}
fn toTop(&mut self, n: uint)
{
if n == 0
{ return; }
let idx = self.checkSlot(n);
let a = self.stack[idx].clone();
self.stack.remove(idx);
self.stack.push(a);
}
fn reverse(&mut self, n: uint)
{
if n == 0 || n == 1
{ return; }
else if n > self.stack.len()
{ self.error(format!("Trying to reverse more items than there are on the stack"));; }
let lo = self.stack.len() - n - 1;
let hi = self.stack.len() - 1;
for (i, j) in range(lo, hi).zip(range_step(lo, hi, -1))
{
if i == j
{ continue }
let a = self.stack[i].clone();
self.stack[i] = self.stack[j].clone();
self.stack[j] = a;
}
}
fn mathOp(&mut self, op: |ValNum, ValNum| -> ValNum)
{
let a = self.getNum(1);
let b = self.getNum(0);
self.pop(1);
self.stack[self.stack.len() - 1] = Num(op(a, b));
}
fn compare(&mut self, ord: Order)
{
let a = self.getNum(1);
let b = self.getNum(0);
self.pop(1);
self.stack[self.stack.len() - 1] = Bool(match ord
{
LT => a < b,
LE => a <= b,
GT => a > b,
GE => a >= b,
EQ => a == b,
NE => a != b
});
}
fn idx(&mut self, slot: uint)
{
let arr = self.getArray(slot);
let idx = self.getNum(0);
// Eugh D:
let x = arr.borrow().borrow();
if idx < 0 || idx as uint >= x.get().len()
{ self.error(format!("Invalid array index"));; }
self.stack[self.stack.len() - 1] = x.get()[idx].clone();
}
fn idxa(&mut self, slot: uint)
{
let arr = self.getArray(slot);
let idx = self.getNum(1);
// There has to be an easier way :S
let mut x = arr.borrow().borrow_mut();
if idx < 0 || idx as uint >= x.get().len()
{ self.error(format!("Invalid array index"));; }
let val = self.getSlot(0);
x.get()[idx] = val;
self.pop(2);
}
fn len(&mut self, slot: uint)
{
let arr = self.getArray(slot);
// Just ugly!
let x = arr.borrow().borrow();
self.push(Num(x.get().len() as ValNum));
}
fn skipIfTrue(&mut self)
{
let b = self.getBool(0);
self.pop(1);
if b
{ self.pc += 1; }
}
fn jumpToLabel(&mut self, i: uint)
{
if i < self.labels.len() && self.labels[i].is_some()
{ self.pc = self.labels[i].unwrap(); }
else
{ self.error(format!("No label {} has been defined", i));; }
}
fn call(&mut self, i: uint)
{
self.callStack.push(self.pc);
self.jumpToLabel(i);
}
fn ret(&mut self)
{
match self.callStack.pop_opt()
{
Some(pc) => self.pc = pc,
None => self.error(format!("Call stack underflow"))
}
}
fn print(&mut self, n: uint)
{
if n > self.stack.len()
{ self.error(format!("Stack underflow"));; }
for i in range(self.stack.len() - n, self.stack.len())
{
printValue(self.stack[i].clone());
}
self.pop(n);
}
fn println(&mut self, n: uint)
{
self.print(n);
print!("\n");
}
// =================================================================================================================
// Low-level helpers
fn getNum(&self, n: uint) -> ValNum
{
match self.getSlot(n)
{
Num(n) => return n,
_ => self.error(format!("Expected number"))
}
}
fn getBool(&self, n: uint) -> bool
{
match self.getSlot(n)
{
Bool(b) => return b,
_ => self.error(format!("Expected bool"))
}
}
fn getArray(&self, n: uint) -> ValArray
{
match self.getSlot(n)
{
Array(a) => return a,
_ => self.error(format!("Expected array"))
}
}
fn getSlot(&self, n: uint) -> Value
{
self.stack[self.checkSlot(n)].clone()
}
fn setSlot(&mut self, n: uint, v: Value)
{
self.stack[self.checkSlot(n)] = v;
}
fn checkSlot(&self, n: uint) -> uint
{
if n >= self.stack.len()
{ self.error(format!("Invalid stack index")); }
return self.stack.len() - n - 1;
}
fn error(&self, msg: ~str) -> !
{
println!("!!! Error at pc = {}: {}", self.pc - 1, msg);
println!("Stack dump:");
for (i, v) in self.stack.iter().enumerate()
{
print!("{}: ", i);
printValue(v.clone());
println!("");
}
fail!();
}
}
// makes it a little less verbose :P
fn pushString(s: ~str) -> Op { PushString(Rc::new(s)) }
fn main()
{
loopExample();
arrayExample();
callExample();
}
fn loopExample()
{
println!("Let's loop from 1 to 10!");
let mut i = Interpreter::new();
i.run(~[
PushNum(1),
Label(0),
Dup(0),
PushNum(10),
Cmp(LE),
SkipIfTrue,
Jump(1),
Dup(0),
Println(1),
Dup(0),
PushNum(1),
Add,
Swap(1),
Pop(1),
Jump(0),
Label(1)
]);
println!("");
}
fn arrayExample()
{
println!("Let's make an array, then loop over it and double the elements!");
let mut i = Interpreter::new();
i.run(~[
PushNum(1), // 1
PushNum(2), // 1 2
PushNum(3), // 1 2 3
NewArray(3), // a
Dup(0), // a a
Println(1), // a
Len(0), // a 3
PushNum(1), // a 3 1
Sub, // a i
Label(0),
Dup(0), // a i i
PushNum(0), // a i i 0
Cmp(GE), // a i c
SkipIfTrue, // a i
Jump(1),
Dup(0), // a i i
Dup(0), // a i i i
Idx(3), // a i i v
PushNum(2), // a i i v 2
Mul, // a i i v
Idxa(3), // a i
PushNum(1), // a i 1
Sub, // a i
Jump(0),
Label(1),
Pop(1), // a
Println(1), //
]);
println!("");
}
static Fib: uint = 10;
fn callExample()
{
println!("Let's make a fibonacci function and call it with numbers from 0 to 10!");
let mut i = Interpreter::new();
i.run(~[
PushNum(0),
Label(0),
Dup(0),
PushNum(10),
Cmp(LE),
SkipIfTrue,
Halt,
pushString(~"fib("),
Dup(1),
pushString(~") = "),
Dup(1),
Call(Fib),
Println(4),
PushNum(1),
Add,
Jump(0),
Label(Fib), // i
Dup(0), // i i
PushNum(1), // i i 1
Cmp(LE), // i c
SkipIfTrue, // i
Jump(Fib + 1), // i
Pop(1), //
PushNum(1), // 1
Ret,
Label(Fib + 1), // i
Dup(0), // i i
PushNum(1), // i i 1
Sub, // i i-1
Call(Fib), // i fib(i-1)
Dup(1), // i fib(i-1) i
PushNum(2), // i fib(i-1) i 2
Sub, // i fib(i-1) i-2
Call(Fib), // i fib(i-1) fib(i-2)
Add, // i ret
Swap(1), // ret i
Pop(1), // ret
Ret, // ret
]);
println!("");
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment