From 95ce33948581a10c2d55793b6317c7ce273f936a Mon Sep 17 00:00:00 2001 From: JJ Date: Thu, 6 Apr 2023 14:24:38 -0700 Subject: rename project, write parser tests --- Cargo.lock | 14 ++++++------ Cargo.toml | 2 +- README.md | 2 +- src/ast.rs | 11 +++++----- src/lib.rs | 6 ++++++ src/main.rs | 12 ++++------- src/parser.rs | 35 ++++++++++++++++++------------ src/simple.rs | 17 +++------------ src/util.rs | 60 ++++++++++++++++++++++++++++++++++++++++++++++++++++ tests/test_parser.rs | 46 ++++++++++++++++++++++++++++++++++++++++ 10 files changed, 155 insertions(+), 50 deletions(-) create mode 100644 src/lib.rs create mode 100644 src/util.rs create mode 100644 tests/test_parser.rs diff --git a/Cargo.lock b/Cargo.lock index 1f0b48f..964cc1d 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -2,6 +2,13 @@ # It is not intended for manual editing. version = 3 +[[package]] +name = "chrysanthemum" +version = "0.1.0" +dependencies = [ + "peg", +] + [[package]] name = "peg" version = "0.8.1" @@ -47,13 +54,6 @@ dependencies = [ "proc-macro2", ] -[[package]] -name = "type-systems" -version = "0.1.0" -dependencies = [ - "peg", -] - [[package]] name = "unicode-ident" version = "1.0.8" diff --git a/Cargo.toml b/Cargo.toml index e32075d..079d964 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -1,5 +1,5 @@ [package] -name = "type-systems" +name = "chrysanthemum" version = "0.1.0" edition = "2021" diff --git a/README.md b/README.md index 4c7830c..4b26e2d 100644 --- a/README.md +++ b/README.md @@ -3,7 +3,7 @@ ## todo - [x] the simple lambda calculus: implement `execute` -- [ ] to lose my sanity: implement `parse` +- [x] to lose my sanity: implement `parse` - [ ] bidirectional typechecking: implement `infer` and `check` - [ ] simple effects: extend `ast` - [ ] type classes: implement `monomorphize` diff --git a/src/ast.rs b/src/ast.rs index 9202968..4bbc7ed 100644 --- a/src/ast.rs +++ b/src/ast.rs @@ -19,7 +19,7 @@ pub enum Expression { // _every_ type in our language is represented as this and interpreted as a type. // how to store more data than fits... hmm -pub type Value = i8; +pub type Value = u64; #[derive(Debug, Copy, Clone, PartialEq, Eq)] pub enum Type { @@ -27,6 +27,7 @@ pub enum Type { Unit, Bool, Natural, + Integer, // Float, // String, // Enum(Vec), @@ -44,12 +45,12 @@ pub struct Term { impl fmt::Debug 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.val), 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::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), } } } diff --git a/src/lib.rs b/src/lib.rs new file mode 100644 index 0000000..f4a5765 --- /dev/null +++ b/src/lib.rs @@ -0,0 +1,6 @@ +pub mod ast; +// pub mod classes; +// pub mod effects; +pub mod parser; +pub mod util; +pub mod simple; diff --git a/src/main.rs b/src/main.rs index f31e163..6d74f54 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,14 +1,10 @@ use std::io::{Write, stdout, stdin}; -use crate::ast::*; -mod ast; -mod classes; -mod effects; -mod parser; -mod simple; +use chrysanthemum::*; +use chrysanthemum::ast::*; fn main() { - println!("type-systems"); + println!("chrysanthemum"); let mut input = String::new(); loop { println!("infer, check, or execute? (i/c/e)"); @@ -43,7 +39,7 @@ fn main() { input.clear(); stdin().read_line(&mut input).unwrap(); - simple::execute(Context::new(), parser::parse(&input)); + println!("{:?}", simple::execute(Context::new(), parser::parse(&input))); }, _ => println!("invalid option {}. please try again.", input.trim()) } diff --git a/src/parser.rs b/src/parser.rs index cb86ea7..2f918a8 100644 --- a/src/parser.rs +++ b/src/parser.rs @@ -15,13 +15,29 @@ pub fn parse_str(input: &str) -> Result() } + rule constant() -> Expression + = p:"-"? c:['0'..='9']+ { + let value = c.iter().collect::().parse::().unwrap(); + Expression::Constant { + term: Term { + val: if let Some(_) = p { + value.wrapping_neg() + } else { + value + }, + kind: Type::Empty + } + } + } rule kind() -> Type = k:identifier() { match k.as_str() { + "empty" => Type::Empty, "unit" => Type::Unit, "bool" => Type::Bool, - "int" => Type::Natural, - _ => panic!("invalid type") + "nat" => Type::Natural, + "int" => Type::Integer, + _ => panic!("invalid type"), // fixme: raise an error } } rule annotation() -> Expression @@ -31,31 +47,22 @@ pub fn parse_str(input: &str) -> Result Expression - = c:['0'..='9']+ { - Expression::Constant { - term: Term { - val: c.iter().collect::().parse::().unwrap(), - kind: Type::Empty - } - } - } rule variable() -> Expression = v:identifier() { Expression::Variable { id: v } } - // fixme: lambda is causing problems with rust-peg rule abstraction() -> Expression - = "λ" " "* p:identifier() " "+ "." " "+ f:expression() { + = ("λ" / "lambda ") " "* p:identifier() " "* "." " "* f:expression() { Expression::Abstraction { param: p, func: Box::new(f) } } + // fixme: more cases should parse, but how? rule application() -> Expression - = "(" f:(abstraction() / annotation()) ")" " "+ a:expression() { + = "(" f:(annotation() / abstraction()) ")" " "* a:expression() { Expression::Application { func: Box::new(f), arg: Box::new(a) diff --git a/src/simple.rs b/src/simple.rs index f71da46..9393c00 100644 --- a/src/simple.rs +++ b/src/simple.rs @@ -17,7 +17,7 @@ pub fn execute(context: Context, expression: Expression) -> Term { Expression::Annotation { expr, .. } => return execute(context, *expr), Expression::Constant { term } => return term, Expression::Variable { id } => return context[&id], - Expression::Abstraction { .. } => panic!(), + Expression::Abstraction { .. } => panic!("attempting to execute an abstraction"), Expression::Application { func, arg } => { match *func { Expression::Abstraction { param, func } => { @@ -25,26 +25,15 @@ pub fn execute(context: Context, expression: Expression) -> Term { context.insert(param, execute(context.clone(), *arg)); return execute(context, *func); }, - _ => panic!() + _ => panic!("attempting to execute an application to nothing") } }, Expression::Conditional { if_cond, if_then, if_else } => { match execute(context.clone(), *if_cond).val { 1 => execute(context, *if_then), 0 => execute(context, *if_else), - _ => panic!() + _ => panic!("invalid type for a conditional") } }, } } - -// intentionally small: i want to run into errors -/// assumption: the count is instantiated to zero -fn uniquify(count: &mut u8) -> String { - *count += 1; - if *count == 0 { - panic!("we've overflowed!"); - } else { - return String::from(format!("{:X}", count)); - } -} diff --git a/src/util.rs b/src/util.rs new file mode 100644 index 0000000..9ed38d1 --- /dev/null +++ b/src/util.rs @@ -0,0 +1,60 @@ +#![allow(non_snake_case)] + +use crate::ast::*; + +// intentionally small: i want to run into errors +/// assumption: the count is instantiated to zero +pub fn unique_ident(count: &mut u8) -> String { + *count += 1; + if *count == 0 { + panic!("we've overflowed!"); + } else { + return String::from(format!("{:X}", count)); + } +} + +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), + kind: kind + }; +} + +pub fn Const(val: Value, kind: Type) -> Expression { + return Expression::Constant { + term: Term {val, kind} + }; +} + +pub fn Var(id: &str) -> Expression { + return Expression::Variable { + id: String::from(id) + }; +} + +pub fn Abs(param: &str, func: Expression) -> Expression { + return Expression::Abstraction { + param: String::from(param), + func: Box::new(func), + }; +} + +pub fn App(func: Expression, arg: Expression) -> Expression { + return Expression::Application { + func: Box::new(func), + arg: Box::new(arg) + }; +} + +pub fn Cond(if_cond: Expression, if_then: Expression, if_else: Expression) -> Expression { + return Expression::Conditional { + if_cond: Box::new(if_cond), + if_then: Box::new(if_then), + if_else: Box::new(if_else) + }; +} + diff --git a/tests/test_parser.rs b/tests/test_parser.rs new file mode 100644 index 0000000..958fc37 --- /dev/null +++ b/tests/test_parser.rs @@ -0,0 +1,46 @@ +use chrysanthemum::ast::*; +use chrysanthemum::parser::*; +use chrysanthemum::util::*; + +#[test] +fn test_simple_phrases() { + assert_eq!(parse_str("123"), Ok(Const(123, Type::Empty))); + assert_eq!(parse_str("x12"), Ok(Var("x12"))); + assert_eq!(parse_str("x12x2"), Ok(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_str("12x").is_err()); + assert!(parse_str("12x23").is_err()); +} + +#[test] +fn test_simple_annotations() { + assert_eq!(parse_str("t: int"), Ok(Ann(Var("t"), Type::Integer))); + assert_eq!(parse_str("12: nat"), Ok(Ann(Const(12, Type::Empty), Type::Natural))); + // assert!(parse_str("t: fake").is_err()); // fixme: currently panics +} + +#[test] +fn test_simple_expressions() { + assert_eq!(parse_str("λx.y"), Ok(Abs("x", Var("y")))); + assert_eq!(parse_str("λ x.y"), Ok(Abs("x", Var("y")))); + assert_eq!(parse_str("λx.y"), Ok(Abs("x", Var("y")))); + assert_eq!(parse_str("lambda x . y"), Ok(Abs("x", Var("y")))); + assert!(parse_str("(λx.y)").is_err()); // fixme: should be fine + assert_eq!(parse_str("(λx.y) x"), Ok(App(Abs("x", Var("y")), Var("x")))); + assert_eq!(parse_str("(λx.y) x"), Ok(App(Abs("x", Var("y")), Var("x")))); + assert_eq!(parse_str("if x then y else z"), Ok(Cond(Var("x"), Var("y"), Var("z")))); + assert_eq!(parse_str("if xeme then yak else zebra"), Ok(Cond(Var("xeme"), Var("yak"), Var("zebra")))); + assert_eq!(parse_str("if 413 then 612 else 1025"), Ok(Cond(Const(413, Type::Empty), Const(612, Type::Empty), Const(1025, Type::Empty)))); // invalid, but should parse +} + +#[test] +fn test_complex_expressions() { + assert_eq!(parse_str("(λy.if y then 0 else 1) z"), Ok(App(Abs("y", Cond(Var("y"), Const(0, Type::Empty), Const(1, Type::Empty))), Var("z")))); +} + +#[test] +fn test_file() { + +} + -- cgit v1.2.3-70-g09d2