从零写一个lambda演算解释器

2009 年 3 月 3 日

2020年夏天带着实习生搞了一个实验性的语言 HiLang：

这个语言是运行在 railgun 虚拟机上的，所以它是强类型的动态语言。因为有编译到字节码的过程，所以我希望为 HiLang 加上静态类型，就如 TypeScript 所做的那样。

由于参与这个项目的同学大多数都是编译器背景的，而不是编程语言背景的，对于在语法文件里直接添加类型感到很棘手。我突然想起来王垠曾经写过一篇解释器的文章：

所以就想不如自己实现一个小的解释器，可以实现simply typed lambda calculus。通过这个系统，可以检验简单的类型推导算法。到刚刚为止，刚好完成了无类型的 lambda 演算。

由于我不喜欢安装各种环境，所以就没有照着王垠的racket的解释器去写，而是采用cpp重写了所有的逻辑，同时把前缀表达式也转成了中缀表达式。

来看一个例子，引自main.cpp

eval("fac = $f=>$n=>1 if n == 1 else n*f(n-1);"
         "U = $u=>u(u);"
         "Y = $f=>U($x=>f($v=>x(x)(v)));" 
         "print(Y(fac)(5));");

显然，这是一个Y combinator。

这个解释器也和普通的编译器一样，有词法分析器(lexer)，文法分析器(parser)，然后就直接在抽象语法树上做解释执行了。结构非常简单。为了避免采用bison, yacc等工具，这些部分全部手写了。而且，为了做到直观，也没有采用表格制导的词法/文法分析。

Lexical Scoping

王垠的文章里提到了Lexical Scoping和Dynamic Scoping的区别，我这里采用了和他一样的lexical scoping。从直观上说，对于语句

add = $x => $y => x + y;

显然的是lambda表达式的定义在前，而赋值给变量“add”在后，这就是说，采用lexical scoping，在定义lambda表达式的时候，变量 add 还没有定义，所以，这种写法在我们的解释器里是不成立的：

fact = $n=> 1 if n == 1 else n * fact(n-1);

因为在定义 lambda 表达式的时候，fact是没有定义的，这就会出错了。至此，在函数里不能通过名称调用自己这个结论就变得非常直接了。

解决的方法也比较简单：

Y Combinator

关于 Y 组合子，知乎上有很多答案了，其中这篇回答写得是比较直观的：

更容易理解一些。

我们这个解释器提供了 if / else 的三元表达式，而U组合子和Y组合子天然就存在于lambda演算中。感觉已经可以做很多计算了。

未来的计划

主要就是为这套系统增加类型。这一部分工作大家如果有兴趣，可以fork到本地，然后将这个工程当做实验田，随便做各种类型系统相关的实验。

另外，词法错误，文法错误，运行时错误，虚拟机的运态类型，以及内存的统一管理和统一释放都还没做（不写delete的CPP，就问你怕不怕），这一部分由于已经写过很多遍了，懒得写了，如果大家有兴趣，可以帮助补充一下。欢迎提交PR。

谢谢大家。

懒散，不想无聊