implement typeclasses as interfaces

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));