diff options
| -rw-r--r-- | src/ast.rs | 76 | ||||
| -rw-r--r-- | src/bidirectional.rs | 38 | ||||
| -rw-r--r-- | src/parser.rs | 2 | ||||
| -rw-r--r-- | src/util.rs | 5 |
4 files changed, 67 insertions, 54 deletions
@@ -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; |