在看了TAPL之后，就一直想写一个带类型系统的函数式语言的解释器，花了几天写了一个出来，并且使用天下第一的Rust语言然后clone满天飞了，下面来说说语言的设计和实现过程。
设计
我们的语法希望和简单类型Lambda演算一样，通过Lambda表达式来构造函数，通过函数调用来进行计算。除此之外，我们也希望加上一些拓展，包括元组、union、列表和不动点算子（这个很破坏类型系统，但还是要加一个）。为了方便，元组和union都是匿名的，不支持自定义类型。我们也希望有两个基本类型：Int，Bool。
在此基础上我们需要有一些运算符，包括算术、比较、逻辑。
元组的表达式设计为(xxx,xxx)，无元素元组为()，单元素元组则为(xxx,)。元组索引则类似Rust，使用x.0。
union因为是匿名的，所以没有啥好的设计可以参考，为了保证类型推导可以完成，我设计为(Int | Bool true)的形式，里面恰好有一项是有值的。解开union则需要用case表达式，设计的形式是case u of (Int a => ... | Bool b => ...)。
列表这里，我本来想有下标运算，但是这就和列表的构造冲突了，无法解析，之后是想着引入nil head tail三个“函数”（其实是运算符），但感觉这样太过奇怪，最后设计为给列表一个固定的模式匹配，也就是match l of ([] => ... | x::xs => ...)。
然后语句，语句有两种：let绑定（类型标注可选）、匿名表达式。
在实现简单类型系统之后，我又把它升级成了HM类型系统，支持自动类型推导。效果还是很满意的。
词法和语法分析
编译原理传统来了。手写词法分析器没啥好说的，Token的类型我感觉设计的还是有些问题。我利用了Rust的迭代器模式，将词法分析器的Token流做成一个迭代器，从而方便了语法分析器可以利用迭代器的peekable进行缓存。还有就是Rust没有peeking_take_while，调了下库。
手写语法分析器就比较麻烦了，我是手写自顶向下LL(1)分析器，通过将类型和表达式划分为不同的层级来避免左递归。 这时候出现了优先级的问题，我改动了好几次最后确定了现在的优先级顺序，将表达式划分为atom_expr、suffix_expr term_expr expr四个层次，分别解析：括号等无需优先级的表达式、后缀运算（元组索引）、前缀一元运算和函数调用、二元运算。
这里就感觉到Rust的错误处理，包括问号运算符，是真的好用。
为了方便输出表达式，我给Type Expr实现了Display trait，但是涉及到优先级加括号的部分感觉处理的很乱。
还有就是交互处理，为了有一个较好的效果（记录历史、左右移动光标）我使用了linefeed库。
类型检查和求值
首先是简单类型系统的检查，自底向上地完成检查。由于要解析标识符，所以需要引入上下文，包括全局上下文（let语句绑定）和局部上下文（lambda表达式引入）。然后就是自底向上地进行检查，这里又涉及到所有权的问题，我的做法是类型检查不保留中间结果，所以总是将推断出的类型的所有权传递到上层，遇到需要clone的地方显式地clone。
HM类型系统的检查在此基础上，引入了类型变量、代换、合一。我们引入了类型上下文和类型变量。类型变量包括两种，一种是自由的，一种是被代换成了关于其他变量的表达式。我们首先遍历表达式，找出所有的自由变量；然后进行自底向上的类型检查，遇到有类型约束的时候进行合一，合一失败即代表类型检查错误。还有一种情况，就是x.0一类的表达式，如果完全不知道x的类型，那么我们其实也是无法推导的，因为我们无法表达“长度大于等于1的元组类型”。
这里出了不少bug，比如合一的时候，自由变量和受限变量是完全不同的处理方法；比如在什么时机应该将受限变量消去。这方面代码也是完全clone满天飞了。
此外，为了方便显示，我会在类型推导完成后，重命名所有的自由变量，变成希腊字母（如果数量足够少的话）的形式。
求值和类型检查则很不一样，完全不需要考虑类型（即类型擦除），求值时和无类型的演算并无区别。为了保证递归可用，我们必须是惰性求值，也就是lambda和fix都不做化简，除非它被作为函数调用了。
这里就体现出fix对类型系统的破坏作用了，利用fix我们可以轻易构造出无法计算的任意类型的值，所以会出现无法求值的情况（例如(fix \x:Int x)+3，需要手动报错。
最后结果
最后的效果还是比较满意的。例如，我们可以推导map的类型：
1 | > let map = fix \map \f \l match l of ([] => [] | x::xs => (f x)::(map f xs)); |
我们可以利用fix构造阶乘函数fact，并将其用到map上去：
1 | > let fact = fix \f \x if x==0 then 1 else f(x-1)*x; |