Added tests for type_check. Implemented std::fmt::Display for many enums. Added type variants List(Type), and UndefinedType for use in error messages. Implemented type utility arr(a, b).

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())
+}
+