说点题外话
第一次看到λ演算的时候，脑子里只有一个词来形容它：美感。
（相对来说，需要读写头和纸带的图灵机，可能只算得上一个能work的方案。）
类似的感觉只在看到Lambert的Paxos以及中本聪的区块链的时候出现过。
为了表示对作者的敬仰之情，我特地把之前做的项目起名为“丘奇”，也算是能力之内的一种致敬吧。
λ演算和程序语言的渊源，要从麦卡锡和他的Lisp说起，当然如果这么别下去，大概就没完没了了，在这里我想表达的是，自从那一颗小小的种子种下起，就一直期待着，能实现一个基于Lambda演算的解释器，或者说一个Lisp的解释器。借此去理解一下，计算或者说编程的本质到底是什么。
从麦卡锡开始，到格雷尔姆，到弗里德曼，到王垠，实际上我看过好多个版本的Lisp解释器的实现，但一直似懂非懂，而直到Norvig大叔的版本，借着一点点残留的Python基础，我大概懂了Lisp的精髓。
这一篇不会实现完整的Lisp，但会包含其中最关键的部分，也就是关于函数调用的实现。
从一个计算器开始
所以，她和大学时代你用C写的那个计算器有什么区别？
从本质上来说其实并没有。
回忆一下，你从stdin读进来3 + 4，然后解析出+、3、4这几个元素，接着 把加法作用于3和4的值 。
为了方便，我们可以让输入的格式是形如：(* (+ 1 2) (+ 3 4))的样子，所以你依然把输入解析为*、(+ 1 2)、(+ 3 4)，然后继续用刚才的方式 把乘法作用于(+ 1 2)和(+ 3 4)的值 。
让我们简单抽象一下，输入的表达式（Expression）可以分为几个部分：
(operator expression1 expression2)
（这里的第一个参数operator，实际上也可以是expression）
因此，她的内核，实际上就只有一行代码：
eval(expression) = apply(operator,
eval(expression1),
eval(expression2)
)
表达式expression的求值结果，等于把算子作用于子表达式1和子表达式2的值。
我相信我能体会到约翰麦卡锡在60年前，第一次看到她时候的震撼。
表达式
前面讲到，她是基于表达式求值的，也就是说每一行源代码都会有一个求值结果。
作为一个递归函数，肯定会有一个终止条件，求值的终止条件，在于某个子表达式是原子类型。
所以我们把表达式，细分成了原子表达式和复合表达式。
复合表达式如：(+ 1 2)或者如一个变量定义(define pi 3.14)。它的求值逻辑在前面已经讲过了。
原子表达式如：数字1，求值结果依然是数字1，字符串foo，求值结果依然是字符串foo。
上下文
刚才介绍原子表达式的时候，我们忽略了一种情况，如果是变量，比如pi，应该怎么办？
实际上我们应该尝试去获取变量的定义，也就是尝试从上下文（或者说环境变量）中取值。
那么上下文又是什么？
实际上你可以把它简单的理解成一个Map
（在没有函数调用的情况下，这样的解释总是说的通）。
每当对define相关的表达式进行求值时，比如(define pi 3.14)，实际上，就是把这一个键值对设置进上下文中。
（还记得我们的apply函数吗？这就是define关键字apply的结果，也可以说是define的语义。）
因此，当尝试对于pi进行求值时，实际上是去Map里根据key去查value。
Lambda！
终于轮到函数登场了。
我们知道在JVM里，一次函数调用，意味着栈帧的一次压栈和出栈。而在我们的解释器里，不需要栈的概念。
让我们来手动模拟一下解释器的行为。现在你是一个刚初始化的解释器，你有一个环境变量，里面什么都没有。
这时候，用户输入了(define pi 3.14)，此时，环境变量变成了{pi : 3.14}。
接下来用户输入(* pi 2)，此时你从环境中寻找pi的值，判断其为一个数值类型后，执行相应的数值计算（这里假设你已经知道如何处理乘法）
先看一下函数的定义：
(define circle-area
(lambda (r) (* pi (* r r))))
此时环境变成了：{pi : 3.14 ; circle-area : LAMBDA(…)}
其中LAMBDA(…)代表一个过程，其中又包含以下信息：
函数参数：r
函数体：(* pi (* r r))
本地环境：{pi : 3.14}
这里姑且把本地环境称为local env。
同时它引用了上层环境（global env）的值。
可以简单的理解为做了一次**深拷贝**。
接下来，当用户输入(circle-area 2)，你会从当前环境中寻找circle-area的值，当看到LAMBDA字样后，判断其为一个过程后，执行过程调用。
过程调用的步骤如下：
-
把函数调用的实参和形参绑定，在这里也就是把这一个键值对压入本地环境，此时
local env = {r : 2 ; pi : 3.14}，假设在global env中存在r的定义，则这里会刷掉重新用实参来赋值。 -
计算函数体，当遇到变量时，在local env中查找，如果找得到，则进行相应的运算，如果找不到则报错。在这个例子里，会把函数体
(* pi (* r r))替换为(* 3.14 (* 2 2))，是不是又回到了最简单的场景？
再来一个稍微复杂点的场景。
我们把时间倒退到最开始的时候，假设用户输入的是计算阶乘函数：
(define fact
(lambda (n)
(if (<= n 1) 1 (* n (fact (- n 1))))))
此时global env变为：{fact : LAMBDA(…)}
其中LAMBDA(…)又包含以下信息：
函数参数：n
函数体：(if (<= n 1) 1 (* n (fact (- n 1))))
local env：{fact : LAMBDA(…)}
此时用户输入(fact 3)，你判断fact的值为过程，首先绑定参数：
local env1 = {n : 3 ; fact : LAMBDA(…)}
再尝试执行函数体：(* 3 (fact 2))
此时，发现fact仍然为一个过程，再次执行过程调用，其中：
local env2 = {n : 2 ; local env1的深拷贝}，注意这里的n被覆盖为2而不是3。
再次尝试对函数体(* 3 (* 2 (fact 1)))
执行过程中发现fact仍然为一个过程，再次执行过程调用。终于，函数体被展开成了(* 3 (* 2 1))，一切又回到了最原始的场景。
所以，看到这里，希望你能“啊哈”一下，这种不停的进行字符串替换的把戏，竟然可以实现计算！
我们没有依赖栈这种结构，仅靠递归，也完成了函数调用。
顺便也能理解一个Lisp圈的老梗，只要给它足够的时间，Lisp表达式总能得到结果。
闭包！
如果稍微联想一下，其实可以很容易的发现，实际上，刚才的LAMBDA(…)就是很多语言中闭包的概念。
所谓的闭包，除了函数定义的部分，还带上了上下文，简单说就是那个local env。
如果在这里，再次听到一声“啊哈”，那这篇文章就没有白写～
网友评论