aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJJ2023-04-13 07:20:06 +0000
committerJJ2023-04-13 07:21:28 +0000
commit5ae010fef48cc2bf83a0d366d2a1cfa74ecce278 (patch)
tree2241dcec8d38d16e2314e94b4dec0ed61e20d922
parent188631f3bb263700c34d578af5968ab80e699485 (diff)
major cleanups: extend Type, refactor Term, and switch to String errs
-rw-r--r--README.md8
-rw-r--r--src/ast.rs105
-rw-r--r--src/lib.rs2
-rw-r--r--src/main.rs13
-rw-r--r--src/parser.rs28
-rw-r--r--src/simple.rs140
-rw-r--r--src/util.rs10
7 files changed, 206 insertions, 100 deletions
diff --git a/README.md b/README.md
index ea42c78..7140111 100644
--- a/README.md
+++ b/README.md
@@ -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
diff --git a/src/ast.rs b/src/ast.rs
index bf34d19..0a0c042 100644
--- a/src/ast.rs
+++ b/src/ast.rs
@@ -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(());
+// }
+// }
diff --git a/src/lib.rs b/src/lib.rs
index f4a5765..dce0be7 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -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 {