dynamic_stack_lang.rs

extern crate collections;

use std::fmt;
use std::io;
use collections::HashMap;

fn main() {
    let mut stdin = io::stdin();
    let mut env = (~[], words::default());
    loop {
        let line = stdin.read_line().unwrap();
        env = eval(env, parse(line));
    }
}

pub type Stack = ~[Term];

pub type Words = HashMap<~str, (Term, Option<~str>)>;

pub type Env = (Stack, Words);

#[deriving(Clone)]
pub enum Term {
    Bool(bool),
    I32(i32),
    String(~str),
    Word(~str),
    Quote(~[Term]),
    Extern(fn(Env) -> Env),
}

impl Term {
    pub fn to_bool(self) -> bool {
        match self { Bool(x) => x, _ => fail!() }
    }
    pub fn to_i32(self) -> i32 {
        match self { I32(x) => x, _ => fail!() }
    }
    pub fn to_string(self) -> ~str {
        match self { String(x) => x, _ => fail!() }
    }
}

impl fmt::Show for Term {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match *self {
            Bool(x)          => write!(f.buf, "{}", x),
            I32(x)           => write!(f.buf, "{}", x),
            String(ref s)    => write!(f.buf, "\"{}\"", *s),
            Word(ref word)   => write!(f.buf, "{}", *word),
            Quote(ref terms) => write!(f.buf, "[ {} ]", *terms),
            Extern(_)        => write!(f.buf, "<extern>"),
        }
    }
}

impl fmt::Char for Term {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match *self {
            Bool(x)          => write!(f.buf, "{}", x),
            I32(x)           => write!(f.buf, "{}", x),
            String(ref s)    => write!(f.buf, "{}", *s),
            Word(ref word)   => write!(f.buf, "<word: {}>", *word),
            Quote(ref terms) => write!(f.buf, "<quote: {}>", *terms),
            Extern(_)        => write!(f.buf, "<extern: ???>"),
        }
    }
}

pub fn parse(s: &str) -> Term {
    Quote(s.words().map(|word| {
        match word {
            "[" => {
                // TODO: parse begin quote
                unimplemented!()
            },
            "]" => {
                // TODO: parse end quote
                unimplemented!()
            },
            word if word.starts_with("\"") => {
                assert!(word.ends_with("\""), "expected closing double quote");
                String(word.slice(1, word.len() - 1).to_owned())
            },
            word => from_str(word).map(|x| Bool(x)).or_else(||
                    from_str(word).map(|x| I32(x))).unwrap_or(Word(word.to_owned())),
        }
    }).collect())
}

pub fn eval(env: Env, term: Term) -> Env {
    match term {
        Word(word) => match get_def(&env, word).clone() {
            Extern(f)      => f(env),
            t @ Word(_)    => eval(env, t),
            t @ Quote(_)   => eval(env, t),
            t @ Bool(_)    => push(env, t),
            t @ I32(_)     => push(env, t),
            t @ String(_)  => push(env, t),
        },
        Quote(terms) => terms.move_iter().fold(
            env, |env, term| { eval(env, term) }
        ),
        x => push(env, x),
    }
}

pub fn get_def<'a>(&(_, ref words): &'a Env, ident: ~str) -> &'a Term {
    words.find(&ident).expect(format!("word not found: {}", ident)).ref0()
}

pub fn last<'a>(&(ref stack, _): &'a Env) -> &'a Term {
    stack.last().expect("stack is empty")
}

pub fn pop((mut stack, words): Env) -> (Env, Term) {
    let x = stack.pop().expect("stack underflow");
    ((stack, words), x)
}

pub fn push((mut stack, words): Env, term: Term) -> Env {
    stack.push(term);
    (stack, words)
}

pub fn binop(env: Env, f: |Term, Term| -> Term) -> Env {
    let (env, x) = pop(env);
    let (env, y) = pop(env);
    push(env, f(x, y))
}

pub mod words {
    use super::{Bool, Env, Extern, I32, Quote, Words};

    pub fn default() -> Words {
        (~[
            (~"==",     (Extern(eq),       None)),
            (~"not",    (Extern(not),      Some(~"Negates a boolean value."))),
            (~"+",      (Extern(add),      Some(~"Adds the top two values in the stack."))),
            (~"-",      (Extern(sub),      Some(~"Subtracts the top two values in the stack."))),
            (~"*",      (Extern(mul),      Some(~"Multiplies the top two values in the stack."))),
            (~"/",      (Extern(div),      Some(~"Divides the top two values in the stack."))),
            (~"%",      (Extern(rem),      Some(~"Finds the remainder of the top two values in the stack."))),
            (~"neg",    (Extern(neg),      Some(~"Negates the top value in the stack."))),
            (~"dup",    (Extern(dup),      Some(~"Duplicates the top term in the stack."))),
            (~"pop",    (Extern(pop),      None)),
            (~"eval",   (Extern(eval),     Some(~"Evaluates the top term in the stack."))),
            (~"quote",  (Extern(quote),    None)),
            (~".",      (Extern(show),     Some(~"Prints top term in the stack."))),
            (~"stack",  (Extern(stack_),   Some(~"Prints the entire contents of the stack."))),
            (~"words",  (Extern(words),    Some(~"Prints the words currently in the environment."))),
        ]).move_iter().collect()
    }

    // == (A . A A -> A A bool)
    pub fn eq(_: Env) -> Env {
        // super::binop(env, |x, y| Bool(x == y))
        unimplemented!()
    }

    // not (bool -> bool)
    pub fn not(env: Env) -> Env {
        let (env, x) = super::pop(env);
        super::push(env, Bool(!x.to_bool()))
    }

    // + (i32 i32 -> i32)
    pub fn add(env: Env) -> Env {
        super::binop(env, |x, y| {
            I32(x.to_i32() + y.to_i32())
        })
    }

    // - (i32 i32 -> i32)
    pub fn sub(env: Env) -> Env {
        super::binop(env, |x, y| {
            I32(x.to_i32() - y.to_i32())
        })
    }

    // * (i32 i32 -> i32)
    pub fn mul(env: Env) -> Env {
        super::binop(env, |x, y| {
            I32(x.to_i32() * y.to_i32())
        })
    }

    // / (i32 i32 -> i32)
    pub fn div(env: Env) -> Env {
        super::binop(env, |x, y| {
            I32(x.to_i32() / y.to_i32())
        })
    }

    // % (i32 i32 -> i32)
    pub fn rem(env: Env) -> Env {
        super::binop(env, |x, y| {
            I32(x.to_i32() % y.to_i32())
        })
    }

    // neg (i32 i32 -> i32)
    pub fn neg(env: Env) -> Env {
        let (env, x) = super::pop(env);
        super::push(env, I32(-x.to_i32()))
    }

    // dup (A . A -> A A)
    pub fn dup(env: Env) -> Env {
        let x = super::last(&env).clone();
        super::push(env, x)
    }

    // pop (A . A ->)
    pub fn pop(env: Env) -> Env {
        let (env, _) = super::pop(env); env
    }

    // quote (A . A -> (-> A))
    pub fn quote(env: Env) -> Env {
        let (env, x) = super::pop(env);
        super::push(env, Quote(~[x]))
    }

    // eval (A . (-> A) -> A)
    pub fn eval(env: Env) -> Env {
        let (env, x) = super::pop(env);
        super::eval(env, x)
    }

    // show (A . A -> A)
    pub fn show(env: Env) -> Env {
        println!("{:c}", *super::last(&env)); env
    }

    // stack (->)
    pub fn stack_((stack, words): Env) -> Env {
        for x in stack.iter() {
            print!("{} ", *x);
        }
        println!("");
        (stack, words)
    }

    // words (->)
    pub fn words((stack, words): Env) -> Env {
        for (word, _) in words.iter() {
            print!("{} ", *word);
        }
        println!("");
        (stack, words)
    }
}