1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
use crate::r#type::{Type, TypeError, Type::*, TypeError::*, util::*};
use crate::sexp::{SExp, SExp::*, SLeaf::*};
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::*},
/// };
///
/// let err = scons(Mul, scons(1, Nil)).type_check();
/// match err {
/// Err(InvalidArgList { .. }) => (),
/// _ => panic!(
/// "passing only 1 argument to '*' should result in InvalidArgList error, found '{:?}'",
/// err
/// ),
/// };
///
/// 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.infer_type(HashMap::new())
}
fn infer_type(&self, ctx: HashMap<String, Type>) -> Result<Type, TypeError> {
match self {
Atom(Int(_)) => Ok(Integer),
Atom(Var(name)) => ctx.get(name)
.ok_or(UndefinedVariable(name.to_string()))
.cloned(),
Atom(Add) => Ok(arr(List(vec![Integer, Integer]), Integer)), // TODO varlen
Atom(Mul) => Ok(arr(List(vec![Integer, Integer]), Integer)), // TODO varlen
Atom(Sub) => Ok(arr(List(vec![Integer, Integer]), Integer)),
Atom(Div) => Ok(arr(List(vec![Integer, Integer]), Integer)),
Atom(Nil) => Ok(List(vec![])),
Atom(Quote) => Ok(List(vec![])), // TODO make it all identity functions
SCons(op, l) if **op == Atom(Quote) => (*l).infer_list_type(ctx),
SCons(op, l) => {
let opertype = (*op).infer_type(ctx.clone())?;
let argstype = (*l).infer_list_type(ctx)?;
match (opertype, argstype) {
(Arrow(a, b), c) => {
if *a != c {
Err(InvalidArgList {
arglist: (**l).clone(),
expected: *a,
found: c,
})
} else {
Ok(*b)
}
},
(t, _) => Err(InvalidOperator {
operator: *op.clone(),
expected: arr(UndefinedType, UndefinedType),
found: t,
}),
}
},
}
}
fn infer_list_type(&self, ctx: HashMap<String, Type>) -> Result<Type, TypeError> {
let mut res = vec![];
for exp in self.clone().parts() {
res.push(exp.infer_type(ctx.clone())?);
}
Ok(List(res))
}
}
|
