论文部分内容阅读
摘要：函数式程序设计语言具有程序简洁，易于进行推理和正确性证明等优点。抽象机技术完成函数式程序设计语言的规约计算到传统体系结构的状态转移计算之间的转换，是函数式语言编译技术的核心。本文基于Spineless G-Machine抽象机的图规约机模型，并在其基础上进行了改进，通过增加闭包，构造全懒惰表达式等，得到了一个更容易理解和易于优化的抽象机模型。并且在此模型上使用了扩展MKAP指令和G-code窥孔优化等方法提高抽象机的效率。
关键词：函数式语言；图规约；抽象机；G-Machine
中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)20-30311-03
Research on G-Machine Technology in Functional Language Compiler
CHEN Zi-xin
(City College Of DongGuan University of Technology,Dongguan 523106,China)
Abstract:In this paper Spineless G-Machine is improved to gain the advantages of STG-Machine but remain the operational semantics of Spineless G-Machine codes.This model is easier to understand and explore optimization space than STG-Machine. Based on this improved Spineless G-Machine, some optimizations on the abstract machine codes are added to explore the improve space,including extend the MKAP instruction and G-code peephole optimizations.
Key words:Functional language;graph reduction;abstract machine;G-Mach
1 前言
随着计算机软件变得越来越复杂，软件的结构化也越来越重要。良好结构的软件应该容易编写、容易调试并且能提供一系列可以重用的模块以减少将来编程的重复工作，这些需要也对程序设计语言提出了新的要求。传统的计算机基于指令集的串行执行，这种计算模型已经存在了很久，并且为大家所熟悉，该计算模型也深刻的影响了程序设计语言，以致直到現在我们也在一定程度上总把程序看成是传统指令序列的高级表示。[1]但是传统的程序设计语言从概念上限制了问题的模块化。于是程序设计语言发展的一个趋势是：把编写程序的模型与计算机底层的计算模型分离开，牺牲一些程序的执行效率，换取程序的简单与清晰。
函数式程序设计就是这样一种计算模型的尝试，它是一种强调表达式求值而不是执行命令的程序设计风格。在这样的语言中表达式由函数将基本的数值联合起来构成。目前限制函数式语言推广的一个重要原因是在传统的冯诺依曼体系结构的计算机上,函数式语言的执行效率不高。因此通过编译器来优化程序，生成高效代码，对函数式语言来说至关重要。
本文研究了函数式语言编译技术，特别是对函数式语言的G-Machine编译模型进行了分析。然后在Spineless G-Machine抽象机的图规约机模型的基础上进行改进，通过增加闭包，构造全懒惰表达式等方法，得到了一个更容易理解和易于优化的抽象机模型。并且在此模型上使用了扩展MKAP指令和G-code窥孔优化等方法进一步提高了抽象机的效率。通过上述改进，本文得到了一种比传统STG-Machine更高效的混合G-Machine模型。
2 函数式语言的编译技术
函数式语言（functional language或者applicative language）是支持和鼓励用函数式风格编写程序的一类语言。 函数式语言的程序由“纯函数”（pure functions）构成，纯函数的一个特点是没有副作用（side effect）即纯函数的计算不会改变计算的环境，就是说函数式程序中没有“状态”这一传统程序设计的基本概念。和其它的语言模型相比，函数语言有如下特征：
(1)函数式语言式以问题为导向的，它是从“what”的角度来描述问题，而命令式的语言（C，Pascal，Java）是从“how”的角度来解决问题。因此，函数式语言对问题的描述更接近问题本身。
(2)函数式语言的数学基础－－λ演算，具有非常简洁的表示方式。λ演算在定理证明方面相对与命令式语言有优势。
(3)纯的（pure）函数式语言没有副作用（Side-effects），即程序或者函数的输出完全由输入决定，而与系统的状态无关。函数式语言的可并行性和代码复用性大大超过了其它语言类型。[2]
2.1 λ演算
λ演算对计算机科学具有重要的意义，它提供函数的表示和转换规则，是函数式程序设计的数学基础，多数函数式语言编译器都采用λ演算或扩展的λ演算作为编译器的内部核心语言。λ演算中的计算通过规约来表示，它不同于冯诺依曼体系结构的状态转移模型。
简单地说，λ演算提供了一种匿名函数地表达式，语法如下：
<λ expression> ::=
|
|λ.<λ expression>
|<λ expression><λ expression>
定义了两个基本的归约（reduction）：δ归约和β归约。
δ归约：可看成是函数应用的计算，比如+13→δ4（即1+3可归约为4，函数‘+’在这里用前缀表示法）
β归约：可看成λ抽象的应用，比如（λx*xx）2→δ*22
函数式语言的执行过程就是对表达式的计算，即利用两种规约把表达式简化为最终需要结果的过程。规约的效率直接关系到函数式程序的执行效率。经典的规约方法有：串规约（string reduction）、标准环境规约（standrad environment reduction）、图规约（graph reduction）等。可选择的方法也更多，通常有SECD抽象机、图规约机、基于组合子的图规约机等。
图规约的思想是：用图来表示λ表达式，并通过图的转化规则来完成λ表达式的求值。其优点是：公共表达式容易共享，不需要特殊的结构来保存环境，表达清晰并且效率相对较高。
组合子是一种特殊的函数，它具有和原始函数一样的常量特征。组合子可以看成不包括自由变量的λ表达式，如何可计算函数都能转换成组合子的应用。基于组合子的图规约机是目前使用广泛的函数式语言的编译方法。在此基础上进一步提高对公共表达式的优化又提出了超组合子（super-combinators）和范畴逻辑（categorical combinatory logic）等方法。
一般的函数转换为组合子描述后具有如下的形式：
f1x1…xn1=e1
…
fmx1…xm1=em
e0
其中f1…fm是超组合子的定义，e0是要计算的表达式。
2.2 G-Machine及其演化
G-Machine[3]的出现极大地提高了图规约的效率，它注意到超组合子能够被编译成固定的指令序列，顺序执行这些指令能建立超组合子的应用实例。并且G-Machine为更多的优化提供了机会。
G-Machine的核心部分是一个栈，用来保存局部变量的绑定和结合函数（组合子）应用时的形式参数与实际参数，它的每个元素式一个指向图的指针。抽象机定义了一系列的栈操作和图操作的指令集。
G-Machine的一个缺点是几乎所有的优化都关注于使每一步规约更高效，每次规约完成后图的表示都被升级作为下一次规约的初始状态。Spineless G-Machine[4]的提出提高了规约的效率，它只在有可能失去共享（loss of sharing）时才对图进行升级。它即保留了全懒惰性规约的特性，又省略了无用的中间操作。
Spineless G-Machine进一步发展的结果是Spineless Tagless G-Machine（STG-Machine）。STG-Machine增加了很多新特点：
(1)STG-Machine抽象机语言本身就是一种简单的函数式语言，它具有通常的指称语义（denotation semantics），并且每个语言成分又一个直接的操作语义。
(2))直接操作unboxed value，执行效率高。
(3)采用严格性分析（strictness analysis）和共享分析（sharing analysis）改进执行效率。
(4)没有采用其他函数式编译技术常用的λ提升技术。
(5)STG-Machine很适合并行的实现。
3 G-Machine编译技术的改进
Spineless Tagless G-Machine是当前最先进的抽象机之一，但是它也具有明显的缺点：没有更多的优化空间。每个语言成分有一个直接的操作语义的特点使得语言成分之间的关系相互独立，不易于针对其联系进行改进。基于上述原因，本文中没有直接采用基于STG-Machine的抽象机，而是改造Spineless G-Machine的操作语义，通过增加闭包，表达式全懒惰构造使其具有和STG-Machine类似的优点。由此得到一个比STG-Machine更容易理解和改进的抽象机。在此模型上，可以进行一些STG-Machine上无法完成的优化工作。
3.1 增加闭包
高阶语言（high order language）的实现中必须要提供一种表示函数的方法，这种表示可以被看成一种挂起的计算（suspended computation），当它应用到参数上时完成计算。
STG-Machine中采用了一種很紧凑的方式表示函数：静态的代码（被所有实例共享）和自由变量合在一起表示函数，通常这种结构叫做闭包（closure）。闭包物理上是一块在堆中分配的内存，它包含一个指向静态代码的指针合指向自由变量的指针，静态代码执行时会访问闭包中指向的自由变量。
不让函数的静态代码直接访问自由变量的理由是：闭包存在的时间通常比创建它的环境（stack frame）长，因此当闭包被计算时它需要的自由变量很可能已经不在栈里了。
例如：
f=let
x1 = E1
in
f1 x =
let
x2 = E2
in
+ x1 (+x2 x)
当f的表示构造好的时候x1，x2已经不在栈里了，以后f可能多次被用到，通过闭包，能保留x1，x2的指针以访问自由变量。为了使Spineless G-Machine能够不进行λ提升，我们在抽象机中引入了闭包。
3.2 表达式全懒惰构造
G-Machine和Spineless G-Machine虽然实现了惰性计算，即表达式只有在真的需要知道其值的时候才会被计算到。但是他们有一个缺点，不管表达式会不会被计算到，表达式的图表示总是会被创建，而且图创建的开销使运行时的。这极大地降低了抽象机的效率。
例如表达式：f x y = g E1 E2
其中E1，E2为任意表达式。无论如果函数g值使用其中一个参数，甚至不使用任何一个参数，图都会被创建成一个复杂的结构。
TIM（Tree Instruction Machine）[6]的出现节省了这样无用的工作。它引入了两个辅助函数c1，c2：
f x y = g (c1 x y) (c2 x y)
c1 x y = E1
c2 x y = E2
这些做的好处是无论E1，E2有多么复杂，f x y规约时只需要构造(c1 x y)，(c2 x y)就即可。另外，在G-Machine中，f x y = g E1 E2中E1和E2将被C scheme编译，而c1 x y = E1和c2 x y = E2将被E scheme编译，E scheme中的优化（B scheme）将会被用到。
如果参数个数很多的时候，可以把所有的参数放在一个元组（tuple）中，并让辅助函数共享。上述表达式则变为：
f x y =
let
tup = (x, y)
c1 x y = E1
c2 x y = E2
in
g (c1 x y) (c2 x y)
上述变换在文本中称之为表达式全懒惰构造，完成该变换后Spineless G-Machine和STG-Machine的行为已经十分类似。不同的是本文的抽象机仍然采用先编译各种语言成分到G-code，然后在抽象机上执行G-code的运行模式。
3.2.1. 扩展MKAP指令
观察G-Machine生成的代码序列，在构造表达式的时候能看到几个PUSH，PUSHINT操作后面紧跟几个MKAP操作。例如：C[let x = 5 in + x x ] r 0 ＝PUSHINT 5; PUSH 0; PUSH 1; PUSHFUN +; MKAP; MKAP; SLIDE 1。可以看出，PUSH 0和PUSH 1的作用仅仅是为了让MKAP能够找到正确的指针，他们入栈后马上出栈，这包含了一些多余的操作。下面的方法扩展了MKAP指令，减少了栈操作。
引入一个新的操作MKAP_EX(n,m,pop)，它的作用是创建一个新的应用节点，用栈中TOS-n位置指向的图作为其左子树（函数），用TOS-m位置指向的图作为其右子树（参数），然后从栈中弹出pop个元素（pop=0,1,2），然后把新的应用节点的指针入栈。由此上例可变为：C[let x = 5 in + x x ]r 0 = PUSHINT 5; PUSHFUN x; MKAP_EX(0,1,1); MKAP_EX(0,1,1); SLIDE 1。可以看出减少了2个PUSH操作，从而减少了栈的使用。
3.3 G-code窥孔优化
把各种语言成分先编译成G-code的好处是能在抽象机一级进行代码变换，可以对G-code序列进行窥孔优化（peephole optimization）：
(1)G-Machine产生的代码有时候会包含连续的SLIDE操作，根据SLIDE的定义：将TOS向下滑动m个位置，可以把相邻的SLIDE合并，即SLIDE(m); SLIDE(n)用SLIDE(n+m)代替。
(2)在栈中生存周期很短的指针，可以经过寄存器來中转，减少栈的操作。
(3)如果PUSH操作后紧跟GET操作，可以直接把要入栈的图压入操作数栈，这样可以减少对栈的连续PUSH和POP操作。
改进的抽象机模型为G-code级的优化提供了很好的基础。很多源码级的优化技术可以极大提高抽象机的效率。
4 结束语
本文主要研究了函数式语言的编译技术，特别是实现规约计算模型到状态转移计算模型之间变换的抽象机技术。本文在Spineless G-Machine抽象机模型的基础上进行改进，得到了一个更容易理解和易于优化的抽象机模型。
本文强调了对抽象机代码序列的优化，以得到更多的优化机会。实现编译器对Spineless G-Machine的改进，包括引入闭包和表达式全懒惰构造变换，使其具有STG-Machine的优点，同时又可以尝试在抽象机代码上的优化工作，其中包括扩展MKAP指令和窥孔优化。
参考文献：
[1] A.J.Field and P.G.Harrison, Functional Programming: Addison-Wesley,1988.
[2] J.Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of program, Commun.ACM,1978(21):613-641.
[3] T.Johnsson,Efficient compilation of lazy evaluation,in Proceedings of the 1984 SIGPLAN symposium on Compiler construction. Montreal, Canada: ACM Press,1984.
[4] G.L.Burn, S.L.P.Jones, and J.D.Robson, “the spineless G-machine”, ub Proceedings of the 1988ACM conference on LISP and functional programming. Snowbird, Utah, United States: ACM Press, 1988
[5] W.Taha, Multi-Stage Programming: Its Theory and Applications, 1999, PhD thesis, Oregon Graduate Institute School of Science and Engineering.
[6] S.P.Jones and D.Lester, Implementing functional languages: a tutorial: Prentice Hall,1992.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”
关键词：函数式语言；图规约；抽象机；G-Machine
中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)20-30311-03
Research on G-Machine Technology in Functional Language Compiler
CHEN Zi-xin
(City College Of DongGuan University of Technology,Dongguan 523106,China)
Abstract:In this paper Spineless G-Machine is improved to gain the advantages of STG-Machine but remain the operational semantics of Spineless G-Machine codes.This model is easier to understand and explore optimization space than STG-Machine. Based on this improved Spineless G-Machine, some optimizations on the abstract machine codes are added to explore the improve space,including extend the MKAP instruction and G-code peephole optimizations.
Key words:Functional language;graph reduction;abstract machine;G-Mach
1 前言
随着计算机软件变得越来越复杂，软件的结构化也越来越重要。良好结构的软件应该容易编写、容易调试并且能提供一系列可以重用的模块以减少将来编程的重复工作，这些需要也对程序设计语言提出了新的要求。传统的计算机基于指令集的串行执行，这种计算模型已经存在了很久，并且为大家所熟悉，该计算模型也深刻的影响了程序设计语言，以致直到現在我们也在一定程度上总把程序看成是传统指令序列的高级表示。[1]但是传统的程序设计语言从概念上限制了问题的模块化。于是程序设计语言发展的一个趋势是：把编写程序的模型与计算机底层的计算模型分离开，牺牲一些程序的执行效率，换取程序的简单与清晰。
函数式程序设计就是这样一种计算模型的尝试，它是一种强调表达式求值而不是执行命令的程序设计风格。在这样的语言中表达式由函数将基本的数值联合起来构成。目前限制函数式语言推广的一个重要原因是在传统的冯诺依曼体系结构的计算机上,函数式语言的执行效率不高。因此通过编译器来优化程序，生成高效代码，对函数式语言来说至关重要。
本文研究了函数式语言编译技术，特别是对函数式语言的G-Machine编译模型进行了分析。然后在Spineless G-Machine抽象机的图规约机模型的基础上进行改进，通过增加闭包，构造全懒惰表达式等方法，得到了一个更容易理解和易于优化的抽象机模型。并且在此模型上使用了扩展MKAP指令和G-code窥孔优化等方法进一步提高了抽象机的效率。通过上述改进，本文得到了一种比传统STG-Machine更高效的混合G-Machine模型。
2 函数式语言的编译技术
函数式语言（functional language或者applicative language）是支持和鼓励用函数式风格编写程序的一类语言。 函数式语言的程序由“纯函数”（pure functions）构成，纯函数的一个特点是没有副作用（side effect）即纯函数的计算不会改变计算的环境，就是说函数式程序中没有“状态”这一传统程序设计的基本概念。和其它的语言模型相比，函数语言有如下特征：
(1)函数式语言式以问题为导向的，它是从“what”的角度来描述问题，而命令式的语言（C，Pascal，Java）是从“how”的角度来解决问题。因此，函数式语言对问题的描述更接近问题本身。
(2)函数式语言的数学基础－－λ演算，具有非常简洁的表示方式。λ演算在定理证明方面相对与命令式语言有优势。
(3)纯的（pure）函数式语言没有副作用（Side-effects），即程序或者函数的输出完全由输入决定，而与系统的状态无关。函数式语言的可并行性和代码复用性大大超过了其它语言类型。[2]
2.1 λ演算
λ演算对计算机科学具有重要的意义，它提供函数的表示和转换规则，是函数式程序设计的数学基础，多数函数式语言编译器都采用λ演算或扩展的λ演算作为编译器的内部核心语言。λ演算中的计算通过规约来表示，它不同于冯诺依曼体系结构的状态转移模型。
简单地说，λ演算提供了一种匿名函数地表达式，语法如下：
<λ expression> ::=
|
|λ
|<λ expression><λ expression>
定义了两个基本的归约（reduction）：δ归约和β归约。
δ归约：可看成是函数应用的计算，比如+13→δ4（即1+3可归约为4，函数‘+’在这里用前缀表示法）
β归约：可看成λ抽象的应用，比如（λx*xx）2→δ*22
函数式语言的执行过程就是对表达式的计算，即利用两种规约把表达式简化为最终需要结果的过程。规约的效率直接关系到函数式程序的执行效率。经典的规约方法有：串规约（string reduction）、标准环境规约（standrad environment reduction）、图规约（graph reduction）等。可选择的方法也更多，通常有SECD抽象机、图规约机、基于组合子的图规约机等。
图规约的思想是：用图来表示λ表达式，并通过图的转化规则来完成λ表达式的求值。其优点是：公共表达式容易共享，不需要特殊的结构来保存环境，表达清晰并且效率相对较高。
组合子是一种特殊的函数，它具有和原始函数一样的常量特征。组合子可以看成不包括自由变量的λ表达式，如何可计算函数都能转换成组合子的应用。基于组合子的图规约机是目前使用广泛的函数式语言的编译方法。在此基础上进一步提高对公共表达式的优化又提出了超组合子（super-combinators）和范畴逻辑（categorical combinatory logic）等方法。
一般的函数转换为组合子描述后具有如下的形式：
f1x1…xn1=e1
…
fmx1…xm1=em
e0
其中f1…fm是超组合子的定义，e0是要计算的表达式。
2.2 G-Machine及其演化
G-Machine[3]的出现极大地提高了图规约的效率，它注意到超组合子能够被编译成固定的指令序列，顺序执行这些指令能建立超组合子的应用实例。并且G-Machine为更多的优化提供了机会。
G-Machine的核心部分是一个栈，用来保存局部变量的绑定和结合函数（组合子）应用时的形式参数与实际参数，它的每个元素式一个指向图的指针。抽象机定义了一系列的栈操作和图操作的指令集。
G-Machine的一个缺点是几乎所有的优化都关注于使每一步规约更高效，每次规约完成后图的表示都被升级作为下一次规约的初始状态。Spineless G-Machine[4]的提出提高了规约的效率，它只在有可能失去共享（loss of sharing）时才对图进行升级。它即保留了全懒惰性规约的特性，又省略了无用的中间操作。
Spineless G-Machine进一步发展的结果是Spineless Tagless G-Machine（STG-Machine）。STG-Machine增加了很多新特点：
(1)STG-Machine抽象机语言本身就是一种简单的函数式语言，它具有通常的指称语义（denotation semantics），并且每个语言成分又一个直接的操作语义。
(2))直接操作unboxed value，执行效率高。
(3)采用严格性分析（strictness analysis）和共享分析（sharing analysis）改进执行效率。
(4)没有采用其他函数式编译技术常用的λ提升技术。
(5)STG-Machine很适合并行的实现。
3 G-Machine编译技术的改进
Spineless Tagless G-Machine是当前最先进的抽象机之一，但是它也具有明显的缺点：没有更多的优化空间。每个语言成分有一个直接的操作语义的特点使得语言成分之间的关系相互独立，不易于针对其联系进行改进。基于上述原因，本文中没有直接采用基于STG-Machine的抽象机，而是改造Spineless G-Machine的操作语义，通过增加闭包，表达式全懒惰构造使其具有和STG-Machine类似的优点。由此得到一个比STG-Machine更容易理解和改进的抽象机。在此模型上，可以进行一些STG-Machine上无法完成的优化工作。
3.1 增加闭包
高阶语言（high order language）的实现中必须要提供一种表示函数的方法，这种表示可以被看成一种挂起的计算（suspended computation），当它应用到参数上时完成计算。
STG-Machine中采用了一種很紧凑的方式表示函数：静态的代码（被所有实例共享）和自由变量合在一起表示函数，通常这种结构叫做闭包（closure）。闭包物理上是一块在堆中分配的内存，它包含一个指向静态代码的指针合指向自由变量的指针，静态代码执行时会访问闭包中指向的自由变量。
不让函数的静态代码直接访问自由变量的理由是：闭包存在的时间通常比创建它的环境（stack frame）长，因此当闭包被计算时它需要的自由变量很可能已经不在栈里了。
例如：
f=let
x1 = E1
in
f1 x =
let
x2 = E2
in
+ x1 (+x2 x)
当f的表示构造好的时候x1，x2已经不在栈里了，以后f可能多次被用到，通过闭包，能保留x1，x2的指针以访问自由变量。为了使Spineless G-Machine能够不进行λ提升，我们在抽象机中引入了闭包。
3.2 表达式全懒惰构造
G-Machine和Spineless G-Machine虽然实现了惰性计算，即表达式只有在真的需要知道其值的时候才会被计算到。但是他们有一个缺点，不管表达式会不会被计算到，表达式的图表示总是会被创建，而且图创建的开销使运行时的。这极大地降低了抽象机的效率。
例如表达式：f x y = g E1 E2
其中E1，E2为任意表达式。无论如果函数g值使用其中一个参数，甚至不使用任何一个参数，图都会被创建成一个复杂的结构。
TIM（Tree Instruction Machine）[6]的出现节省了这样无用的工作。它引入了两个辅助函数c1，c2：
f x y = g (c1 x y) (c2 x y)
c1 x y = E1
c2 x y = E2
这些做的好处是无论E1，E2有多么复杂，f x y规约时只需要构造(c1 x y)，(c2 x y)就即可。另外，在G-Machine中，f x y = g E1 E2中E1和E2将被C scheme编译，而c1 x y = E1和c2 x y = E2将被E scheme编译，E scheme中的优化（B scheme）将会被用到。
如果参数个数很多的时候，可以把所有的参数放在一个元组（tuple）中，并让辅助函数共享。上述表达式则变为：
f x y =
let
tup = (x, y)
c1 x y = E1
c2 x y = E2
in
g (c1 x y) (c2 x y)
上述变换在文本中称之为表达式全懒惰构造，完成该变换后Spineless G-Machine和STG-Machine的行为已经十分类似。不同的是本文的抽象机仍然采用先编译各种语言成分到G-code，然后在抽象机上执行G-code的运行模式。
3.2.1. 扩展MKAP指令
观察G-Machine生成的代码序列，在构造表达式的时候能看到几个PUSH，PUSHINT操作后面紧跟几个MKAP操作。例如：C[let x = 5 in + x x ] r 0 ＝PUSHINT 5; PUSH 0; PUSH 1; PUSHFUN +; MKAP; MKAP; SLIDE 1。可以看出，PUSH 0和PUSH 1的作用仅仅是为了让MKAP能够找到正确的指针，他们入栈后马上出栈，这包含了一些多余的操作。下面的方法扩展了MKAP指令，减少了栈操作。
引入一个新的操作MKAP_EX(n,m,pop)，它的作用是创建一个新的应用节点，用栈中TOS-n位置指向的图作为其左子树（函数），用TOS-m位置指向的图作为其右子树（参数），然后从栈中弹出pop个元素（pop=0,1,2），然后把新的应用节点的指针入栈。由此上例可变为：C[let x = 5 in + x x ]r 0 = PUSHINT 5; PUSHFUN x; MKAP_EX(0,1,1); MKAP_EX(0,1,1); SLIDE 1。可以看出减少了2个PUSH操作，从而减少了栈的使用。
3.3 G-code窥孔优化
把各种语言成分先编译成G-code的好处是能在抽象机一级进行代码变换，可以对G-code序列进行窥孔优化（peephole optimization）：
(1)G-Machine产生的代码有时候会包含连续的SLIDE操作，根据SLIDE的定义：将TOS向下滑动m个位置，可以把相邻的SLIDE合并，即SLIDE(m); SLIDE(n)用SLIDE(n+m)代替。
(2)在栈中生存周期很短的指针，可以经过寄存器來中转，减少栈的操作。
(3)如果PUSH操作后紧跟GET操作，可以直接把要入栈的图压入操作数栈，这样可以减少对栈的连续PUSH和POP操作。
改进的抽象机模型为G-code级的优化提供了很好的基础。很多源码级的优化技术可以极大提高抽象机的效率。
4 结束语
本文主要研究了函数式语言的编译技术，特别是实现规约计算模型到状态转移计算模型之间变换的抽象机技术。本文在Spineless G-Machine抽象机模型的基础上进行改进，得到了一个更容易理解和易于优化的抽象机模型。
本文强调了对抽象机代码序列的优化，以得到更多的优化机会。实现编译器对Spineless G-Machine的改进，包括引入闭包和表达式全懒惰构造变换，使其具有STG-Machine的优点，同时又可以尝试在抽象机代码上的优化工作，其中包括扩展MKAP指令和窥孔优化。
参考文献：
[1] A.J.Field and P.G.Harrison, Functional Programming: Addison-Wesley,1988.
[2] J.Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of program, Commun.ACM,1978(21):613-641.
[3] T.Johnsson,Efficient compilation of lazy evaluation,in Proceedings of the 1984 SIGPLAN symposium on Compiler construction. Montreal, Canada: ACM Press,1984.
[4] G.L.Burn, S.L.P.Jones, and J.D.Robson, “the spineless G-machine”, ub Proceedings of the 1988ACM conference on LISP and functional programming. Snowbird, Utah, United States: ACM Press, 1988
[5] W.Taha, Multi-Stage Programming: Its Theory and Applications, 1999, PhD thesis, Oregon Graduate Institute School of Science and Engineering.
[6] S.P.Jones and D.Lester, Implementing functional languages: a tutorial: Prentice Hall,1992.
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”