feat(grfn/achilles): Implement tuples, and tuple patterns r/2522

Implement tuple expressions, types, and patterns, all the way through
the parser down to the typechecker. In LLVM, these are implemented as
anonymous structs, using an `extract` instruction when they're pattern
matched on to get out the individual fields.

Currently the only limitation here is patterns aren't supported in
function argument position, but you can still do something like

    fn xy = let (x, y) = xy in x + y

Change-Id: I357f17e9d4052e741eda8605b6662822f331efde
Reviewed-on: https://cl.tvl.fyi/c/depot/+/3027
Reviewed-by: grfn <grfn@gws.fyi>
Tested-by: BuildkiteCI

2 files changed, 45 insertions, 3 deletions

diff --git a/users/grfn/achilles/src/interpreter/mod.rs b/users/grfn/achilles/src/interpreter/mod.rs
index a8ba2dd3acdc..70df7a0724a5 100644
--- a/users/grfn/achilles/src/interpreter/mod.rs
+++ b/users/grfn/achilles/src/interpreter/mod.rs
@@ -1,9 +1,12 @@
 mod error;
 mod value;
 
+use itertools::Itertools;
+use value::Val;
+
 pub use self::error::{Error, Result};
 pub use self::value::{Function, Value};
-use crate::ast::hir::{Binding, Expr};
+use crate::ast::hir::{Binding, Expr, Pattern};
 use crate::ast::{BinaryOperator, FunctionType, Ident, Literal, Type, UnaryOperator};
 use crate::common::env::Env;
 
@@ -24,6 +27,17 @@ impl<'a> Interpreter<'a> {
             .ok_or_else(|| Error::UndefinedVariable(var.to_owned()))
     }
 
+    fn bind_pattern(&mut self, pattern: &'a Pattern<'a, Type>, value: Value<'a>) {
+        match pattern {
+            Pattern::Id(id, _) => self.env.set(id, value),
+            Pattern::Tuple(pats) => {
+                for (pat, val) in pats.iter().zip(value.as_tuple().unwrap().clone()) {
+                    self.bind_pattern(pat, val);
+                }
+            }
+        }
+    }
+
     pub fn eval(&mut self, expr: &'a Expr<'a, Type>) -> Result<Value<'a>> {
         let res = match expr {
             Expr::Ident(id, _) => self.resolve(id),
@@ -53,9 +67,9 @@ impl<'a> Interpreter<'a> {
             }
             Expr::Let { bindings, body, .. } => {
                 self.env.push();
-                for Binding { ident, body, .. } in bindings {
+                for Binding { pat, body, .. } in bindings {
                     let val = self.eval(body)?;
-                    self.env.set(ident, val);
+                    self.bind_pattern(pat, val);
                 }
                 let res = self.eval(body)?;
                 self.env.pop();
@@ -115,6 +129,13 @@ impl<'a> Interpreter<'a> {
                     body: (**body).to_owned(),
                 }))
             }
+            Expr::Tuple(members, _) => Ok(Val::Tuple(
+                members
+                    .into_iter()
+                    .map(|expr| self.eval(expr))
+                    .try_collect()?,
+            )
+            .into()),
         }?;
         debug_assert_eq!(&res.type_(), expr.type_());
         Ok(res)
diff --git a/users/grfn/achilles/src/interpreter/value.rs b/users/grfn/achilles/src/interpreter/value.rs
index 55ba42f9de58..272d1167a33c 100644
--- a/users/grfn/achilles/src/interpreter/value.rs
+++ b/users/grfn/achilles/src/interpreter/value.rs
@@ -6,6 +6,7 @@ use std::rc::Rc;
 use std::result;
 
 use derive_more::{Deref, From, TryInto};
+use itertools::Itertools;
 
 use super::{Error, Result};
 use crate::ast::hir::Expr;
@@ -25,6 +26,7 @@ pub enum Val<'a> {
     Float(f64),
     Bool(bool),
     String(Cow<'a, str>),
+    Tuple(Vec<Value<'a>>),
     Function(Function<'a>),
 }
 
@@ -49,6 +51,7 @@ impl<'a> fmt::Debug for Val<'a> {
             Val::Function(Function { type_, .. }) => {
                 f.debug_struct("Function").field("type_", type_).finish()
             }
+            Val::Tuple(members) => f.debug_tuple("Tuple").field(members).finish(),
         }
     }
 }
@@ -79,6 +82,7 @@ impl<'a> Display for Val<'a> {
             Val::Bool(x) => x.fmt(f),
             Val::String(s) => write!(f, "{:?}", s),
             Val::Function(Function { type_, .. }) => write!(f, "<{}>", type_),
+            Val::Tuple(members) => write!(f, "({})", members.iter().join(", ")),
         }
     }
 }
@@ -91,6 +95,7 @@ impl<'a> Val<'a> {
             Val::Bool(_) => Type::Bool,
             Val::String(_) => Type::CString,
             Val::Function(Function { type_, .. }) => Type::Function(type_.clone()),
+            Val::Tuple(members) => Type::Tuple(members.iter().map(|expr| expr.type_()).collect()),
         }
     }
 
@@ -114,6 +119,22 @@ impl<'a> Val<'a> {
             }),
         }
     }
+
+    pub fn as_tuple(&self) -> Option<&Vec<Value<'a>>> {
+        if let Self::Tuple(v) = self {
+            Some(v)
+        } else {
+            None
+        }
+    }
+
+    pub fn try_into_tuple(self) -> result::Result<Vec<Value<'a>>, Self> {
+        if let Self::Tuple(v) = self {
+            Ok(v)
+        } else {
+            Err(self)
+        }
+    }
 }
 
 #[derive(Debug, PartialEq, Clone, Deref)]