generics, somewhat. also minor code cleanups

4 files changed, 67 insertions, 54 deletions

diff --git a/src/ast.rs b/src/ast.rs
index 99c9b6c..60e4db9 100644
--- a/src/ast.rs
+++ b/src/ast.rs
@@ -14,13 +14,15 @@ pub struct Signature {
     pub to: Type
 }
 
+/// Fundamental expressions for the lambda calculus.
+/// To be extended: bindings, loops/continuations, typedefs?
 // note: built-in functions do NOT go here!
+// note: we keep parameters as an Identifier because we annotate the WHOLE Abstraction
 #[derive(Debug, Clone, PartialEq)]
 pub enum Expression {
     Annotation{expr: Box<Expression>, kind: Type},
     Constant{term: Term},
     Variable{id: Identifier},
-    // note: we keep parameters as an Identifier because we annotate the WHOLE Abstraction
     Abstraction{param: Identifier, func: Box<Expression>},
     Application{func: Box<Expression>, arg: Box<Expression>},
     Conditional{if_cond: Box<Expression>, if_then: Box<Expression>, if_else: Box<Expression>}
@@ -29,23 +31,18 @@ pub enum Expression {
 /// All supported types.
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub enum Type {
-    Empty,
-    Error,
-    Unit,
-    Boolean,
-    Natural,
-    Integer,
-    Float,
-    String,
+    Empty, Error, Unit, Boolean,                    // primitive types
+    Natural, Integer, Float, String,
     List(Box<Type>),
-    Array(Box<Type>, usize), // todo: replace with dependent types
-    Slice(Box<Type>), // potentially fucky lifetime stuff too
-    Union(Vec<Type>), // unordered
-    Struct(BTreeMap<Identifier, Type>), // unordered
-    Tuple(Vec<Type>, Vec<Option<Identifier>>), // ordered with labels
-    Function{from: Box<Type>, to: Box<Type>},
-    Interface(Vec<Signature>, Option<Box<Type>>), // typeclasses "interfaces"
-    Oneself,
+    Array(Box<Type>, usize),                        // todo: replace with dependent types
+    Slice(Box<Type>),                               // potentially fucky lifetime stuff too
+    Union(Vec<Type>),                               // unordered
+    Struct(BTreeMap<Identifier, Type>),             // unordered
+    Tuple(Vec<Type>, Vec<Option<Identifier>>),      // ordered with labels (vectors must be same length)
+    Function(Box<Type>, Box<Type>),                 // from, to: multiple params expressed via tuples
+    Interface(Vec<Signature>, Option<Box<Type>>),   // typeclasses "interfaces"
+    Oneself,                                        // "Self" type associated with interfaces. replaced by subtyping checks
+    Generic(Option<Vec<Type>>),                     // stand in generic type. fully generic, or a list of valid types.
 }
 
 /// Data associated with a type.
@@ -53,12 +50,9 @@ pub enum Type {
 // Note: no Functions: those inhabit a separate context. it's just easier
 #[derive(Debug, Clone, PartialEq)]
 pub enum Term {
-    Unit(),
-    Boolean(bool),
-    Natural(usize),
-    Integer(isize),
-    Float(f32),
-    String(String),
+    Unit(), Boolean(bool),
+    Natural(usize), Integer(isize),
+    Float(f32), String(String),
     List(Vec<Term>),
     Array(Vec<Term>),
     Union(Box<Term>),
@@ -68,6 +62,7 @@ pub enum Term {
 
 impl Term {
     /// Convert a term into its corresponding type.
+    // Empty lists/arrays and unions currently cannot be inferred.
     pub fn convert(&self) -> Result<Type> {
         match self {
             Term::Unit() => Ok(Type::Unit),
@@ -77,14 +72,14 @@ impl Term {
             Term::Float(_) => Ok(Type::Float),
             Term::String(_) => Ok(Type::String),
             Term::List(data) => match data.len() {
-                0 => Err("attempting to get the type of an empty list!".into()),
+                0 => Err("attempting to infer the type of an empty list!".into()),
                 _ => Ok(Type::List(Box::new(data.get(0).unwrap().convert()?))),
             },
             Term::Array(data) => match data.len() {
-                0 => Err("attempting to get the type of an empty array!".into()),
+                0 => Err("attempting to infer the type of an empty array!".into()),
                 _ => Ok(Type::Array(Box::new(data.get(0).unwrap().convert()?), data.len()))
             },
-            Term::Union(data) => data.convert(),
+            Term::Union(data) => Err("attempting to infer the type of a union variant!".into()),
             Term::Struct(data) => {
                 let mut result = BTreeMap::new();
                 for (key, val) in data {
@@ -105,6 +100,8 @@ impl Term {
 
 impl Type {
     /// Get the default value of a type. Throws an error if it doesn't exist.
+    // Unions are invalid as they are not ordered.
+    // Empty, Error, Slice, Function, Interface, Onself, Generic are invalid as they cannot be constructed.
     pub fn default(&self) -> Result<Term> {
         match self {
             Type::Empty => Err("attempting to take the default term for empty".into()),
@@ -118,7 +115,7 @@ impl Type {
             Type::List(data) => Ok(Term::List(Vec::<Term>::new())),
             Type::Array(data, len) => Ok(Term::Array(vec![data.default()?; *len])),
             Type::Slice(_) => Err("attempting to take the default term of a slice".into()),
-            Type::Union(data) => Err("attempting to take the default term of a union".into()),
+            Type::Union(_) => Err("attempting to take the default term of a union".into()),
             Type::Struct(data) => {
                 let mut result = BTreeMap::new();
                 for (key, val) in data {
@@ -133,10 +130,14 @@ impl Type {
                 }
                 Ok(Term::Tuple(result, fields.clone()))
             },
-            Type::Function { from, to } =>
+            Type::Function(from, to) =>
                 Err("attempting to take the default term of a function type".into()),
-            Type::Interface(_, _) => Err("attempting to take the default term of an interface".into()),
-            Type::Oneself => Err("attempting to take the default term of Self".into()),
+            Type::Interface(_, _) =>
+                Err("attempting to take the default term of an interface".into()),
+            Type::Oneself =>
+                Err("attempting to take the default term of Self".into()),
+            Type::Generic(_) =>
+                Err("attempting to take the default term of a generic".into()),
         }
     }
 }
@@ -201,7 +202,7 @@ impl core::fmt::Display for Type {
                 }
                 write!(f, "]")
             },
-            Type::Function { from, to } => write!(f, "{}->{}", from, to),
+            Type::Function(from, to) => write!(f, "{}->{}", from, to),
             Type::Interface(data, kind) => {
                 write!(f, "interface[")?;
                 for (i, sig) in data.iter().enumerate() {
@@ -216,6 +217,18 @@ impl core::fmt::Display for Type {
                 write!(f, "]")
             },
             Type::Oneself => write!(f, "Self"),
+            Type::Generic(data) =>  {
+                write!(f, "generic[")?;
+                if let Some(data) = data {
+                    for (i, kind) in data.iter().enumerate() {
+                        write!(f, "{}", kind)?;
+                        if !(i == data.len() - 1) {
+                            write!(f, ", ")?;
+                        }
+                    }
+                }
+                write!(f, "]")
+            },
         }
     }
 }
@@ -240,6 +253,7 @@ impl core::fmt::Display for Term {
     }
 }
 
+/// expose necessary functions for the underlying HashMaps
 impl Context {
     pub fn new() -> Self {
         Context(HashMap::new(), HashMap::new())
diff --git a/src/bidirectional.rs b/src/bidirectional.rs
index 4b34ab2..4e69372 100644
--- a/src/bidirectional.rs
+++ b/src/bidirectional.rs
@@ -26,7 +26,7 @@ impl Context {
             },
             // Bt-Abs
             Expression::Abstraction { param, func } => match target {
-                Type::Function { from, to } => {
+                Type::Function(from, to) => {
                     let mut context = self.clone();
                     context.insert_term(param, from.default()?);
                     return context.check(*func, &to);
@@ -65,14 +65,14 @@ impl Context {
             },
             // Bt-App
             Expression::Application { func, arg } => match self.infer(*func)? {
-                Type::Function { from, to } => self.check(*arg, &*from).map(|x| *to),
-                _ => Err(format!("application abstraction is not a function type").into())
+                Type::Function(from, to) => self.check(*arg, &*from).map(|x| *to),
+                _ => Err("application abstraction is not a function type".into())
             },
             // inference from an abstraction is always an error
             // we could try and infer the func without adding the parameter to scope:
             // but this is overwhelmingly likely to be an error, so just report it now.
             Expression::Abstraction { param, func } =>
-                Err(format!("attempting to infer from an abstraction").into()),
+                Err("attempting to infer from an abstraction".into()),
             // idk
             Expression::Conditional { if_cond, if_then, if_else } => {
                 self.check(*if_cond, &Type::Boolean)?;
@@ -91,6 +91,12 @@ impl Context {
     /// "is" is a subtype of "of", i.e. "is" can be safely used in any context "of" is expected.
     pub fn subtype(&self, is: &Type, of: &Type) -> bool {
         match (is, of) {
+            (_, Type::Empty) => true,   // top type: every type is a subtype of the empty type (empty as in structurally empty)
+            (Type::Error, _) => true,   // bottom type: no type is a subtype of the error type
+            (Type::Natural, Type::Integer) => true, // obviously not, but let's pretend
+            (Type::List(is), Type::Slice(of)) | (Type::Array(is, _), Type::Slice(of)) |
+            (Type::List(is), Type::List(of)) |  (Type::Slice(is), Type::Slice(of)) => self.subtype(is, of),
+            (Type::Array(is, is_size), Type::Array(of, of_size)) => self.subtype(is, of) && is_size == of_size,
             (Type::Tuple(is_data, is_fields), Type::Tuple(of_data, of_fields)) => {
                 // length, order, and subtype
                 if is_data.len() != of_data.len() || is_fields.len() != of_fields.len() {
@@ -131,8 +137,7 @@ impl Context {
                 }
                 true
             },
-            (Type::Function { from: is_from, to: is_to },
-             Type::Function { from: of_from, to: of_to }) => {
+            (Type::Function(is_from, is_to), Type::Function(of_from, of_to)) => {
                 self.subtype(of_from, is_from) && self.subtype(is_to, of_to)
             },
             (is, Type::Interface(signatures, associated)) => {
@@ -151,12 +156,8 @@ impl Context {
                 }
                 true
             },
-            (Type::List(is), Type::Slice(of)) | (Type::Array(is, _), Type::Slice(of)) |
-            (Type::List(is), Type::List(of)) |  (Type::Slice(is), Type::Slice(of)) => self.subtype(is, of),
-            (Type::Array(is, is_size), Type::Array(of, of_size)) => self.subtype(is, of) && is_size == of_size,
-            (Type::Natural, Type::Integer) => true, // obviously not, but let's pretend
-            (_, Type::Empty) => true,   // top type: every type is a subtype of the empty type (empty as in structurally empty)
-            (Type::Error, _) => true,   // bottom type: no type is a subtype of the error type
+            (is, Type::Generic(Some(data))) => data.contains(is),
+            (_, Type::Generic(None)) => true,
             (_, _) => is == of
         }
     }
@@ -178,12 +179,13 @@ impl Type {
                 data.iter().map(|(k, v)| (k.clone(), v.clone().deselfify(replacement))).collect()),
             Type::Tuple(data, idents) => Type::Tuple(
                 data.iter().map(|x| x.clone().deselfify(replacement)).collect(), idents),
-            Type::Function { from, to } => Type::Function {
-                from: Box::new(from.deselfify(replacement)),
-                to: Box::new(to.deselfify(replacement))
-            },
-            Type::Interface(signatures, associated) =>
-                Type::Interface(signatures, associated.map(|x| Box::new(x.deselfify(replacement)))),
+            Type::Function(from, to) => Type::Function(
+                Box::new(from.deselfify(replacement)), Box::new(to.deselfify(replacement))),
+            Type::Interface(signatures, associated) => Type::Interface(signatures,
+                associated.map(|x| Box::new(x.deselfify(replacement)))),
+            Type::Generic(Some(data)) => Type::Generic(
+                Some(data.iter().map(|x| x.clone().deselfify(replacement)).collect())),
+            Type::Generic(None) => Type::Generic(None),
         }
     }
 }
diff --git a/src/parser.rs b/src/parser.rs
index 298e09d..9051bfb 100644
--- a/src/parser.rs
+++ b/src/parser.rs
@@ -40,7 +40,7 @@ pub fn parse_lambda(input: &str) -> Result<Expression> {
             }
             // fixme: brackets are necessary here
             rule function() -> Type = "(" f:kind() " "* "->" " "* t:kind() ")" {
-                Type::Function { from: Box::new(f), to: Box::new(t) }
+                Type::Function(Box::new(f), Box::new(t))
             }
             rule kind() -> Type
              = k:(function() / primitive()) {
diff --git a/src/util.rs b/src/util.rs
index 5d3baaa..1962fb4 100644
--- a/src/util.rs
+++ b/src/util.rs
@@ -53,10 +53,7 @@ pub fn Cond(if_cond: Expression, if_then: Expression, if_else: Expression) -> Ex
 }
 
 pub fn Func(from: Type, to: Type) -> Type {
-    return Type::Function {
-        from: Box::new(from),
-        to: Box::new(to)
-    }
+    return Type::Function(Box::new(from), Box::new(to))
 }
 
 pub const Empty: Type = Type::Empty;