( 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/*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里的例子。
racket alligator.rkt
alligator-cps.rkt对Alligator做了CPS变换和一些简单的CPS代码优化。一个很有意思的地方是做完CPS变换后，一些语句如异常处理就消失了。CPS代码优化写得比较乱，做了beta展开、eta归约和常数折叠三个优化。是处于试验阶段的代码，都是拍脑袋就写的，估计bug比较多。运行alligator-cps.rkt文件会测试testcases.rkt里的例子。
racket alligator-cps.rkt
输出比较多，可能需要重定向到文件再看。
长路漫漫
本来只想打发郁闷的时间而随便写写。现在发现写文章不仅能改善心情，对加深理解也有好处。我把后面想写的内容列下了，以激励自己。
- 基于文本替换的解释器。
- 环境。引入环境，CEK，作用域（静态，动态），SECD，无名变量，加入多参数。
- 状态。显式引用，隐式引用，垃圾回收，按需传值，按引用传值。
- Continuation。letcc与cc，异常处理，多线程。
- CPS变换，CPS代码优化？
- 类型系统……（待定）
- 面向对象……（待定）
程序语言这领域我才刚跨过半条腿，如有谬误，欢迎斧正。