A simple stack based evaluator

gistfile1.rs

//! A simple stack based evaluator.
//! You can modify this code to create your own domain specific language.
//!
//! Terminology:
//! - A 'stack' here is represented as a vector.
//! - The 'top' of the stack means the end of the vector.
//!
//! In this example we will create a language that evaluates:
//!
//!     Point3D
//!         +
//!             5.0
//!             4.0
//!         3.0
//!         1.0
//!

/// Contains the generic code for stack evaluation.
mod eval {

    /// A function reads from the top of the stack.
    /// If it succeeds, it returns a value and a number.
    /// The number tells how many '.pop()' to call before adding
    /// the computed value to the stack.
    type Function<T> = fn(&[T]) -> Option<(T, int)>;

    /// Evaluates a list of functions on top of stack.
    pub fn eval_stack_top<T>(functions: &[Function<T>], stack: &mut ~[T]) {
        let mut run = true;
        // Run in a loop while any function does something.
        while run {
            run = false;
            for f in functions.iter() {
                match (*f)(*stack) {
                    Some((token, n)) => {
                        // The function succeeded.
                        // Remove the unused values from the stack.
                        for _ in range(0, n) { stack.pop(); }
                        // Put in the new value.
                        stack.push(token);
                        // Tell we did something.
                        run = true;
                    },
                    None => {},
                }
            }
        }
    }

}

/// A token is any form of value that can be on the stack.
/// They can represent computed values, expressions, etc.
pub enum Token<'a> {
    /// Unparsed values and function names are represented as strings.
    Str(&'a str),
    /// Returned by the 'add' function.
    Num(f64),
    /// Returned by the 'point3d' function.
    Point3D(f64, f64, f64),
}

impl<'a> Token<'a> {
    /// Converts a token to a f64 number.
    /// This is called by functions that expect 'f64' as argument.
    /// If the token is a string, it becomes converted.
    pub fn to_num(&'a self) -> Option<f64> {
        match *self {
            Num(val) => Some(val),
            Str(text) => from_str(text),
            _ => None
        }
    }
}

/// Adds two numbers.
///
///     '+'
///         .to_num()
///         .to_num()
///
pub fn add(t: &[Token]) -> Option<(Token, int)> {
    let n = t.len();
    // Check that the stack is big enough.
    if n < 3 { return None; }
    // Pattern match the top of the stack.
    match (t[n-3], t[n-2], t[n-1]) {
        (Str(&"+"), a, b) => match (a.to_num(), b.to_num()) {
            (Some(a), Some(b)) => Some((Num(a + b), 3)),
            _ => None,
        },
        _ => None
    }
}

/// Creates a 'Point3D' token.
///
///     'Point3D'
///         .to_num()
///         .to_num()
///         .to_num()
///
pub fn point3d(t: &[Token]) -> Option<(Token, int)> {
    let n = t.len();
    // Check that the stack is big enough.
    if n < 4 { return None; }
    // Pattern match the top of the stack.
    match (t[n-4], t[n-3], t[n-2], t[n-1]) {
        (Str(&"Point3D"), x, y, z) => 
            match (x.to_num(), y.to_num(), z.to_num()) {
                (Some(x), Some(y), Some(z)) => 
                    Some((Point3D(x, y, z), 4)),
                _ => None,
            },
        _ => None
    }
}

fn main() {
    // The list of functions.
    let functions = [add, point3d];

    // The program we want to evaluate.
    let program = ~[
        "Point3D", 
            "+",
                "4.0",
                "5.0", 
            "3.0", 
            "1.0"
    ];

    // Turn the program into a list of tokens.
    let program: ~[Token] = program.iter().map(|&x| Str(x)).collect();
    // Create a stack.
    let mut stack: ~[Token] = ~[];
    // Push instructions one by one on the stack.
    for token in program.iter() {
        stack.push(*token);
        // Evaluate the top of stack.
        eval::eval_stack_top(functions, &mut stack);
        // Print out the content on the stack.
        println!("{:?}", stack);
    }

    // Output:
    // ~[Str("Point3D")]
    // ~[Str("Point3D"), Str("+")]
    // ~[Str("Point3D"), Str("+"), Str("4.0")]
    // ~[Str("Point3D"), Num(9f64)]
    // ~[Str("Point3D"), Num(9f64), Str("3.0")]
    // ~[Point3D(9f64, 3f64, 1f64)]
}