Rustでインタプリタを実装 (元ネタ: http://qiita.com/shuetsu@github/items/ac21e597265d6bb906dc)

washilang.rs

#![feature(question_mark)]

extern crate combine;

use combine::{ParseResult, ParseError};
use std::collections::HashMap;
use std::rc::Rc;

fn parse_expr(s: &str) -> Result<Expression, ParseError<combine::State<&str>>> {
    use combine::{Parser, State};
    use combine::combinator::{parser, between, many1, satisfy, skip_many,
        skip_many1, token, eof, try, optional};
    use combine::char::{space, newline};
    use combine::range::{range, take_while1};

    macro_rules! skip_chars {
        () => { skip_many(space().or(newline())) }
    }

    fn parse_arg(s: State<&str>) -> ParseResult<Expression, State<&str>> {
        let unit = try((token('('), skip_chars!(), token(')')).map(|_| Expression::Value(Value::Unit)));

        let int = (optional(token('-').or(token('+'))), take_while1(|c: char| c.is_digit(10)))
            .map(|(sign, ds): (Option<char>, &str)| {
                let mut s = String::with_capacity(if sign.is_some() { 1 } else { 0 } + ds.len());
                if let Some(sign) = sign {
                    s.push(sign);
                }
                s.push_str(ds);
                Expression::Value(Value::Int(s.parse().unwrap()))
            });

        // FIXME: handle escape sequences
        let string = (token('\"'), many1::<String, _>(satisfy(|c: char| c != '"')), token('\"'))
            .map(|(_, s, _)| Expression::Value(Value::Str(s)));

        let boolean =
            try(range("true")
                .map(|_| Expression::Value(Value::Bool(true))))
            .or(try(range("false")
                .map(|_| Expression::Value(Value::Bool(false)))));

        unit.or(int).or(string).or(boolean).or(parser(parse_inner)).parse_stream(s)

    }

    fn parse_inner(s: State<&str>) -> ParseResult<Expression, State<&str>> {
        let operator = many1::<String, _>(satisfy(|c: char| !c.is_whitespace()));

        let list = (operator, skip_many1(space().or(newline())), many1(parser(parse_arg).skip(skip_chars!())))
            .map(|(op, _, args)| {
                Expression::Call(op, args)
            });

        skip_chars!()
            .with(between((token('('), skip_chars!()),
                (skip_chars!(), token(')')), list))
            .skip(skip_chars!())
            .parse_stream(s)
    }

    try(parser(parse_inner)).or(skip_chars!().with(parser(parse_arg)).skip(skip_chars!()))
        .skip(eof()).parse_stream(State::new(s))
        .map(|(e, _)| e).map_err(|c| c.into_inner())
}

#[derive(Debug, Clone, PartialEq, Eq)]
enum Value {
    Int(i32),
    Str(String),
    Bool(bool),
    Unit,
}

impl From<i32> for Value {
    fn from(x: i32) -> Value {
        Value::Int(x)
    }
}

impl From<String> for Value {
    fn from(x: String) -> Value {
        Value::Str(x)
    }
}

impl From<bool> for Value {
    fn from(x: bool) -> Value {
        Value::Bool(x)
    }
}

impl From<()> for Value {
    fn from(_: ()) -> Value {
        Value::Unit
    }
}

#[derive(Debug, PartialEq, Eq, Clone)]
enum Expression {
    Call(String, Vec<Expression>),
    Value(Value),
}

impl Expression {
    fn eval(&self, e: &mut Engine) -> Result<Value, EvalError> {
        match *self {
            Expression::Call(ref op, ref args) => {
                let op = e.operators.get(op).ok_or(EvalError::UnknownOperator)?.clone();
                op.call(e, args)
            }

            Expression::Value(ref value) => {
                Ok(value.clone())
            }
        }
    }
}

trait Operator {
    fn call(&self, e: &mut Engine, args: &[Expression]) -> Result<Value, EvalError>;
}

struct AddOperator;

impl Operator for AddOperator {
    fn call(&self, e: &mut Engine, args: &[Expression]) -> Result<Value, EvalError> {
        let mut sum = 0;

        for a in args {
            if let Value::Int(x) = a.eval(e)? {
                sum += x;
            } else {
                return Err(EvalError::TypeError);
            }
        }

        Ok(sum.into())
    }
}

struct MultiplyOperator;

impl Operator for MultiplyOperator {
    fn call(&self, e: &mut Engine, args: &[Expression]) -> Result<Value, EvalError> {
        let mut prod = 1;

        for a in args {
            if let Value::Int(x) = a.eval(e)? {
                prod *= x;
            } else {
                return Err(EvalError::TypeError);
            }
        }

        Ok(prod.into())
    }
}

struct EqualOperator;

impl Operator for EqualOperator {
    fn call(&self, e: &mut Engine, args: &[Expression]) -> Result<Value, EvalError> {
        let args: Result<Vec<_>, _> = args.iter().map(|a| a.eval(e)).collect();
        for w in args?.windows(2) {
            if w[0] != w[1] {
                return Ok(false.into());
            }
        }

        Ok(true.into())
    }
}

struct SetOperator;

impl Operator for SetOperator {
    fn call(&self, e: &mut Engine, args: &[Expression]) -> Result<Value, EvalError> {
        if args.len() != 2 {
            Err(EvalError::WrongArity)
        } else if let Value::Str(ref s) = args[0].eval(e)? {
            let v = args[1].eval(e)?;
            Ok(e.variables.insert(s.clone(), v)
                .unwrap_or(Value::Unit))
        } else {
            Err(EvalError::TypeError)
        }
    }
}

struct GetOperator;

impl Operator for GetOperator {
    fn call(&self, e: &mut Engine, args: &[Expression]) -> Result<Value, EvalError> {
        if args.len() != 1 {
            Err(EvalError::WrongArity)
        } else if let Value::Str(ref s) = args[0].eval(e)? {
                match e.variables.get(s) {
                    Some(v) => Ok(v.clone()),
                    None => Err(EvalError::UnsetVariable),
                }
        } else {
            Err(EvalError::TypeError)
        }
    }
}

struct DoOperator;

impl Operator for DoOperator {
    fn call(&self, e: &mut Engine, args: &[Expression]) -> Result<Value, EvalError> {
        match args.split_last() {
            Some((last, init)) => {
                for a in init {
                    a.eval(e)?;
                }

                Ok(last.eval(e)?)
            }
            None => Ok(Value::Unit)
        }
    }
}

struct PrintOperator;

impl Operator for PrintOperator {
    fn call(&self, e: &mut Engine, args: &[Expression]) -> Result<Value, EvalError> {
        if !args.is_empty() {
            print!("{:?}", args[0].eval(e)?);
            for a in &args[1..] {
                print!(" {:?}", a.eval(e)?);
            }
        }

        println!("");

        Ok(Value::Unit)
    }
}

struct UntilOperator;

impl Operator for UntilOperator {
    fn call(&self, e: &mut Engine, args: &[Expression]) -> Result<Value, EvalError> {
        if args.len() >= 2 {
            let cond = &args[0];
            let (last, init) = args.split_last().unwrap();
            if Value::Bool(true) != cond.eval(e)? {
                loop {
                    for a in init {
                        a.eval(e)?;
                    }

                    if Value::Bool(true) != cond.eval(e)? {
                        last.eval(e)?;
                        continue;
                    } else {
                        return Ok(last.eval(e)?);
                    }
                }
            }

            Ok(Value::Unit)
        } else {
            Err(EvalError::WrongArity)
        }
    }
}

#[derive(Debug)]
enum EvalError {
    ParseError(String),
    UnknownOperator,
    TypeError,
    WrongArity,
    UnsetVariable,
}

#[derive(Default)]
struct Engine {
    operators: HashMap<String, Rc<Box<Operator>>>,
    variables: HashMap<String, Value>,
}

impl Engine {
    fn new() -> Engine {
        let mut ops = HashMap::new();

        macro_rules! add_op {
            ($symbol:expr, $op:expr) => {
                ops.insert($symbol.into(), Rc::new(Box::new($op) as Box<Operator>));
            }
        }

        add_op!("+", AddOperator);
        add_op!("*", MultiplyOperator);
        add_op!("=", EqualOperator);
        add_op!("set", SetOperator);
        add_op!("get", GetOperator);
        add_op!("do", DoOperator);
        add_op!("print", PrintOperator);
        add_op!("until", UntilOperator);

        Engine {
            operators: ops,
            variables: HashMap::new(),
        }
    }

    fn eval(&mut self, expr: &str) -> Result<Value, EvalError> {
        parse_expr(expr)
            .map_err(|e| EvalError::ParseError(e.to_string()))?
            .eval(self)
    }
}

#[test]
fn test_eval() {
    let mut engine = Engine::new();
    let result = engine.eval(r#"
(do
 (set "i" 10)
 (set "sum" 0)
 (until (= (get "i") 0)
        (do
         (set "sum" (+ (get "sum") (get "i")))
         (set "i" (+ (get "i") -1))))
 (get "sum"))"#).unwrap();
    assert_eq!(result, Value::Int(55));

    let result = engine.eval(" 123 ").unwrap();
    assert_eq!(result, Value::Int(123));
}

fn main() {
    let mut engine = Engine::new();
    let result = engine.eval(r#"(+ 1 2 3)"#).unwrap();
    println!("result: {:?}", result);
    println!("variables: {:?}", engine.variables);
}