From 9672fe3861f283efc91a9cca78b17fecc5826210 Mon Sep 17 00:00:00 2001 From: JJ Date: Wed, 19 Jul 2023 19:55:23 -0700 Subject: implement tuples, lists, arrays, slices, fix union subtyping --- README.md | 8 +++- src/ast.rs | 108 +++++++++++++++++++++++++++++++++++++++++---------- src/bidirectional.rs | 44 +++++++++++++++++---- src/util.rs | 8 ++-- 4 files changed, 135 insertions(+), 33 deletions(-) diff --git a/README.md b/README.md index 3f28020..eb32d74 100644 --- a/README.md +++ b/README.md @@ -4,7 +4,10 @@ chrysanthemum is a simple language with a type system, initially written as a te It implements a number of features from the excellent *Types and Programming Languages*, including: - The simply typed lambda calculus - Bidirectional type checking and subtyping support -- A somewhat complex type system: including support for `unit`, `bool`, `nat`, `int`, `float`, `str`, `union`, `struct`, `empty`, and `err` types +- A somewhat complex type system: including support for: + - `unit`, `bool`, `int`, `nat`, `float`, `str`, + - `struct`, `tuple`, `union`, `list`, `array`, `slice`, + - `empty`, `error` ## todo @@ -13,7 +16,8 @@ It implements a number of features from the excellent *Types and Programming Lan - [x] to lose my sanity: implement `parse_file` - [x] bidirectional typechecking: implement `infer` and `check` - [x] extend to additional basic types: refactor `Term` -- [ ] extend to complex types: implement `access` +- [x] extend to complex types: improve `subtype` +- [ ] make complex types useful: implement `access` - [ ] type classes: implement `monomorphize` - [ ] simple effects: extend `ast` - [x] testtesttest diff --git a/src/ast.rs b/src/ast.rs index 6bb7171..cc6170b 100644 --- a/src/ast.rs +++ b/src/ast.rs @@ -29,8 +29,12 @@ pub enum Type { Integer, Float, String, - Union(Vec), - Struct(HashMap), + List(Box), + Array(Box, usize), // todo: replace with dependent types + Slice(Box), // potentially fucky lifetime stuff too + Union(Vec), // unordered + Struct(HashMap), // unordered + Tuple(Vec, Vec>), // ordered with labels Function{from: Box, to: Box}, } @@ -42,9 +46,12 @@ pub enum Term { Natural(usize), Integer(isize), Float(f32), - String{len: usize, cap: usize, data: Vec}, - Union{val: usize, data: Box}, // is this right? - Struct(HashMap), // is this right? + String(String), + List(Vec), + Array(Vec), + Union(Box), + Struct(HashMap), + Tuple(Vec, Vec>), Function(Box) // this should allow us to bind functions } @@ -57,14 +64,29 @@ impl Term { Term::Natural(_) => Ok(Type::Natural), Term::Integer(_) => Ok(Type::Integer), Term::Float(_) => Ok(Type::Float), - Term::String { len, cap, data } => Ok(Type::String), - Term::Union { val, data } => data.convert(), + Term::String(_) => Ok(Type::String), + Term::List(data) => match data.len() { + 0 => Err("attempting to get 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()), + _ => Ok(Type::Array(Box::new(data.get(0).unwrap().convert()?), data.len())) + }, + Term::Union(data) => data.convert(), Term::Struct(data) => { let mut result = HashMap::new(); for (key, val) in data { result.insert(key.clone(), val.convert()?); } - return Ok(Type::Struct(result)); + Ok(Type::Struct(result)) + }, + Term::Tuple(data, fields) => { + let mut result = Vec::new(); + for val in data { + result.push(val.convert()?); + } + Ok(Type::Tuple(result, fields.clone())) }, Term::Function(func) => match *func.clone() { Expression::Annotation { expr, kind } => match kind { @@ -72,7 +94,7 @@ impl Term { _ => Err("function term value not a function!".into()) } _ => Err("function term value does not have an annotation!".into()) - } + }, } } } @@ -88,17 +110,24 @@ impl Type { Type::Natural => Ok(Term::Natural(0)), Type::Integer => Ok(Term::Integer(0)), Type::Float => Ok(Term::Float(0.0)), - Type::String => Ok(Term::String { len: 0, cap: 0, data: vec!()}), - Type::Union(data) => match data.len() { - 0 => Err("attempting to get a default term of an enum with no variants!".into()), - _ => Ok(Term::Union { val: 0, data: Box::new(data.get(0).unwrap().default()?) }) - }, + Type::String => Ok(Term::String(String::new())), + Type::List(data) => Ok(Term::List(Vec::::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::Struct(data) => { let mut result = HashMap::new(); for (key, val) in data { result.insert(key.clone(), val.default()?); } - return Ok(Term::Struct(result)); + Ok(Term::Struct(result)) + }, + Type::Tuple(data, fields) => { + let mut result = Vec::new(); + for kind in data { + result.push(kind.default()?) + } + Ok(Term::Tuple(result, fields.clone())) }, Type::Function { from, to } => Err("attempting to take the default term of a function type".into()), @@ -130,13 +159,49 @@ impl core::fmt::Display for Type { Type::Integer => write!(f, "int"), Type::Float => write!(f, "float"), Type::String => write!(f, "str"), - Type::Union(data) => write!(f, "({:?})", data), - Type::Struct(data) => write!(f, "{{{:?}}}", data), + Type::List(data) => write!(f, "list[{}]", data), + Type::Array(data, len) => write!(f, "array[{}, {}]", data, len), + Type::Slice(data) => write!(f, "slice[{}]", data), + Type::Union(data) => { + write!(f, "union[")?; + for (i, val) in data.iter().enumerate() { + write!(f, "{}", val)?; + if !(i == data.len() - 1) { + write!(f, ", ")?; + } + } + write!(f, "]") + }, + Type::Struct(data) => { + write!(f, "struct[")?; + for (i, (key, val)) in data.iter().enumerate() { + write!(f, "{}: {}", key, val)?; + if !(i == data.len() - 1) { + write!(f, ", ")?; + } + } + write!(f, "]") + }, + Type::Tuple(data, fields) => { + write!(f, "tuple[")?; + for (i, (val, ident)) in std::iter::zip(data, fields).enumerate() { + match ident { + Some(key) => write!(f, "{}: {}", key, val)?, + None => write!(f, "{}", val)? + } + if !(i == data.len() - 1) { + write!(f, ", ")?; + } + } + write!(f, "]") + }, Type::Function { from, to } => write!(f, "{}->{}", from, to), } } } +// hatehatehate that you can't implement a trait for foreign types +// let me impl display for vec god dammit impl core::fmt::Display for Term { fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { match self { @@ -145,9 +210,12 @@ impl core::fmt::Display for Term { Term::Natural(term) => write!(f, "{}", term), Term::Integer(term) => write!(f, "{}", term), Term::Float(term) => write!(f, "{}", term), - Term::String { len, cap, data } => write!(f, "\"{:?}\"", data), - Term::Union { val, data } => write!(f, "{:?}", data), - Term::Struct(term) => write!(f, "{:?}", term), + Term::String(data) => write!(f, "\"{}\"", data), + Term::List(data) => write!(f, "[{:?}]", data), + Term::Array(data) => write!(f, "[{:?}]", data), + Term::Union(data) => write!(f, "{{{:?}}}", data), + Term::Struct(term) => write!(f, "{{{:?}}}", term), + Term::Tuple(data, fields) => write!(f, "({:?})", data), Term::Function(expr) => write!(f, "{}", *expr), } } diff --git a/src/bidirectional.rs b/src/bidirectional.rs index d62267c..e22b314 100644 --- a/src/bidirectional.rs +++ b/src/bidirectional.rs @@ -92,12 +92,31 @@ impl Context { impl Type { /// The subtyping relation between any two types. + /// Self is a subtype of Other. + /// Self can be safely used in any context Other is expected. pub fn subtype(&self, other: &Self) -> bool { match (self, other) { - (Type::Struct(is_fields), Type::Struct(of_fields)) => { + (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() { + return false; + } + for (is, of) in std::iter::zip(is_data, of_data) { + if !is.subtype(of) { + return false; + } + } + for (is, of) in std::iter::zip(is_fields, of_fields) { + if is != of { + return false; + } + } + true + }, + (Type::Struct(is), Type::Struct(of)) => { // width, depth, and permutation - for (key, of_value) in of_fields { - match is_fields.get(key) { + for (key, of_value) in of { + match is.get(key) { Some(is_value) => { if !is_value.subtype(of_value) { return false; @@ -106,16 +125,27 @@ impl Type { None => return false } } - return true; + true + }, + (Type::Union(is), Type::Union(of)) => { + // a union type is a subtype of another if the latter has *more* fields (opposite structs!) + for data in of { + if !is.contains(data) { + return false; + } + } + true }, - (Type::Union(is_variants), Type::Union(of_variants)) => false, // fixme (Type::Function { from: is_from, to: is_to }, Type::Function { from: of_from, to: of_to }) => { of_from.subtype(is_from) && is_to.subtype(of_to) }, + (Type::List(is), Type::Slice(of)) | (Type::Array(is, _), Type::Slice(of)) | + (Type::List(is), Type::List(of)) | (Type::Slice(is), Type::Slice(of)) => is.subtype(of), + (Type::Array(is, is_size), Type::Array(of, of_size)) => is.subtype(of) && is_size == of_size, (Type::Natural, Type::Integer) => true, // obviously not, but let's pretend - (_, Type::Empty) => true, - (Type::Error, _) => true, + (_, 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 (_, _) if self == other => true, (_, _) => false } diff --git a/src/util.rs b/src/util.rs index 39ac263..5d3baaa 100644 --- a/src/util.rs +++ b/src/util.rs @@ -70,10 +70,10 @@ pub fn Float(term: f32) -> Term { return Term::Float(term) } -pub fn Str(len: usize, cap: usize, data: Vec) -> Term { - return Term::String { len, cap, data } +pub fn Str(data: &str) -> Term { + return Term::String(data.into()) } -pub fn Union(val: usize, data: Term) -> Term { - return Term::Union { val, data: Box::new(data) } +pub fn Union(data: Term) -> Term { + return Term::Union(Box::new(data)) } -- cgit v1.2.3-70-g09d2