基于文本替换的解释器：小结

基于文本替换的解释器：小结2015-01-12（ ewcommand{mt}[1]{ ext{#1}}）

关于语法

我们现在用的这种充满括号和前缀表达式的语法叫做“S表达式”。 S表达式看似奇怪，其实是一种简约风格的语法。 S表达式的表达式一般是这么设计的：首先第一个词表示这个表达式的类别（如if表达式还是let表达式），然后后面依次列出这个表达式的所有元素，最后用一对括号把整个表达式括起来。比如if表达式有三个元素条件表达式和两个分支表达式，所以if表达式是$（mt{if} ; L ; M ; N）$；加法则是一个加号后面跟上要相加的表达式：$（+ ; M ; N）$。

与其说S表达式语法简单，不如说S表达式几乎没有语法。 S表达式的代码已经是一棵抽象语法树。它的一个很明显的好处是解释器几乎不用做语法分析。关于语法分析，编译原理课程已是阐之未尽，我也没什么可说的。我想说的都是一些语义方面的内容，所以我希望尽量避免语法分析。减掉一些东西意味着减少许多麻烦（位移归约冲突够玩一阵子了）。语法分析有时候会出现一些意想不到的bug。比如《UNIX痛恨者手册》里有个例子，假设p是C语言的一个指向浮点数的指针。现在要计算*p的倒数，于是有这么一小段代码：

1 1/*p

嗯？

S表达式一直被诟病括号多。其实许多人（这些人应该都没学过Lisp）不喜欢S表达式的原因不在于括号多，而是因为S表达式与C语言（或者JAVA、Python）“不够像”。

See you later, alligator

为了引用方便，应该给我们正在实现的这门语言起个名字，就叫Alligator吧。

Alligator的语法： egin{equation*}egin{array}{lcl} M, N, L &=& X \ &|& b \ &|& lambda X.M \ &|& （mt{fix} ; X_1 ; X_2 ; M） \ &|& （+ ; M ; N） \ &|& （- ; M ; N） \ &|& （mt{iszero} ; M） \ &|& （M ; N） \ end{array}end{equation*}

值： egin{equation*}egin{array}{lcl} V &=& X \ &|& b \ &|& lambda X.M end{array}end{equation*}

宏： egin{equation*}egin{array}{lcl} （mt{if} ; L ; M ; N） &=& （（（L ; lambda X.M） ; lambda X.N） ; 0） \ && ext{其中}X otin FV（M）, X otin FV（N） \ （mt{let} ; X ; N ; M） &=& （lambda X.M ; N） \ （mt{letrec} ; X_1 ; X_2 ; N ; M） &=& （lambda X_1.M ; （mt{fix} ; X_1 ; X_2 ; N）） end{array}end{equation*}

Alligator采用call-by-value的调用方式，它的求值过程如下（continuation passing）： egin{equation*}egin{array}{lcl} left<X, kappa ight>_v & ightarrow_v& left<X, kappa ight>_c \ left<b, kappa ight>_v & ightarrow_v& left<b, kappa ight>_c \ left<lambda X.M, kappa ight>_v & ightarrow_v& left<lambda X.M, kappa ight>_c \ left<（mt{fix} ; X_1 ; X_2 ; M）, kappa ight>_v & ightarrow_v& left<lambda X_2.M[X_1 leftarrow （mt{fix} ; X_1 ; X_2 ; M）], kappa ight>_c \ left<（o^n ; M_1 ; M_2 ; ... ; M_n）, kappa ight>_v & ightarrow_v& left<M_1, left<mt{opd}, kappa, o^n, （M_2 ; ... ; M_n）, （） ight> ight>_v \ left<V, left<mt{opd}, kappa, o^n, （M_{i+1} ; ... ; M_n）, （V_1 ; ... ; V_{i-1}） ight> ight>_c & ightarrow_c& left<M_{i+1}, left<mt{opd}, kappa, o^n, （... ; M_n）, （V_1 ; ... ; V_{i-1} V） ight> ight>_v \ left<V, left<mt{opd}, kappa, o^n, （）, （V_1 ; ... ; V_{n-1}） ight> ight>_c & ightarrow_c& left<V", kappa ight>_c \ && ext{其中} V" = o^n（V_1, ..., V_{n-1}, V） \ left<（M ; N）, kappa ight>_v & ightarrow_v& left<M, left<mt{arg}, kappa, N ight> ight>_v \ left<V, left<mt{arg}, kappa, N ight> ight>_c & ightarrow_c& left<N, left<mt{fun}, kappa, V ight> ight>_v \ left<V, left<mt{fun}, kappa, lambda X.L ight> ight>_c & ightarrow_c& left<L[X leftarrow V], kappa ight>_v end{array}end{equation*}

===我是穿越的分割线================================================

由于写解释器太欢乐了，所以我不知不觉就把Alligator写到这个系列大约三分之二的进度。下面链接是Alligator解释器的代码：

https://github.com/sKabYY/Alligator

这个Alligator包含多参数函数、互递归、赋值、垃圾回收、letcc与cc、异常处理等新功能。

testcases.rkt是测试用的例子。运行alligator.rkt文件会测试testcases.rkt里的例子。

1 racket alligator.rkt

alligator-cps.rkt对Alligator做了CPS变换和一些简单的CPS代码优化。一个很有意思的地方是做完CPS变换后，一些语句如异常处理就消失了。CPS代码优化写得比较乱，做了beta展开、eta归约和常数折叠三个优化。是处于试验阶段的代码，都是拍脑袋就写的，估计bug比较多。运行alligator-cps.rkt文件会测试testcases.rkt里的例子。

1 racket alligator-cps.rkt

输出比较多，可能需要重定向到文件再看。

长路漫漫

本来只想打发郁闷的时间而随便写写。现在发现写文章不仅能改善心情，对加深理解也有好处。我把后面想写的内容列下了，以激励自己。

1.基于文本替换的解释器。

2.环境。引入环境，CEK，作用域（静态，动态），SECD，无名变量，加入多参数。

3.状态。显式引用，隐式引用，垃圾回收，按需传值，按引用传值。

4.Continuation。letcc与cc，异常处理，多线程。

5.CPS变换，CPS代码优化？

6.类型系统……（待定）

7.面向对象……（待定）

程序语言这领域我才刚跨过半条腿，如有谬误，欢迎斧正。