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

interp.rs

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!("");
}