高级语言程序中的数据结构优化

1、中南大学本科生毕业论文（设计）论文翻译 题 目 数据结构可视化实验平台 学生姓名 祝 杰 指导教师 余 腊 生 学 院 信息科学与工程学院 专业班级 计科0902班 完成时间 2013年4月 14高级语言程序中的数据结构优化基于分级的可扩展编译器新方向Tiark Rompf Arvind K.Sujeeth Nada AminKevin J. Browny Vojin Jovanovic HyoukJoong Leey Manohar Jonnalagedda Kunle Olukotuny Martin Odersky瑞士洛桑理工大学: first.lastepfl.chOracle实验室斯

2、坦福大学: asujeeth, kjbrown, hyouklee, 摘要高层次的数据结构是现代编程的基石，同时也阻碍了编译器优化。为了解释用户或库定义的数据结构，编译器需要具备可扩展性。扩展编译器的通用机制分为两类。前端宏，分级或部分评估系统，可用于在程序进入编译器前以编程的方式删除抽象，进行相应的具象化。此外，有些编译器通过在编译过程中添加新的变型或增加新的中间表示（IR）类型来扩展编译内部的运作。这两者单独都不足以处理高层次的数据结构所带来的挑战。本文展示了一种新颖的方式将两者结合起来，这种方式所产生效益远远大于两者效益之和。分段技术不仅可以用于前端，我

3、们在内部编译器变型中也可以使用分段。这些内部类型通过程序的执行来创建变型IR。总所周知，分段可以简化程序的生成，并可以通过同样的方式简化程序的转换。把转化定义为阶段IR解释器比在IR转化器上实现低级的IR要来得简单。通过自定义IR节点，很多被表示为从IR节点到分级程序片段的重写的优化可以被整合成一个变型，以缓和无序问题。推理性的重写可以在循环结构周围保持乐观的判断。我们演示了几个使用了这种架构而且功能特别强大的程序优化方式，它们面向以下数据结构：一个新的循环融合和砍伐森林算法，结构数组到数组的结构之间的转换，面向多样并行设备的对象扁平化和代码生成。我们通过一些展现出巨大加速的不平凡的案例研究来

4、验证我们的方法。分类和主题描述D.3.4编程语言：处理器-代码生成，优化，运行时环境；D.1.3编程技术：并发程序设计-并行程序设计通用术语设计，语言，性能关键词分级，代码生成，数据结构，可扩充编译程序/ 向量object Vector def fromArrayT:Numeric(a: ArrayT) =new Vector val data = a def zerosT:Numeric(n: Int) =Vector.fromArray(Array.fill(n)(i = zeroT)abstract class VectorT:Numeric val data: ArrayTdef +(

5、that: VectorT) =Vector.fromArray(data.zipWith(that.data)(_ + _) ./ 矩阵abstract class MatrixT:Numeric . / 复数case class Complex(re: Double, im: Double) def +(that: Complex) = Complex(re + that.re, im + that.im)def *(that: Complex) = .图 1. 高等级的Scala线性代数包的框架1. 引言将高级语言程序编译成低级语言程序是很难的，特别是因为这样的程序，使用了高层次的抽象和

6、定义。编译器无法看穿这些抽象和定义（“抽象代价”），它不能推理出领域特有的属性（“通用瓶颈”）。数据结构和操作集是其中最重要的抽象，也是目前被认为最难使用到优化编译程序中的。让我们考虑在Scala中的高级语言编程实例。我们要实现一个稠密线性代数包。图1显示了一个通过Array扩展而来的Vector和Matrix的框架，框架内部使用了高级操作集（fill，zipWith）。Vector和Matrix包含数值类型（模板类Numeric）。我们同时定义复数为一个新的数字类型。有了这些定义，我们可以像这样编写程序：def diag(k:Int) = k * Matrix.identity(n)val

7、m1 = (v1+v2).transpose * (v1+v2)val m2 = diag(l)if (scale) println(m1*m2) / = m1*(k*id) = k*m1*id = k*m1else println(m1) / 不需要计算 m2这样的代码优雅而高级，展示了Scala如何将注意力集中在抽象和归纳发展生产力的提高。不幸的是，代码将运行得很慢，比已经调整过只使用数组和while循环的低级实现方式慢一到两个数量级（见第5部分）。到底是什么回事？部分原因是：1）无论是Scala编译器还是JVM中的及时编译器都无法将诸如公共子表达式或冗余代码消除（CSE，DCE），通用优

8、化成非平凡的矩阵或矢量计算。2) 编译器对于像m*id = m（其中m是一个矩阵, id是单位矩阵）这样可以进行优化的特定领域的规则没有任何概念。3) 在函数式编程风格中，编程过程中会产生很多中间对象。4) 统一的JVM堆分配的对象无法表示复数。为了使编译器能够理解高级语言的抽象和定义，我们需要一种机制来扩展编译器以便于它能够处理这些抽象。有两个常见的方法。第一种是在程序编译前进行翻译，这样编译器就不需要知道这些抽象和定义。这是宏系统和分段的原理。部分求值（PE）也可以在程序编译前对其进行详细说明。第二种选择是教会编译器领域相关的规则。通常，编译器的可扩展性被理解为增加新的阶段的一种手段。一些

9、可扩展的编译器还允许添加新的IR类型，但新的节点与现有的通用的优化互相之间如何影响一般都没有明确。然而，两种方法都不足以单独解决高级数据结构与抽象定义带来的挑战。回到我们的例子，如果我们只有阶段或宏，表达m * id，也就是m，在到达编译器前就会被扩展为循环，所以我们无法对m进行化简。在一般情况下，有限的形式化简可以添加（见C+ expression templates51）如果想要添加进来的化简生效，所有的通用的编译器优化（CSE，常数传递，等）也会需要被复制。在另一方面，如果我们已经能够添加新的编译器关口，我们可以添加一个把m * id优化为m的关口，但是我们需要另一个把矩阵乘法扩展成循环

10、的关口。这些关口需要被实现成低级IR到IR的转换，这比仅仅使用普通的（多级）的计算表达来表达目标代码的宏观或分段的方法难多了。把优化实现为单独的关口的方式在许多优化被独立添加时会引起关口排序的问题。我们认为，我们真正需要的是最好的两个世界：一方面，我们想要将操作符号化以便于他们能够适应于转换规则。另一方面，我们也要使用分段来以编程方式定义转换的结果。此外，在使用优化时我们需要一种方法来定义转换的独立性以避免阶段排序问题。贡献在本文中，我们提出了一个可扩展编译器的框架，解决了这一挑战，同时尽量降低表达优化和转换的编码量。通过采用分段技术的中间语言以及一种不会产生阶段排序问题的方法整合独立的指定优

11、化，我们融合了操作集，改变了数据布局，对高级对象进行了深度优化，我们的方法极大地提升了高级程序的速度。为了说明我们的系统在较高的水平下如何工作，我们再来考虑线性代数的例子。通过分期我们从最初的程序中获得一个中间表达式。为了避免采用纯分期或宏观的方法，我们在不同的层次应用优化，我们将尽可能多的优化放在同一个关口以避免诸多传统的阶段排序问题。线性代数库的作者，通过重写将符号表达式重写为分段的程序片段的规则来实现线性代数优化。该系统通过积极假设，当事实证明中间转换不准确时则回滚，来进行重写。这种策略消除了由于一个优化模块不得不对另外一个模块的结果进行悲观假设而引起的阶段排序问题。一旦在线性代数的层面

12、无法进行更深的优化，我们就只能考虑由数组和循环组成的低级表达方式。我们把这种“昏暗的”转换实现成了中间程序的分段解释器。由于解释器也使用分段，它创建了新的程序，看起来似乎像是程序转化器。默认情况下，解释器会将每个表达式映射到一个在结构上相当的表达式。该库的作者将线性代数运算映射到它的低级表示。在这一水平上，该系统在组合关口，重新应用全局优化方面应用另一套优化，来更好的利用改变表达式带来的新机会。这个过程可以重复进行任意次。特别是，我们做出了如下贡献： 我们使用分段构建可扩展多关口的编译器同时可以有效地把模块化的优化整合成单一关口：分段IR解释器作为IR转换和推理重写允许将独立指定优化进行整合的

13、同时保持乐观的假设。 我们使用基于图的中间表示可能包含结构化的复合表达式。拆分和合并复合表达式使我们能够重用现有的优化（例如，DCE删除数据结构中未使用的部分）。这种方法扩展了强大的数据格式转换（例如，阵列结构到结构数组）。 我们提出了一种新的能够统一处理水平和垂直融合和非对称结构的遍历（flatMap，groupBy）的数据并行循环融合算法。 我们通过一些不平凡的案例演示了该编译器架构如何解决与数据结构相关的棘手的优化问题。我们初期的工作建立在Lightweight Modular Staging(LMS) 39之上，并且会随着工作的进行标注与之相似的和不同的工作。推理重写的方法是基于Len

14、er，Grove和Chambers的工作29。2. 背景 许多计算可以自然地根据执行的频率和信息的可用性来分成不同的阶段。Taha和Sheard46建立了多级编程（简称MSP），他们将阶段分得十分明确，允许程序员在下一个阶段求表达式的值（也叫表达式分段）。现阶段作为一个高效的代码生成器，在运行时产生下一个阶段的程序。分段和部分求值20密切相关，它将程序分成输入确定的一些部分。基于本文的目的，我们可以把部分求值（尤其是绑定时间分析（BTA）当成自动分级，把分级当成程序员控制的部分求值。一个关键的区别是，部分求值严格地使程序专门化，通常有着健全的保障。然而，在像MetaOCaml7这样的MSP语言

15、中添加分级注释使得分段的阶段划分时更加自由但是需要一定的注意以保证不改变计算的结果。大部分关于分段和部分求值的研究都是为了简化编译器的开发。例如，把解释器专门化成一个特定的程序能够产生一个去除了解释器（第一个Futamura投影15）的已编译程序。自适应的部分求值器可以通过解释器和编译器生成器来生成编译器。本文的论述中使用Scala和轻量级模块化分段（LMS）39，一种理论上的分段方法。与基于准引号的专用MSP语言相反，LMS只使用类型来区分计算阶段。属于第二阶段的表达式在第一阶段中有类型RepT，当在第二阶段时，会得到类型为T的运算。普通类型T的表达式将在第一阶段求值，在第二阶段中则变成了常

16、数。普通的Scala类型系统传播关于哪些表达式分段了的信息，从而作为本地的半自动BTA。因此，LMS从自动PE和手动分段中获得了不少好处。例子：零耗抽象遍历Scala中的Array是在遍历时需要循环和索引的JVM纯数组。Scala的标准库提供了一个foreach方法：array foreach i = println(i) foreach方法是通过隐式转换来实现的：implicit def enrichArrayT(a: ArrayT) = new def foreach(f: T = Unit): Unit = var i = 0; while (i B（分段函数对象）类型和RepA=Rep

17、B（分段值上的函数）之间的不同。通过使用后者时，foreach确保函数的参数总是在分段时间内求值和展开。只允许删除表达式树的宏系统只能支持RepA = B类型。这限制了表现力并且无法保证高阶函数在分段时间内求值。在除了LMS框架，我们使用Scala虚拟编译器32，它把几个核心的语言功能重新定义为函数，从而使它们能够重载。例如，下面的代码/ 数组implicit def enrichArrayT(a: RepArrayT) = new def foreach(f: RepT = RepUnit): RepUnit = var i = 0; while (i RepT) =Array.fill(a

18、.length min b.length) i = f(a(i), b(i) / 向量trait VectorT extends Struct val data: ArrayT implicit def enrichVectorT:Numeric(a: RepVectorT) = new def +(b: RepVectorT) =Vector.fromArray(a.data.zipWith(b.data)(_ + _) ./ ( 与Array.fill 和Vector.fromArray所在定义的对象一起)图 2, 分段数组和矢量操作var i = 0; while (i n) i = i

19、 + 1 会被解释为如下：val i = _newVar(0); _while(i println(i) 中，在图2中定义的分段函数foreach只会执行compute()方法一次，而纯粹的语法扩展产生这种目标代码：while (i v在膨胀前的发生移除zero。让我们想象一下，我们的系统能够以这样一种方式实现矢量加法操作，它可以检查参数来查找Vector.zeros的调用。这将解决上述例子中的问题，但如果我们稍微将使用情况复杂化一点，我们仍会面临其他问题：val v1 = .val v2 = Vector.zeros(n)v1 + v2处理这样的程序，只是检查（语法）参数是不足够的。我们需要

20、将分期扩展与某种形式的转发数据流整合来传播，否则加法的参数仅仅是一个标识符。更深层次的问题是，我们不得不使用单一的数据表示。即便我们将分段整合到一个可扩展的编译器中，我们仍需作出一个决定：我们是应该为了便于优化把向量当做拥有代数定律的象征性实体，实现成IR节点？还是将它们分段好让编译器只看到循环和数组而没有抽象的开销？以下各节将论述将这些方法整合的机制，以及如何以一个更抽象的方式来对待数据结构。3. 通过分级实现的程序转化分段通常是一个用于生成程序的方法：由目标程序建立的多级程序随即再次正常编译。我们发现，分段可以作为程序转换的一个有效的工具。任何转换可以细分成一种遍历和生成部分。并不奇怪的是

21、，分段有助于生成部分。在我们的例子中，内部编译器关口为恰好分段的IR解释器，它们将返回一个新的程序。通过这种方式，它们可以在程序执行时建立程序转换的结果。程序转换的分段有很多好处。首先，建立一个（分段）IR解释器比建设一个不平凡的IR到IR转换器简单得多。其次，优化可逐渐加入到一个分段的程序中，从图2中的代码开始。第三，程序本身（或库）受翻译过程控制并且会影响到将产生什么样的代码。我们的方法中关键环节之一是区分两种转换：优化和降低程序级别。降低程序级别是将程序翻译成低级表示（如从线性代数到数组和循环的转换）。 降低程序有着自然的顺序，这使得他们能够方便地安排单独的关口中。相反，优化没有明确的顺

22、序，而且容易导致阶段排序问题。因此，需要将它们结合来获得更大的效果。此外，大多数降低程序级别是必需的，而优化通常是可选的。当然，两者的区别并不始终明确，但许多变换只属于其中一种。在任何情况下，重要的是所有适用的优化应该在降低程序级别前采用。否则，可能会错过高级的优化机会。降低程序级别后，有可能仍有新的优化机会。因此，我们的系统会执行一序列的优化，降低程序级别，再优化操作，直到程序用最低级别的表示。 对于目标代码来说最终的表示是未解析的。4. 数据结构优化高层次的数据结构是现代编程的基石，同时也阻碍了编译器优化。我们通过两个主要的编程范式来阐明编译器在数据结构方面遇到的主要问题。OOP面向对象编

23、程把每一个数据值看做一个对象。这是一个功能强大的模式，使得它易于扩展语言新的功能。例如，在Scala中很容易添加复数类。但要付出相应的代价：把每一个复数作为一个单独的对象来分配效率不高。此外，我们用到复数数组时，如果我们用一个结构数组表示将获得了更好的性能。分段和嵌入式编译器允许我们抽象出对象的抽象，推出组成对象的独立数据片段，并可能以更有效的方式重新排列数据。FP函数式程序会产生大量的中间结果。这种情况在集合操作中特别严重。从理论上讲，编译器可以利用引用透明度。但是不纯的函数式语言需要复杂的效果分析，若其中包含大量的抽象这将变得很困难。因为剥离了抽象，我们的分段程序要简单得多。我们可以做更好

24、更简单的效果分析。一个简单的活跃度分析，可以将复制转化为就地修改。一种新型的循环融合算法（数据并行且非对称，包括flatMap和groupBy方法）删除许多中间结果。5. 案例学习我们提出了几个案例研究，以阐明我们的编译器体系结构，特别是在分段方面与数据结构相关的高级优化。所有的实验都在有两个四核Xeon2.67GHz处理器和96GB的RAM的Dell Precision T7500n机器上运行。Scala代码运行在Oracle Java SE运行时环境1.7.0版和默认配置的Hotspot64位服务器VM上。每个应用程序我们都运行了10次（使JIT活跃）并且报告最后5次运行的平均时间。每次运

25、行我们都只计算应用程序计算部分所占的比例。6. 讨论正如在第5节所示，我们的系统能够实现在较宽范围不平凡高级语言程序上拥有较大幅度（在某种情况下甚至接近）的速度提升的排序。虽然我们不知道是否确实存在其他能够在相同数量级的程序下产生可比较结果的系统，但这些结果让我们怀疑通过其他的方式是否可以付出相同的代价来得到。我们的审稿人之一提出，更简单的设计能使优化自动化。例如，我们可以用一个特殊类表示零矢量来将向量和矩阵实现成类的层次结构，而不是在IR模型中静态地区分零矢量。这当然是一种有效的设计，但它也有许多缺陷。首先，运行时的区别带来了解释的开销，间接和虚拟调用，这也让编译器更难生成高效的代码。其次，

26、虽然在某些情况下动态信息可能会比静态信息更加精确，但是在其他重要方面动态优化的可能非常有限：例如，目前并没有明确的方法融合DCE或任何其他需要的非局部知识（活性，横向融合）的优化。审稿人提出的另一个问题是，相比Spoofax 24或JetBrains MPS 19这些包括在语言工作台上的目前技术水平的重写系统，分段是否真的简化了转换。的确，这些系统令人印象深刻，我们相信他们服务于不同的目的，以编程方式删除所有中间层抽象并且能够强力保障残留代码的处理的能力，在程序优化的背景下是很难夸大的。例如，通过高阶函数和分段删除的类型类实例，无需删除专用的编译器分析，图3中的代码就可以将符号表示的线性代数运

27、算转化为图2中所示的相同的零耗遍历。分段使我们能够将程序（或模型）转化器当成解释器；这是一个优势因为即便拥有良好的工具包支持，使用一种有表现力的语言来编写一个解释器比实现一个转换器可以说简单得多。一个重要方面是在语言上重用元语言的抽象定义。例如，我们最近关于使用LMS 27产生JavaScript的工作在分段期间重用了Scala的CPS转换40来产生异步代码，也即延续传传递风格（CPS）。相比之下，实现在Spoofax下的WebDSL 17，对每种目标语言的语言结构必须重新实现CPS转换。处理一个基于图形的IR相比表达式树也有质的区别。最重要的是，需要依赖信息的转换更容易实现。例如，我们的融合

28、算法（4.4节），不需要循环来在语法上接近融合：def calcSum() = array.sumdef calcCount() = array.filter(_ 0).countprintln(sum: + calcSum()println(avg: + (calcSum() / calcCount()分段会将calcSum和calcCount的调用内联而融合算法会将遍历整合到一个循环中。任何只考虑依赖遍历表达式的算法将错过在这两个println语句之间进行水平融合的机会。这就是通常的情况下纯前端基于比如C+表达式模板的方法。我们设计的另一个重要方面是如何对待降低程序等级（处理一个有一个独立

29、的关口）和优化（通过推理重写整合成化简关口）。我们相信这样的区别对于通过避免阶段排序问题进行优化以及保证高层次的优化在降低程序等级之前执行是非常有必要的。最后，关于实现类似的结果程序员需要付出的努力的问题。从我们的角度来看，最重要的方面是我们提出的优化能否逐步实施，以及经过优化的库能否被所有的客户端重用。我们希望，终端用户程序员不要经常自己写转换，如果他们需要可以重写。库开发人员如果要添加优化，需要实现与我们展示的代码（例如在图3中）一样的函数，他们也可以按照以下步骤来做：首先编写类似于图1中的代码，添加分段（图2），如果这还不够，添加进一步的优化（图3）。延迟重写（第3.3），可进一步降低冗

30、余。类型系统（在分段期间计算的非RepT表达式）和智能构造函数（如果重写匹配则不创建IR节点）有利于保障优化按照预期的方式执行。作为调试帮助，转换后的代码可以在任何时候发出。6.1 相关工作关于可扩展的编译器的研究已经持续很长一段时间了，在Java世界中最近的例子是Polyglot33和JastAdd 13。Glasgow Haskell编译器还允许自定义重写规则22。也有一些源自正式方法的库专门化优化方面细致的研究。ROSE 36是一个用于创建在库抽象领域通过语义注释来进行自动优化的源到源翻译器的框架。COBALT 30是一种用于实现对自动正确性推理的优化的特定领域的语言。Tate以及其他人

31、48提出了一种在转换前后自动根据例子程序执行编译器优化的方法。Delite 5，28，41是除了LMS之外DSLs的又一个并行框架。Delite之前有一个多层IR的概念：在相同的时间一些IR节点可以从几个不同的角度来看（例如，一个并发的循环，同时也可以是一个矩阵运算）。这将导致问题，因为“早些时候”，更多的高层次的看法执行，过时或已经充分利用的信息未被丢弃，这就限制了编译器的选择。我们使用这项技术来扩展Delite，在现有的类似OptiML44这样的Delite DSLs中实现领域特殊化优化（就像案例分析中提出的那些）。Delite也被用来作为本文案例分析中的并行执行引擎。与Delite相比，

32、本文提出了一种通用扩展编译器架构，它不仅限于领域特殊化的语言。以前关于LMS 38，39的出版物只提出了纯前端，单一关口实例。在LMS中使用RepT类型来定义汇编时间，是受到早期关于无标签或多态性语言嵌入10，18的研究的启发。我们的编译器基础设施以可重用的方式实现了一套先进的优化技术。相关工作包括采用了先进的重写规则4，结合了分析与优化9，29，53，以及用于消除中间结果12，54和循环融合16的技术的程序转换。可以替代推理重写的一个有趣的选择是相等等饱和47，它包括了许多种表达IR操作的方式。作为在程序转换中使用部分求值的一个例子，Sperber和Thiemann 43作了闭包转换和在一个

33、合适的解释器上进行离线部分求值的尾部调用的介绍。最近，Cook等人11通过对模式解释器执行部分求值进行了模式转换。部分评估一般意味着常量折叠和专业化，而我们的方法允许对编译器进行任意的优化，在任意时刻计算分期/特殊化的时间以消除抽象开销，并能保障什么会变成残留代码（类型RepT残留，T静态）。6.2 结论 我们展示了一个编译器架构，它通过融合操作集，改变数据布局以及通过采用分段技术的中间语言以及一种不会产生阶段排序问题的方法整合独立的指定优化对高级对象进行的深度优化极大地提升了程序的速度。我们的系统结合了一些现有的新技术，提供的优化效果要远大于各个部分之和。致谢我们感谢POPL审稿人的宝贵意见

34、和建议。赞助这项研究有欧洲研究委员会（ERC）的587327“DOPPLER”资助，DARPA（美国国防部先进研究项目局）通过Oracle下的订单US103282，DARPA的合同HR0011-11-C-0007“SEEC”，NSF（国家科学基金会)资助SHF CCF-1111943，斯坦福大学普适并行实验室联合计划（由Oracle，AMD，Intel，NVIDIA支持）和Oracle额外的支持。参考文献1 S. Ackermann, V. Jovanovic, T. Rompf, and M. Odersky. Jet: An embedded dsl for high performanc

35、e big data processing. BigData, 2012.http:/infoscience.epfl.ch/record/181673/files/paper.pdf.2 M. S. Ager, O. Danvy, and H. K. Rohde. Fast partial evaluation of pattern matching in strings. ACM Trans. Program. Lang. Syst., 28(4):696714, 2006.3 J. Auerbach, D. F. Bacon, P. Cheng, and R. Rabbah. Lime:

36、 a javacompatible and synthesizable language for heterogeneous architectures.OOPSLA, 2010.4 M. Bravenboer, A. van Dam, K. Olmos, and E. Visser. Program transformation with scoped dynamic rewrite rules. Fundam. Inf., 69:123178, July 2005.5 K. J. Brown, A. K. Sujeeth, H. Lee, T. Rompf, H. Chafi, M. Od

37、ersky,and K. Olukotun. A heterogeneous parallel framework for domainspecific languages. PACT, 2011.6 J. A. Brzozowski. Derivatives of regular expressions. J. ACM, 11(4):481494, 1964.7 C. Calcagno, W. Taha, L. Huang, and X. Leroy. Implementing multistage languages using asts, gensym, and reflection.

38、In GPCE, 2003.8 J. Carette, O. Kiselyov, and C. chieh Shan. Finally tagless, partially evaluated: Tagless staged interpreters for simpler typed languages. J.Funct. Program., 19(5):509543, 2009.9 C. Click and K. D. Cooper. Combining analyses, combining optimizations.ACM Trans. Program. Lang. Syst., 1

39、7:181196, March 1995.10 C. Consel and O. Danvy. Partial evaluation of pattern matching in strings. Inf. Process. Lett., 30(2):7986, 1989.11 W. R. Cook, B. Delaware, T. Finsterbusch, A. Ibrahim, and B. Wiedermann.Model transformation by partial evaluation of model interpreters.Technical Report TR-09-

40、09, UT Austin Department of Computer Science, 2008.12 D. Coutts, R. Leshchinskiy, and D. Stewart. Stream fusion: from lists to streams to nothing at all. In ICFP, 2007.13 T. Ekman and G. Hedin. The jastadd system - modular extensible compiler construction. Sci. Comput. Program., 69(1-3):1426, 2007.1

41、4 C. Elliott, S. Finne, and O. de Moor. Compiling embedded languages.In W. Taha, editor, Semantics, Applications, and Implementation of Program Generation, volume 1924 of Lecture Notes in Computer Science, pages 926. Springer Berlin / Heidelberg, 2000.15 Y. Futamura. Partial evaluation of computatio

42、n process - an approach to a compiler-compiler. Higher-Order and Symbolic Computation, 12(4):381391, 1999.16 C. Grelck, K. Hinckfu, and S.-B. Scholz. With-loop fusion for data locality and parallelism. IFL, 2006.17 D. M. Groenewegen, Z. Hemel, L. C. L. Kats, and E. Visser. WebDSL:a domain-specific l

43、anguage for dynamic web applications. In OOPSLA Companion, 2008.18 C. Hofer, K. Ostermann, T. Rendel, and A. Moors. Polymorphic embedding of DSLs. GPCE, 2008.19 JetBrains. Meta Programming System, 2009. URL 20 N. D. Jones, C. K. Gomard, and P. Sestoft. Partial evaluation and automatic program genera

44、tion. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1993.21 S. L. P. Jones, R. Leshchinskiy, G. Keller, and M. M. T. Chakravarty. Harnessing the Multicores: Nested Data Parallelism in Haskell. In FSTTCS, 2008.22 S. P. Jones, A. Tolmach, and T. Hoare. Playing by the rules: rewriting as a practica

45、l optimisation technique in ghc. Haskell, 2001.23 S. Karmesin, J. Crotinger, J. Cummings, S. Haney, W. Humphrey, J. Reynders, S. Smith, and T. J.Williams. Array design and expression evaluation in pooma ii. In ISCOPE, 1998.24 L. C. L. Kats and E. Visser. The Spoofax language workbench. Rules for dec

46、larative specification of languages and IDEs. In SPLASH/OOPSLA Companion, 2010.25 R. Kelsey and P. Hudak. Realistic compilation by program transformation. In POPL, 1989.26 K. Kennedy, B. Broom, A. Chauhan, R. Fowler, J. Garvin, C. Koelbel, C. McCosh, and J. Mellor-Crummey. Telescoping languages: A s

47、ystem for automatic generation of domain languages. Proceedings of the IEEE, 93(3):387408, 2005.27 G. Kossakowski, N. Amin, T. Rompf, and M. Odersky. Javascript as an embedded dsl. In ECOOP, 2012.28 H. Lee, K. J. Brown, A. K. Sujeeth, H. Chafi, T. Rompf, M. Odersky, and K. Olukotun. Implementing dom

48、ain-specific languages for heterogeneous parallel computing. IEEE Micro, 31(5):4253, 2011.29 S. Lerner, D. Grove, and C. Chambers. Composing dataflow analyses and transformations. SIGPLAN Not., 37:270282, January 2002.30 S. Lerner, T. D. Millstein, and C. Chambers. Automatically proving the correctn

49、ess of compiler optimizations. In PLDI, 2003.31 A. Mller. dk.brics.automaton finite-state automata and regular expressions for Java, 2010. http:/www.brics.dk/automaton/.32 A. Moors, T. Rompf, P. Haller, and M. Odersky. Scala-virtualized. PEPM, 2012.33 N. Nystrom, M. R. Clarkson, and A. C. Myers. Pol

50、yglot: An extensible compiler framework for java. In CC, 2003.34 N. Nystrom, D. White, and K. Das. Firepile: run-time compilation for gpus in scala. GPCE, 2011.35 S. Owens, J. Reppy, and A. Turon. Regular-expression derivatives reexamined. J. Funct. Program., 19(2):173190, Mar. 2009.36 D. J. Quinlan

51、, M. Schordan, Q. Yi, and A. Sbjrnsen. Classification and utilization of abstractions for optimization. In ISoLA (Preliminary proceedings), 2004.37 T. Rompf. Lightweight Modular Staging and Embedded Compilers: Abstraction Without Regret for High-Level High-Performance Programming. PhD thesis, EPFL,

52、2012.38 T. Rompf and M. Odersky. Lightweight modular staging: a pragmatic approach to runtime code generation and compiled dsls. GPCE, 2010.39 T. Rompf and M. Odersky. Lightweight modular staging: a pragmatic approach to runtime code generation and compiled dsls. Commun. ACM, 55(6):121130, 2012.40 T. Rompf, I. Maier, and M. Odersky. Implementing first-class