diff options
| -rw-r--r-- | README.md | 10 | ||||
| -rw-r--r-- | src/ast.rs | 73 | ||||
| -rw-r--r-- | src/bidirectional.rs | 84 | ||||
| -rw-r--r-- | src/lib.rs | 1 | ||||
| -rw-r--r-- | src/simple.rs | 4 | ||||
| -rw-r--r-- | tests/test_execution.rs | 4 |
6 files changed, 123 insertions, 53 deletions
@@ -1,13 +1,13 @@ # chrysanthemum -chrysanthemum is a simple language with a type system, initially written as a term project for CPSC 539. +chrysanthemum is a simple language with a complex type system, initially written as a term project for CPSC 539. 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`, `int`, `nat`, `float`, `str`, - `struct`, `tuple`, `union`, `list`, `array`, `slice`, - - `empty`, `error` + - `interface`, `empty`, `error` ## todo @@ -17,6 +17,7 @@ It implements a number of features from the excellent *Types and Programming Lan - [x] bidirectional typechecking: implement `infer` and `check` - [x] extend to additional basic types: refactor `Term` - [x] extend to complex types: improve `subtype` +- [x] meet my original standards: implement `interface` - [ ] make complex types useful: implement `access` - [ ] type classes: implement `monomorphize` - [ ] simple effects: extend `ast` @@ -39,9 +40,10 @@ test/ # various tests ## bibliography -- [TAPL](https://www.cis.upenn.edu/~bcpierce/tapl/) +- [Types and Programming Languages](https://www.cis.upenn.edu/~bcpierce/tapl/) +- [Advanced Topics in Types and Programming Languages](https://www.cis.upenn.edu/~bcpierce/attapl/) - [Bidirectional Typing Rules: A Tutorial](https://www.davidchristiansen.dk/tutorials/bidirectional.pdf) - [Bidirectional Typechecking](https://research.cs.queensu.ca/home/jana/bitype.pdf) -- [Typechecking for Higher-Rank Polymorphism](https://arxiv.org/pdf/1306.6032.pdf) - [Bidirectional Type Class Instances](https://arxiv.org/pdf/1906.12242.pdf) +- [Typechecking for Higher-Rank Polymorphism](https://arxiv.org/pdf/1306.6032.pdf) - [How to make ad-hoc polymorphism less ad-hoc](https://dl.acm.org/doi/pdf/10.1145/75277.75283) @@ -1,10 +1,18 @@ -use std::collections::HashMap; +use std::collections::{BTreeMap, HashMap}; pub type Result<T> = core::result::Result<T, Box<dyn std::error::Error>>; -pub type Identifier = String; #[derive(Debug, Clone, PartialEq)] -pub struct Context(HashMap<Identifier, Term>); +pub struct Context(HashMap<Identifier, Term>, HashMap<Signature, Expression>); + +pub type Identifier = String; + +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub struct Signature { + pub name: Identifier, + pub from: Type, + pub to: Type +} // note: built-in functions do NOT go here! #[derive(Debug, Clone, PartialEq)] @@ -19,7 +27,7 @@ pub enum Expression { } /// All supported types. -#[derive(Debug, Clone, PartialEq)] +#[derive(Debug, Clone, PartialEq, Eq, Hash)] pub enum Type { Empty, Error, @@ -33,12 +41,16 @@ pub enum Type { Array(Box<Type>, usize), // todo: replace with dependent types Slice(Box<Type>), // potentially fucky lifetime stuff too Union(Vec<Type>), // unordered - Struct(HashMap<Identifier, 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, } /// Data associated with a type. +// Note: no Interfaces, Slices, Empty, Error: those cannot be constructed. +// Note: no Functions: those inhabit a separate context. it's just easier #[derive(Debug, Clone, PartialEq)] pub enum Term { Unit(), @@ -50,9 +62,8 @@ pub enum Term { List(Vec<Term>), Array(Vec<Term>), Union(Box<Term>), - Struct(HashMap<Identifier, Term>), + Struct(BTreeMap<Identifier, Term>), Tuple(Vec<Term>, Vec<Option<Identifier>>), - Function(Box<Expression>) // this should allow us to bind functions } impl Term { @@ -75,7 +86,7 @@ impl Term { }, Term::Union(data) => data.convert(), Term::Struct(data) => { - let mut result = HashMap::new(); + let mut result = BTreeMap::new(); for (key, val) in data { result.insert(key.clone(), val.convert()?); } @@ -88,13 +99,6 @@ impl Term { } Ok(Type::Tuple(result, fields.clone())) }, - Term::Function(func) => match *func.clone() { - Expression::Annotation { expr, kind } => match kind { - Type::Function { from, to } => Ok(Type::Function { from, to }), - _ => Err("function term value not a function!".into()) - } - _ => Err("function term value does not have an annotation!".into()) - }, } } } @@ -116,7 +120,7 @@ impl Type { 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(); + let mut result = BTreeMap::new(); for (key, val) in data { result.insert(key.clone(), val.default()?); } @@ -131,6 +135,8 @@ impl Type { }, 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()), } } } @@ -182,7 +188,7 @@ impl core::fmt::Display for Type { } write!(f, "]") }, - Type::Tuple(data, fields) => { + Type::Tuple(data, fields) => { write!(f, "tuple[")?; for (i, (val, ident)) in std::iter::zip(data, fields).enumerate() { match ident { @@ -196,6 +202,20 @@ impl core::fmt::Display for Type { write!(f, "]") }, Type::Function { from, to } => write!(f, "{}->{}", from, to), + Type::Interface(data, kind) => { + write!(f, "interface[")?; + for (i, sig) in data.iter().enumerate() { + write!(f, "func {}({}): {}", sig.name, sig.from, sig.to)?; + if !(i == data.len() - 1) { + write!(f, ", ")?; + } + } + if let Some(data) = kind { + write!(f, " for {}", data)?; + } + write!(f, "]") + }, + Type::Oneself => write!(f, "Self"), } } } @@ -216,19 +236,30 @@ impl core::fmt::Display for Term { 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), } } } impl Context { pub fn new() -> Self { - Context(HashMap::new()) + Context(HashMap::new(), HashMap::new()) } - pub fn get(&self, k: &Identifier) -> Option<&Term> { + pub fn get_term(&self, k: &Identifier) -> Option<&Term> { self.0.get(k) } - pub fn insert(&mut self, k: Identifier, v: Term) -> Option<Term> { + pub fn insert_term(&mut self, k: Identifier, v: Term) -> Option<Term> { self.0.insert(k, v) } + pub fn get_func(&self, k: &Signature) -> Option<&Expression> { + self.1.get(k) + } + pub fn insert_func(&mut self, k: Signature, v: Expression) -> Option<Expression> { + self.1.insert(k, v) + } + pub fn contains_term(&self, k: &Identifier) -> bool { + self.0.contains_key(k) + } + pub fn contains_sig(&self, k: &Signature) -> bool { + self.1.contains_key(k) + } } diff --git a/src/bidirectional.rs b/src/bidirectional.rs index e22b314..4b34ab2 100644 --- a/src/bidirectional.rs +++ b/src/bidirectional.rs @@ -1,5 +1,3 @@ -// Simple bidirectional type checking - use crate::ast::*; impl Context { @@ -9,20 +7,20 @@ impl Context { // fall through to inference mode Expression::Annotation { expr, kind } => { let result = self.infer(Expression::Annotation { expr, kind })?; - return match result.subtype(&target) { + return match self.subtype(&result, &target) { true => Ok(()), false => Err(format!("inferred type {result} does not match target {target}").into()) } }, // Bt-CheckInfer - Expression::Constant { term } => match &term.convert()?.subtype(&target) { + Expression::Constant { term } => match self.subtype(&term.convert()?, &target) { true => Ok(()), false => Err(format!("constant is of wrong type, expected {target}").into()) // false => Ok(()) // all our constants are Empty for now }, // Bt-CheckInfer - Expression::Variable { id } => match self.get(&id) { - Some(term) if term.convert()?.subtype(&target) => Ok(()), + Expression::Variable { id } => match self.get_term(&id) { + Some(term) if self.subtype(&term.convert()?, &target) => Ok(()), Some(_) => Err(format!("variable {id} is of wrong type").into()), None => Err(format!("failed to find variable {id} in context").into()) }, @@ -30,7 +28,7 @@ impl Context { Expression::Abstraction { param, func } => match target { Type::Function { from, to } => { let mut context = self.clone(); - context.insert(param, from.default()?); + context.insert_term(param, from.default()?); return context.check(*func, &to); }, _ => Err(format!("attempting to check an abstraction with a non-function type {target}").into()) @@ -38,7 +36,7 @@ impl Context { // fall through to inference mode Expression::Application { func, arg } => { let result = &self.infer(Expression::Application { func, arg })?; - return match result.subtype(&target) { + return match self.subtype(result, target) { true => Ok(()), false => Err(format!("inferred type {result} does not match {target}").into()) } @@ -61,7 +59,7 @@ impl Context { // Bt-True / Bt-False / etc Expression::Constant { term } => term.convert(), // Bt-Var - Expression::Variable { id } => match self.get(&id) { + Expression::Variable { id } => match self.get_term(&id) { Some(term) => Context::new().infer(Expression::Constant { term: term.clone() }), None => Err(format!("failed to find variable in context {self:?}").into()) }, @@ -80,7 +78,7 @@ impl Context { self.check(*if_cond, &Type::Boolean)?; let if_then = self.infer(*if_then)?; let if_else = self.infer(*if_else)?; - if if_then.subtype(&if_else) && if_else.subtype(&if_then) { + if self.subtype(&if_then, &if_else) && self.subtype(&if_else, &if_then) { Ok(if_then) // fixme: should be the join } else { Err(format!("if clauses of different types: {if_then} and {if_else}").into()) @@ -88,21 +86,18 @@ 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::Tuple(is_data, is_fields), Type::Tuple (of_data, of_fields)) => { + /// "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::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) { + if !self.subtype(is, of) { return false; } } @@ -118,7 +113,7 @@ impl Type { for (key, of_value) in of { match is.get(key) { Some(is_value) => { - if !is_value.subtype(of_value) { + if !self.subtype(is_value, of_value) { return false; } } @@ -138,16 +133,57 @@ impl Type { }, (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) + self.subtype(of_from, is_from) && self.subtype(is_to, of_to) + }, + (is, Type::Interface(signatures, associated)) => { + if let Some(of) = associated && !self.subtype(is, of) { + return false; + } + for sig in signatures.clone() { + let signature = Signature { + name: sig.name, + from: sig.from.deselfify(is), + to: sig.to.deselfify(is) + }; + if !(self.contains_sig(&signature)) { // we need context for interfaces... + return false; + } + } + 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)) => is.subtype(of), - (Type::Array(is, is_size), Type::Array(of, of_size)) => is.subtype(of) && is_size == of_size, + (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 - (_, _) if self == other => true, - (_, _) => false + (_, _) => is == of + } + } +} + +impl Type { + /// Replace explicit Oneself types with a replacement type. For interfaces. + fn deselfify(self, replacement: &Type) -> Self { + match self { + Type::Oneself => replacement.clone(), + Type::Empty | Type::Error | Type::Unit | Type::Boolean | + Type::Natural | Type::Integer | Type::Float | Type::String => self, + Type::List(data) => Type::List(Box::new(data.deselfify(replacement))), + Type::Array(data, len) => Type::Array(Box::new(data.deselfify(replacement)), len), + Type::Slice(data) => Type::Slice(Box::new(data.deselfify(replacement))), + Type::Union(data) => Type::Union( + data.iter().map(|x| x.clone().deselfify(replacement)).collect()), + Type::Struct(data) => Type::Struct( + 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)))), } } } @@ -1,4 +1,5 @@ #![allow(unused_variables, non_upper_case_globals)] +#![feature(let_chains)] pub mod ast; pub mod bidirectional; diff --git a/src/simple.rs b/src/simple.rs index e763221..c659058 100644 --- a/src/simple.rs +++ b/src/simple.rs @@ -6,7 +6,7 @@ impl Context { match expression { Expression::Annotation { expr, .. } => self.execute(*expr), Expression::Constant { term } => Ok(term), - Expression::Variable { id } => match self.get(&id) { + Expression::Variable { id } => match self.get_term(&id) { Some(term) => Ok(term.clone()), None => Err(format!("no such variable in context {self:?}").into()) }, @@ -16,7 +16,7 @@ impl Context { Expression::Abstraction { param, func } => { let value = self.execute(*arg)?; let mut context = self.clone(); - context.insert(param, value); + context.insert_term(param, value); return context.execute(*func); } _ => Err(format!("attempting to execute an application to non-abstraction {}", *func).into()) diff --git a/tests/test_execution.rs b/tests/test_execution.rs index 44df5ae..4254978 100644 --- a/tests/test_execution.rs +++ b/tests/test_execution.rs @@ -14,8 +14,8 @@ fn test_simple() { #[test] fn test_complex() { let mut context = Context::new(); - context.insert(String::from("x"), Term::Natural(413)); - context.insert(String::from("y"), Term::Boolean(true)); + context.insert_term(String::from("x"), Term::Natural(413)); + context.insert_term(String::from("y"), Term::Boolean(true)); assert_eq!(context.execute(Var("x")).unwrap(), Term::Natural(413)); assert_eq!(context.execute(Cond(Var("y"), Const(Term::Integer(612)), Var("x"))).unwrap(), Term::Integer(612)); |