抽象机模式
（已发表在《程序员》2003年第1期上）
撰文/Julio García-Martín Miguel Sutil-Martín
Universidad Politécnica de Madrid[1]
翻译/马维达
摘要
由于现代高级编程语言和现有硬件之间的差异日渐增大，常常有必要引入中间语言、并在原始硬件之上构建抽象机。本论文描述了抽象机（Abstract Machine），一种对抽象机的本质特性进行捕捉的结构型模式；这些特性给出了对抽象机的定义。该模式将抽象机的静态特性和动态特性作为分离的组件进行描述，并且还考虑了指令集和这些指令的语义，以及此模式的其他一些重要组件。
意图
为抽象机的设计定义通用模板。该模式捕捉在抽象机之下的本质特性（也就是，数据区、程序、指令集，等等），将它们的相互分离的、松耦合的组件封装进结构模式中。此外，本论文还提供了抽象机的各组件进行交互的协作结构。
别名
虚拟机（Virtual Machine）、抽象状态机（Abstract State Machine）。
动机
在今天，Java是计算机科学中的一个时髦话语。尽管Java是一种用于分布式和GUI应用开发的面向对象语言，但几乎每天它都在增加新的非常有用的编程特性和工具。作为一项事实，在Java的成功中，虚拟机技术的使用有着极为重大的意义[2]。众所周知，Java虚拟机（Java Virtual Machine，JVM）是基于软件的抽象机，可在不同的微处理器机器上工作（也就是，独立于硬件）。JVM的设计者必须遵从JVM的规范，进行必要的处理，将JVM虚拟环境桥接进具体的操作系统和微处理器中。这个在虚拟环境之后的“桥梁”允许软件开发者“一次编程，到处运行”（Write Once，Run Anywhere）[1]，因为不管底层的微处理器是什么，JVM都必须根据JVM的标准规范以同样的方式工作。
由于现代高级编程语言和现有硬件之间的差异日渐增大，常常有必要引入中间语言、并在原始硬件之上构建抽象机。但是，在许多情况下，差异是如此之大，以致于我们难以看出源语言是怎样与中间语言相关联的，或者，难以看出中间语言是怎样与硬件相关联的。遗憾的是，在许多情况下，抽象机仅仅被表示为一些寄存器、内存区和机器指令集的集合，只有很少的、或没有与源语言的对应性。
图1 抽象机的例子：Abstract-WAM [3]
该项工作的目标是双重的：a）首先，为抽象机的设计发明一套方法学；其次，b）使用此方法学来描述一个基于模式的构架，用于设计编程语言编译器。对这样的实现技术（也就是，抽象机）的使用允许将编译任务规划为渐进的优化过程，这样，就可以根据中间的抽象机之间的关系来一步一步获得高性能特性。通过此过程还保持了一个抽象机与下一个抽象机之间的同一性。每个编译步骤都明确地生成一些新特性和变动，并将其增加到全局编译过程中（见图2）。
* 也可以是“定义”
图2 通过虚拟机渐进优化进行的编译过程
该过程给出了更为抽象和系统的构造编译器的方法。此外，它还促进了对编译过程的理解，并简化了对先前的设计进行优化和复用的任务。一个（原型）编译器或多或少有可能作为抽象机设计的边际效应自动导出。
适用性
抽象机模式适用于下面的任意一种情形：
l 当我们想要定义抽象机时。该模式提供了编写高级规范的通用骨架，允许程序员将注意力更多地集中在定义抽象机的各组件上，而不是去担心它们的合并（这可以由此模式“免费”提供）。所编写的规范可以是形式化或非形式化的。
l 当我们想要通过使用抽象机技术来编译语言时。抽象机提供了适当的构架来描述通过中间语言的渐进优化进行的编译过程（也就是，原型式开发）。在这样的过程中，各中间语言（也就是，抽象机）之间的关系定义了整个编译过程。
l 当我们想要定义通过应用抽象机获得的编译器时。这是对上面的两种情况进行结合的结果。
l 当我们想要测试同一指令的不同语义时。可以为同一指令定义不同的语义，同样，也可以获得同一语义的不同实现。
l 当我们想要测试同一抽象机的不同指令集时。可以为同一抽象机定义不同的指令集。而且，编译过程的渐进优化意味着每个中间的抽象机都定义了比前一抽象机所管理的指令集更为优化的指令集。
l 当我们想要对我们的程序的执行进行模拟时。程序模拟将可视化工具和调试工具强制性地结合进程序中。很容易将这些查看组件和其他特性视为抽象机模式的参与者。特别地，与可视化或调试有关的执行代码可以通过增强抽象机的指令来定义。
结构
抽象机模式的结构如图3所示。
图3 抽象机模式（结构）
参与者
抽象机可抽象地定义为两个部分的联合：(i)静态部分，由与状态（state）有关的组件组成，(ii)动态部分，确定与抽象机的行为（behavior）相关联的要素。抽象机模式将两个部分的参与者组织和定位为它的结构的组件。
抽象机的状态由以下组件组成：
1. Abstract-Machine Factory（抽象机工厂）：它为创建Abstract DataArea和Abstract Program的操作声明接口。
2. Abstract DataArea（抽象数据区）：它为数据区对象类型声明接口，用以配置抽象机。它声明两种抽象操作：
l Init操作，用以确定数据区的初始配置，以及
l Stop操作，确定抽象机的执行是否已结束。如果结束条件不依赖于数据区，Stop操作就返回true。
3. Concrete DataArea（具体数据区）：它定义具体的数据区对象。具体数据区可以是简单对象或复杂对象结构（对象容器）。该组件必须提供Abstract DataArea接口的实现。
4. Abstract Program（抽象程序）：它为汇编程序声明通用接口。它的定义必须处理一系列指令（Abstract Instruction）及一个指令集（Abstract Instruction Set）。此外，它还声明了四种抽象操作：
l Init操作，用以确定汇编程序的初始配置。
l Stop操作，用以确定抽象机是否到达它的最终阶段。如果终止条件不依赖于任何程序配置，Stop操作返回true。
l LoadProg操作负责构造抽象机程序的汇编指令。该操作从输入流中读取文本表示，并将每条指令翻译为Concrete Instruction对象。
l CurrentInst操作返回要由抽象机执行的指令。
5. Concrete Program（具体程序）：它定义具体的程序对象。它被定义为具体指令集和一些程序计数器的集合。它必须实现在Abstract Program中定义的Init、Stop和CurrentInst操作。
6. Abstract Instruction Set（抽象指令集）：它声明用以表示一组抽象指令的通用接口。
7. Concrete Instruction Set（具体指令集）：它通过Concrete Instruction对象来定义一组对象。具体指令集与具体数据区及具体程序相联系。它必须实现Abstract Instruction Set的各操作。
8. Abstract Instruction（抽象指令）：它声明用以表示抽象机指令的通用接口。
9. Concrete Instruction（具体指令）：它定义具体的指令对象。具体指令直接与具体数据区和具体程序相联系。它必须实现Abstract Instruction的各操作。
在抽象机的行为这一方面，它依赖于在静态组件之上工作的一些操作。这些操作是抽象机状态的定义的一部分，它们负责描述在执行过程中抽象机所到达的不同状态。这些操作描述如下：
1. Abstract-Machine State（抽象机状态）：作为汇编Concrete Instruction的执行结果，它对DataArea和Program之间的交互进行协调。因而，它有着与MEDIATOR模式[4]类似的角色。抽象机状态可以到达三个不同的阶段（initial、executing和final），它们与以下操作相联系：
l Init操作，在程序开始执行时用以确定抽象机的初始状态。
l Stop操作，用以确定执行是否到达了抽象机的最终状态。
l Transition操作，用以完成抽象机程序的执行。它被定义为while循环控制结构；每一轮循环都执行程序计数器（CurrentInst）所指向的指令。Transition操作从初始的抽象机配置状态开始执行，并持续直到到达最终阶段为止。
2. Abstract & Concrete Instruction（抽象和具体指令）：
l SI操作（语义函数）确定抽象机的配置怎样随着指令的执行而演变。每条指令都定义它自己的SI语义函数，并确定抽象机的状态怎样变化（更改数据区和/或程序）。为了完成这些变动，各指令必须能够访问当前状态上的组件。这是通过抽象机状态的copy-reference（拷贝引用）来完成的；该copy-reference被作为参数传递给指令。
协作
抽象机在执行过程中可能到达三个不同的阶段：initialization（初始化）、transition（迁移）和ending（结束）。图4、5、6勾画了这些阶段。
阶段1：Initialization
图4 初始化阶段（协作）
抽象机在这一阶段被初始化。结果DataArea和Program都会被初始化。Program的初始化是由Init操作完成的，并涉及将其组件设置为初始值（也就是，程序计数器、指令阵列，等等）。然后，负责汇编程序加载（也就是，将来自inputStream的汇编指令的文本表示翻译为程序的指令对象）的LoadProgram操作被执行。另一方面，Init操作对DataArea中的组件（也就是，数据寄存器或控制寄存器，等等）进行初始化。
阶段2：Transition
图5 迁移阶段（协作）
如前面所说的，Transition操作完成抽象机执行。因而，Transition操作（通过CurrentInst操作）从程序那里请求所要执行的指令，即由程序计数器所指向的指令。各指令的执行构成抽象机的执行，直到到达结束状态为止。每条抽象机指令负责定义它自己的语义。因而，每条指令都提供SI操作——取决于指令是否更改程序和/数据区——其执行对抽象机的状态（也就是，程序和/或数据区）进行更改。更改被完成的次序仅由指令语义来决定。
阶段3：Ending
图6 最终阶段（协作）
抽象机在它的两个组件中的任何一个（或两者同时）到达结束状态时（例如，执行了一条具体的停止命令，数据区溢出，等等）到达结束阶段。该状态对DataArea和Program的Stop操作进行求值，并合并它们的结果。
效果
抽象机模式显示出以下优越性：
l 提供了用以开发抽象机的框架。该模式定义了用以开发抽象机的高级而灵活的设计。
l 提供了用以通过抽象机的渐进优化来开发编译器的框架。在编译过程中的优化步骤可以根据抽象机的结构或其组件的优化来表述。
l 使抽象机各参与者之间的关系去耦合。Abstract Machine Factory帮助使Abstract Machine State和具体的数据区及程序实现隔离开来。Abstract Machine State通过各实例的抽象接口来对它们进行操作。在Abstract Instruction Set这一边，它被用作由程序进行管理的指令集的抽象工厂。
l 提供用以测试不同指令集的框架。该模式使得变换指令集变得更为容易，允许数据区和程序独立于任何具体的指令集进行维护。要改变具体的指令集，只需重新配置抽象机。
l 提供用以测试同一机器指令的不同指令语义或实现的框架。因为语义封装在指令（SI操作）中，我们可以重新定义它们，而不会影响数据区和/或程序。
l 提供更高水平的抽象机复用。在大多数情况下，全部或部分的抽象机，可在新的开发中被高度复用。
l 提倡一种用于最为系统的抽象机开发的方法学。通过使抽象机的参与者分离在各组件中（也就是，数据区、程序、指令集和指令语义），我们引入了一些设计约束，强制用户遵循系统化的方法。
抽象机模式也显示出以下不足：
l 产生出低效的实现。
l 在Abstract-Machine State和Abstract Instruction之间引发通信开销。
实现
考虑以下实现问题：
1. 创建具体的Data Area和Program。Abstract-Machine Factory只为创建Data Area和Program对象声明了一个接口。遵循为ABSTRACT-FACTORY模式所给出的类似提示[4]。
2. Concrete Data Area可以具有复杂的对象成分。遵循COMPOSITE模式中的同样的实现问题的解决方法[4]。
3. 将Abstract Data Area、Abstract Program、Abstract Instruction和Abstract Instruction Set定义为接口。例如，遵循Java约定：
public interface AbstractInstruction
{
public void SI (AbstractMachineState state);
public String Name ();
public int NumArguments ();
public String ToString ();
public void Process (String args [])
}
public interface AbstractInstructionSet
{ ... }
public interface AbstractProgram
{
public AbstractInstruction CurrentInst ();
public void Init ();
public boolean Stop ();
public void LoadProgram (Stream assemblerCode);
}
public interface AbstractDataArea
{
public void Init ();
public boolean Stop ();
}
Abstract Instruction接口提供了两个方法来确定与指令有关的信息（也就是，Name、NumArguments）；方法SI声明指令语义；以及最后，方法Process将指令参数的文本表示编译/翻译为该指令所管理的信息。SI方法将对Abstract Machine State的引用作为参数进行接收。
Abstract Instruction Set定义可由程序进行管理的指令集。该组件可以是目录名、指令名的枚举集、包、模块，等等……在Abstract Instruction Set接口中定义的操作只关心所选择的表示法。
Abstract Program定义汇编程序的通用接口。CurrentInst操作被用于访问将要被执行的指令。此外，LoadProgram操作负责构建将要被加入程序中的Concrete Instruction对象。
4. 作为模板参数的AbstractDataArea、AbstractProgram和AbstractInstruction。在类C++语法中，如下所示：
class AbstractInstruction
{ .. }
template
class AbstractProgram <class AbstractInstruction>
{ .. }
class AbstractDataArea
{ .. }
template
class AbstractMachineState < class AbstractDataArea,
class AbstractProgram <AbstractInstruction>>
{ .. }
5. 省略Abstract-Machine State类。它与MEDIATOR模式的情况类似[4]。
6. 原始操作（Primitive operation）。在Abstract DataArea、Abstract Program和Abstract Instruction中定义的一些操作是原始的。因而，它们必须被重新定义。例如，它们可以被声明为纯虚函数（C++方法），或是接口的一部分（Java方法）。在Abstract-Machine State中的操作Init、Transition和Stop不能被重新定义。
示例代码
下面的示例代码给出了抽象机模式的某些部分的Java实现。
1. 首先，我们定义对应于Abstract DataArea、Abstract Program和Abstract Instruction的各个接口（见实现部分）。
2. 一个抽象类（在C++或Java行话中）意味着Abstract Program的一种可选实现。在此例中，抽象类可以提供一些额外的功能（例如，程序计数器P和指令集）。
import AbstractInstruction;
import AbstractInstructionSet;
public abstract class AbstractProgram
{
public int P;
private Vector program; // A container of AbstractInstruction
private AbstractInstructionSet instSet;
AbstractProgram (AbstractInstructionSet instSet)
{
this.instSet = instSet;
}
public void Init ()
{
P = <<init program address>>;
Program = new Vector ();
}
public void LoadProgram (Stream assemblerCode)
{
<< load instructions from the assembler code >>
}
public AbstractInstruction CurrentInst ()
{
return program.Get (P);
}
public void Next ()
{
P++;
}
abstract public boolean Stop ();
}
3. Abstract Machine Factory的实现：
import AbstractDataArea;
import AbstractProgram;
public interface AbstractMachineFactory
{
public AbstractDataArea CreateDataArea ();
public AbstractProgram CreateProgram ();
}
4. Abstract Machine State的实现：
import AbstractDataArea;
import AbstractProgram;
import AbstractInstruction
public class AbstractMachineState
{
private AbstractDataArea da;
private AbstractProgram prog;
public AbstractMachineState (AbstractMachineFactory factory)
{
prog = factory.CreateProgram();
da = factory.CreateDataArea();
}
public AbstractDataArea DataArea ()
{
return da;
}
public AbstractProgram Program ()
{
return prog;
}
public void Init (Stream s)
{
da.Init ();
prog.Init ();
prog.LoadProgram (s);
}
public boolean Stop ()
{
return prog.Stop () && da.Stop();
}
public void Transition ()
{
while (!Stop ())
{
prog.CurrentInst().SI (this);
}
}
}
5. 要创建具体的Abstract Machine State（例如，在动机部分描述的WAM抽象机），你可以采用下面的一系列指令：
import AbstractStateMachine;
import WAM_Factory;
import WAM_InstructionSet;
class WAM_Client
{
static public void main (String args []) throws IOException
{
FileInputStream targetCode = new FileInputStream (arg [0]);
WAM_Factory factory = new WAM_Factory ();
AbstractMachineState machine = new AbstractMachineState (factory);
machine.Init (targetCode);
machine.Transition ();
}
}
6. 如图1所示，WAM State数据区被定义为一些数据组件的集合（也就是，OrStack、Heap和Registers）。
import OrStack;
import Heap;
import Registers
public class WAM_DataArea implements AbstractDataArea
{
public OrStack orStack;
public Heap heap;
public Registers regs;
public WAM_DataArea ()
{
orStack = new OrStack ();
heap = new Heap ();
regs = new Registers ();
}
public void Init ()
{
orStack.Init ();
heap.Init ();
regs.Init ();
}
public boolean Stop ()
{
return true;
}
}
7. 在WAM Program这一边，它被定义为Abstract Program的实例，用于具体的WAM Instruction Set。而且，WAM Program用一个新的程序计数器（CP）扩展了Abstract Program。
public class WAM_Program extends AbstractProgram
{
public int CP; file://
WAM_Program (AbstractInstructionSet instSet)
{
super (instSet);
}
public void Init ()
{
P = 0;
CP = 0;
}
public int Consult_CP ()
{
return CP;
}
public boolean Stop ()
{
return CurrentInst().Name().equals (“stop”);
}
}
8. 最后，我们描述WAM指令集中的一些指令的例子。让我们设想下面的每一条指令是怎样通过更改WAM State（也就是，WAM DataArea和/或WAM Program）来实现它的语义的（WAM抽象机是怎样演变的）。
a) 下面的代码描述WAM指令“allocate n”的Java实现。该指令的执行（它的语义）在WAM抽象机的or-stack中分配n个未使用的变量。然后，该指令将程序计数器移向下一条指令（调用WAM Program上的Next）。
public class Allocate implements AbstractInstruction
{
private int numVars = 0;
Allocate ()
{}
public String Name ()
{
return “allocate”;
}
public int NumArguments ()
{
return 1;
}
public String ToString ()
{
return Name() + “ “ + numVars;
}
public void SI (AbstractMachineState state)
{
WAM_DataArea WAM_da = (WAM_DataArea) state.DataArea();
WAM_Program WAM_prog = (WAM_Program) state.Program();
// Implementation of allocate semantics
WAM_da.orStack.Push (numVars);
WAM_prog.Next();
}
public void Process (String args[] )
{
// Proces the text representation of the instruction
// arguments into an int value.
numVars = Integer.valueOf (args [0]).intValue();
}
}
b) 下面的代码描述WAM指令“call <addr>”的Java实现。它的执行意味着将CP的当前值拷贝进OrStack（在数据区中），将CP的计数器值赋给P，然后，将计数器P赋给progAddr。
public class Call implements AbstractInstruction
{
private int progAddr;
...
public void SI (AbstractMachineState state)
{
WAM_DataArea WAM_da = (WAM_DataArea) state.DataArea();
WAM_Program WAM_prog = (WAM_Program) state.Program();
// Implementation of call semantics
WAM_da.orStack.Set_CP (WAM_prog.CP);
WAM_prog.CP = P;
WAM_prog.P = progAddr;
}
...
}
c) 现在设想call指令的一个新版本，它能够支持可视化工具。我们从前面的类派生一个新的ViewCall类，并重定义SI操作如下：
public class ViewCall extends Call
{
public void SI (AbstractMachineState state)
{
super.SI (state); // Execute the Call semantics
state.notify (); // Notify the change and redraw
}
}
已知使用
本文所介绍的模式已被用于形式化及实现Prolog语言的一种抽象编译器[2]。作为此工作的成果，我们已经获得了一种基于抽象机技术的多阶段编译方法。此外，我们还发现抽象机模式十分适于以一种非侵入式的方式、轻易地在抽象机中包含可视化工具和调试机制及工具[3]。
相关模式
在[5]中介绍的工作研究了用于构建虚拟机的模式语言的定义。与[5]不同，我们的建议更为聚焦于提供更高级的设计构架，而不是那么多地描述虚拟机的低级层面。
抽象机模式结合了在[4]中介绍的一些模式：
l Abstract Machine State，MEDIATOR模式的一种变种，就属于这种情况，
l Abstract Machine Factory和Abstract Instruction Set属于ABSTRACT FACTORY模式，
l 另一方面，在SI操作（在Abstract Instruction中）的后面有着一种隐藏的STRATEGY模式，以及
l 最后，在Abstract Machine State中的Init、Transition和Stop操作是TEMPLATE METHOD模式的明显实例。
参考文献
[1] Arnold & Gosling. The Java Programming Language. Addison-Wesley, Reading, Massachusetts, 1996.
[2] García J. & Moreno J.J. Visualization as Debugging : Understanding/Debugging the WAM, Automated and Algoritmic Debugging (AADEBUG'93), Lecture Notes in Computer Science (LNCS 749), Springer-Verlag, 1993.
[3] García J. & Moreno J.J. A Formal Definition of an Abstract Prolog Compiler, AMAST'93. Workshops in Computer Science, Lecture Notes in Artificial Intelligence (LNAI), Springer-Verlag, 1993.
[4] Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides. Design Patterns. Elements of reusable object-oriented software. Addison-Wesley, Reading, MA, 1995.
[5] Jacobsen, E.E. & Nowack, P. A Pattern Language for Building Virtual Machines. 2th European Conf. Pattern Languages of Programming, Irse (Germany) , July 1996.
[6] Reade, C, Elements of Functional Programming, Addison-Wesley, 1989.
[7] Warren, D. H.D, An Abstract Prolog Instruction Set. Tec. Note 309, SRI International, Menlo Park, California, October 1983.
[1]LSIIS Department, Facultad de informática, Campus de Montegancedo, Boadilla del Monte, 28660 Madrid, Spain. Email:juliog@fi.upm.es
[2]在过去，在Java的兴盛很久以前，许多有关说明性编程（declarative programming）的工作已经指出，抽象机作为常用的实现技术的一项替代在编译语言上的成功。像Prolog[7]或SML[6]这样的例子是通过抽象机来实现高性能编程语言的好例子。在今天，使用“虚拟机”进行表达已经非常普遍。
