理解编程语言的设计与实现

编程语言本质上是给开发者使用的工具，不同的业务领域使用不同的编程语言去实现具体的业务，是基于语言本身的设计理念与实现方式来做选择，那么作为开发者应该了解一下编程语言是如何被发明的，且其设计理念是什么。

Ruby 是我大学期间课余接触且实际使用过的一门语言，目前我甚是喜爱，其作者松本行弘设计 Ruby 的初心是：为开发者服务，注重简洁和效率。这篇文章主要也是为了记录在拜读了松本行弘先生新书《编程语言的设计与实现》之后掌握的一些相关的关键知识点和其它收获。由于该书主要是围绕作者在设计 Ruby 和新语言 Streem 过程中的一些思考和经验，有些东西可能不太具备普适性，而我在这里主要还是关注一些通用性的知识点和概念。

为什么要创造编程语言

在过去，计算机信息技术行业还不够发达，在没有成为主流的时候，编程语言一般是作为商业化附属品出现的，普通人很难能免费且容易的获取到编程语言作为工具使用。所以，基于需求创造自己的编程语言就显得很合理了。然而，当今由于开源技术的盛行，很多编程语言都以开源的形式存在，作为开发者现在很容易就能获取到不同的编程语言作为自己的工具进行业务开发，那为什么还要创造新的编程语言？或者说，为什么现如今新的语言仍然层出不穷？

软件编程本质上是“人机交互”，开发者使用编程语言设计业务逻辑，然后交由机器具体来执行，编程语言作为开发者与机器之间交流的媒介存在。随着时代的发展，业务需求和场景日益复杂，开发者与机器之间的交流也日趋复杂，为了让开发者“更轻松”地与机器交流，抽象度更高且更简洁的新编程语言作为新的交流媒介被发明。回忆一下计算机发展史，软件编程正是遵循从“汇编语言”（指令、0 和 1）到“低级语言”（例如 C/C++，语句、函数、数据类型）再到“高级语言”（例如 Java/Go，面向对象、并发、自动 GC）的发展路径。

对于个人来说，创造编程语言，或者说深入了解如何创造编程语言，可以提升自己的技术能力和设计能力，也能在一定程度上打造自己的个人品牌（提高个人声望）。

编程语言的设计与实现

对于现今的大多数编程语言来说，都属于“低级语言”和“高级语言”的范畴，而机器只能直接理解汇编语言。那么，设计编程语言是在设计什么？

语言和语言处理器

编程语言在使用过程中可大致分为两个阶段：编写代码和运行代码。前者注重的是语言本身，而后者具体要解决的就是语言代码如何让机器能理解进而执行。

语言是由语法和词汇构成的。语法是一种规则，规定了在该语言中如何表述才能使程序有效；而词汇是能从使用该语言编写的程序中调用的功能的集合，之后会以库的形式逐渐增加。 在设计语言的场景中说起词汇，就是指该语言一开始就具备的内置功能。

我们可以用不同的编程语言实现同样的功能，但有的语言实现起来复杂繁琐，但有的语言实现起来简单容易，这就是语言层面的直观体现。可以想象的是，很多新出现的编程语言首要解决的就是该问题，如何设计让语法规则更简单易用，内置功能更加强大。

另一方面，用语言编写的代码如何在机器上实际运行？

语言处理器是能够使语法和词汇在计算机上实际运行的软件。 要想使编程语言成为真正的语言，而非仅仅停留在一个想法上，是离不开语言处理器的。无法运行的编程语言在严格意义上不能称为编程语言。

我们通常所说的“编译器”、“解释器”、“虚拟机”、“JIT（即时编译）“等概念，均属于语言处理器相关的内容。

所以，编程语言的设计是在设计：语言本身和语言处理器。

语言处理器的构成

先来看看语言处理器相关的内容。

语言处理器大体上可分为解释语法的“编译器”、相当于词汇的“库”，以及实际运行软件所需的“运行时（系统）”。 这三大构成要素的比重会因语言和处理器性质的不同而发生变化。

如何理解后一句，来看看具体的实例即可。

早期的 TinyBASIC 语言很简单，编译器做的工作很少，主要的处理集中在运行时完成，对于这样的语言处理器可称之为”解释器“（interpreter）。现在这些复杂的语言的处理器都是先将程序编译为内部代码，再在运行时执行内部代码，这种“编译器＋运行时”的组合形式，看起来像源代码未经转换就被直接执行了，因此有时也被称为“解释型”，例如 Ruby。然而，像 C 语言这种在与机器非常接近的层面上追求效率的语言，几乎不存在运行时，只有解释语法的编译器部分非常突出，这样的语言处理器被称为“编译型”。

在 C 语言这类语言中，作为转换结果的程序（可执行文件）是可以直接运行的软件，所以不需要负责运行的运行时。部分运行时的工作，比如内存管理等，由库和操作系统的系统调用负责。

对于如今市场上主流的 Java 语言，其语言处理器设计较为复杂，首先通过编译器将源代码转换为虚拟机的机器码（JVM 字节码），并由虚拟机（JVM）来执行。而且，为了提高效率，运行时采用了将字节码转换为机器码的即时编译（Just In Time Compiler）等技术。

######### 编译器（Compiler）

**编译器的工作是将编程语言的源代码（原始语言）转换为可执行的形式（目标语言）。**其大致按顺序会执行多个或所有以下流程：预处理、词法分析、语法分析（解析）、语义分析（语法导向翻译）、将输入程序转换为中间表示（IR）、代码优化和代码生成。

编译器设计一般分为三个阶段，前端、中端和后端。编译前端包括生成中间表示（IR）之前的流程，这个 IR 通常是程序相对于源代码的较低级别的表示，在该阶段主要做一些静态分析工作，例如类型检查。编译中端则是对前端生成的 IR 做进一步处理，该阶段主要做与 CPU 架构无关的优化，例如去除无用（消除死代码）或无法访问（可达性分析）的代码。编译后端对中端生成的优化 IR 基于特定的 CPU 架构做进一步的分析、转换和优化处理，最终生成依赖于特定平台的汇编代码。

编译器这种前/中/后的设计方式使得不同语言的前端与不同 CPU 架构的后端相结合成为可能，同时共享中端的优化。例如，GNU 编译器集（GCC）、Clang（LLVM）等。

############# 提前编译（AOT）与即时编译（JIT）

目前根据编译的时机可将其分为静态编译和动态编译。其中静态编译通常称为提前编译（Ahead-of-time compilation），是指在程序执行之前将高级编程语言编译成低级语言的行为，减少需要在运行时执行的工作量，通常性能最优。而动态编译技术目前最具代表性的则为即时编译（Just-in-time compilation），是指在程序执行期间（在运行时）而不是在执行之前进行编译，是对两种传统的机器代码翻译方法（提前编译和解释）的结合，具有编译代码的速度和解释的灵活性，当然也引入了解释器的开销和编译及链接的额外开销。

############# 词法分析

词法分析器构成了现代处理中编译器前端的第一阶段。词法分析（Lexical analysis）简单来说就是“将源代码由字符序列转换为有意义的单词（token）序列”的工序。将只是字符串的源代码整理为有些许意义的单词序列，后续阶段的处理就会变得简单。

以 C 语言为例说明：

x = a + b * 2;

上面的表达式经过词法分析后生成如下内容：

[(identifier, x), (operator, =), (identifier, a), (operator, +), (identifier, b), (operator, *), (literal, 2), (separator, ;)]

我们可以借助 lex 工具根据编写单词的规则自动生成词法分析函数。

############# 语法分析

语法分析（Syntax analysis）是检查在词法分析阶段准备好的单词是否符合语法，并进行符合语法的处理的工序，最终结果是生成一个解析树（parse tree）数据结构。语法分析的方法有好几种，其中最有名、最简单的方法是使用别名为“生成编译器的编译器”的语法分析函数生成工具，比如 yacc（yet another compiler compiler）。

############# 抽象语法树

抽象语法树（Abstract syntax tree）是用编程语言编写的源代码的抽象语法结构的树表示，树的每个节点表示源代码中出现的一个构造。语法是“抽象的”，因为它不代表真实语法中出现的每个细节，而只是结构或与内容相关的细节。例如，分组括号在树结构中是隐含的，因此不必将它们表示为单独的节点。

抽象语法树在语义分析期间被大量使用，其中编译器检查程序和语言元素的正确使用。编译器还在语义分析期间根据 AST 生成符号表。树的完整遍历允许验证程序的正确性。验证正确性后，AST 作为代码生成的基础。AST 通常用于为代码生成生成中间表示 (IR)，有时也称为中间语言。

抽象语法树多用于程序分析和程序转换系统。

######### 标准库（Standard Library）

**语言的标准库通常被其用户视为语言的一部分，包括常用算法、数据结构和输入输出机制的定义。**标准库为程序员利用该语言实现更复杂的功能提供了必要的依赖。

那么，标准库中应该包含什么？对于标准库的设计哲学，可以参考 C/C++ 和 Java/Python，前者只提供在实现程序功能时必要且合理的数据结构和算法，规模相对较小，而后者旨在提供更多的便利、易于编码，封装了较为复杂和强大的功能，规模相对来说更为庞大。因此，Python 成为了目前主流的用来科学研究的语言，它可以很方便的完成复杂的数学计算和科学分析工作。

######### 运行时（Runtime）

每种编程语言都指定了一个执行模型，并且许多语言在运行时系统中至少实现了该模型的一部分。运行时系统为程序提供了运行的环境，这种环境可以解决许多问题，包括应用程序内存的管理、程序如何访问变量、在子程序之间传递参数的机制、与操作系统的接口等。换句话说，编译器根据具体平台的运行时系统产生正确的代码，运行时系统将负责设置和管理堆栈和堆，并且可能包括诸如垃圾收集、线程或其他内置于语言中的动态特性。

############# 执行模型（Execution model）

编程语言由文法/句法加上执行模型组成。执行模型指定语言元素的行为。通过应用执行模型，可以推导出用该编程语言编写的程序的行为。

例如，当程序员“阅读”代码时，在他们的脑海中，他们会浏览每一行代码的作用。实际上，他们模拟了他们头脑中的行为。程序员正在做的是将执行模型应用于代码，这会导致代码的行为。

虚拟机（Virtual Machine）

虚拟机是运行时的一种技术实现，是用软件实现的（无实际硬件的）计算机，区别于系统虚拟机，将其称之为“进程虚拟机”。进程虚拟机最初是作为中间语言的抽象平台出现的，中间语言被编译器用作程序的中间表示（IR）。它的目的是提供一个独立于平台的编程环境，抽象出底层硬件或操作系统的细节，并允许程序在任何平台上以相同的方式执行。因此，虚拟机最大的优点就是拥有可移植性。

配合各种各样的 CPU 生成机器语言的代码生成处理是编译器中最复杂的部分，适配新出现的 CPU 架构重新开发代码生成处理，对语言处理器的开发者来说是很大的负担，虚拟机在减少这类负担上起到了很大作用。另一方面，与在硬件上直接执行相比，模拟虚拟的 CPU 运行的虚拟机在性能上有很大损失，但可以通过引入即时编译（JIT）技术来弥补。

虚拟机性能相关的实现技术可以了解一下：

• RISC 与 CISC
• 栈与寄存器
• 指令格式

RISC 是 Reduced Instruction Set Computer（精简指令集计算机）的缩写，是通过减少指令的种类、简化电路来提高 CPU 性能的架构。具有代表性的 CPU 有 MIPS 和 SPARC 等。在移动设备上广泛使用的 ARM 处理器就属于 RISC。

CISC 是与 RISC 相对的一个词汇，是 Complex Instruction Set Computer（复杂指令集计算机）的缩写，简单来说就是“不是 RISC 的 CPU”。CISC 的每个指令执行的处理都非常大，而且指令的种类繁多，因此实现起来也比较复杂。

对用软件实现的虚拟机来说，我们就不能忽视取指令（Instruction Fetch，IF）处理所需要的成本。也就是说，做同样的处理时所需的指令数越少越好。好的虚拟机指令集是类 CISC 架构的指令集，它的全部指令都是高粒度的。

虚拟机架构的两大流派是栈式虚拟机和寄存器式虚拟机。栈式虚拟机原则上通过栈对数据进行操作，而寄存器式虚拟机的指令中包含寄存器编号，原则上对寄存器进行操作。

与寄存器式虚拟机相比，栈式虚拟机更为简单，程序也相对较小。然而，由于所有的指令都通过栈来交换数据，所以对指令之间的先后顺序有很大的依赖，很难实施交换指令顺序这样的优化。而寄存器式虚拟机由于指令中包含寄存器信息，所以程序相对较大。

用哪种架构取决于具体场景，著名的 Java 虚拟机（JVM）采用的是栈式虚拟机架构，而谷歌为优化移动设备性能，为 Android 提供的 Dalvik 虚拟机则采用的是寄存器式虚拟机架构。

虚拟机解释的中间语言（指令序列）被称为“字节码”，源于 Smalltalk 的指令是以字节为单位的。当然，不是所有虚拟机都拥有字节单位的指令集，例如 mruby 的指令集就是用 32 位整数表示的，可以称之为“字码”，但因为 JVM 比较出名且其采用的是字节码，所以一般将虚拟机解释的中间语言称之为“字节码”。字码与字节码的优缺点不在这里赘述。

参考

• 《松本行弘：编程语言的设计与实现》，[日] 松本行弘，郑明智 译
• https://en.wikipedia.org/wiki/Compiler
• https://en.wikipedia.org/wiki/Ahead-of-time_compilation
• https://en.wikipedia.org/wiki/Just-in-time_compilation
• https://en.wikipedia.org/wiki/Abstract_syntax_tree
• https://en.wikipedia.org/wiki/Library_(computing)
• https://en.wikipedia.org/wiki/Runtime_system
• https://en.wikipedia.org/wiki/Virtual_machine