aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJJ2023-07-20 10:14:55 +0000
committerJJ2023-07-20 10:21:59 +0000
commit3cf3e70cb7fcd75d53828924496699678796f5ed (patch)
tree3c4d1980cb7e8eb13017413e61eb1b15f1f2a20d
parent9672fe3861f283efc91a9cca78b17fecc5826210 (diff)
implement typeclasses as interfaces
-rw-r--r--README.md10
-rw-r--r--src/ast.rs73
-rw-r--r--src/bidirectional.rs84
-rw-r--r--src/lib.rs1
-rw-r--r--src/simple.rs4
-rw-r--r--tests/test_execution.rs4
6 files changed, 123 insertions, 53 deletions
diff --git a/README.md b/README.md
index eb32d74..dcc79bd 100644
--- a/README.md
+++ b/README.md
@@ -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)
diff --git a/src/ast.rs b/src/ast.rs
index cc6170b..99c9b6c 100644
--- a/src/ast.rs
+++ b/src/ast.rs
@@ -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)))),
}
}
}
diff --git a/src/lib.rs b/src/lib.rs
index 617f158..372d8d9 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -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));