aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/ast.rs76
-rw-r--r--src/bidirectional.rs38
-rw-r--r--src/parser.rs2
-rw-r--r--src/util.rs5
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;