mal 是 GitHub 上的一个开源项目，这是关于它的简单的介绍:使用75种语言编写一个 Lisp 解释器。
这是 mal 语言的语法简介和由 JS 实现的一个在线 repl。
在这篇文章中，我们会依托 mal 提供的步骤说明，讲讲如何实现一个简单的 Lisp 解释器。在步骤说明中介绍的内容，我们不会过多重复。
简单了解解释器
解释器是将一种编程语言的代码逐句解释执行的软件。要实现解释器的功能，至少要实现以下的功能：
输入
读取输入字符串：程序代码是以字符串的形式输入的。
预处理
- 词法解析：把字符串转化为 token，类似于自然语言中的分词、断句。例如把
(+ 1 2)转化为(，+，1，2和)。 - 语法解析：把 token 的序列转化为解释器内部能够理解的数据结构，即抽象语法树（AST）。例如，把由
( def a ( - (+ 1 2 ) 3 ) )组成的序列转化为：
// 示意：
( def a
( -
(+ 1 2 )
3 ))
当然，上面的形式只是个示意，假如实现解释器的语言是 Java，数据结构可能会是一个嵌套的数组，每层数组可能会表示一个运算（例如 def, - 或者 +）。
解释执行
解释器的核心，将抽象语法树解释为目标语言（在本项目里就是你用来实现解释器的语言）的程序，并执行。
输出
将程序运行的结果（可能是字符串、数值或者其他的数据形式）转化为字符串的形式输出。
相比其它语言的解释器，Lisp 解释器的优势是词法解析和语法解析的过程非常简单，因为一个 Lisp 程序本身几乎就是一个抽象语法树了，而像 Java、Swift 之类语法更复杂的语言，词法解析和语法解析的过程会复杂的多。这样，从学习的角度出发，实现一个 Lisp 解释器可以更专注于解释器的核心功能上。
第0步：搭建框架
建立 READ, EVAL, PRINT 三个主要模块，以及把他们连起来的 rep()。
只是搭建一个骨架而已，编码毫无难度。
问题有可能出现在命令行操作和写 Makefile 上，好在用到的也都是基本操作，可以简单看一下教学，如果你用的语言已经由别人实现过，也可以借用别人写好的 Makefile。
参考资料：
The Linux Command Line (英文版)
The Linux Command Line (中文版)
跟我一起写 Makefile
Make 命令教程
第1步：读取和打印
前面讲了解释器的四项工作：输入、预处理、解释执行、输出。这一步完成输入、预处理、和输出部分，其中预处理部分包含在输入中。
tokenizer() 函数负责词法分析。
read_form() 函数负责语法分析。
可能遇到的问题：正则表达式。这个我没有网上资源推荐给你，你可以自己找一下；我使用的是实体书《精通正则表达式》。注意：正则表达式有不同流派，项目 guide 中使用的是 PCRE 。
注意：
项目中的任务有的被标识为 optional 或者 deferable。
跳过 optional（可选的）任务不会影响后续任务，但有可能导致单元测试中出现错误。
跳过 deferable （可推迟）的任务可能会导致后面的步骤执行不畅，而且将来返工可能会更麻烦一点，所以建议尽最大努力完成，如果确定要跳过，也请尽早回头补上。
这一步中的 deferable 任务可能显得难一点，如果你要跳过，至少看一眼这项任务都是什么，心理先有个数。
第2步：求值
Lisp 程序需要递归地执行两个相互调用的步骤：求值 eval 和应用 apply。解释器对一个列表（List）求值，首先要对这个列表的每个元素求值，然后将操作符（第一个元素）应用到被操作数（其它元素）上。
例如，对于列表 (+ a ( + 1 2 ))求值：
- 需要先分别求值
+，a，( + 1 2 )，然后将+的值应用到a和( + 1 2 )的值上。 -
+的求值结果为 "将操作数加到一起的操作"；a如果有定义，它的求值结果就是变量 a 绑定的值；而( + 1 2 )并不能直接得到，需要将求值应用循环对( + 1 2 )执行一次。 - 求值：分别求出
+，1，2的值，+的值已经知道了，1，2作为整数是自求值对象，对它们求值的结果是它们本身。这样，所有的值都得到了。 - 应用：将
+应用到1，2上，得到 3。 - 回到外层的 List ，假设 a 的值为 5。那么 将
+应用到5，3上，得到 8。 - 8 就是这个 List 求值的结果。
在 mal 项目中，基本上 EVAL() 函数负责的是应用的部分，eval_ast()函数负责的是求值的部分。
第3步：环境
在上一步的例子中，有个未解决的问题。解释器是怎么知道变量a的值？更进一步，解释器是怎么知道 + 代表求和的运算的？
在上一步中定义的 repl_env 就相当于一个全局的环境 Environment。解释器如果想知道任何变量（包括函数名）的值，都可以在 repl_env 中查找。但在大多数真实存在的编程语言中，并不是所有的变量都是全局变量，变量是有自己的作用域的。例如：
function foo() {
var x = 1
{
var y = 0
print(x)
}
print(y)
}
上面的实例语言和很多真实的语言一样，使用大括号作为作用域的开始和结束。
对于大多数语言，print(x)会打印 1，因为第一个 print()在自己的作用域中找不到 x 的值，它会继续逐级向上层寻找，在上一层找到 x = 1 ；而print(y) 很可能会报错，因为它找不到 y 的定义。
在 mal 中 let* 会生成新的环境，而 def! 会修改当前的环境。除了全局环境外，每个环境都有它的外层环境。大多数其他语言的工作原理也是类似的，只不过它们实现环境的方法一般会高效的多。
第4步：函数定义和控制流
之前实现的求值和环境组成了一个解释器最核心的部分，而有了这一步实现函数定义和控制流功能后，mal 看起来已经像一个能用的真正的编程语言了。
如何实现定义函数闭包略微有一点烧脑：
以当前环境为外层环境，创建一个新的环境。在新的环境中，函数的每个形参作为键，调用函数使用的实参作为值。将函数体在这个新的环境中求得的值作为返回值。
而上面说的的这一切不是即刻执行的，而是定义在一个闭包之中，直到对这个闭包求值时才会执行。
通过一个简单的例子想一下：
function bar (left, right) {
return left * right + left
}
上面定义了一个将两个数相乘再加上第一个数的函数，并给这个函数起名字叫 bar，相当于 mal 中的 :
(def! (fn (left right)
(函数体...) )
bar)
定义一个函数会保存两个信息：参数列表(left, right) 和函数体 { return left * right + left }。除了这些数据，还要告诉函数的执行者使用函数时怎么继续操作：
- 在函数体中，把所有形参
(left, right)替换为实参，例如当执行bar (3, 5)时，就是把函数体变成{ return 3 * 5 + 3 }。 - 对替换后的函数体求值就得到了想要的值。
第5步：尾调用优化
递归和迭代是程序设计领域中两个重要的概念。一般来说递归程序更容易设计，但由于大量的递归调用会消耗更多的栈空间，所以在执行时时间和空间效率往往低于程序的迭代版本，而且有可能导致栈溢出。
尾调用优化（尾递归优化）可以将符合特定条件的递归过程转化为迭代过程，这样可以提高程序的性能。
尾调用优化的条件是，外层函数执行的最后一步是调用内层函数，符合这种条件时，解释器可以自动执行尾调用优化。
例子（来源：阮一峰的博客）：
写一个求阶乘的函数
function factorial (n) {
if (n == 1) return 1;
return n * factorial(n - 1);
}
factorial(5) // 120
上面的函数是一个递归函数，但不是尾递归，因为它的最后一步不是调用factorial(n - 1)，而是一个乘法。
把它改写成尾递归的形式：
function factorial(n, total) {
if (n === 1) return total;
return factorial(n - 1, n * total);
}
factorial(5, 1) // 120
这样它就变成了一个可以优化的尾递归函数了。
总结一下，这个求递归函数的核心就是反复地使用 n 和部分积相乘，在第一个例子中是 n * factorial(n - 1)，在第二个例子中是 n * total 。程序的其他部分都是用于保证相乘能正确地继续执行和恰当地停止。
按着这个思路，手动把尾递归变成迭代过程：
function factorial(n, total) {
while ( n > 1 ) {
total = n * total
n = n - 1
}
return total;
}
factorial(5, 1) // 120
把函数的核心部分用一个 while 循环包裹起来，在合适的时候结束迭代。mal 解释器实现的尾调用优化，大致也是这个原理。
待续。
网友评论