aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--README.md33
-rw-r--r--src/ast.rs181
-rw-r--r--src/bidirectional.rs203
-rw-r--r--src/classes.rs3
-rw-r--r--src/main.rs8
-rw-r--r--src/parser.rs65
-rw-r--r--src/simple.rs53
-rw-r--r--src/util.rs4
-rw-r--r--tests/test_checking.rs40
-rw-r--r--tests/test_execution.rs17
-rw-r--r--tests/test_parser.rs44
11 files changed, 342 insertions, 309 deletions
diff --git a/README.md b/README.md
index 7140111..3f28020 100644
--- a/README.md
+++ b/README.md
@@ -1,4 +1,10 @@
-# chrysanthemum: a simple type system
+# chrysanthemum
+
+chrysanthemum is a simple language with a 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`, `nat`, `int`, `float`, `str`, `union`, `struct`, `empty`, and `err` types
## todo
@@ -8,19 +14,30 @@
- [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`
+- [ ] simple effects: extend `ast`
- [x] testtesttest
## architecture
```bash
src/
-src/main.rs # the user facing program
-src/parser.rs # parses user programs into proper data structures
-src/ast.rs # the fundamental representation of the program
-src/simple.rs # the core of the lambda calculus: checking, inference, evaluation
-src/effects.rs # code for effects idk
-src/classes.rs # a monomorphization pass for type classes
+src/main.rs # the user facing program
+src/simple.rs # the simple lambda calculus: execution
+src/ast.rs # the fundamental representation of types and terms
+src/bidirectional.rs # the core of the language: checking, inference
+src/unification.rs # an alternate core: checking and inference by unification
+src/parser.rs # parses user programs into proper data structures
+src/monomorphize.rs # a monomorphization pass for type classes
+src/effects.rs # code for effects idk
test/ # various tests
```
+
+## bibliography
+
+- [TAPL](https://www.cis.upenn.edu/~bcpierce/tapl/)
+- [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)
+- [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 bd0d8b4..6bb7171 100644
--- a/src/ast.rs
+++ b/src/ast.rs
@@ -1,10 +1,10 @@
-// The abstract syntax tree. All supported types go here.
-
-use core::fmt;
use std::collections::HashMap;
+pub type Result<T> = core::result::Result<T, Box<dyn std::error::Error>>;
pub type Identifier = String;
-pub type Context = HashMap<Identifier, Term>;
+
+#[derive(Debug, Clone, PartialEq)]
+pub struct Context(HashMap<Identifier, Term>);
// note: built-in functions do NOT go here!
#[derive(Debug, Clone, PartialEq)]
@@ -18,6 +18,7 @@ pub enum Expression {
Conditional{if_cond: Box<Expression>, if_then: Box<Expression>, if_else: Box<Expression>}
}
+/// All supported types.
#[derive(Debug, Clone, PartialEq)]
pub enum Type {
Empty,
@@ -28,11 +29,12 @@ pub enum Type {
Integer,
Float,
String,
- Enum(Vec<Type>),
- Record(HashMap<Identifier, Type>),
+ Union(Vec<Type>),
+ Struct(HashMap<Identifier, Type>),
Function{from: Box<Type>, to: Box<Type>},
}
+/// Data associated with a type.
#[derive(Debug, Clone, PartialEq)]
pub enum Term {
Unit(),
@@ -41,13 +43,71 @@ pub enum Term {
Integer(isize),
Float(f32),
String{len: usize, cap: usize, data: Vec<usize>},
- Enum{val: usize, data: Box<Term>}, // is this right?
- Record(HashMap<Identifier, Term>), // is this right?
+ Union{val: usize, data: Box<Term>}, // is this right?
+ Struct(HashMap<Identifier, Term>), // is this right?
Function(Box<Expression>) // this should allow us to bind functions
}
-impl fmt::Display for Expression {
- fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+impl Term {
+ /// Convert a term into its corresponding type.
+ pub fn convert(&self) -> Result<Type> {
+ match self {
+ 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::Union { val, data } => data.convert(),
+ Term::Struct(data) => {
+ let mut result = HashMap::new();
+ for (key, val) in data {
+ result.insert(key.clone(), val.convert()?);
+ }
+ return Ok(Type::Struct(result));
+ },
+ 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())
+ }
+ }
+ }
+}
+
+impl Type {
+ /// Get the default value of a type. Throws an error if it doesn't exist.
+ pub fn default(&self) -> Result<Term> {
+ match self {
+ Type::Empty => Err("attempting to take the default term for empty".into()),
+ Type::Error => Err("attempting to take the default term for error".into()),
+ 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::Union(data) => match data.len() {
+ 0 => Err("attempting to get a default term of an enum with no variants!".into()),
+ _ => Ok(Term::Union { val: 0, data: Box::new(data.get(0).unwrap().default()?) })
+ },
+ Type::Struct(data) => {
+ let mut result = HashMap::new();
+ for (key, val) in data {
+ result.insert(key.clone(), val.default()?);
+ }
+ return Ok(Term::Struct(result));
+ },
+ Type::Function { from, to } =>
+ Err("attempting to take the default term of a function type".into()),
+ }
+ }
+}
+
+impl core::fmt::Display for Expression {
+ fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
match self {
Expression::Annotation { expr, kind } => write!(f, "({}: {})", expr, kind),
Expression::Constant { term } => write!(f, "'{:?}", term),
@@ -59,8 +119,8 @@ impl fmt::Display for Expression {
}
}
-impl fmt::Display for Type {
- fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+impl core::fmt::Display for Type {
+ fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
match self {
Type::Empty => write!(f, "⊤"),
Type::Error => write!(f, "⊥"),
@@ -70,15 +130,15 @@ impl fmt::Display for Type {
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::Union(data) => write!(f, "({:?})", data),
+ Type::Struct(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 {
+impl core::fmt::Display for Term {
+ fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
match self {
Term::Unit() => write!(f, "∅"),
Term::Boolean(term) => write!(f, "{}", term),
@@ -86,90 +146,21 @@ impl fmt::Display for 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),
- Term::Record(term) => write!(f, "{:?}", term),
+ Term::Union { val, data } => write!(f, "{:?}", data),
+ Term::Struct(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(());
-// }
-// }
-
-/// 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 } => convert(data),
- 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 *func.clone() {
- Expression::Annotation { expr, kind } => match kind {
- Type::Function { from, to } => Ok(Type::Function { from, to }),
- _ => Err("function term value not a function!".to_string())
- }
- _ => Err("function term value does not have an annotation!".to_string())
- }
+impl Context {
+ pub fn new() -> Self {
+ Context(HashMap::new())
}
-}
-
-/// 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: Box::new(default(data.get(0).unwrap())?) })
- },
- 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()),
+ pub fn get(&self, k: &Identifier) -> Option<&Term> {
+ self.0.get(k)
+ }
+ pub fn insert(&mut self, k: Identifier, v: Term) -> Option<Term> {
+ self.0.insert(k, v)
}
}
diff --git a/src/bidirectional.rs b/src/bidirectional.rs
index 493ae2f..d62267c 100644
--- a/src/bidirectional.rs
+++ b/src/bidirectional.rs
@@ -2,119 +2,122 @@
use crate::ast::*;
-/// Checking judgement: takes an expression and a type to check against and calls out to `infer` as needed.
-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, Expression::Annotation { expr, kind })?;
- return match subtype(&result, &target) {
- true => Ok(()),
- false => Err(format!("inferred type {result} does not match target {target}"))
- }
- },
- // Bt-CheckInfer
- Expression::Constant { term } => match subtype(&convert(&term)?, &target) {
- true => Ok(()),
- 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(&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.clone();
- context.insert(param, default(from)?);
- return check(&context, *func, &to);
+impl Context {
+ /// Checking judgement: takes an expression and a type to check against and calls out to `infer` as needed.
+ pub fn check(&self, expression: Expression, target: &Type) -> Result<()> {
+ match expression {
+ // fall through to inference mode
+ Expression::Annotation { expr, kind } => {
+ let result = self.infer(Expression::Annotation { expr, kind })?;
+ return match result.subtype(&target) {
+ true => Ok(()),
+ false => Err(format!("inferred type {result} does not match target {target}").into())
+ }
},
- _ => 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, Expression::Application { func, arg })?;
- return match subtype(&result, &target) {
+ // Bt-CheckInfer
+ Expression::Constant { term } => match &term.convert()?.subtype(&target) {
true => Ok(()),
- false => Err(format!("inferred type {result} does not match {target}"))
+ 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(()),
+ Some(_) => Err(format!("variable {id} is of wrong type").into()),
+ None => Err(format!("failed to find variable {id} in context").into())
+ },
+ // Bt-Abs
+ Expression::Abstraction { param, func } => match target {
+ Type::Function { from, to } => {
+ let mut context = self.clone();
+ context.insert(param, from.default()?);
+ return context.check(*func, &to);
+ },
+ _ => Err(format!("attempting to check an abstraction with a non-function type {target}").into())
+ },
+ // fall through to inference mode
+ Expression::Application { func, arg } => {
+ let result = &self.infer(Expression::Application { func, arg })?;
+ return match result.subtype(&target) {
+ true => Ok(()),
+ false => Err(format!("inferred type {result} does not match {target}").into())
+ }
+ },
+ // T-If
+ Expression::Conditional { if_cond, if_then, if_else } => {
+ self.check(*if_cond, &Type::Boolean)?;
+ self.check(*if_then, &target)?;
+ self.check(*if_else, &target)?;
+ return Ok(());
}
- },
- // T-If
- Expression::Conditional { if_cond, if_then, if_else } => {
- check(context, *if_cond, &Type::Boolean)?;
- check(context, *if_then, &target)?;
- check(context, *if_else, &target)?;
- return Ok(());
}
}
-}
-/// Inference judgement: takes an expression and attempts to infer the associated type.
-pub fn infer(context: &Context, expression: Expression) -> Result<Type, String> {
- match expression {
- // Bt-Ann
- Expression::Annotation { expr, kind } => check(context, *expr, &kind).map(|x| kind),
- // Bt-True / Bt-False / etc
- Expression::Constant { term } => convert(&term),
- // Bt-Var
- Expression::Variable { id } => match context.get(&id) {
- 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, *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(format!("attempting to infer from an abstraction")),
- // idk
- Expression::Conditional { if_cond, if_then, 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(format!("if clauses of different types: {if_then} and {if_else}"))
+ /// Inference judgement: takes an expression and attempts to infer the associated type.
+ pub fn infer(&self, expression: Expression) -> Result<Type> {
+ match expression {
+ // Bt-Ann
+ Expression::Annotation { expr, kind } => self.check(*expr, &kind).map(|x| kind),
+ // Bt-True / Bt-False / etc
+ Expression::Constant { term } => term.convert(),
+ // Bt-Var
+ Expression::Variable { id } => match self.get(&id) {
+ Some(term) => Context::new().infer(Expression::Constant { term: term.clone() }),
+ None => Err(format!("failed to find variable in context {self:?}").into())
+ },
+ // Bt-App
+ Expression::Application { func, arg } => match self.infer(*func)? {
+ Type::Function { from, to } => self.check(*arg, &*from).map(|x| *to),
+ _ => Err(format!("application abstraction is not a function type").into())
+ },
+ // 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(format!("attempting to infer from an abstraction").into()),
+ // idk
+ Expression::Conditional { if_cond, if_then, if_else } => {
+ 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) {
+ Ok(if_then) // fixme: should be the join
+ } else {
+ Err(format!("if clauses of different types: {if_then} and {if_else}").into())
+ }
}
}
}
}
-/// The subtyping relation between any two types.
-pub fn subtype(is: &Type, of: &Type) -> bool {
- match (is, of) {
- (Type::Record(is_fields), Type::Record(of_fields)) => {
- // width, depth, and permutation
- for (key, of_value) in of_fields {
- match is_fields.get(key) {
- Some(is_value) => {
- if !subtype(is_value, of_value) {
- return false;
+impl Type {
+ /// The subtyping relation between any two types.
+ pub fn subtype(&self, other: &Self) -> bool {
+ match (self, other) {
+ (Type::Struct(is_fields), Type::Struct(of_fields)) => {
+ // width, depth, and permutation
+ for (key, of_value) in of_fields {
+ match is_fields.get(key) {
+ Some(is_value) => {
+ if !is_value.subtype(of_value) {
+ return false;
+ }
}
+ None => return false
}
- None => return false
}
- }
- return true;
- },
- (Type::Enum(is_variants), Type::Enum(of_variants)) => false, // fixme
- (Type::Function { from: is_from, to: is_to },
- Type::Function { from: of_from, to: of_to }) => {
- subtype(of_from, is_from) && subtype(is_to, of_to)
- },
- (Type::Natural, Type::Integer) => true, // obviously not, but let's pretend
- (_, Type::Empty) => true,
- (Type::Error, _) => true,
- (_, _) if is == of => true,
- (_, _) => false
+ return true;
+ },
+ (Type::Union(is_variants), Type::Union(of_variants)) => false, // fixme
+ (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)
+ },
+ (Type::Natural, Type::Integer) => true, // obviously not, but let's pretend
+ (_, Type::Empty) => true,
+ (Type::Error, _) => true,
+ (_, _) if self == other => true,
+ (_, _) => false
+ }
}
}
-
diff --git a/src/classes.rs b/src/classes.rs
deleted file mode 100644
index 38a4847..0000000
--- a/src/classes.rs
+++ /dev/null
@@ -1,3 +0,0 @@
-// Typeclass pass: monomorphize based on usage, pretty much
-
-
diff --git a/src/main.rs b/src/main.rs
index a33e963..b93e778 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -24,7 +24,7 @@ fn main() {
input.clear();
stdin().read_line(&mut input).unwrap();
- match infer(&empty_context, parser::parse_lambda(&input).unwrap()) {
+ match empty_context.infer(parser::parse_lambda(&input).unwrap()) {
Ok(kind) => println!("infers! {}", kind),
Err(e) => println!("{:?}", e),
}
@@ -36,10 +36,10 @@ fn main() {
input.clear();
stdin().read_line(&mut input).unwrap();
- let kind = infer(&empty_context, parser::parse_lambda(&input).unwrap());
+ let kind = empty_context.infer(parser::parse_lambda(&input).unwrap());
match kind {
Ok(kind) => {
- match check(&empty_context, parser::parse_lambda(&input).unwrap(), &kind) {
+ match empty_context.check(parser::parse_lambda(&input).unwrap(), &kind) {
Ok(_) => println!("checks!"),
Err(e) => println!("{:?}", e),
}
@@ -54,7 +54,7 @@ fn main() {
input.clear();
stdin().read_line(&mut input).unwrap();
- match execute(&empty_context, parser::parse_lambda(&input).unwrap()) {
+ match empty_context.execute(parser::parse_lambda(&input).unwrap()) {
Ok(term) => println!("{}", term),
Err(e) => println!("{:?}", e)
}
diff --git a/src/parser.rs b/src/parser.rs
index d3895a4..298e09d 100644
--- a/src/parser.rs
+++ b/src/parser.rs
@@ -2,7 +2,7 @@ use crate::ast::*;
use multipeek::multipeek;
/// Parses a lambda-calculus-like language into an AST.
-pub fn parse_lambda(input: &str) -> Result<Expression, peg::error::ParseError<peg::str::LineCol>> {
+pub fn parse_lambda(input: &str) -> Result<Expression> {
// this is kinda awful, i miss my simple nim pegs
peg::parser! {
grammar lambda() for str {
@@ -98,7 +98,7 @@ pub fn parse_lambda(input: &str) -> Result<Expression, peg::error::ParseError<pe
}
}
}
- return lambda::expr(input.trim());
+ return Ok(lambda::expr(input.trim())?);
}
const operators: [char; 17] =
@@ -115,15 +115,15 @@ pub enum Token {
Value(String),
Char(char),
String(String),
- Comment(String),
- Token(String), // catch-all
+ Comment(String), // unused tbh
+ // Token(String), // catch-all
ScopeBegin, // {
ScopeEnd, // }
ExprEnd, // ;
}
/// Properly lexes a whitespace-oriented language into a series of tokens.
-pub fn lex(input: &str) -> Result<Vec<Token>, &'static str> {
+pub fn lex(input: &str) -> Result<Vec<Token>> {
enum State {
Default,
Char,
@@ -142,6 +142,7 @@ pub fn lex(input: &str) -> Result<Vec<Token>, &'static str> {
let mut buffer = String::new();
let mut result = Vec::new();
+ // .next() advances the iterator, .peek() does not
let mut input = multipeek(input.chars()); // multipeek my beloved
while let Some(c) = input.next() {
match state {
@@ -151,9 +152,36 @@ pub fn lex(input: &str) -> Result<Vec<Token>, &'static str> {
result.push(parse_token(&buffer)?);
buffer.clear();
},
- ' ' => todo!(),
- '\n' => todo!(),
- '\t' => return Err("Tabs are not supported!"),
+ ' ' => {
+ // hmm
+ todo!()
+ },
+ '\n' => {
+ if let Some(previous) = result.last() {
+ match previous {
+ // same scope, no seperator
+ Token::Operator(_) => (),
+ // do we have this tbh????
+ Token::Keyword(_) => return Err("lines shouldn't end with a keyword i think".into()),
+ // i think uhh
+ Token::Identifier(_) | Token::Value(_) | Token::Char(_) | Token::String(_) =>
+ result.push(Token::ExprEnd),
+ // always scope??
+ Token::Separator(_) => result.push(Token::ScopeBegin),
+ // idk
+ Token::Comment(_) | Token::ScopeBegin | Token::ScopeEnd | Token::ExprEnd =>
+ return Err("uhh idk always scope lol".into()),
+ }
+ }
+ todo!()
+ },
+ '\t' => return Err("Tabs are not supported!".into()),
+ _ if indent.blank => {
+ indent.blank = false;
+ // indentation check
+ todo!();
+ buffer.push(c);
+ },
'\'' => {
result.push(parse_token(&buffer)?);
buffer.clear();
@@ -187,12 +215,6 @@ pub fn lex(input: &str) -> Result<Vec<Token>, &'static str> {
indent.blank = false;
}
}
- _ if indent.blank => {
- indent.blank = false;
- // indentation check
- todo!();
- buffer.push(c);
- }
_ => buffer.push(c)
},
State::Char => match c {
@@ -205,11 +227,11 @@ pub fn lex(input: &str) -> Result<Vec<Token>, &'static str> {
Some('t') => result.push(Token::Char('\t')),
Some('\"') => result.push(Token::Char('\"')),
Some('\'') => result.push(Token::Char('\'')),
- _ => return Err("Invalid string escape sequence!"),
+ _ => return Err("Invalid string escape sequence!".into()),
}
state = State::Default;
if input.next() != Some('\'') {
- return Err("Invalid character sequence!")
+ return Err("Invalid character sequence!".into())
}
},
'\'' => {
@@ -220,7 +242,7 @@ pub fn lex(input: &str) -> Result<Vec<Token>, &'static str> {
result.push(Token::Char(c));
state = State::Default;
if input.next() != Some('\'') {
- return Err("Invalid character sequence!")
+ return Err("Invalid character sequence!".into())
}
}
},
@@ -233,7 +255,7 @@ pub fn lex(input: &str) -> Result<Vec<Token>, &'static str> {
Some('t') => buffer.push('\t'),
Some('\"') => buffer.push('\"'),
Some('\'') => buffer.push('\''),
- _ => return Err("Invalid string escape sequence!"),
+ _ => return Err("Invalid string escape sequence!".into()),
},
'\"' => {
state = State::Default;
@@ -255,7 +277,8 @@ pub fn lex(input: &str) -> Result<Vec<Token>, &'static str> {
State::Comment => match c {
'\n' => {
state = State::Default;
- result.push(Token::Comment(buffer.to_string()));
+ // result.push(Token::Comment(buffer.to_string()));
+ buffer.clear();
},
_ => buffer.push(c)
},
@@ -264,7 +287,7 @@ pub fn lex(input: &str) -> Result<Vec<Token>, &'static str> {
return Ok(result);
}
-fn parse_token(token: &str) -> Result<Token, &'static str> {
+fn parse_token(token: &str) -> Result<Token> {
if keywords.contains(&token) {
Ok(Token::Keyword(token.to_string()))
} else if is_operator(token) {
@@ -274,7 +297,7 @@ fn parse_token(token: &str) -> Result<Token, &'static str> {
} else if is_identifier(token) {
Ok(Token::Identifier(token.to_string()))
} else {
- Err("Could not parse token!")
+ Err("Could not parse token!".into())
}
}
diff --git a/src/simple.rs b/src/simple.rs
index 8d87dbf..e763221 100644
--- a/src/simple.rs
+++ b/src/simple.rs
@@ -1,32 +1,33 @@
use crate::ast::*;
-/// Evaluates an expression given a context (of variables) to a term, or fails.
-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(format!("no such variable in context {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, *arg)?;
- let mut context = context.clone();
- context.insert(param, value);
- return execute(&context, *func);
- }
- _ => Err(format!("attempting to execute an application to non-abstraction {}", *func))
- },
- Expression::Conditional { if_cond, if_then, if_else } => {
- 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)?))
+impl Context {
+ /// Evaluates an expression given a context (of variables) to a term, or fails.
+ pub fn execute(&self, expression: Expression) -> Result<Term> {
+ match expression {
+ Expression::Annotation { expr, .. } => self.execute(*expr),
+ Expression::Constant { term } => Ok(term),
+ Expression::Variable { id } => match self.get(&id) {
+ Some(term) => Ok(term.clone()),
+ None => Err(format!("no such variable in context {self:?}").into())
+ },
+ Expression::Abstraction { param, func } =>
+ Err(format!("attempting to execute an abstraction ({}){}", param, func).into()),
+ Expression::Application { func, arg } => match *func {
+ Expression::Abstraction { param, func } => {
+ let value = self.execute(*arg)?;
+ let mut context = self.clone();
+ context.insert(param, value);
+ return context.execute(*func);
+ }
+ _ => Err(format!("attempting to execute an application to non-abstraction {}", *func).into())
+ },
+ Expression::Conditional { if_cond, if_then, if_else } => {
+ match self.execute(*if_cond)? {
+ Term::Boolean(true) => self.execute(*if_then),
+ Term::Boolean(false) => self.execute(*if_else),
+ term => Err(format!("invalid type {} for a conditional", &term.convert()?).into())
+ }
}
}
}
}
-
diff --git a/src/util.rs b/src/util.rs
index a27f32c..39ac263 100644
--- a/src/util.rs
+++ b/src/util.rs
@@ -74,6 +74,6 @@ pub fn Str(len: usize, cap: usize, data: Vec<usize>) -> Term {
return Term::String { len, cap, data }
}
-pub fn Enum(val: usize, data: Term) -> Term {
- return Term::Enum { val, data: Box::new(data) }
+pub fn Union(val: usize, data: Term) -> Term {
+ return Term::Union { val, data: Box::new(data) }
}
diff --git a/tests/test_checking.rs b/tests/test_checking.rs
index e553a4e..b0f4140 100644
--- a/tests/test_checking.rs
+++ b/tests/test_checking.rs
@@ -32,15 +32,15 @@ fn test_parsing_succeeds() {
#[test]
fn test_inference() {
let context = Context::new();
- assert_eq!(infer(&context, parse_lambda(sanity_check).unwrap()), Ok(Int));
- assert_eq!(infer(&context, parse_lambda(negate).unwrap()), Ok(Func(Bool, Bool)));
- assert_eq!(infer(&context, parse_lambda(basic_abstraction).unwrap()), Ok(Func(Int, Int)));
- assert_eq!(infer(&context, parse_lambda(basic_application).unwrap()), Ok(Int));
- assert_eq!(infer(&context, parse_lambda(correct_cond_abs).unwrap()), Ok(Func(Bool, Int)));
- assert_eq!(infer(&context, parse_lambda(correct_cond).unwrap()), Ok(Nat));
- assert!(infer(&context, parse_lambda(not_inferrable).unwrap()).is_err());
- assert!(infer(&context, parse_lambda(incorrect_branches).unwrap()).is_err());
- assert!(infer(&context, parse_lambda(incorrect_cond_abs).unwrap()).is_err());
+ assert_eq!(context.infer(parse_lambda(sanity_check).unwrap()).unwrap(), Int);
+ assert_eq!(context.infer(parse_lambda(negate).unwrap()).unwrap(), Func(Bool, Bool));
+ assert_eq!(context.infer(parse_lambda(basic_abstraction).unwrap()).unwrap(), Func(Int, Int));
+ assert_eq!(context.infer(parse_lambda(basic_application).unwrap()).unwrap(), Int);
+ assert_eq!(context.infer(parse_lambda(correct_cond_abs).unwrap()).unwrap(), Func(Bool, Int));
+ assert_eq!(context.infer(parse_lambda(correct_cond).unwrap()).unwrap(), Nat);
+ assert!(context.infer(parse_lambda(not_inferrable).unwrap()).is_err());
+ assert!(context.infer(parse_lambda(incorrect_branches).unwrap()).is_err());
+ assert!(context.infer(parse_lambda(incorrect_cond_abs).unwrap()).is_err());
}
#[test]
@@ -48,17 +48,17 @@ fn test_checking() {
let context = Context::new();
// uninteresting
- assert!(check(&context, parse_lambda(sanity_check).unwrap(), &Int).is_ok());
- assert!(check(&context, parse_lambda(negate).unwrap(), &Func(Bool, Bool)).is_ok());
- assert!(check(&context, parse_lambda(basic_abstraction).unwrap(), &Func(Int, Int)).is_ok());
- assert!(check(&context, parse_lambda(basic_application).unwrap(), &Int).is_ok());
- assert!(check(&context, parse_lambda(correct_cond_abs).unwrap(), &Func(Bool, Int)).is_ok());
- assert!(check(&context, parse_lambda(correct_cond).unwrap(), &Nat).is_ok());
- assert!(check(&context, parse_lambda(incorrect_branches).unwrap(), &Unit).is_err());
- assert!(check(&context, parse_lambda(incorrect_cond_abs).unwrap(), &Error).is_err());
+ assert!(context.check(parse_lambda(sanity_check).unwrap(), &Int).is_ok());
+ assert!(context.check(parse_lambda(negate).unwrap(), &Func(Bool, Bool)).is_ok());
+ assert!(context.check(parse_lambda(basic_abstraction).unwrap(), &Func(Int, Int)).is_ok());
+ assert!(context.check(parse_lambda(basic_application).unwrap(), &Int).is_ok());
+ assert!(context.check(parse_lambda(correct_cond_abs).unwrap(), &Func(Bool, Int)).is_ok());
+ assert!(context.check(parse_lambda(correct_cond).unwrap(), &Nat).is_ok());
+ assert!(context.check(parse_lambda(incorrect_branches).unwrap(), &Unit).is_err());
+ assert!(context.check(parse_lambda(incorrect_cond_abs).unwrap(), &Error).is_err());
// more fun
- assert!(check(&context, parse_lambda(not_inferrable).unwrap(), &Func(Bool, Func(Int, Func(Int, Int)))).is_ok());
- assert!(check(&context, parse_lambda(not_inferrable).unwrap(), &Func(Bool, Func(Nat, Func(Nat, Nat)))).is_ok());
- assert!(check(&context, parse_lambda(not_inferrable).unwrap(), &Func(Bool, Func(Unit, Func(Unit, Unit)))).is_ok());
+ assert!(context.check(parse_lambda(not_inferrable).unwrap(), &Func(Bool, Func(Int, Func(Int, Int)))).is_ok());
+ assert!(context.check(parse_lambda(not_inferrable).unwrap(), &Func(Bool, Func(Nat, Func(Nat, Nat)))).is_ok());
+ assert!(context.check(parse_lambda(not_inferrable).unwrap(), &Func(Bool, Func(Unit, Func(Unit, Unit)))).is_ok());
}
diff --git a/tests/test_execution.rs b/tests/test_execution.rs
index d9b1c5e..44df5ae 100644
--- a/tests/test_execution.rs
+++ b/tests/test_execution.rs
@@ -5,10 +5,10 @@ use chrysanthemum::util::*;
#[test]
fn test_simple() {
let context = Context::new();
- assert_eq!(execute(&context, Const(Term::Boolean(false))), Ok(Term::Boolean(false)));
- assert_eq!(execute(&context, Const(Term::Natural(123))), Ok(Term::Natural(123)));
- assert_eq!(execute(&context, Const(Term::Integer(123))), Ok(Term::Integer(123)));
- assert!(execute(&context, Var("x")).is_err());
+ assert_eq!(context.execute(Const(Term::Boolean(false))).unwrap(), Term::Boolean(false));
+ assert_eq!(context.execute(Const(Term::Natural(123))).unwrap(), Term::Natural(123));
+ assert_eq!(context.execute(Const(Term::Integer(123))).unwrap(), Term::Integer(123));
+ assert!(context.execute(Var("x")).is_err());
}
#[test]
@@ -16,8 +16,9 @@ fn test_complex() {
let mut context = Context::new();
context.insert(String::from("x"), Term::Natural(413));
context.insert(String::from("y"), Term::Boolean(true));
- assert_eq!(execute(&context, Var("x")), Ok(Term::Natural(413)));
- assert_eq!(execute(&context, Cond(Var("y"), Const(Term::Integer(612)), Var("x"))), Ok(Term::Integer(612)));
- assert_eq!(execute(&context,
- App(Abs("z", Cond(Const(Term::Boolean(false)), Var("x"), Var("z"))), Const(Term::Integer(1025)))), Ok(Term::Integer(1025)));
+ 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));
+ assert_eq!(context.execute(App(Abs("z", Cond(Const(Term::Boolean(false)),
+ Var("x"), Var("z"))), Const(Term::Integer(1025)))).unwrap(), Term::Integer(1025));
}
diff --git a/tests/test_parser.rs b/tests/test_parser.rs
index 9ac8f32..84f6395 100644
--- a/tests/test_parser.rs
+++ b/tests/test_parser.rs
@@ -6,9 +6,9 @@ use chrysanthemum::util::*;
#[test]
fn test_simple_phrases() {
- assert_eq!(parse_lambda("-123"), Ok(Const(Term::Integer(-123))));
- assert_eq!(parse_lambda("x12"), Ok(Var("x12")));
- assert_eq!(parse_lambda("x12x2"), Ok(Var("x12x2")));
+ assert_eq!(parse_lambda("-123").unwrap(), Const(Term::Integer(-123)));
+ assert_eq!(parse_lambda("x12").unwrap(), Var("x12"));
+ assert_eq!(parse_lambda("x12x2").unwrap(), Var("x12x2"));
// so i _don't_ want these to be valid identifiers:
// but i actually have no idea why my peg is rejecting them lmao
assert!(parse_lambda("12x").is_err());
@@ -17,36 +17,36 @@ fn test_simple_phrases() {
#[test]
fn test_simple_annotations() {
- assert_eq!(parse_lambda("t: int"), Ok(Ann(Var("t"), Int)));
- assert_eq!(parse_lambda("12: nat"), Ok(Ann(Const(Term::Natural(12)), Nat)));
+ assert_eq!(parse_lambda("t: int").unwrap(), Ann(Var("t"), Int));
+ assert_eq!(parse_lambda("12: nat").unwrap(), Ann(Const(Term::Natural(12)), Nat));
assert!(parse_lambda("t: fake").is_err());
}
#[test]
fn test_simple_expressions() {
- assert_eq!(parse_lambda("λx.y"), Ok(Abs("x", Var("y"))));
- assert_eq!(parse_lambda("λ x.y"), Ok(Abs("x", Var("y"))));
- assert_eq!(parse_lambda("λx.y"), Ok(Abs("x", Var("y"))));
- assert_eq!(parse_lambda("lambda x . y"), Ok(Abs("x", Var("y"))));
- assert_eq!(parse_lambda("(λx.y)"), Ok(Abs("x", Var("y"))));
- assert_eq!(parse_lambda("(λx.y) x"), Ok(App(Abs("x", Var("y")), Var("x"))));
- assert_eq!(parse_lambda("(λx.y) x"), Ok(App(Abs("x", Var("y")), Var("x"))));
- assert_eq!(parse_lambda("if x then y else z"), Ok(Cond(Var("x"), Var("y"), Var("z"))));
- assert_eq!(parse_lambda("if xeme then yak else zebra"), Ok(Cond(Var("xeme"), Var("yak"), Var("zebra"))));
- assert_eq!(parse_lambda("if 413 then 612 else 1025"), Ok(Cond(Const(Term::Natural(413)), Const(Term::Natural(612)), Const(Term::Natural(1025))))); // invalid, but should parse
+ assert_eq!(parse_lambda("λx.y").unwrap(), Abs("x", Var("y")));
+ assert_eq!(parse_lambda("λ x.y").unwrap(), Abs("x", Var("y")));
+ assert_eq!(parse_lambda("λx.y").unwrap(), Abs("x", Var("y")));
+ assert_eq!(parse_lambda("lambda x . y").unwrap(), Abs("x", Var("y")));
+ assert_eq!(parse_lambda("(λx.y)").unwrap(), Abs("x", Var("y")));
+ assert_eq!(parse_lambda("(λx.y) x").unwrap(), App(Abs("x", Var("y")), Var("x")));
+ assert_eq!(parse_lambda("(λx.y) x").unwrap(), App(Abs("x", Var("y")), Var("x")));
+ assert_eq!(parse_lambda("if x then y else z").unwrap(), Cond(Var("x"), Var("y"), Var("z")));
+ assert_eq!(parse_lambda("if xeme then yak else zebra").unwrap(), Cond(Var("xeme"), Var("yak"), Var("zebra")));
+ assert_eq!(parse_lambda("if 413 then 612 else 1025").unwrap(), Cond(Const(Term::Natural(413)), Const(Term::Natural(612)), Const(Term::Natural(1025)))); // invalid, but should parse
}
#[test]
fn test_complex_expressions() {
- assert_eq!(parse_lambda("(λy.if y then false else true) z"), Ok(App(Abs("y", Cond(Var("y"), Const(Term::Boolean(false)), Const(Term::Boolean(true)))), Var("z"))));
+ assert_eq!(parse_lambda("(λy.if y then false else true) z").unwrap(), App(Abs("y", Cond(Var("y"), Const(Term::Boolean(false)), Const(Term::Boolean(true)))), Var("z")));
}
#[test]
fn test_complex_annotations() {
- assert_eq!(parse_lambda("(lambda x . y) : int"), Ok(Ann(Abs("x", Var("y")), Int)));
- assert_eq!(parse_lambda("((lambda x. y): (int -> int)) -413: int"), Ok(App(Ann(Abs("x", Var("y")), Func(Int, Int) ), Ann(Const(Term::Integer(-413)), Int))));
- assert_eq!(parse_lambda("if false: bool then true: bool else 2: int"), Ok(Cond(Ann(Const(Term::Boolean(false)), Bool), Ann(Const(Term::Boolean(true)), Bool), Ann(Const(Term::Natural(2)), Int))));
- assert_eq!(parse_lambda("(lambda x. if x then true: bool else false: bool): (int -> bool)"), Ok(Ann(Abs("x", Cond(Var("x"), Ann(Const(Term::Boolean(true)), Bool), Ann(Const(Term::Boolean(false)), Bool))), Func(Int, Bool))));
- assert_eq!(parse_lambda("(lambda x. if x then 1: int else 0: int): (bool -> int)"), Ok(Ann(Abs("x", Cond(Var("x"), Ann(Const(Term::Natural(1)), Int), Ann(Const(Term::Natural(0)), Int))), Func(Bool, Int))));
- assert_eq!(parse_lambda("(lambda x. if x then false else true): (bool -> bool)"), Ok(Ann(Abs("x", Cond(Var("x"), Const(Term::Boolean(false)), Const(Term::Boolean(true)))), Func(Bool, Bool))));
+ assert_eq!(parse_lambda("(lambda x . y) : int").unwrap(), Ann(Abs("x", Var("y")), Int));
+ assert_eq!(parse_lambda("((lambda x. y): (int -> int)) -413: int").unwrap(), App(Ann(Abs("x", Var("y")), Func(Int, Int) ), Ann(Const(Term::Integer(-413)), Int)));
+ assert_eq!(parse_lambda("if false: bool then true: bool else 2: int").unwrap(), Cond(Ann(Const(Term::Boolean(false)), Bool), Ann(Const(Term::Boolean(true)), Bool), Ann(Const(Term::Natural(2)), Int)));
+ assert_eq!(parse_lambda("(lambda x. if x then true: bool else false: bool): (int -> bool)").unwrap(), Ann(Abs("x", Cond(Var("x"), Ann(Const(Term::Boolean(true)), Bool), Ann(Const(Term::Boolean(false)), Bool))), Func(Int, Bool)));
+ assert_eq!(parse_lambda("(lambda x. if x then 1: int else 0: int): (bool -> int)").unwrap(), Ann(Abs("x", Cond(Var("x"), Ann(Const(Term::Natural(1)), Int), Ann(Const(Term::Natural(0)), Int))), Func(Bool, Int)));
+ assert_eq!(parse_lambda("(lambda x. if x then false else true): (bool -> bool)").unwrap(), Ann(Abs("x", Cond(Var("x"), Const(Term::Boolean(false)), Const(Term::Boolean(true)))), Func(Bool, Bool)));
}