虚拟机随叙（一）

虚拟机随谈（一）

?

转载自 ---- 作者：RednaxelaFX -> rednaxelafx.iteye.com

?

1、解析器与解释器

解析器是parser，而解释器是interpreter。两者不是同一样东西，不应该混用。

前者是编译器/解释器的重要组成部分，也可以用在IDE之类的地方；其主要作用是进行语法分析，提取出句子的结构。广义来说输入一般是程序的源码，输出一般是语法树（syntax tree，也叫parse tree等）或抽象语法树（abstract syntax tree，AST）。进一步剥开来，广义的解析器里一般会有扫描器（scanner，也叫tokenizer或者lexical analyzer，词法分析器），以及狭义的解析器（parser，也叫syntax analyzer，语法分析器）。扫描器的输入一般是文本，经过词法分析，输出是将文本切割为单词的流。狭义的解析器输入是单词的流，经过语法分析，输出是语法树或者精简过的AST。
（在一些编译器/解释器中，解析也可能与后续的语义分析、代码生成或解释执行等步骤融合在一起，不一定真的会构造出完整的语法树。但概念上说解析器就是用来抽取句子结构用的，而语法树就是表示句子结构的方式。关于边解析边解释执行的例子，可以看看这帖的计算器。）
举例：将i = a + b * c作为源代码输入到解析器里，则广义上的解析器的工作流程如下图：

其中词法分析由扫描器完成，语法分析由狭义的解析器完成。
（嗯，说来其实“解析器”这词还是按狭义用法比较准确。把扫描器和解析器合起来叫解析器总觉得怪怪的，但不少人这么用，这里就将就下吧 =_=
不过近来“scannerless parsing”也挺流行的：不区分词法分析与语法分析，没有单独的扫描器，直接用解析器从源码生成语法树。这倒整个就是解析器了，没狭不狭义的问题）

后者则是实现程序执行的一种实现方式，与编译器相对。它直接实现程序源码的语义，输入是程序源码，输出则是执行源码得到的计算结果；编译器的输入与解释器相同，而输出是用别的语言实现了输入源码的语义的程序。通常编译器的输入语言比输出语言高级，但不一定；也有输入输出是同种语言的情况，此时编译器很可能主要用于优化代码。
举例：把同样的源码分别输入到编译器与解释器中，得到的输出不同：

值得留意的是，编译器生成出来的代码执行后的结果应该跟解释器输出的结果一样——它们都应该实现源码所指定的语义。

在很多地方都看到解析器与解释器两个不同的东西被混为一谈，感到十分无奈。
最近某本引起很多关注的书便在开篇给读者们当头一棒，介绍了“JavaScript解析机制”。“编译”和“预处理”也顺带混为一谈了，还有“预编译” 0_0
我一直以为“预编译”应该是ahead-of-time compilation的翻译，是与“即时编译”（just-in-time compilation，JIT）相对的概念。另外就是PCH（precompile header）这种用法，把以前的编译结果缓存下来称为“预编译”。把AOT、PCH跟“预处理”（preprocess）混为一谈真是诡异。算了，我还是不要淌这浑水的好……打住。


2、“解释器”到底是什么？“解释型语言”呢？

很多资料会说，Python、Ruby、JavaScript都是“解释型语言”，是通过解释器来实现的。这么说其实很容易引起误解：语言一般只会定义其抽象语义，而不会强制性要求采用某种实现方式。
例如说C一般被认为是“编译型语言”，但C的解释器也是存在的，例如Ch。同样，C++也有解释器版本的实现，例如Cint。
一般被称为“解释型语言”的是主流实现为解释器的语言，但并不是说它就无法编译。例如说经常被认为是“解释型语言”的Scheme就有好几种编译器实现，其中率先支持R6RS规范的大部分内容的是Ikarus，支持在x86上编译Scheme；它最终不是生成某种虚拟机的字节码，而是直接生成x86机器码。

解释器就是个黑箱，输入是源码，输出就是输入程序的执行结果，对用户来说中间没有独立的“编译”步骤。这非常抽象，内部是怎么实现的都没关系，只要能实现语义就行。你可以写一个C语言的解释器，里面只是先用普通的C编译器把源码编译为in-memory image，然后直接调用那个image去得到运行结果；用户拿过去，发现直接输入源码可以得到源程序对应的运行结果就满足需求了，无需在意解释器这个“黑箱子”里到底是什么。
实际上很多解释器内部是以“编译器+虚拟机”的方式来实现的，先通过编译器将源码转换为AST或者字节码，然后由虚拟机去完成实际的执行。所谓“解释型语言”并不是不用编译，而只是不需要用户显式去使用编译器得到可执行代码而已。

那么虚拟机（virtual machine，VM）又是什么？在许多不同的场合，VM有着不同的意义。如果上下文是Java、Python这类语言，那么一般指的是高级语言虚拟机（high-level language virtual machine，HLL VM），其意义是实现高级语言的语义。VM既然被称为“机器”，一般认为输入是满足某种指令集架构（instruction set architecture，ISA）的指令序列，中间转换为目标ISA的指令序列并加以执行，输出为程序的执行结果的，就是VM。源与目标ISA可以是同一种，这是所谓same-ISA VM。
前面提到解释器中的编译器的输出可能是AST，也可能是字节码之类的指令序列；一般会把执行后者的程序称为VM，而执行前者的还是笼统称为解释器或者树遍历式解释器（tree-walking interpreter）。这只是种习惯而已，并没有多少确凿的依据。只不过线性（相对于树形）的指令序列看起来更像一般真正机器会执行的指令序列而已。
其实我觉得把执行AST的也叫VM也没啥大问题。如果认同这个观点，那么把DLR看作一种VM也就可以接受了——它的“指令集”就是树形的Expression Tree。

VM并不是神奇的就能执行代码了，它也得采用某种方式去实现输入程序的语义，并且同样有几种选择：“编译”，例如微软的.NET中的CLR；“解释”，例如CPython、CRuby 1.9，许多老的JavaScript引擎等；也有介于两者之间的混合式，例如Sun的JVM，HotSpot。如果采用编译方式，VM会把输入的指令先转换为某种能被底下的系统直接执行的形式（一般就是native code），然后再执行之；如果采用解释方式，则VM会把输入的指令逐条直接执行。
换个角度说，我觉得采用编译和解释方式实现虚拟机最大的区别就在于是否存下目标代码：编译的话会把输入的源程序以某种单位（例如基本块/函数/方法/trace等）翻译生成为目标代码，并存下来（无论是存在内存中还是磁盘上，无所谓），后续执行可以复用之；解释的话则把源程序中的指令是逐条解释，不生成也不存下目标代码，后续执行没有多少可复用的信息。有些稍微先进一点的解释器可能会优化输入的源程序，把满足某些模式的指令序列合并为“超级指令”；这么做就是朝着编译的方向推进。后面讲到解释器的演化时再讨论超级指令吧。

如果一种语言的主流实现是解释器，其内部是编译器+虚拟机，而虚拟机又是采用解释方式实现的，或者内部实现是编译器+树遍历解释器，那它就是名副其实的“解释型语言”。如果内部用的虚拟机是用编译方式实现的，其实跟普遍印象中的“解释器”还是挺不同的……

可以举这样一个例子：ActionScript 3，一般都被认为是“解释型语言”对吧？但这种观点到底是把FlashPlayer整体看成一个解释器，因而AS3是“解释型语言”呢？还是认为FlashPlayer中的虚拟机采用解释执行方案，因而AS3是“解释型语言”呢？
其实Flash或Flex等从AS3生成出来的SWF文件里就包含有AS字节码（ActionScript Byte Code，ABC）。等到FlashPlayer去执行SWF文件，或者说等到AVM2（ActionScript Virtual Machine 2）去执行ABC时，又有解释器和JIT编译器两种实现。这种需要让用户显式进行编译步骤的语言，到底是不是“解释型语言”呢？呵呵。所以我一直觉得“编译型语言”跟“解释型语言”的说法太模糊，不太好。
有兴趣想体验一下从命令行编译“裸”的AS3文件得到ABC文件，再从命令行调用AVM2去执行ABC文件的同学，可以从这帖下载我之前从源码编译出来的AVM2，自己玩玩看。例如说要编译一个名为test.as的文件，用下列命令：

这是对AST的后序遍历：假设有一个eval(Node n)函数，用于解释AST上的每个节点；在解释一个节点时如果依赖于子树的操作，则对子节点递归调用eval(Node n)，从这些递归调用的返回值获取需要的值（或副作用）——也就是说子节点都eval好了之后，父节点才能进行自己的eval——典型的后序遍历。
（话说，上图中节点左下角有蓝色标记的说明那是节点的“内在属性”。从属性语法的角度看，如果一个节点的某个属性的值只依赖于自身或子节点，则该属性被称为“综合属性”（synthesized attribute）；如果一个节点的某个属性只依赖于自身、父节点和兄弟节点，则该属性被称为“继承属性”（inherited attribute）。上图中节点右下角的红色标记都只依赖子节点来计算，显然是综合属性。）

SquirrelFish之前的JavaScriptCore、CRuby 1.9之前的CRuby就都是采用这种方式来解释执行的。

可能需要说明的：
·左值与右值
在源代码i = a + b * c中，赋值符号左侧的i是一个标识符，表示一个变量，取的是变量的“左值”（也就是与变量i绑定的存储单元）；右侧的a、b、c虽然也是变量，但取的是它们的右值（也就是与变量绑定的存储单元内的值）。在许多编程语言中，左值与右值在语法上没有区别，它们实质的差异容易被忽视。一般来说左值可以作为右值使用，反之则不一定。例如数字1，它自身有值就是1，可以作为右值使用；但它没有与可赋值的存储单元相绑定，所以无法作为左值使用。
左值不一定只是简单的变量，还可以是数组元素或者结构体的域之类，可能由复杂的表达式所描述。因此左值也是需要计算的。

·优先级、结合性与求值顺序
这三个是不同的概念，却经常被混淆。通过AST来看就很容易理解：（假设源码是从左到右输入的）
所谓优先级，就是不同操作相邻出现时，AST节点与根的距离的关系。优先级高的操作会更远离根，优先级低的操作会更接近根。为什么？因为整棵AST是以后序遍历求值的，显然节点离根越远就越早被求值。
所谓结合性，就是当同类操作相邻出现时，操作的先后顺序同AST节点与根的距离的关系。如果是左结合，则先出现的操作对应的AST节点比后出现的操作的节点离根更远；换句话说，先出现的节点会是后出现节点的子节点。
所谓求值顺序，就是在遍历子节点时的顺序。对二元运算对应的节点来说，先遍历左子节点再遍历右子节点就是左结合，反之则是右结合。
这三个概念与运算的联系都很紧密，但实际描述的是不同的关系。前两者是解析器根据语法生成AST时就已经决定好的，后者则是解释执行或者生成代码而去遍历AST时决定的。
在没有副作用的环境中，给定优先级与结合性，则无论求值顺序是怎样的都能得到同样的结果；而在有副作用的环境中，求值顺序会影响结果。

赋值运算虽然是右结合的，但仍然可以用从左到右的求值顺序；事实上Java、C#等许多语言都在规范里写明表达式的求值顺序是从左到右的。上面的例子中就先遍历的=的左侧，求得i的左值；再遍历=的右侧，得到表达式的值23；最后执行=自身，完成对i的赋值。
所以如果你要问：赋值在类似C的语言里明明是右结合的运算，为什么你先遍历左子树再遍历右子树？上面的说明应该能让你发现你把结合性与求值顺序混为一谈了。

看看Java从左到右求值顺序的例子：

（假设a、b、c、i分别被分配到局部变量区的slot 0到slot 3）
能看出Java字节码与源码间的对应关系了么？
一个Java编译器的输入是Java源代码，输出是含有Java字节码的.class文件。它里面主要包含扫描器与解析器，语义分析器（包括类型检查器/类型推导器等），代码生成器等几大部分。上图所展示的就是代码生成器的工作。对Java编译器来说，代码生成就到字节码的层次就结束了；而对native编译器来说，这里刚到生成中间表示的部分，接下去是优化与最终的代码生成。

如果你对Python、CRuby 1.9之类有所了解，会发现它们的字节码跟Java字节码在“基于栈”的这一特征上非常相似。其实它们都是由“编译器+VM”构成的，概念上就像是Java编译器与JVM融为一体一般。
从这点看，Java与Python和Ruby可以说是一条船上的。虽说内部具体实现的显著差异使得先进的JVM比简单的JVM快很多，而JVM又普遍比Python和Ruby快很多。

当解释器中用于解释执行的中间代码是树形时，其中能被称为“编译器”的部分基本上就是解析器；中间代码是线性形式（如字节码）时，其中能被称为编译器的部分就包括上述的代码生成器部分，更接近于所谓“完整的编译器”；如果虚拟机是基于寄存器架构的，那么编译器里至少还得有虚拟寄存器分配器，又更接近“完整的编译器”了。


7、基于栈与基于寄存器架构的VM的一组图解

要是拿两个分别实现了基于栈与基于寄存器架构、但没有直接联系的VM来对比，效果或许不会太好。现在恰巧有两者有紧密联系的例子——JVM与Dalvik VM。JVM的字节码主要是零地址形式的，概念上说JVM是基于栈的架构。Google Android平台上的应用程序的主要开发语言是Java，通过其中的Dalvik VM来运行Java程序。为了能正确实现语义，Dalvik VM的许多设计都考虑到与JVM的兼容性；但它却采用了基于寄存器的架构，其字节码主要是二地址/三地址混合形式的，乍一看可能让人纳闷。考虑到Android有明确的目标：面向移动设备，特别是最初要对ARM提供良好的支持。ARM9有16个32位通用寄存器，Dalvik VM的架构也常用16个虚拟寄存器（一样多……没办法把虚拟寄存器全部直接映射到硬件寄存器上了）；这样Dalvik VM就不用太顾虑可移植性的问题，优先考虑在ARM9上以高效的方式实现，发挥基于寄存器架构的优势。
Dalvik VM的主要设计者Dan Bornstein在Google I/O 2008上做过一个关于Dalvik内部实现的演讲；同一演讲也在Google Developer Day 2008 China和Japan等会议上重复过。这个演讲中Dan特别提到了Dalvik VM与JVM在字节码设计上的区别，指出Dalvik VM的字节码可以用更少指令条数、更少内存访问次数来完成操作。（看不到YouTube的请自行想办法）

眼见为实。要自己动手感受一下该例子，请先确保已经正确安装JDK 6，并从官网获取Android SDK 1.6R1。连不上官网的也请自己想办法。

创建Demo.java文件，内容为：

（图中数字均以十六进制表示。其中字节码的一列表示的是字节码指令的实际数值，后面跟着的助记符则是其对应的文字形式。标记为红色的值是相对上一条指令的执行状态有所更新的值。下同）
说明：Java字节码以1字节为单元。上面代码中有11条指令，每条都只占1单元，共11单元==11字节。
程序计数器是用于记录程序当前执行的位置用的。对Java程序来说，每个线程都有自己的PC。PC以字节为单位记录当前运行位置里方法开头的偏移量。
每个线程都有一个Java栈，用于记录Java方法调用的“活动记录”（activation record）。Java栈以帧（frame）为单位线程的运行状态，每调用一个方法就会分配一个新的栈帧压入Java栈上，每从一个方法返回则弹出并撤销相应的栈帧。
每个栈帧包括局部变量区、求值栈（JVM规范中将其称为“操作数栈”）和其它一些信息。局部变量区用于存储方法的参数与局部变量，其中参数按源码中从左到右顺序保存在局部变量区开头的几个slot。求值栈用于保存求值的中间结果和调用别的方法的参数等。两者都以字长（32位的字）为单位，每个slot可以保存byte、short、char、int、float、reference和returnAddress等长度小于或等于32位的类型的数据；相邻两项可用于保存long和double类型的数据。每个方法所需要的局部变量区与求值栈大小都能够在编译时确定，并且记录在.class文件里。
在上面的例子中，Demo.foo()方法所需要的局部变量区大小为3个slot，需要的求值栈大小为2个slot。Java源码的a、b、c分别被分配到局部变量区的slot 0、slot 1和slot 2。可以观察到Java字节码是如何指示JVM将数据压入或弹出栈，以及数据是如何在栈与局部变量区之前流动的；可以看到数据移动的次数特别多。动画里可能不太明显，iadd和imul指令都是要从求值栈弹出两个值运算，再把结果压回到栈上的；光这样一条指令就有3次概念上的数据移动了。

对了，想提醒一下：Java的局部变量区并不需要把某个局部变量固定分配在某个slot里；不仅如此，在一个方法内某个slot甚至可能保存不同类型的数据。如何分配slot是编译器的自由。从类型安全的角度看，只要对某个slot的一次load的类型与最近一次对它的store的类型匹配，JVM的字节码校验器就不会抱怨。以后再找时间写写这方面。

Dalvik VM：

说明：Dalvik字节码以16位为单元（或许叫“双字节码”更准确 =_=|||）。上面代码中有5条指令，其中mul-int/lit8指令占2单元，其余每条都只占1单元，共6单元==12字节。
与JVM相似，在Dalvik VM中每个线程都有自己的PC和调用栈，方法调用的活动记录以帧为单位保存在调用栈上。PC记录的是以16位为单位的偏移量而不是以字节为单位的。
与JVM不同的是，Dalvik VM的栈帧中没有局部变量区与求值栈，取而代之的是一组虚拟寄存器。每个方法被调用时都会得到自己的一组虚拟寄存器。常用v0-v15这16个，也有少数指令可以访问v0-v255范围内的256个虚拟寄存器。与JVM相同的是，每个方法所需要的虚拟寄存器个数都能够在编译时确定，并且记录在.dex文件里；每个寄存器都是字长（32位），相邻的一对寄存器可用于保存64位数据。方法的参数按源码中从左到右的顺序保存在末尾的几个虚拟寄存器里。
与JVM版相比，可以发现Dalvik版程序的指令数明显减少了，数据移动次数也明显减少了，用于保存临时结果的存储单元也减少了。

你可能会抱怨：上面两个版本的代码明明不对应：JVM版到return前完好持有a、b、c三个变量的值；而Dalvik版到return-void前只持有b与c的值（分别位于v0与v1），a的值被刷掉了。
但注意到a与b的特征：它们都只在声明时接受过一次赋值，赋值的源是常量。这样就可以对它们应用常量传播，将

其实上图画得不准确，a、b、c的右值不应该画在节点上的；节点应该只保存了它们的左值才对，要获取对应的右值就要查询变量表。我修改了图更新到正文了。原本的图里对i的赋值看起来很奇怪，就像是遍历过程经过了两次i节点一般，而事实不是那样的。