编程语言杂谈

前段时间在公司以《在Go语言中引入lambda》表达式为题目，进行了一次技术分享，效果差强人意（无奈脸）。可能有人一听lambda，还要在Go里引入，第一反应就是厌恶，心想，这帮邪教又想搞什么事情祸害我简洁的Go语言，企图通过新增各种鸡肋特性把Go拉入C++的深渊。因此，这些人肯定是对我嗤之以鼻的，更不用说花宝贵的时间来听相关分享了。来听的大部分同学都是吃瓜群众，好多甚至从来都不曾接触过编译原理。实际上我在准备PPT的时候也在想，在短短的一小时，到底要分享哪些内容，才能让大家都不虚此行呢，毕竟编译原理是太复杂高深的领域。事实上，这确实很难。
很多编程开发者可能都疑惑过，自己平时使用的语言到底是怎么发明的。Go一开始是用C写的，C又是用啥写的？好像又没听说过用啥写的，隐约记得跟汇编有关系，难道是用汇编写的？那汇编又是啥写的，写汇编的又是啥写的？感觉无限循环了，就像先有鸡还是先有蛋的问题…
很久之前，我也思考过这样的问题，觉得好高深莫测，于是望而却步。编译原理入门的曲线比较陡，一开始各种各样的概念会让你头晕眼花，于是很多人去网上求助如何学习编译原理。不幸的是，网上很多人为了装X不说实话，或者他们其实也不懂，完全就是误人子弟。随便一搜你能发现，无数的答案给初学者推荐“龙书”（编译原理领域的权威）。不否认它是一部巨著，但是给初学者看这个书完全就是抹杀他们的兴趣。很多人忘了，他们学习数学也不是一开始就学微积分，也是从小学一年级课本从1+1开始学的。所以我建议，学习编译原理千万不要一开始就去读这些大部头，读这些书唯一的作用就是让你知难而退。
言归正传，本文是对之前分享的一个总结和补充，希望用最简洁的文字，让大家都认识这个领域，都有兴趣去“把玩”相关技术。
学习编译原理的第一件事情，是想清楚编译技术到底是为了解决什么问题。只有想清楚了这个问题，你才能够把握住它的主干脉络。编译原理的英文叫Programming Language Theory，简写为PLT。很容易看出，其实它就是和编程语言强相关的一门技术。它并不解决现实世界问题，而是解决编程语言的问题。那么编程语言有什么问题呢？

表达力

表达力是编程语言面临的第一个问题。那什么是表达力呢？大家都听说过计算机刚被发明的时候，计算机读取纸袋，根据一行的某些位置有孔还是无孔，决定接下来执行什么指令。假设一行有8个“槽”，那么计算机能识别的指令一共不超过2^8=256个。比如01010100代表执行一个加法，00011000代表执行一个减法…。可以想象，最终你的代码将会变成这样：

01010101
11101000
10101010
10000111
# ...

如果代码是这样的，我敢保证你很快就不知道自己在写什么了，这里面不止有指令，还有参与计算的数。显而易见，在纸带上写0101来编程没有任何表达力，它没有任何抽象能力，也几乎没有任何人能看懂它。正如我们看书做笔记一样，一种显而易见的帮助你理解二进制代码的方法也是做笔记，比如：

01010101  #ADD
11101000  #232
10101010  #170
10000111  #...

这样便容易理解多了，因此你可以现在纸上写好代码，确认好逻辑再开始给纸袋打洞，剩下打洞的过程就是机械的重复了。
诶！！等等，既然我们的注释和代码实际是一一对应的，那么我们能不能编写一个程序，让它来完成这个简单的翻译呢？之后我们输入ADD这样的符号，用一个软件把它翻译成对应的机器指令。这便是最早的汇编器。它其实一点也不复杂，因为CPU厂商已经规定好了，01010101代表做加法，那么每次遇到ADD就把它替换成01010101。用现在的话来说，汇编器其实就是一个字符串到二进制串的转换函数。相信稍微有点编程基础的同学都能用高级语言实现出来。有了汇编器之后，代码焕然一新：

ADD 0 1
DEC 5 8
JMP 10

比起之前的01串，现在的代码好懂多了。虽然用现在的高级语言实现汇编器非常简单，但如果限制只能使用机器码来开发这个程序，那将变得很困难。但是，它并不是一个不可完成的任务，只要多花些时间，依然是能够开发出来的（在开发第一个汇编器之前，实际上可以先在纸上写汇编代码，在纸上完成编程，然后通过人脑进行汇编到机器码的转换，最终输入到计算机里）。总之，通过一系列努力，我们终于不用再写机器码了。你可以看到，这便是表达力的提升。

代码复用

有了汇编之后大家的工作效率比以前提高了不少，但是问题也随之而来。比如在一个游戏程序中，我们经常需要计算两个点之间的距离，从而判断两个物体是否相撞。回忆一下距离公式：

dist = 根号下((x1-x2)^2+(y1-y2)^2)

计算距离的汇编伪代码如下：

DEC X1 X2
MUL X2 X2 
DEC Y1 Y2
MUL Y2 Y2
ADD X2 Y2 # Y2保存了平方和
... # 剩下很多行代码用于开根号

如果每次遇到要计算距离，都把这段代码写一遍，显然也是一件很痛苦的事情。而且你也很容易看到，即使是汇编代码，即使是解决计算距离这么个简单的问题，也需要很多行代码，而且一旦把代码放在一起，你很难看明白它是在干什么。那么如之前一样，一个简单的办法是做笔记，比如：

#CalculateDistance
DEC X1 X2
MUL X2 X2
DEC Y1 Y2
MUL Y2 Y2
ADD X2 Y2
...
---CalculateDistance

这就是“过程”的概念——用一个符号代表一段代码。那么我们能不能再开发一个软件，能够支持通过用一个符号来标注“过程”，之后可以使用那个符号代表“过程”。这个软件的实现其实也很简单，每次遇到一个符号，就用对应的代码来替换这个符号，这其实就是现在所谓的宏。有了代码复用，代码可以进一步简化，表达力进一步增强。当然代码复用不仅只此…

抽象能力

支持了最简单的代码复用，软件开发更容易了。但是容易也是相对的，汇编代码依然晦涩难懂。因为到目前为止，代码依然还只是机器码的映射，操作的对象是一个一个的寄存器。你需要站在机器的角度去思考，完成一个数值计算要移动哪些寄存器，哪个寄存器里放哪个变量。那么我们希望的代码长什么样呢？能不能不关心CPU那一级的东西，不用去关心寄存器，用数学语言来描述程序逻辑。

比如说我要计算 3 + 5，写汇编代码时我需要指定：

• 3放到哪个寄存器
• 5放到哪个寄存器
• 结果放到哪里（不同实现不一样，大多放到目标寄存器）

那我们能不能实现一个简单的翻译软件，自动给我分配两个寄存器和插入运算指令呢，比如：

1 + 3

翻译成：

MOV $1  RAX
MOV $3  RBX
ADD RBX RAX

这个怎么实现呢？你仔细一想发现稍微有点困难了，虽然能直接把1翻译成 "MOV 1 寄存器" ，把3翻译成"MOV 3 寄存器"，"+" 也能翻译成 "ADD 寄存器A 寄存器B"。但是问题也显而易见——顺序。按照我们想要的写法，加号在1 和 3 中间， 如果先翻译1 然后翻译加号，这时候另一个寄存器还不知道分配的啥，而且还得把加法这条指令插到后面一条指令之后。好吧，说实话这个问题也不是那么复杂，要交换顺序就交换呗，后一个指令要用什么寄存器我可以提前决定呗。但是问题又来了，如果算式稍微复杂一点呢，比如：

1 + 3 * 2

啊哈？有点困难了，因为乘法和除法优先级比加减法高，这时候你想一想怎么翻译呢？不过我估计到这里也难不住你，你可以维护两个栈的数据结构来解决这个问题（ACM入门题）。那么再复杂一点的算式呢，比如：

1 + 3 * (2 - 8 / (1^100+ 5 * 5))

Oops ，这就触及到我知识的盲区了……怎么办呢？其实还是有办法的！ 1 + 3这种写法我们看着是比较习惯，但不一定非要这么写嘛，我如果写成这样呢：

1 3 +

先是两个操作数，然后是操作符，这种书写方式用习惯了也没什么问题，比如 1 + 3 * 2 换一种写法就是：

1 3 2 * +

翻译起来就非常简便了，直接按顺序翻译就行：

MOV  $1  RAX
MOV  $3  RBX
MOV  $2  RCX
MUL  RCX RBX
ADD RBX RAX

是吧，一气呵成。虽然实现这个翻译程序很简单，但是就需要程序员在写代码的时候自己做一次转换，把我们习惯的表达式转成上面说的表达方式，其实也就是所谓的“中缀表达式”转“后缀表达式”。这同样还有另一个巨大的好处，就是翻译程序不用考虑优先级问题，比如 2 * ( 4 - 1) + 3，写成后缀表达式就是：

2 4 1 - * 3 +

虽然还是不如中缀表达式看着直观，但这种代码比直接操作寄存器好懂多了。这也算一个进步！但是，你如果多写几个后缀表达式你就会发现，其实它还是挺难懂的，为了看懂它你得在大脑中做很多转换。那么有没有更好懂而且实现容易的方式呢？
其实很简单，把后缀表达式改成前缀表达式就行了，比如上面的：

• 中缀表达式 ：2 * ( 4 - 1) + 3
• 后缀表达式： 2 4 1 - * 3 +
• 前缀表达式： + 3 * 2 - 4 1

也许你会说，r u kidding me? 这前缀表达式哪里好懂了，不也差不多吗？但是，但是啊，如果加个括号做助记符，你看看：

• 没有括号：+ 3 * 2 - 4 1
• 加了括号：+ 3 ( * 2 (- 4 1) )

这个翻译起来也很简单：整个式子是做一个加法， 第一个加数是 3，第二个加数是一个算式的结果，这个算式是一个乘法，第一个因数是2 第二个因数是一个算式，这个算式是一个减法，减数是4被减数是1。

对吧，很容易的，一个递归就解决问题了。看到这里，你是不是想起了LISP？想起LISP就对了，LISP代码其实就是这样的。当然，LISP的发明绝不是这么发明的，它是λ演算进化而来，一开始是为了研究人工智能的，，没错，就是人工智能，1958年…

但是另一个问题你得知道，不论LISP是如何而来，它不能超越时代的发展，在那个年代要去实现LISP解释器，用前缀表达式或许就是工程上最佳的选择。但是用了前缀表达式，括号写多了，也有一种brainfuck的感觉，但有些人就是喜欢，不过这是后话了……

到这里你可以发现，随着我们对编程语言的基本需求，我们总是能想出办法：

通过实现一个小的翻译软件，能让我们代码编写稍微更容易，然后通过稍微容易一点的编程语言，我们又能实现一个新的能够翻译更具表达力的编程语言

这个翻译软件其实就是我们常用的编译器。20世纪50年代这方面的技术（PLT）就开始不断发展，到现在PLT已经非常非常复杂了。龙、虎、鲸书便是这几十年几代人智慧的结晶，其复杂度可想而知。那么PLT到底研究什么呢？

如果只用我上面介绍的部分，那么很关键的一点就是，寄存器如何分配。因为CPU中通用寄存器有限（假设有8个），那么在面对比如这样的算式：1+2+3+4+5+6+7+8+9+10，那么要怎么分配寄存器呢？实际上你发现其实两个就够了，比如：

MOV $1 EAX
MOV $2 EBX
ADD EBX EAX #结果存到EAX中
MOV $3 EBX
ADD EBX EAX
MOV $4 EBX
ADD EBX EAX
# ...

其实就是不断地重复利用寄存器。当然PLT研究的领域还有很多很多，最重要的领域之一就是如何识别程序代码。编译器怎么“看懂”程序员的代码，并进行准确的翻译。这也就是阻碍我们学习PLT的第一道门槛。大多数相关书籍在这部分会介绍非常非常多的名词，经常会让人摸不着头脑。那么为什么会有这么多名词呢，为什么一开始学PLT都要按照这个路子学呢？

从一道简单的题目看PLT

其实你可以发现，从前文中讲的语言的演进，实际上都是小步发展的，每一步都是基于之前的工作，通过一个简单的语言实现一个稍微复杂一点的编译器，能够识别更复杂一点但表达力更强的语言，再通过该语言实现更复杂一点的编译器，如此循环…但是随着编程语言不断地发展，最终还是要落实到人来写代码，因此只有中缀表达式才是符合人类思维的舒适的语法。那么我们就要想办法，实现一个能够编译中缀表达式的编译器。不管你如何厉害，这其实都不是一个容易的工作。另一方面，编程语言和英语、法语也是语言，各种语言研究方法也加入其中。当然，如果在这里讲得太多，显然也没有人愿意看。我们还是说点简单的内容。

经过多年的发展，我们可以把如何识别编程语言这件任务简化成以下一个非常容易理解的题目：

有一个字符串S，长度任意。有一个集合M，M中每个元素也是一个字符串mi。如果S可以由M中的字符串组合而成（M中的字符串可以重复使用多次），那么就是S是合法的串。现给定S和M，问S是否合法

比如S："abcaacad"，M：{"a", "abc", "cad"}，那么S可以被这样划分：(abc)(a)(a)(cad)，所以对于M来说，S是一个合法的串。

其实编译器做的也是这么一件事情，输入一个xxx.java，实际上对编译器来说就是个长度任意的字符串S。JAVA语法规范规定了JAVA的若干种语法，这些语法组成一个集合M，编译器最基本的任务就是判断S是否是合法的串，这其实就是语法检查。在进行语法检查的时，实际上编译器也把源文件按照语法做了一个划分，用树型结构表示。当然和上述的简化模型不同，每一种语法规则描述的是一类字符串，而不是某一个。比如变量名，只要是字母打头并且由字母、数字或下划线组成的，都符合”变量名“的规则。又比如函数签名，只要符合某些规则的，都属于合法的函数签名。编译器通过一次遍历，把源程序成功进行了一个划分，最后用树的结构表示，我们称这个树就叫抽象语法树。

从前面讲的内容你应该知道，前缀表达式和后缀表达式都很容易翻译成低级的代码。那如果编译器把中缀表达式也转成了一棵树，那么运用大一数据结构课第一次课后作业的知识，是不是只要进行先序或者后序遍历就能完成中缀到前缀、后缀的转换？转换完也就可以开始翻译了，对吧。

当然，说得容易做着难。怎么构建这颗中缀树？前面那道字符串划分的题目怎么做？如何解决这个问题，这么些年研究了很多方法，都收录于各大”编译原理“书籍中。归根到底，就是引入一个自动机的概念。说到自动机我想到了一件趣事，我高中的时候参加信息学竞赛，每次在判题系统提交题目，如果正确的话会显示”AC“（Accepted）。后来有一天听大佬们讨论一个叫”AC自动机“的算法，心中惊愕，还有这么牛逼的算法？是不是偷偷把标准答案从判题系统里读出来，然后直接根据输入直接输出结果啊。弱弱地去问大佬，招来了大佬一顿嘲讽：”AC自动机不是自动AC机“…

当然自动机是个很大的话题，里面涵盖了非常多完备的数学理论，我这里也不多说了，感兴趣的可以去看看相关资料。总之，通过各种算法，我们始终是可以把一段代码”无歧义“地划分成一个一个语法的组合，最后在内存中以树的结构保存，这颗树叫抽象语法树AST（Abstract Syntax Tree）。这其实也就是编译器的”前端“。编译器也分前后端，前端就是前述内容，把源文件转成AST。后端就是对这颗AST进行某种方式地遍历，然后把每个语法规则识别到的内容转成另一种语言，一般就是汇编，但也有例外，比如JAVA就转成了能在JVM上执行的字节码。

别看着上面就是几句话的事儿，但是怎么转换，怎么对转换内容进行优化，这是非常难的。比如:

• a + 1 + 2，是不是可以直接优化成 a + 3？
• 函数中有int a; a+=10;但是后面又没用到a，是不是可以把这段冗余代码干掉？
• 如果函数最后一个return语句是递归调用自己，是否可以给它改成非递归？

龙书有一大半都是在讲这些内容，编译器的开发者也在不断研究这些内容。想象一下，如果自己实现了一个C语言的编译器，别人的代码只需要换成我的编译器进行编译，最后程序运行速度就能有数倍的提升，这是多么自豪的事情啊。

在Go中引入λ表达式

这是我分享中的另一个主题，当然，这只是一个玩票性质的项目。你可能会问为什么要搞这个，我只能说：”自己如果从头造一个语言，又没有人用。写scala是不可能写scala的，改go的编译器又不会，只有写个内置解释器支持些语法糖，才能维持得了生活介样几。搞JVM的里面个个都是人才，说（技）话（术）又好（先）听（进），比Go那帮stuck in 70's好多了“。所以加完lambda表达式之后效果如下：

import "github.com/caibirdme/yql"

dst := []int{1, 2, 3, 4, 5, 6, 7}
r := yql.Filter(`(v) => v > 3 && v <= 7`).Map(`(v) => v << 2`).Filter(`(v) => v % 8 == 0`).Call(dst)
s, err := r.Interface()
// s == []int{16, 24}

支持了Filter和Map，每个Filter和Map里接收一个lambda表达式，这用起来就很函数式了。当然你会觉得没有什么egg用，但毕竟玩技术嘛，聊胜于无。性能嘛，其实也还好，只有第一次会做语法解析，之后转成bytecode，后续的调用都是在内置VM中实现。也就是说，和JAVA一样，只是代码是在第一次运行到这里再实时编译的，之后再执行到这里，就直接跑字节码了。当然作为一个玩具项目，JAVA的Hotspot VM JIT这些高大上的技术当然是没有用了。但是作为一个非JAVA选手，倒是深刻地理解了JAVA为什么要做这些以及可能会怎么做。

所以你也可以看到，PLT其实也能玩得很花，在玩的同时它能帮你更深刻地认识编程语言的本质，学习的过程中经常会有恍然大悟的感觉。PLT不仅仅是编译器开发者的领域，其实我觉得所有程序员都有必要了解一下，增加你的见识开阔你的眼界。同时，对于JAVA程序员，也不用再惧怕面试时别人问你JVM了…

写在最后

PLT其实是一门很”美“的学科，不要先去看龙书，找本简单有趣的书开始学习吧。强烈推荐《the little schemer》，据说作者是王垠大佬的导师。看了之后再买两本在逼乎上被强烈吐槽的书，比如《自制编程语言》、《自制编译器》这类书，能够快速让你熟悉工作流，当然知识体系是不可能有知识体系的（一般逼乎上说太水不推荐的书，我觉得都挺不错的。逼乎党喜欢推荐大部头让你知难而退，好让他们继续装逼）…稍微有点感觉之后，然后你自己就可以到处找资料，用你熟悉的语言实现一个蹩脚LISP方言，基本上就算是入门。最后，你再去看看龙书，很多问题就逐渐明了了。