diff options
| -rw-r--r-- | README.md | 8 | ||||
| -rw-r--r-- | src/ast.rs | 105 | ||||
| -rw-r--r-- | src/lib.rs | 2 | ||||
| -rw-r--r-- | src/main.rs | 13 | ||||
| -rw-r--r-- | src/parser.rs | 28 | ||||
| -rw-r--r-- | src/simple.rs | 140 | ||||
| -rw-r--r-- | src/util.rs | 10 |
7 files changed, 206 insertions, 100 deletions
@@ -3,13 +3,13 @@ ## todo - [x] the simple lambda calculus: implement `execute` -- [x] to lose my sanity: implement `parse` +- [x] to be fancy: implement `parse` +- [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` - [ ] simple effects: extend `ast` - [ ] type classes: implement `monomorphize` -- [x] to be fancy: implement `parse_file` -- [ ] extend to additional basic types: implement `cast` -- [ ] extend to complex types - [x] testtesttest ## architecture @@ -1,4 +1,4 @@ -// Bidirectional type checking, simple types for effects (or perhaps subtyping?) and typeclasses +// Bidirectional type checking, subtyping, and typeclasses use core::fmt; use std::collections::HashMap; @@ -6,8 +6,8 @@ use std::collections::HashMap; pub type Identifier = String; pub type Context = HashMap<Identifier, Term>; -// note: when comes the time, we'll put effects in here (i think) -#[derive(Clone, PartialEq, Eq)] +// note: built-in functions do NOT go here! +#[derive(Debug, Clone, PartialEq)] pub enum Expression { Annotation{expr: Box<Expression>, kind: Type}, Constant{term: Term}, @@ -18,11 +18,7 @@ pub enum Expression { Conditional{if_cond: Box<Expression>, if_then: Box<Expression>, if_else: Box<Expression>} } -// _every_ type in our language is represented as this and interpreted as a type. -// how to store more data than fits... hmm... a problem for later -pub type Value = u64; - -#[derive(Debug, Clone, PartialEq, Eq)] +#[derive(Debug, Clone, PartialEq)] pub enum Type { Empty, Error, @@ -30,29 +26,96 @@ pub enum Type { Boolean, Natural, Integer, - // Float, - // String, + Float, + String, Enum(Vec<Type>), Record(HashMap<Identifier, Type>), Function{from: Box<Type>, to: Box<Type>}, } -// this means that functions cannot have types? unless we put them as empty values ig -#[derive(Debug, Clone, PartialEq, Eq)] -pub struct Term { - pub val: Value, - pub kind: Type, // currently useless / redundant: will be useful for casting +#[derive(Debug, Clone, PartialEq)] +pub enum Term { + Unit(), + Boolean(bool), + Natural(usize), + Integer(isize), + Float(f32), + String{len: usize, cap: usize, data: Vec<usize>}, + Enum{val: usize, data: Vec<Type>}, // is this right? + Record(HashMap<Identifier, Term>), // is this right? + Function(Box<Expression>) // this should allow us to bind functions } -impl fmt::Debug for Expression { +impl fmt::Display for Expression { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { match self { - Expression::Annotation { expr, kind } => write!(f, "({:?}: {:?})", expr, kind), - Expression::Constant { term } => write!(f, "'{}", term.val), + Expression::Annotation { expr, kind } => write!(f, "({}: {})", expr, kind), + Expression::Constant { term } => write!(f, "'{:?}", term), Expression::Variable { id } => write!(f, "{}", id), - Expression::Abstraction { param, func } => write!(f, "(λ{}.{:?})", param, func), - Expression::Application { func, arg } => write!(f, "({:?} {:?})", func, arg), - Expression::Conditional { if_cond, if_then, if_else } => write!(f, "(if {:?} then {:?} else {:?})", if_cond, if_then, if_else), + Expression::Abstraction { param, func } => write!(f, "(λ{}.{})", param, func), + Expression::Application { func, arg } => write!(f, "({} {})", func, arg), + Expression::Conditional { if_cond, if_then, if_else } => write!(f, "(if {} then {} else {})", if_cond, if_then, if_else), + } + } +} + +impl fmt::Display for Type { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match self { + Type::Empty => write!(f, "⊤"), + Type::Error => write!(f, "⊥"), + Type::Unit => write!(f, "unit"), + Type::Boolean => write!(f, "bool"), + Type::Natural => write!(f, "nat"), + Type::Integer => write!(f, "int"), + Type::Float => write!(f, "float"), + Type::String => write!(f, "str"), + Type::Enum(data) => write!(f, "({:?})", data), + Type::Record(data) => write!(f, "{{{:?}}}", data), + Type::Function { from, to } => write!(f, "{}->{}", from, to), } } } + +impl fmt::Display for Term { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match self { + Term::Unit() => write!(f, "∅"), + Term::Boolean(term) => write!(f, "{}", 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::Enum { val, data } => write!(f, "{:?}", data.get(*val)), + Term::Record(term) => write!(f, "{:?}", term), + Term::Function(expr) => write!(f, "{}", *expr), + } + } +} + +// hatehatehate that you can't implement a trait for foreign types +// impl<T> fmt::Display for Vec<T> where T: fmt::Display { +// fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { +// for (i, val) in self.enumerate() { +// if i == 0 { +// write!(f, "{}", val); +// } else { +// write!(f, ",{}", val); +// } +// } +// return Ok(()); +// } +// } + +// impl<T, U> fmt::Display for HashMap<T, U> where T: fmt::Display, U: fmt::Display { +// fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { +// for (i, (key, val)) in self.enumerate() { +// if i == 0 { +// write!(f, "{}={}", key, val); +// } else { +// write!(f, ",{}={}", key, val); +// } +// } +// return Ok(()); +// } +// } @@ -1,3 +1,5 @@ +#![allow(unused_variables)] + pub mod ast; // pub mod classes; // pub mod effects; diff --git a/src/main.rs b/src/main.rs index 2a44397..4504d87 100644 --- a/src/main.rs +++ b/src/main.rs @@ -6,6 +6,7 @@ use chrysanthemum::ast::*; fn main() { println!("chrysanthemum"); let mut input = String::new(); + let empty_context = Context::new(); loop { println!("infer, check, or execute? (i/c/e)"); print!("\x1b[1m==> \x1b[22m"); @@ -21,8 +22,8 @@ fn main() { input.clear(); stdin().read_line(&mut input).unwrap(); - match simple::infer(Context::new(), parser::parse_lambda(&input).unwrap()) { - Ok(term) => println!("infers! {:?}", term), + match simple::infer(&empty_context, parser::parse_lambda(&input).unwrap()) { + Ok(kind) => println!("infers! {}", kind), Err(e) => println!("{:?}", e), } }, @@ -33,10 +34,10 @@ fn main() { input.clear(); stdin().read_line(&mut input).unwrap(); - let kind = simple::infer(Context::new(), parser::parse(&input)); + let kind = simple::infer(&empty_context, parser::parse(&input)); match kind { Ok(kind) => { - match simple::check(Context::new(), parser::parse_lambda(&input).unwrap(), kind) { + match simple::check(&empty_context, parser::parse_lambda(&input).unwrap(), &kind) { Ok(_) => println!("checks!"), Err(e) => println!("{:?}", e), } @@ -51,8 +52,8 @@ fn main() { input.clear(); stdin().read_line(&mut input).unwrap(); - match simple::execute(Context::new(), parser::parse_lambda(&input).unwrap()) { - Ok(term) => println!("{:?}", term), + match simple::execute(&empty_context, parser::parse_lambda(&input).unwrap()) { + Ok(term) => println!("{}", term), Err(e) => println!("{:?}", e) } }, diff --git a/src/parser.rs b/src/parser.rs index 6e6a262..8eac52d 100644 --- a/src/parser.rs +++ b/src/parser.rs @@ -6,7 +6,7 @@ pub fn parse(input: &str) -> Expression { Ok(expr) => return expr, Err(e) => println!("invalid expression! {:?}", e) } - return Expression::Constant { term: Term { val: 0, kind: Type::Empty } }; + return Expression::Constant { term: Term::Unit() }; } /// Parses a Nim-like language into an AST. @@ -35,15 +35,12 @@ pub fn parse_lambda(input: &str) -> Result<Expression, peg::error::ParseError<pe } rule cons() -> Expression = p:"-"? c:['0'..='9']+ { - let value = c.iter().collect::<String>().parse::<Value>().unwrap(); + let value = c.iter().collect::<String>().parse::<usize>().unwrap(); Expression::Constant { - term: Term { - val: if let Some(_) = p { - value.wrapping_neg() - } else { - value - }, - kind: Type::Empty + term: if let Some(_) = p { + Term::Integer(-1 * isize::try_from(value).unwrap()) + } else { + Term::Natural(value) } } } @@ -236,15 +233,12 @@ pub fn parse_lang(input: &str) -> Result<Vec<Expression>, peg::error::ParseError } // constants rule cons() -> Expression = p:"-"? c:['0'..='9']+ { - let value = c.iter().collect::<String>().parse::<Value>().unwrap(); + let value = c.iter().collect::<String>().parse::<usize>().unwrap(); Expression::Constant { - term: Term { - val: if let Some(_) = p { - value.wrapping_neg() - } else { - value - }, - kind: Type::Empty // fixme + term: if let Some(_) = p { + Term::Integer(-1 * isize::try_from(value).unwrap()) + } else { + Term::Natural(value) } } } diff --git a/src/simple.rs b/src/simple.rs index 6a40b67..c67fe2e 100644 --- a/src/simple.rs +++ b/src/simple.rs @@ -1,117 +1,117 @@ // Simple bidirectional type checking -#![allow(unused_variables)] - use crate::ast::*; +use std::collections::HashMap; -pub fn check(context: Context, expression: Expression, target: Type) -> Result<(), (&'static str, Context, Type)> { +pub fn check(context: &Context, expression: Expression, target: &Type) -> Result<(), String> { match expression { // fall through to inference mode Expression::Annotation { expr, kind } => { - let result = infer(context.clone(), Expression::Annotation { expr, kind })?; + let result = infer(context, Expression::Annotation { expr, kind })?; return match subtype(&result, &target) { true => Ok(()), - false => Err(("inferred type does not match target", context, target)) + false => Err(format!("inferred type {result} does not match target {target}")) } }, // Bt-CheckInfer - Expression::Constant { term } => match subtype(&term.kind, &target) { + Expression::Constant { term } => match subtype(&convert(&term)?, &target) { true => Ok(()), - false => Ok(()) // all our constants are Empty for now - // false => Err(("constant is of wrong type", context, target)) + false => Err(format!("constant is of wrong type, expected {target}")) + // false => Ok(()) // all our constants are Empty for now }, // Bt-CheckInfer Expression::Variable { id } => match context.get(&id) { - Some(term) if subtype(&term.kind, &target) => Ok(()), - Some(_) => Err(("variable is of wrong type", context, target)), - None => Err(("failed to find variable in context", context, target)) + Some(term) if subtype(&convert(term)?, &target) => Ok(()), + Some(_) => Err(format!("variable {id} is of wrong type")), + None => Err(format!("failed to find variable {id} in context")) }, // Bt-Abs Expression::Abstraction { param, func } => match target { Type::Function { from, to } => { - let mut context = context; - context.insert(param, Term { val: 0, kind: *from }); // hack - return check(context, *func, *to); + let mut context = context.clone(); + context.insert(param, default(from)?); + return check(&context, *func, &to); }, - _ => Err(("attempting to check an abstraction with a non-function type", context, target)) + _ => Err(format!("attempting to check an abstraction with a non-function type {target}")) }, // fall through to inference mode Expression::Application { func, arg } => { - let result = &infer(context.clone(), Expression::Application { func, arg })?; + let result = &infer(context, Expression::Application { func, arg })?; return match subtype(&result, &target) { true => Ok(()), - false => Err(("inferred type does not match target", context, target)) + false => Err(format!("inferred type {result} does not match {target}")) } }, // T-If Expression::Conditional { if_cond, if_then, if_else } => { - check(context.clone(), *if_cond, Type::Boolean)?; - check(context.clone(), *if_then, target.clone())?; - check(context.clone(), *if_else, target.clone())?; + check(context, *if_cond, &Type::Boolean)?; + check(context, *if_then, &target)?; + check(context, *if_else, &target)?; return Ok(()); } } } -pub fn infer(context: Context, expression: Expression) -> Result<Type, (&'static str, Context, Type)> { +pub fn infer(context: &Context, expression: Expression) -> Result<Type, String> { match expression { // Bt-Ann - Expression::Annotation { expr, kind } => check(context, *expr, kind.clone()).map(|x| kind), + Expression::Annotation { expr, kind } => check(context, *expr, &kind).map(|x| kind), // Bt-True / Bt-False / etc - Expression::Constant { term } => Ok(term.kind), + Expression::Constant { term } => convert(&term), // Bt-Var Expression::Variable { id } => match context.get(&id) { - Some(term) => Ok(term.clone().kind), - None => Err(("failed to find variable in context", context, Type::Empty)) + Some(term) => infer(&Context::new(), Expression::Constant { term: term.clone() }), + None => Err(format!("failed to find variable in context {context:?}")) }, // Bt-App - Expression::Application { func, arg } => match infer(context.clone(), *func)? { - Type::Function { from, to } => check(context, *arg, *from).map(|x| *to), - _ => Err(("application abstraction is not a function type", context, Type::Empty)) + Expression::Application { func, arg } => match infer(context, *func)? { + Type::Function { from, to } => check(context, *arg, &*from).map(|x| *to), + _ => Err(format!("application abstraction is not a function type")) }, // 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(("attempting to infer from an abstraction", context, Type::Empty)), + Err(format!("attempting to infer from an abstraction")), // idk Expression::Conditional { if_cond, if_then, if_else } => { - check(context.clone(), *if_cond, Type::Boolean)?; - let if_then = infer(context.clone(), *if_then)?; - let if_else = infer(context.clone(), *if_else)?; + check(context, *if_cond, &Type::Boolean)?; + let if_then = infer(context, *if_then)?; + let if_else = infer(context, *if_else)?; if subtype(&if_then, &if_else) && subtype(&if_else, &if_then) { Ok(if_then) // fixme: should be the join } else { - Err(("if clauses of different types", context, Type::Empty)) + Err(format!("if clauses of different types: {if_then} and {if_else}")) } } } } /// Evaluates an expression given a context (of variables) to a term, or fails. -pub fn execute(context: Context, expression: Expression) -> Result<Term, (&'static str, Context)> { +pub fn execute(context: &Context, expression: Expression) -> Result<Term, String> { match expression { Expression::Annotation { expr, .. } => execute(context, *expr), Expression::Constant { term } => Ok(term), Expression::Variable { id } => match context.get(&id) { Some(term) => Ok(term.clone()), - None => Err(("no such variable in context", context)) + None => Err(format!("no such variable in context {context:?}")) }, - Expression::Abstraction { .. } => Err(("attempting to execute an abstraction", context)), + Expression::Abstraction { param, func } => + Err(format!("attempting to execute an abstraction ({}){}", param, func)), Expression::Application { func, arg } => match *func { Expression::Abstraction { param, func } => { - let value = execute(context.clone(), *arg)?; - let mut context = context; + let value = execute(context, *arg)?; + let mut context = context.clone(); context.insert(param, value); - return execute(context, *func); + return execute(&context, *func); } - _ => Err(("attempting to execute an application to nothing", context)) + _ => Err(format!("attempting to execute an application to non-abstraction {}", *func)) }, Expression::Conditional { if_cond, if_then, if_else } => { - match execute(context.clone(), *if_cond) { - Ok(Term { val: 1, .. }) => execute(context, *if_then), - Ok(Term { val: 0, .. }) => execute(context, *if_else), - _ => Err(("invalid type for a conditional", context)) + match execute(context, *if_cond)? { + Term::Boolean(true) => execute(context, *if_then), + Term::Boolean(false) => execute(context, *if_else), + term => Err(format!("invalid type {} for a conditional", convert(&term)?)) } } } @@ -145,3 +145,55 @@ pub fn subtype(is: &Type, of: &Type) -> bool { (_, _) => false } } + +/// Convert a term into its corresponding type. +pub fn convert(term: &Term) -> Result<Type, String> { + match term { + Term::Unit() => Ok(Type::Unit), + Term::Boolean(_) => Ok(Type::Boolean), + Term::Natural(_) => Ok(Type::Natural), + Term::Integer(_) => Ok(Type::Integer), + Term::Float(_) => Ok(Type::Float), + Term::String { len, cap, data } => Ok(Type::String), + Term::Enum { val, data } => data.get(*val) + .ok_or_else(|| "enum value out of range!".to_string()).cloned(), + Term::Record(data) => { + let mut result = HashMap::new(); + for (key, val) in data { + result.insert(key.clone(), convert(val)?); + } + return Ok(Type::Record(result)); + }, + Term::Function(func) => match infer(&Context::new(), *func.clone()) { + Ok(Type::Function { from, to }) => Ok(Type::Function { from, to }), + _ => Err("function term value not a function!".to_string()) + } + } +} + +/// Get the default value of a type. Throws an error if it doesn't exist. +pub fn default(kind: &Type) -> Result<Term, String> { + match kind { + Type::Empty => Err("attempting to take the default term for empty".to_string()), + Type::Error => Err("attempting to take the default term for error".to_string()), + Type::Unit => Ok(Term::Unit()), + Type::Boolean => Ok(Term::Boolean(false)), + 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::Enum(data) => match data.len() { + 0 => Err("attempting to get a default term of an enum with no variants!".to_string()), + _ => Ok(Term::Enum { val: 0, data: data.clone() }) + }, + Type::Record(data) => { + let mut result = HashMap::new(); + for (key, val) in data { + result.insert(key.clone(), default(&val)?); + } + return Ok(Term::Record(result)); + }, + Type::Function { from, to } => + Err("attempting to take the default term of a function type".to_string()), + } +} diff --git a/src/util.rs b/src/util.rs index 5011ac7..70bd8e4 100644 --- a/src/util.rs +++ b/src/util.rs @@ -13,10 +13,6 @@ pub fn unique_ident(count: &mut u8) -> String { } } -pub fn Term(val: Value, kind: Type) -> Term { - return Term {val, kind}; -} - pub fn Ann(expr: Expression, kind: Type) -> Expression { return Expression::Annotation { expr: Box::new(expr), @@ -24,10 +20,8 @@ pub fn Ann(expr: Expression, kind: Type) -> Expression { }; } -pub fn Const(val: Value) -> Expression { - return Expression::Constant { - term: Term {val, kind: Type::Empty} - }; +pub fn Const(term: Term) -> Expression { + return Expression::Constant { term }; } pub fn Var(id: &str) -> Expression { |