aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/sexp/display.rs45
-rw-r--r--src/sexp/mod.rs2
-rw-r--r--src/type/check.rs121
-rw-r--r--src/type/display.rs85
-rw-r--r--src/type/mod.rs35
-rw-r--r--src/type/util.rs7
6 files changed, 282 insertions, 13 deletions
diff --git a/src/sexp/display.rs b/src/sexp/display.rs
new file mode 100644
index 0000000..e6dbb7c
--- /dev/null
+++ b/src/sexp/display.rs
@@ -0,0 +1,45 @@
+
+use std::fmt;
+use crate::sexp::{SLeaf, SExp, SLeaf::*, SExp::*, util::*};
+
+
+impl fmt::Display for SLeaf {
+
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ write!(f, "{}", match self {
+ Add => "+".to_string(),
+ Sub => "-".to_string(),
+ Mul => "*".to_string(),
+ Div => "/".to_string(),
+ Int(x) => x.to_string(),
+ Var(s) => s.to_string(),
+ Quote => "quote".to_string(),
+ Nil => "()".to_string(),
+ })
+ }
+
+}
+
+
+impl fmt::Display for SExp {
+
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ match self {
+ Atom(leaf) => write!(f, "{}", leaf.to_string()),
+ SCons(a, b) => {
+ match scons(a.clone(), b.clone()).into_vec() {
+ Ok(l) => write!(
+ f,
+ "({})",
+ l.into_iter()
+ .map(|x| x.to_string())
+ .collect::<Vec<String>>()
+ .join(" ")
+ ),
+ Err(_) => write!(f, "({} {})", *a, *b),
+ }
+ }
+ }
+ }
+
+}
diff --git a/src/sexp/mod.rs b/src/sexp/mod.rs
index 71e62e9..0fb5e25 100644
--- a/src/sexp/mod.rs
+++ b/src/sexp/mod.rs
@@ -2,6 +2,7 @@
pub mod step;
pub mod util;
pub mod subst;
+pub mod display;
/// A leaf node for S-Expressions.
///
@@ -36,6 +37,7 @@ pub enum SExp {
use SExp::*;
use SLeaf::*;
+
impl SExp {
pub fn is_value(&self) -> bool {
match self {
diff --git a/src/type/check.rs b/src/type/check.rs
new file mode 100644
index 0000000..3f3b864
--- /dev/null
+++ b/src/type/check.rs
@@ -0,0 +1,121 @@
+
+use crate::r#type::{Type, TypeError};
+use crate::sexp::SExp;
+use std::collections::HashMap;
+
+impl SExp {
+
+ /// Returns the type of valid expressions.
+ /// Invalid expressions result in an error.
+ ///
+ /// Examples of simple expressions and their simple types:
+ /// ```rust
+ /// use melisp::{
+ /// r#type::{*, Type::*, TypeError::*},
+ /// sexp::{SExp::*, SLeaf::*, util::*},
+ /// };
+ ///
+ /// assert_eq!(Atom(Int(1)).type_check(), Ok(Integer));
+ /// ```
+ ///
+ /// Quotes are given list types:
+ /// ```rust
+ /// use melisp::{
+ /// r#type::{*, Type::*, TypeError::*, util::*},
+ /// sexp::{SExp::*, SLeaf::*, util::*},
+ /// };
+ ///
+ /// assert_eq!(
+ /// scons(Quote, scons(1, scons(2, Nil))).type_check(),
+ /// Ok(List(vec![Integer, Integer]))
+ /// );
+ /// ```
+ /// Though so is Nil given too:
+ /// ```rust
+ /// use melisp::{
+ /// r#type::{*, Type::*, TypeError::*, util::*},
+ /// sexp::{SExp::*, SLeaf::*, util::*},
+ /// };
+ ///
+ /// assert_eq!(
+ /// Atom(Nil).type_check(),
+ /// Ok(List(vec![]))
+ /// );
+ /// ```
+ ///
+ /// Some common operators get arrow types:
+ /// ```rust
+ /// use melisp::{
+ /// r#type::{*, Type::*, TypeError::*, util::*},
+ /// sexp::{SExp::*, SLeaf::*, util::*},
+ /// };
+ ///
+ /// assert_eq!(Atom(Add).type_check(), Ok(arr(List(vec![Integer, Integer]), Integer)));
+ /// assert_eq!(Atom(Mul).type_check(), Ok(arr(List(vec![Integer, Integer]), Integer)));
+ /// assert_eq!(Atom(Sub).type_check(), Ok(arr(List(vec![Integer, Integer]), Integer)));
+ /// assert_eq!(Atom(Div).type_check(), Ok(arr(List(vec![Integer, Integer]), Integer)));
+ /// ```
+ ///
+ /// Though perhaps the most important task of the type system
+ /// is to increase safety by being able to warn about errors
+ /// before evaluation. Here are some failing examples:
+ /// ```rust
+ /// use melisp::{
+ /// r#type::{*, Type::*, TypeError::*, util::*},
+ /// sexp::{SExp::*, SLeaf::*, util::*},
+ /// };
+ ///
+ /// match scons(Mul, scons(1, Nil)).type_check() {
+ /// Err(InvalidArgList { .. }) => (),
+ /// _ => panic!(
+ /// "passing only 1 argument to '*' should result in InvalidArgList error"
+ /// ),
+ /// };
+ ///
+ /// match scons(Sub, scons(1, scons(2, scons(3, Nil)))).type_check() {
+ /// Err(InvalidArgList { .. }) => (),
+ /// _ => panic!(
+ /// "passing over 2 arguments to '-' should result in InvalidArgList error"
+ /// ),
+ /// };
+ ///
+ /// match scons(1, scons(2, Nil)).type_check() {
+ /// Err(InvalidOperator { .. }) => (),
+ /// _ => panic!(
+ /// "'1' as an operator should result in InvalidOperator error"
+ /// ),
+ /// };
+ ///
+ /// match scons(Add, scons(Sub, scons(1, Nil))).type_check() {
+ /// Err(InvalidArgList { .. }) => (),
+ /// _ => panic!(
+ /// "passing '-' as an argument to '+' should return in InvalidArgList error"
+ /// ),
+ /// };
+ /// ```
+ ///
+ /// Also, free variables should result in an error
+ /// as their type can't be known by the type checker.
+ /// ```rust
+ /// use melisp::{
+ /// r#type::{*, Type::*, TypeError::*, util::*},
+ /// sexp::{SExp::*, SLeaf::*, util::*},
+ /// };
+ ///
+ /// match scons(Quote, scons(var("a"), Nil)).type_check() {
+ /// Err(UndefinedVariable(a)) if &a == "a" => (),
+ /// _ => panic!(
+ /// "passing a free variable in type check should result in UndefinedVariable error"
+ /// ),
+ /// };
+ /// ```
+ pub fn type_check(&self) -> Result<Type, TypeError> {
+ self.type_check_ctx(HashMap::new())
+ }
+
+
+ fn type_check_ctx(&self, ctx: HashMap<String, Type>) -> Result<Type, TypeError> {
+ todo!();
+ }
+
+}
diff --git a/src/type/display.rs b/src/type/display.rs
new file mode 100644
index 0000000..781d614
--- /dev/null
+++ b/src/type/display.rs
@@ -0,0 +1,85 @@
+
+use std::fmt;
+use crate::r#type::{Type, TypeError, Type::*, TypeError::*};
+
+
+impl fmt::Display for Type {
+ /// Formats the type for display to the programmer
+ /// using this programming language.
+ ///
+ /// Examples:
+ /// ```rust
+ /// use melisp::r#type::{Type::*, util::*};
+ /// assert_eq!(Integer.to_string(), "Int".to_string());
+ /// assert_eq!(arr(Integer, Integer).to_string(), "Int -> Int".to_string());
+ /// assert_eq!(List(vec![Integer, Integer, Integer]).to_string(), "(Int Int Int)".to_string());
+ /// ```
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ match self {
+ Integer => write!(f, "{}", "Int"),
+ Arrow(a, b) => write!(f, "{} -> {}", a, b),
+ List(types) => write!(
+ f,
+ "({})",
+ types.into_iter()
+ .map(|t| t.to_string())
+ .collect::<Vec<String>>()
+ .join(" ")
+ ),
+ UndefinedType => write!(f, "?"),
+ }
+ }
+}
+
+
+impl fmt::Display for TypeError {
+ /// Formats this type error for display to humans.
+ ///
+ /// Examples:
+ /// ```rust
+ /// use melisp::r#type::{TypeError::*, Type::*, util::*};
+ /// use melisp::sexp::{SExp, SExp::*, SLeaf::*, util::*};
+ ///
+ /// assert_eq!(
+ /// UndefinedVariable(String::from("x")).to_string(),
+ /// "undefined variable: 'x'".to_string()
+ /// );
+ /// assert_eq!(
+ /// InvalidOperator {
+ /// operator: Atom(Int(1)),
+ /// expected: arr(UndefinedType, UndefinedType),
+ /// found: Integer
+ /// }.to_string(),
+ /// "invalid operator: '1'\nexpected: '? -> ?'\nfound: 'Int'".to_string()
+ /// );
+ /// assert_eq!(
+ /// InvalidArgList {
+ /// arglist: scons(1, scons(2, scons(3, Nil))),
+ /// expected: List(vec![Integer, Integer]),
+ /// found: List(vec![Integer, Integer, Integer]),
+ /// }.to_string(),
+ /// "invalid argument list: '(1 2 3)'\nexpected: '(Int Int)'\nfound: '(Int Int Int)'".to_string()
+ /// );
+ /// ```
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ match self {
+ UndefinedVariable(name) => write!(f, "undefined variable: '{}'", name),
+ InvalidOperator { operator, expected, found } => {
+ write!(
+ f,
+ "invalid operator: '{}'\nexpected: '{}'\nfound: '{}'",
+ operator, expected, found
+ )
+ },
+ InvalidArgList { arglist, expected, found } => {
+ write!(
+ f,
+ "invalid argument list: '{}'\nexpected: '{}'\nfound: '{}'",
+ arglist, expected, found
+ )
+ },
+ OtherError => write!(f, "uncategorized error"),
+ }
+ }
+}
+
diff --git a/src/type/mod.rs b/src/type/mod.rs
index 623edc9..12d1132 100644
--- a/src/type/mod.rs
+++ b/src/type/mod.rs
@@ -1,34 +1,43 @@
-use crate::sexp::{SExp, SExp::*};
+pub mod util;
+pub mod display;
+pub mod check;
+
+
+use crate::sexp::SExp;
+
+
+#[derive(Debug,PartialEq)]
pub enum Type {
+
Integer,
+
Arrow(Box<Type>, Box<Type>),
+
+ List(Vec<Type>),
+
+ UndefinedType, // only for errors
+
}
+
+#[derive(Debug,PartialEq)]
pub enum TypeError {
+
UndefinedVariable(String),
+
InvalidOperator {
operator: SExp,
expected: Type,
found: Type,
},
+
InvalidArgList {
arglist: SExp,
expected: Type,
found: Type,
},
- OtherError
-}
-impl SExp {
- /// ```rust
- /// use melisp::{
- /// r#type::{*, Type::*, TypeError::*},
- /// sexp::{SExp::*, SLeaf::*, util::*},
- /// };
- /// ```
- pub fn type_check(&self) -> Result<Type, TypeError> {
- todo!()
- }
+ OtherError
}
diff --git a/src/type/util.rs b/src/type/util.rs
new file mode 100644
index 0000000..27fc661
--- /dev/null
+++ b/src/type/util.rs
@@ -0,0 +1,7 @@
+
+use crate::r#type::{*, Type::*};
+
+pub fn arr(a: impl Into<Box<Type>>, b: impl Into<Box<Type>>) -> Type {
+ Arrow(a.into(), b.into())
+}
+
generated by cgit v1.2.3 (git 2.25.1) at 2025-08-25 10:27:01 +0000