merge(glittershark/achilles): Subtree import at 'b93268085a' r/2279

Imported from https://github.com/glittershark/achilles/

git-subtree-dir: users/glittershark/achilles
git-subtree-mainline: 4d193f239525954631ba9d789ca3aea9a2f4e14d
git-subtree-split: b93268085aab14c80a400c299da5d04d2781098e
Change-Id: I64a583b454bbe03e20358ad7808939a4cbc212ba

3 files changed, 398 insertions, 0 deletions

diff --git a/users/glittershark/achilles/src/interpreter/error.rs b/users/glittershark/achilles/src/interpreter/error.rs
new file mode 100644
index 000000000000..268d6f479a1e
--- /dev/null
+++ b/users/glittershark/achilles/src/interpreter/error.rs
@@ -0,0 +1,19 @@
+use std::result;
+
+use thiserror::Error;
+
+use crate::ast::{Ident, Type};
+
+#[derive(Debug, PartialEq, Eq, Error)]
+pub enum Error {
+    #[error("Undefined variable {0}")]
+    UndefinedVariable(Ident<'static>),
+
+    #[error("Unexpected type {actual}, expected type {expected}")]
+    InvalidType {
+        actual: Type<'static>,
+        expected: Type<'static>,
+    },
+}
+
+pub type Result<T> = result::Result<T, Error>;
diff --git a/users/glittershark/achilles/src/interpreter/mod.rs b/users/glittershark/achilles/src/interpreter/mod.rs
new file mode 100644
index 000000000000..3bfeeb52e85c
--- /dev/null
+++ b/users/glittershark/achilles/src/interpreter/mod.rs
@@ -0,0 +1,176 @@
+mod error;
+mod value;
+
+pub use self::error::{Error, Result};
+pub use self::value::{Function, Value};
+use crate::ast::hir::{Binding, Expr};
+use crate::ast::{BinaryOperator, FunctionType, Ident, Literal, Type, UnaryOperator};
+use crate::common::env::Env;
+
+#[derive(Debug, Default)]
+pub struct Interpreter<'a> {
+    env: Env<&'a Ident<'a>, Value<'a>>,
+}
+
+impl<'a> Interpreter<'a> {
+    pub fn new() -> Self {
+        Self::default()
+    }
+
+    fn resolve(&self, var: &'a Ident<'a>) -> Result<Value<'a>> {
+        self.env
+            .resolve(var)
+            .cloned()
+            .ok_or_else(|| Error::UndefinedVariable(var.to_owned()))
+    }
+
+    pub fn eval(&mut self, expr: &'a Expr<'a, Type>) -> Result<Value<'a>> {
+        let res = match expr {
+            Expr::Ident(id, _) => self.resolve(id),
+            Expr::Literal(Literal::Int(i), _) => Ok((*i).into()),
+            Expr::Literal(Literal::Bool(b), _) => Ok((*b).into()),
+            Expr::Literal(Literal::String(s), _) => Ok(s.clone().into()),
+            Expr::UnaryOp { op, rhs, .. } => {
+                let rhs = self.eval(rhs)?;
+                match op {
+                    UnaryOperator::Neg => -rhs,
+                    _ => unimplemented!(),
+                }
+            }
+            Expr::BinaryOp { lhs, op, rhs, .. } => {
+                let lhs = self.eval(lhs)?;
+                let rhs = self.eval(rhs)?;
+                match op {
+                    BinaryOperator::Add => lhs + rhs,
+                    BinaryOperator::Sub => lhs - rhs,
+                    BinaryOperator::Mul => lhs * rhs,
+                    BinaryOperator::Div => lhs / rhs,
+                    BinaryOperator::Pow => todo!(),
+                    BinaryOperator::Equ => Ok(lhs.eq(&rhs).into()),
+                    BinaryOperator::Neq => todo!(),
+                }
+            }
+            Expr::Let { bindings, body, .. } => {
+                self.env.push();
+                for Binding { ident, body, .. } in bindings {
+                    let val = self.eval(body)?;
+                    self.env.set(ident, val);
+                }
+                let res = self.eval(body)?;
+                self.env.pop();
+                Ok(res)
+            }
+            Expr::If {
+                condition,
+                then,
+                else_,
+                ..
+            } => {
+                let condition = self.eval(condition)?;
+                if *(condition.as_type::<bool>()?) {
+                    self.eval(then)
+                } else {
+                    self.eval(else_)
+                }
+            }
+            Expr::Call { ref fun, args, .. } => {
+                let fun = self.eval(fun)?;
+                let expected_type = FunctionType {
+                    args: args.iter().map(|_| Type::Int).collect(),
+                    ret: Box::new(Type::Int),
+                };
+
+                let Function {
+                    args: function_args,
+                    body,
+                    ..
+                } = fun.as_function(expected_type)?;
+                let arg_values = function_args.iter().zip(
+                    args.iter()
+                        .map(|v| self.eval(v))
+                        .collect::<Result<Vec<_>>>()?,
+                );
+                let mut interpreter = Interpreter::new();
+                for (arg_name, arg_value) in arg_values {
+                    interpreter.env.set(arg_name, arg_value);
+                }
+                Ok(Value::from(*interpreter.eval(body)?.as_type::<i64>()?))
+            }
+            Expr::Fun { args, body, type_ } => {
+                let type_ = match type_ {
+                    Type::Function(ft) => ft.clone(),
+                    _ => unreachable!("Function expression without function type"),
+                };
+
+                Ok(Value::from(value::Function {
+                    // TODO
+                    type_,
+                    args: args.iter().map(|(arg, _)| arg.to_owned()).collect(),
+                    body: (**body).to_owned(),
+                }))
+            }
+        }?;
+        debug_assert_eq!(&res.type_(), expr.type_());
+        Ok(res)
+    }
+}
+
+pub fn eval<'a>(expr: &'a Expr<'a, Type>) -> Result<Value<'a>> {
+    let mut interpreter = Interpreter::new();
+    interpreter.eval(expr)
+}
+
+#[cfg(test)]
+mod tests {
+    use std::convert::TryFrom;
+
+    use super::value::{TypeOf, Val};
+    use super::*;
+    use BinaryOperator::*;
+
+    fn int_lit(i: u64) -> Box<Expr<'static, Type<'static>>> {
+        Box::new(Expr::Literal(Literal::Int(i), Type::Int))
+    }
+
+    fn do_eval<T>(src: &str) -> T
+    where
+        for<'a> &'a T: TryFrom<&'a Val<'a>>,
+        T: Clone + TypeOf,
+    {
+        let expr = crate::parser::expr(src).unwrap().1;
+        let hir = crate::tc::typecheck_expr(expr).unwrap();
+        let res = eval(&hir).unwrap();
+        res.as_type::<T>().unwrap().clone()
+    }
+
+    #[test]
+    fn simple_addition() {
+        let expr = Expr::BinaryOp {
+            lhs: int_lit(1),
+            op: Mul,
+            rhs: int_lit(2),
+            type_: Type::Int,
+        };
+        let res = eval(&expr).unwrap();
+        assert_eq!(*res.as_type::<i64>().unwrap(), 2);
+    }
+
+    #[test]
+    fn variable_shadowing() {
+        let res = do_eval::<i64>("let x = 1 in (let x = 2 in x) + x");
+        assert_eq!(res, 3);
+    }
+
+    #[test]
+    fn conditional_with_equals() {
+        let res = do_eval::<i64>("let x = 1 in if x == 1 then 2 else 4");
+        assert_eq!(res, 2);
+    }
+
+    #[test]
+    #[ignore]
+    fn function_call() {
+        let res = do_eval::<i64>("let id = fn x = x in id 1");
+        assert_eq!(res, 1);
+    }
+}
diff --git a/users/glittershark/achilles/src/interpreter/value.rs b/users/glittershark/achilles/src/interpreter/value.rs
new file mode 100644
index 000000000000..55ba42f9de58
--- /dev/null
+++ b/users/glittershark/achilles/src/interpreter/value.rs
@@ -0,0 +1,203 @@
+use std::borrow::Cow;
+use std::convert::TryFrom;
+use std::fmt::{self, Display};
+use std::ops::{Add, Div, Mul, Neg, Sub};
+use std::rc::Rc;
+use std::result;
+
+use derive_more::{Deref, From, TryInto};
+
+use super::{Error, Result};
+use crate::ast::hir::Expr;
+use crate::ast::{FunctionType, Ident, Type};
+
+#[derive(Debug, Clone)]
+pub struct Function<'a> {
+    pub type_: FunctionType<'a>,
+    pub args: Vec<Ident<'a>>,
+    pub body: Expr<'a, Type<'a>>,
+}
+
+#[derive(From, TryInto)]
+#[try_into(owned, ref)]
+pub enum Val<'a> {
+    Int(i64),
+    Float(f64),
+    Bool(bool),
+    String(Cow<'a, str>),
+    Function(Function<'a>),
+}
+
+impl<'a> TryFrom<Val<'a>> for String {
+    type Error = ();
+
+    fn try_from(value: Val<'a>) -> result::Result<Self, Self::Error> {
+        match value {
+            Val::String(s) => Ok(s.into_owned()),
+            _ => Err(()),
+        }
+    }
+}
+
+impl<'a> fmt::Debug for Val<'a> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match self {
+            Val::Int(x) => f.debug_tuple("Int").field(x).finish(),
+            Val::Float(x) => f.debug_tuple("Float").field(x).finish(),
+            Val::Bool(x) => f.debug_tuple("Bool").field(x).finish(),
+            Val::String(s) => f.debug_tuple("String").field(s).finish(),
+            Val::Function(Function { type_, .. }) => {
+                f.debug_struct("Function").field("type_", type_).finish()
+            }
+        }
+    }
+}
+
+impl<'a> PartialEq for Val<'a> {
+    fn eq(&self, other: &Self) -> bool {
+        match (self, other) {
+            (Val::Int(x), Val::Int(y)) => x == y,
+            (Val::Float(x), Val::Float(y)) => x == y,
+            (Val::Bool(x), Val::Bool(y)) => x == y,
+            (Val::Function(_), Val::Function(_)) => false,
+            (_, _) => false,
+        }
+    }
+}
+
+impl<'a> From<u64> for Val<'a> {
+    fn from(i: u64) -> Self {
+        Self::from(i as i64)
+    }
+}
+
+impl<'a> Display for Val<'a> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match self {
+            Val::Int(x) => x.fmt(f),
+            Val::Float(x) => x.fmt(f),
+            Val::Bool(x) => x.fmt(f),
+            Val::String(s) => write!(f, "{:?}", s),
+            Val::Function(Function { type_, .. }) => write!(f, "<{}>", type_),
+        }
+    }
+}
+
+impl<'a> Val<'a> {
+    pub fn type_(&self) -> Type {
+        match self {
+            Val::Int(_) => Type::Int,
+            Val::Float(_) => Type::Float,
+            Val::Bool(_) => Type::Bool,
+            Val::String(_) => Type::CString,
+            Val::Function(Function { type_, .. }) => Type::Function(type_.clone()),
+        }
+    }
+
+    pub fn as_type<'b, T>(&'b self) -> Result<&'b T>
+    where
+        T: TypeOf + 'b + Clone,
+        &'b T: TryFrom<&'b Self>,
+    {
+        <&T>::try_from(self).map_err(|_| Error::InvalidType {
+            actual: self.type_().to_owned(),
+            expected: <T as TypeOf>::type_of(),
+        })
+    }
+
+    pub fn as_function<'b>(&'b self, function_type: FunctionType) -> Result<&'b Function<'a>> {
+        match self {
+            Val::Function(f) if f.type_ == function_type => Ok(&f),
+            _ => Err(Error::InvalidType {
+                actual: self.type_().to_owned(),
+                expected: Type::Function(function_type.to_owned()),
+            }),
+        }
+    }
+}
+
+#[derive(Debug, PartialEq, Clone, Deref)]
+pub struct Value<'a>(Rc<Val<'a>>);
+
+impl<'a> Display for Value<'a> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        self.0.fmt(f)
+    }
+}
+
+impl<'a, T> From<T> for Value<'a>
+where
+    Val<'a>: From<T>,
+{
+    fn from(x: T) -> Self {
+        Self(Rc::new(x.into()))
+    }
+}
+
+impl<'a> Neg for Value<'a> {
+    type Output = Result<Value<'a>>;
+
+    fn neg(self) -> Self::Output {
+        Ok((-self.as_type::<i64>()?).into())
+    }
+}
+
+impl<'a> Add for Value<'a> {
+    type Output = Result<Value<'a>>;
+
+    fn add(self, rhs: Self) -> Self::Output {
+        Ok((self.as_type::<i64>()? + rhs.as_type::<i64>()?).into())
+    }
+}
+
+impl<'a> Sub for Value<'a> {
+    type Output = Result<Value<'a>>;
+
+    fn sub(self, rhs: Self) -> Self::Output {
+        Ok((self.as_type::<i64>()? - rhs.as_type::<i64>()?).into())
+    }
+}
+
+impl<'a> Mul for Value<'a> {
+    type Output = Result<Value<'a>>;
+
+    fn mul(self, rhs: Self) -> Self::Output {
+        Ok((self.as_type::<i64>()? * rhs.as_type::<i64>()?).into())
+    }
+}
+
+impl<'a> Div for Value<'a> {
+    type Output = Result<Value<'a>>;
+
+    fn div(self, rhs: Self) -> Self::Output {
+        Ok((self.as_type::<f64>()? / rhs.as_type::<f64>()?).into())
+    }
+}
+
+pub trait TypeOf {
+    fn type_of() -> Type<'static>;
+}
+
+impl TypeOf for i64 {
+    fn type_of() -> Type<'static> {
+        Type::Int
+    }
+}
+
+impl TypeOf for bool {
+    fn type_of() -> Type<'static> {
+        Type::Bool
+    }
+}
+
+impl TypeOf for f64 {
+    fn type_of() -> Type<'static> {
+        Type::Float
+    }
+}
+
+impl TypeOf for String {
+    fn type_of() -> Type<'static> {
+        Type::CString
+    }
+}