动作编译器生成标准ML代码的方法和性能分析

理论计算机科学电子笔记141（2005）167-188www.elsevier.com/locate/entcs一个针对标准ML的约根·伊弗森计算机科学系1地址：Aarhus，Aabogade 34，DK-8200 Aarhus N，Denmark摘要我们提出了一个动作编译器，可用于与动作语义为基础的编译器生成器。我们的动作编译器生成的代码比其他动作编译器生成的代码执行速度更快，对于一些重要的测试示例，它只比Gnu C编译器生成的代码慢两倍。以标准ML为目标使得代码生成的描述简单且易于实现。动作编译器已经在标准ML的核心描述和C语言的子集关键词：编译器生成，动作语义，代码生成，标准ML1引言从语言的形式描述自动生成编译器并不总是导致高效的编译器。一个形式主义，支持易于建设的可读的，完整的，和可重用的描述，大多数编程语言，并在同一时间有工具支持自动生成高效的编译器似乎是不存在的。一种形式主义，试图满足这些要求的语言描述形式主义，并允许自动生成有效的编译器是动作语义（AS）[12，16]。高效编译器指的是产生快速代码的编译器，而不是运行速度快或产生小代码的编译器。基于AS的编译器生成器产生一个前端，该前端将所描述的语言中的每个程序映射到1计算机科学基础研究（http://www.brics.dk），由丹麦国家研究基金会资助。1571-0661 © 2005 Elsevier B.V. 在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.02.057168J. Iversen/Electronic Notes in Theoretical Computer Science 141（2005）167一个行动。然后前端连接到一个动作编译器，结果是所描述语言的编译器。以前的结果[20，21]表明，有可能生成比手写编译器生成的代码慢10倍的编译器，在某些情况下甚至慢两倍。为了达到这个效果，编译器对处理的动作进行了一些限制，并且动作编译器中代码生成器的实现通常非常复杂。我们提出了一个动作编译器，产生更有效的代码比以前的动作编译器，并在某些例子中，只有一个因素比Gnu C编译器产生的代码慢。代码生成器以直接的方式将动作转换为标准ML（SML）[15]。然后使用MLton2编译器将SML代码编译为可执行文件。动作编译器分几步注释和转换动作我们的动作编译器执行类型推断（第3节）和代码生成（第4节），但没有像以前的结果那样对动作进行优化。相反，我们生成的代码可以很容易地被MLton优化阅读论文时，熟悉AS和SML是一个优势，但不是先决条件。我们将在下一节中简要介绍动作语义。1.1动作语义学动作语义学是指称语义学和操作语义学的混合体。与传统的指称描述一样，归纳定义的语义函数映射程序（以及声明、表达式、语句等）。它们的外延，这模型他们的行为。不同之处在于，这里的表示是动作而不是高阶函数。编程语言的动作语义描述（ASD）必须描述语言的语法、将语言构造映射到动作的语义函数以及在语义函数中使用的语义实体。非平凡语言的ASD，如Java [6]和SML [11]，已经被构造出来。动作用动作符号（AN）[12，16]表示，这是一种类似于英语的符号，但仍然是严格形式的。AN由一个在操作上定义的内核组成; AN的其余部分可以简化为内核符号。操作由yielders、操作常量和操作组合子构成，其中yielders由数据、数据操作和谓词组成屈服者不是2http://www.mlton.org/J. Iversen/Electronic Notes in Theoretical Computer Science 141（2005）167169的内核。操作的执行可以被看作是对数据和数据绑定的函数的评估，附带的影响包括更改存储和发送消息。我们通常将动作的输入数据/绑定称为给定数据/绑定。动作组合子对应于不同的功能组合方式，以获得不同类型的控制和数据流。评估可以以三种不同的方式终止：正常（封闭操作的执行继续正常），突然（封闭操作被跳过，直到异常被处理）或失败（对应于放弃当前选择的替代方案并尝试替代操作）。AN具有表示表达式、声明、抽象、存储操作和代理之间通信的评估的动作。yielder可用于检查内存位置并计算数据和绑定。为了限制本文，我们不关心用于表示代理之间的通信的动作。表1列出了所有内核操作组合子和常量，以及简短的非正式解释。在图A中，范围是行动。行动解释副本返回给定的数据结果D返回数据D给O将数据运算符O应用于给定数据A1然后 A2A1的输出是A2的输入A1然后是 A2测序，结果串联a1和 a2交织，结果被级联不可分割AA不能与其他操作交错检查O如果O返回false则阿塞纳特返回一个随机的非负整数展开A迭代A（结合展开）展开执行最小封闭展开A的动作A扔突然终止，结果是给定的数据A1接 A2如果A1突然终止，则A2A1和-catch A2突然排序，结果被连接失败失败A1elseA 2如果A1失败，A2复制装订将当前绑定作为数据A1范围 A2由A1生成的绑定的作用域是A2递归地允许递归绑定在适用将给定操作应用于给定数据密切计算给定操作的闭包创建分配新位置检查检查给定位置的内容更新用给定数据表1内核AN图1给出了动作的示例。在行1中，分配包含随机非负整数的新存储器位置11在第3行中，标识符170J. Iversen/Electronic Notes in Theoretical Computer Science 141（2005）167--(1)（result x）(2)然后(3)（先创建，然后创建））(4)然后(5)(give））(6) 范围(7)复制装订“ 第4行将元组传递给第1.1行中的操作5，它将数据操作符绑定应用于它并返回绑定映射 x：11。这些绑定的作用域是第7行，它们只是在那里返回作为数据。Fig. 1. 动作示例1.2概述在第2节中，我们介绍了Action Environment，它在我们的编译器生成器中充当前端生成器。动作的类型推断是从动作生成有效代码的重要部分，也是第3节的主题。本文的主要贡献，即将动作转换为SML的规则，在第4节中描述。在第6节中评估动作编译器之前，我们先来看看第5节中以前关于编译动作的工作。第7节讨论了我们的动作编译器的局限性。第8节结束2行动环境Action Environment [4]是一个用于处理编程语言ASD的工具。它支持ASF+SDF [1，8]和ASDF [4，11]。编程语言的具体语法可以使用SDF中表示的任意上下文无关语法来描述。前缀构造函数形式的抽象语法和每个构造的动作语义可以使用ASDF来描述。为了将具体语法映射到抽象语法，可以使用ASF。使用ASF+SDF和ASDF，可以描述从语言的具体语法到动作的映射。图2显示了如何使用动作环境和语言规范将程序转换为动作。然后使用动作编译器和规范的ASDF部分将动作转换为SML。正如[4]中所解释的，这两种形式主义已经被用来描述标准ML语言的核心。J. Iversen/Electronic Notes in Theoretical Computer Science 141（2005）167171--SDFASFASDF程序行动装饰Parsetree行动装饰ABS. 语法行动装饰SML行动编译器行动图二、程序的转换在该环境中，可以导出解析表（用于与独立解析器连接使用）和方程（描述从具体语法到操作的映射，可由ASF评估器使用）。这使得将程序映射到独立于动作环境的动作成为可能。Action Environment是编译器生成器中的编译器前端生成器（前端包括词法分析、解析和转换到中间语言，在我们的例子中是AN）。将前端与动作编译器连接，我们就有了所描述语言的编译器。3类型推断推断动作的类型有两个主要目的。第一个目的是检查动作的类型。如果一个类型可以被推断，我们说这个动作是类型正确的。如果一个操作是类型正确的，则可以保证在操作的计算过程中，没有子操作被赋予意外类型的数据或绑定。例如，操作“result true then give +“类型不正确，因为子操作“give +“需要两个通过确保动作是类型正确的，不需要运行时类型检查，这提高了从动作生成的代码的效率另一个目的是提供有关操作的运行时行为的信息，以便在代码生成中使用。动作及其所有子动作都用动作类型进行了注释，正如我们稍后将看到的，一些代码生成规则使用这种类型信息。类型推理引擎在[10]中描述。动作类型的集合在图3中描述。动作类型（从非终结符类型派生的类型）是函数类型，其中域是一对记录类型，描述了数据类型和给予动作的绑定。我们使用一种记录类型，其中标签是数字来描述产品类型，即，1：integer，2：boolean对应integer *boolean。操作类型的共域是由两个记录组成的对172J. Iversen/Electronic Notes in Theoretical Computer Science 141（2005）167∅型号：：=（RecordType，RecordType）→（RecordType，RecordType）RecordType类型：：=：：={标签：类型，. ，标签：类型}|∅ActionType|RecordType|......这是什么？整数|布尔|标记（标签）|单元格（类型）|图三. 动作类型描述在正常或突然终止的情况下由动作产生的数据类型的类型。如果一个动作不能正常终止或突然终止，则使用特殊的记录类型“终止”来指示这一点。动作类型（{}，{x：cell（integer）}）→（{1：integer，2：token（a）}，n）描述了不期望数据的操作，以及“x“到整数存储单元的绑定这些操作可以正常终止，产生一个由整数和标记“a“组成的对3记录类型告诉我们动作不能突然终止。动作可以有类型，表明它们可以正常终止和突然终止，但当然不是在同一个计算中;类型只是说它们将以两种方式之一终止从非终结符Type派生的类型包含原子类型，如integer、boolean和token（Label）。它还包含记录类型，因为操作可以生成绑定作为输出数据，还包含操作类型，因为操作可以被视为数据。有比这里列出的更多的类型，包括用户在ASDF规范中定义的类型。类型推理引擎还使用来自ASDF规范的信息来确定数据和数据操作符的类型。action（result5@（{}，{}）→（{1：integerr}，n））然后throw@（{1：integer}，{}）→（，{1：integer}））@（{}，{}）→（，{1：integerr}）catchfail@（{1：integer}，{}）→（，））@（{}，{}）→（，）如何使用类型信息将在第4节中解释。知道我们将动作转换为SML，并且SML编译器进行类型推断，人们可能会想知道这种类型推断是否必要。如果SML代码可以在不知道类型的情况下生成，则SML编译器可以尝试推断类型，从而检查输入操作是否类型正确。这种方法的问题是，如果代码生成器不能利用类型注释，则生成的SML代码的效率会降低。为了给出一个例子，与组合子的翻译（规则4）3.描述token的类型是非常细粒度的，因为在推断操作所使用的绑定类型时，需要有关特定token值的知识J. Iversen/Electronic Notes in Theoretical Computer Science 141（2005）167173不第4节）使用关于其子动作产生的数据元组的大小的知识。如果没有这种知识，数据元组将不得不用列表来表示，这是效率较低的。4代码生成我们选择使用SML作为动作编译器的目标语言。以前的工作已经使用了AN汇编代码[21]，C [7，5]，Java [13，5]和定制的字节码语言[5]（见第5节），但我们发现从AN到SML的转换更自然，因为ANSML的形式语义应该使得证明生成的代码在语义上等价于目标操作相对容易。使用条件规则来描述转换，其中一些在图1A和1B中示出。4一个动作通过翻译它的子动作，然后组合产生的代码，从而捕获动作的语义（规则3说明了这一点），从而归纳地翻译为SML。每个操作都被转换为“fn”形式的匿名函数（t，b）=>E表达式E计算应用函数的结果，其对应于：响应评估操作时产生的数据。在这一节中，我们将介绍一些有代表性的规则;其余的可以在附录中找到我们将使用A来范围操作，O来范围数据操作符，E来范围SML表达式（例如， 匿名函数），d和I在SML标识符上进行范围，n在整数上进行范围，i和j在标签上进行范围，t在类型上进行范围。某些规则使用函数它执行一个操作并返回它的类型。 行动的类型当然是依赖于上下文的，并且是由前面的类型推断得出的。我们还将假设在一个动作中出现的所有标识符都被映射到不是SML中的保留字的标识符。4.1控制和数据流操作副本的翻译最简单（规则1），因为它只返回给它的数据。翻译结果D只是稍微复杂一点（规则2）;这里必须将操作产生的数据D翻译为SML表达E. 如果数据D是动作，则使用规则将其转换，在其他情况下，将其转换为数据的SML表示，例如，整数和布尔值只是被转换成相同的整数和布尔值。如thencombinator所描述的，动作的正常组合自然地转换为两个子动作的转换E1和E2将E1应用于给定数据和绑定的结果如下所示174J. Iversen/Electronic Notes in Theoretical Computer Science 141（2005）167T|·|copy−→fn（t，b）=>t（一）D−→EA2−→E2结果D−→fn（t，b）=>EA1−→E1（二）A1则A2−→fn（t， b）=>E2（E1（t，b）， b）n1 =的|normout（TA））|，n=A2−→E2（A1−→E11 2|normout（T（A））|2A1和-然后A2−→fn（t， b）=>（四）letval（d1， . ，dn1）=E1（t，b）;val（dn1+ 1， . ，dn1+n2）= E2（t，b）in（d1， . ，dn1+n2）结图四、控制和数据的正常流程与E1使用的绑定相同。另一种解决方案是在生成的代码前面加上函数= A2（A1（t，b），b）一类似的解决方案可以应用于某些其他代码规则，即规则不依赖于动作类型的情况。它不会改变生成代码的执行时间，也不会使翻译变得非常容易，因此为了保持代码规则的一致性，我们选择了另一种翻译。and-then组合子转换为let-in-end表达式（规则4）。此表达式可用于描述表达式局部的声明。对两个子动作的平移都进行评估在给定的数据和绑定上，得到的数据元组中的元素被绑定到变量d1， . ，dn1+n2，其中，数据元组当给定一个操作类型时，函数normout返回记录类型，描述在正常终止情况下操作产生的数据类型。运算符计算记录的大小，因此可以生成具有正确数量的d的元组模式normout（（A））的情况应该由其他规则处理，因为它表明部分操作将永远不会被计算。规则可以在附录中找到展开A和展开（图5中的规则6和规则5）的动作unfold的语义是它在最近的封闭展开A中计算动作A。unfolding的转换只是将A的转换绑定到标识符unf，所以unfolding的转换应该只是将绑定到unf的函数应用于给定的数据和绑定。由平移去折叠产生的函数是与unf绑定的函数。注意到J. Iversen/Electronic Notes in Theoretical Computer Science 141（2005）167175{}O−→EcheckO−→fn（t，b）=>I=excepid（{}）设val ch =E（t，b）（七）inif ch thent else raiseI（）端A1−→E1I= 例外02-02（图T）（A））（八）1A1catchA2−→fn（t， b）=>（E1（t，b）handleI et=>E2（et， b））unfold−→fn（t，b）=> unf（t，b）（五）A−→E展开A−→令val rec unf =E，UNF结束（六）图五. 迭代控制流程使用不要求unfold调用是尾递归的（就像以前的一些工作[7]中的情况一样），但是SML编译器能够在尾递归的情况下优化代码。见图6。 突变控制流AN中的突发数据流被转换为引发和处理SML异常（图6）。如果对给定数据应用数据运算符O的结果是布尔值false，则操作由于SML要求在使用之前声明异常，因此需要对整个操作进行一些预处理;对于表示由突然终止的子操作产生的数据类型的记录类型的每个唯一出现，都声明一个新的异常。绑定到记录类型的唯一异常名称由函数excepid在应用于记录类型时返回由于check在突然终止时不产生任何数据，因此赋予excepid的记录类型是空记录。 在生成的代码中，SML关键字raise用于引发异常。如果应用数据运算符（ch）的结果为真，则给定的数据（t）就是结果。为了处理突然终止，AN提供了动作组合子catch（规则8）。从它生成的代码使用SML关键字句柄来捕获由左侧表达式（E1（t，b））的求值引发的异常。handle右侧的模式当第一个表达式突然终止时的替代方案176J. Iversen/Electronic Notes in Theoretical Computer Science 141（2005）167复制绑定−→fn（t，b）=> bA1−→E1（九）A1作用域A2−→fn（t，b）=>E2（t，E1（t，b））A2−→E2{i1：t1，. . . ，in：tni}=binding gs（T（recursivelyA））A−→EB= {j1= r1，...，jnj = rnj}/{i1= refb1，.，Ini =refbni}{1：{j1：t1，. . . ，jn：tnj}}=no rmout（T（A））递归A−→让fn （d，{i1= bi，.，Ini = bni）=>端val rec rv1= fnx =>（rv1 x）;val r1= ref rv1;...valrecrvnj=fnx=>（rvnjx）;valrnj=refrvnj;val{j1= reff1，.，jnj = reffnj}= E（t，B）r1：=f1;...; rnj：=fnj;{j1= f1，.，jnj = fnj}（十一）在create−→fn（t，b）=>reft（十二）是 用 引 发 的 数 据 和 原 始 绑 定 计 算 第 二 个 表 达 式 。 类 型 操 作 符proximitout返回描述在突然终止的情况下由动作产生的数据的类型4.2装订和储存与绑定范围有关的操作如图7所示。动作复制绑定（规则9）类似于动作复制，因此生成的代码也类似。唯一的区别是，评估它的结果是给定的绑定，而不是给定的数据。见图7。 绑定的范围当比较组合子作用域（规则10）和then（规则3）时，可以看到相同的相似性。“A1 scope A2“中的第二子操作A2更有趣的是递归规则（规则11），这也是代码生成规则中最复杂的。当“递归地A“评估动作时，由子动作A产生的绑定也是g i v en到A的绑定的一部分。绑定b1给绑定s（T（recursivelyA）和由yA产生的绑定b2被组合通过让b2替代b1，结果给A。这一切都是递归的J. Iversen/Electronic Notes in Theoretical Computer Science 141（2005）167177→n = |normout（T（apply））|apply−→fn（（d1，. . . ，dn），b）=> d1（（d2，. . . ，dn），{}）close−→fn（a，b）=>fn（t，{}）=>a（t，b）（十三）声明，例如递归函数，在A中。为了捕捉这种相对复杂的语义，我们使用了一个技巧，将b 2域中的每个标识符绑定到一个包含“dummy”值的引用，并且b 1域中的每个标识符（但不在b 2域中）绑定到一个包含最初绑定到标识符的值的引用。然后将这些绑定提供给从A生成的代码，这将产生新的绑定。最后，这些绑定用于用正确的值更新包含伪值的引用。使用无限递归函数作为哑值确保所有函数都可以存储在引用中，因为引用将保存类型为α β的函数，其中α和β是类型变量。在规则11中，A被期望生成绑定，其中动作被绑定到标识符，但是如果它绑定其他类型的值，则在生成的代码中使用的虚拟值应该被更改为与绑定值相同类型的值。从上面我们可以看到，在A中查找绑定标识符和创建新的绑定也必须考虑到通过解引用和创建引用来使用引用。有三个动作来描述存储操作，但图7中仅示出了用于分配新存储单元的动作。生成的create代码利用内置的SML数据类型进行引用。构造函数ref用于构造一个引用，该引用包含给定给函数的数据。对于另外两个操作，检查和更新，还有另外两个关于引用的SML数据操作，！ 和：=用于查找存储的值 并在现有引用中存储新值4.3行动作为数据使用SML作为目标语言的最大优点是将与动作相关的动作转换在这里，我们利用SML具有高阶函数的事实。当“result D“产生的数据是一个动作时对于操作apply，生成的代码是一个函数，它需要一个函数（d1）与一些数据（D2，...， dn），然后将d1应用于数据d2，...， Dn以及表示没有绑定的空记录见图8。 行动作为数据178J. Iversen/Electronic Notes in Theoretical Computer Science 141（2005）167{}{}close操作产生一个函数，它既期望一个函数（参数a），又产生一个函数（fn（t，）=> a（t，b））。生成的函数不需要绑定，只需要将函数a应用于数据，并将绑定应用于整个函数。4.4数据和数据操作员AN包含许多针对整数和布尔值的内置数据运算符可以简单地转换为相应的SML数据操作符。绑定映射上的内置数据操作符（创建单个绑定、查找绑定、联合绑定映射等操作符）转换为从记录中选择元素和构建记录。要转换这些数据操作符，需要使用关于给定绑定的类型信息。ASDF允许用户指定数据和数据构造函数，这些也由动作编译器转换为SML。4.5例如为了完成这一部分，我们将给出一个翻译结果的例子。对SML采取行动动作翻译结果如表2所示（我们在一些标识符中添加了整数后缀以提高可读性，并插入了描述子表达式源自哪个子操作的注释）。(fn（t1，b1）=>（* then *）（fn（（d1，d2），b2）=> d1（d2，））（*apply *）（（fn（t3，b3）=>（*and*）letval d1=（fn（t4，b4）=>t4）（t3，b3）;（*copy *）val d2=（fn（t5，b5）=>（* then *）(fn（t6，b6）=>ref t6）（*create *）（（fn（t7， b7）=>5）（* result5 *）(t5，b5），b5））（t3，b3）in（d1，d2）end）（t1，b1），b1））表2生成的代码请注意，当使用then组合子操作时，表示子操作的子表达式的顺序与整个操作相反。let-in-end表达式是子动作的翻译，其中和作为根，并且在这里，评估其两个子动作的结果绑定到标识符d1和d2，然后将其组合成一对;整个子动作的结果。J. Iversen/Electronic Notes in Theoretical Computer Science 141（2005）1671795相关工作Actress系统[7]展示了如何将动作编译成C代码。编译涉及几个动作优化，其中最重要的是绑定消除。 该系统已经过测试，的一个小的命令式语言称为标本，和运行时间的生成的C代码的一些程序已被比较运行时间相同的程序在Pascal中的实现。这个比较表明，生成的C代码比编译的Pascal代码慢5到28倍。描述代码生成的规则很复杂，因为它们使用一组变量在操作之间传递数据，并且必须跟踪子操作使用了哪些变量彼得·布尔贝克这个系统应用了几个已知的手写编译器优化，如常数传播和尾部递归检测。在一个用命令式语言HypoPL生成的编译器编译的程序和用C编写的等价程序以及用GCC 2.4.3（完全优化）编译的程序之间的比较中，Rubbæk表明生成的编译器的代码慢了1.5到4倍。 由于目标语言的层次较低，代码生成比较复杂.继续布朗、科洛尼亚和瓦特在女演员系统上所做的工作tem，Kent D. Lee开发了Genesis系统[13]。这些系统在类型推断和动作转换方面有许多相似之处，但Genesis生成的不是C代码，而是Java字节码。这样做的一个优点是生成代码的可移植性。 与OASIS系统一样，低级目标语言使代码生成变得复杂，并且需要进行特殊的动作转换。Lee没有对生成的代码进行任何评估。Bondorf和Palsberg在[2]中证明了一种稍微不同的方法。通过在Scheme中编写一个动作解释器并应用Similix部分求值器，他们能够生成一个生成Scheme代码的动作编译器。这种方法的优点是，编写动作解释器比编写动作编译器更容易，而艰苦的工作由Similix完成。如果AN发生变化，更新动作解释器也比更新动作编译器更容易。他们对生成的方案代码的评估表明，它比手写编译器生成的代码慢近100倍最近Tijs van der Storm [5]展示了一种更简单的编译方法4代码生成在[21]中没有很好的文档记录，但是OASIS的源代码可以从ftp://ftp.daimi.au.dk/pub/empl/poe/oasis-2.2.tar.gz下载180J. Iversen/Electronic Notes in Theoretical Computer Science 141（2005）167对C和Java的操作。 与Actress和Genesis编译器进行比较更简单，因为它不执行任何类型推断或优化。它不是将动作组合子转换为语句序列，而是将其转换为一个函数，该函数调用表示子动作的函数。因为他的编译器不执行类型推断，所以产生的代码不容易被C（或Java）编译器优化，这在他的测试结果中有所反映。Van der Storm只记录了一个测试，他使用一个动作计算斐波那契数（见[5]中的第5节）。在计算第20个斐波那契数时达到的最佳结果是运行时间为0.8秒。为了比较，我们在比van der Storm（AMD XP 1800+）更慢的硬件（Intel Pentium III 1 Ghz）上计算第33个斐波那契数的运行时间为0.5秒。 我们无法运行他的动作编译器来更好地比较这两个编译器。有一个巨大的选择编译器生成器采用其他形式主义比AS可用。我们将在这里提到两个系统，这两个系统在学术界之外似乎也很流行，与基于AS的系统相反Eli系统[9]是基于属性文法的。除了使用属性语法，用户还可以通过“类比”来指定编译器的一部分，这意味着系统有一个在通用编程语言中使用的大型构造库，所以如果用户想要类似于Algol 60使用的作用域规则，他应该在规范中包含正确的模块，而不是从头开始编写。用户还可以通过“解决方案”指定编译器的一部分在文献中没有使用Eli来实现函数式或面向对象语言的编译器的例子，但是大量现实世界的命令式语言（Algol 60，C，Pascal）已经完全或部分实现。在[14]中，Eli生成的Pascal类语言的编译器与GCC进行了比较，结果表明Eli生成的编译器生成的代码比GCC生成的代码慢大约35%。在Gentle [18]中，编译器的规范是用逻辑编程语言完成的，该语言用于规范的所有部分。规范化语言类似于Prolog，但限制更多，因此可以优化统一算法。在[19] Vollmer报告中，Gentle生成了非常高效的编译器，并且用户经验表明，与手工编码编译器相比，Gentle中开发编译器节省了时间。J. Iversen/Electronic Notes in Theoretical Computer Science 141（2005）1671816动作编译器的评价动作编译器已经使用ASF+SDF实现，这是一种易于实现的形式主义，特别是代码生成规则。缺点是它不会导致快速的可执行文件，因此我们不打算在本节中比较编译时间，因为它在相关工作中已经完成我们已经测试了动作编译器作为我们的编译器生成器的一部分，这意味着我们已经给了编译器生成器两个描述的编程语言，然后编译一些测试程序与生成的测试在3.0G HzIntelephone上运行Pentiumpyruvate4个，512 Kb缓存和1Gb RAM，运行Linux 2.4.20-31.9。从动作编译器生成的SML代码使用MLton 20040227编译器进行编译我们测试的第一个语言是Core ML语言，如[11]所述在表3中示出了测试结果使用了以下测试程序Fibo使用递归函数来计算第40个Fibonacci数。Ackerman在整数3和11上计算Ackerman函数。fibo-while使用while循环和引用计算第40个斐波那契数计算重复200万次，以减少程序启动时间的重要性。length声明一个list数据类型，然后使用递归函数构造一个长度为100000的list，最后使用另一个递归函数计算长度。church构造1000万的Church编码，然后通过将编码应用于增量函数和0，将数字的Church编码转换回整数。测试程序利用了函数和命令两个方面核心ML语言第二列显示的是动作编译器的输出。第三列显示用MLton编译器编译的程序的运行时间，最后一列显示生成的编译器的输出慢了多少倍fibo 程 序 的 结 果 非 常 令 人 满 意 ， 而 ackerman ， fibo-while 和length的结果是可以接受的。fibo-while和length程序速度慢的主要原因是我们在生成的SML代码中表示数据类型（引用和列表）的方式由于Core ML中函数应用程序的语义描述方式，表示ackerman程序的操作不是尾递归的，因为ML程序是尾递归的，因此MLton编译器在优化ML程序方面比在我们的操作编译器生成的代码上做得182J. Iversen/Electronic Notes in Theoretical Computer Science 141（2005）167程序生成编译程序MLton因子菲博4.80秒2.77秒1.7阿克曼4.33秒0.63秒6.9菲博-while1.24秒0.34秒3.6长度1.13秒0.21秒5.4教会7.83秒0.33秒23.7表3 CoreML运行时间在这个节目上。尾递归的问题在递归斐波那契程序（fibo）中并不明显，因为递归函数没有尾递归。 在Core ML的AS描述中，一个函数被包装在一个数据类型中，这是运行church测试程序时产生坏结果的主要原因，该程序利用了高阶函数。编译器生成器也已经在一个小的C子集上进行了测试。该子集包括简单表达式、赋值语句、if语句和while语句、状态块、变量声明和递归函数.值是整数和整数数组，但没有指针。这七个测试项目是：Fibo使用递归函数计算第40个Fibonacci数。Ackerman在整数3和11上计算Ackerman函数。递减包含四个相互递归的函数，将整数参数从1000万递减到零。fibo-while使用while循环计算第40个斐波那契数。计算重复5000万次，以减少程序启动时间的重要性。Euclid是Euclid算法的一个实现，它可以找到37和1023的最大公约数。这个过程重复了2000万次。Sieve是Eratosthenes Sieve的一个实现，可以找到1到2百万之间重复10次。bubble是一个在长度为32000的整数数组上实现的冒泡排序算法。表4比较了生成的编译器输出和用GCC 3.3.2编译的程序除ackerman和decrement程序外，其它程序的测试结果都令人满意。在这些程序上，生成的编译器生成的代码平均只比GCC生成的代码慢两倍J. Iversen/Electronic Notes in Theoretical Computer Science 141（2005）167183程序生成编译程序GCC因子菲博2.81秒1.50秒1.9阿克曼3.60秒0.60秒6.0减量十九点一刻1.26秒15.2菲博-while4.24秒1.70秒2.5欧几里得1.88秒1.12秒1.7筛2.51秒1.25秒2.0泡沫1.69秒0.82秒2.1表4miniC运行时间我们认为生成的编译器在decre- ment程序上生成的代码与GCC编译器相比非常慢，这是因为递归组合子的实现方式，当程序包含相互递归的函数时，这似乎特别在ackerman和decrement程序中，非尾递归操作的问题再次出现。将从C的一个子集生成的编译器与整个C语言的编译器进行比较当然是不公平的。当我们扩展C语言的子集时，生成的编译器可能会变得不那么高效，特别是如果我们允许更多的数据，而不仅仅是整数和整数数组。添加更多的功能通常意味着构造的简单语义被更复杂的语义所取代，例如，将指针和指针添加到C的子集将意味着+的语义变得更加复杂，因为运算符现在应该被重载。另一方面，我们的编译器生成的代码对数组执行边界检查，而GCC编译器没有，这使得生成的编译器效率较低本节的测试结果表明，生成的编译器的效率很大程度上取决于它所基于的动作语义描述的最优性，同时也表明动作编译器在递归组合子的实现和数据表示方面还有待改进。6.1与OASIS将我们的结果与其他人的结果进行比较，很明显，我们生成的编译器比所有基于AS的系统（除了OA- SIS）更有效，但可能不如Eli生成的编译器有效我们自己无法使用184J. Iversen/Electronic Notes in Theoretical Computer Science 141（2005）167因此，我们的比较是基于表5中列出的数字，这些数字摘自[20]中的第4.5节。这些数字显示了使用生成的编译器编译的HypoPL（Pascal的一个子集）程序的运行时间（第二列），使用GCC编译的完全优化的类似程序的运行时间（第三列），以及生成的编译器的输出慢了多少（第四列）。程序生成编译程序GCC因子菲博-while0.8秒0.5 s1.6筛1.4秒0.3 s4.0欧几里得2.1秒0.7 s3.0泡沫0.4 s0.2 s2.0表 5 OASIS运行时间我们已经在miniC中实现了等效的程序，运行时间如表4所示。由于各种原因，很难将我们的动作编译器与OASIS进行比较：• 我们无法测试OASIS。• OASIS使用基于原始AN的受限版本的另一个AN，并扩展了额外的功能。• 在测量OASIS的运行时间时使用了较旧的硬件，因此我们只能比较其输出比GCC的输出慢的因素• HypoPL语言与miniC语言不同。例如，HypoPL既不允许函数有多个参数，也不允许函数相互递归。• OASIS上报告的结果仅具有一位小数精度，因此某些结果的因子可能变化至+/-1总而言之，将布尔贝克的结果与我们的结果进行比较是不公平的。有了这个警告，我们无论如何都要尝试。当比较表4最后四行中因子列中的数字和表5中因子行中的数字时，我们注意到我们生成的编译器的输出平均比gcc慢2.1倍，而OASIS的慢2.7倍。如果能看到OASIS生成的编译器在ackerman和decrement程序上的表现会很有趣，因为我们的结果明显更J. Iversen/Electronic Notes in Theoretical Computer Science 141（2005）1671857限制在我们的编译器生成器中，使用动作语义作为输入和SML作为输出都对可以描述的语言提出了一些限制。动作语义不能描述所有的语言特征，例如，从许多函数式语言中已知的call/cc不能以直接的方式描述。 我们的类型推理算法进一步限制了集合例如，不接受源自利用ML的let多态性的ML程序的动作。最后，动作编译器的目标语言也限制了可以描述的语言特征。SML中严格的类型系统意味着用子类型来描述语言是困难的，如果不是不