理论计算机科学电子笔记177（2007）201-217www.elsevier.com/locate/entcs使用模板Haskell进行抽象解释Clara Segura克拉拉·塞古拉1，2DepartamentodeSistemasInform′ticosyProgramacio′nUniversidad Complutense deMadrid西班牙马德里卡门·托拉诺3DepartamentodeSistemasInform′ticosyProgramacio′nUniversidad Complutense deMadrid西班牙马德里摘要元编程包括编写生成或操作其他程序的程序。Template Haskell是Haskell的最新扩展，目前在Glasgow Haskell编译器中实现，在编译时支持元编程。我们的目标是应用这些设施，以静态分析程序，并在编译时转换它们。在本文中，我们使用模板Haskell来实现基于抽象解释的严格性分析和使用结果的let-to-case转换的分析。这项工作显示了该工具的优点和缺点，以便将新的分析和转换到编译器中，而无需修改它。保留字：元程序设计，模板Haskell，抽象解释，严格性分析。1介绍元编程包括编写生成或操作其他程序的程序。Template Haskell [17，18]是Haskell的一个最新扩展，目前在Glasgow Haskell编译器[12]（GHC 6.4.1）中实现，在编译时支持元编程。它的功能可以从库包Language.Haskell.TH中获得。它已被证明是一个有用的工具，目的[6]，如程序转换[7]或接口的定义，1 工作得到西班牙项目TIN 2004 -07943-C 04的部分支助。2 电子邮件地址：csegura@sip.ucm.es3 电子邮件地址：ctorranog@hotmail.com1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2007.01.012202C. 塞古拉角Torrano/理论计算机科学电子笔记177（2007）201核心业务新证简化器去硫剂CoreToStg图1.一、具有新分析和转换的全球人道主义法规汇编过程带有外部库的Haskell（http：//www.haskell.org/greencard/）。特别有趣的是在不修改GHC的情况下实现了并行函数式语言Eden [15]的编译器。使用这样的扩展，程序员编写的程序可以在编译时进行检查和/或修改，然后再进行其余的编译过程。我们的目标是应用这些元编程设施，以静态分析程序，并在编译时转换它们这将允许我们一方面快速实现为函数式语言定义的新分析，另一方面将这些分析合并到编译器中而无需修改它。在图1中，我们展示了GHC编译过程的方案。Haskell代码被转换成一种更简单的函数式语言，称为Core。GHC中的分析和转换发生在核心语法级别，这被总结为一个更简单的阶段。 为了添加新的分析和转换，有必要修改编译器。但是，通过使用Template Haskell，这些可以在Haskell语法级别合并，而无需修改GHC。在图1中，这是作为抽象语法树级别上的新通道添加的。特别是像Eden [5]这样的语言可以从这些设施中受益。Eden是Haskell的并行扩展，其编译器在GHC上实现[3]。理论上已经为这种语言定义了几种分析[14，11，4]，但它们还没有被合并到编译器中，因为这涉及到GHC的修改，我们可以为每个新的分析定义一次，每次GHC使用Template Haskell，新的分析和/或转换可以首先原型化，然后合并到编译过程中，而无需直接修改编译器的内部在本文中，我们探讨了模板Haskell的有用性，通过实现一个抽象的解释为基础的严格性分析和一个让案例转换，使用的分析结果。这些都是众所周知且已经解决的问题，这使我们能够专注于工具所产生的问题。 在第2节中，我们描述了后面几节中使用的模板Haskell的那些功能。在第三节中，我们介绍了抽象解释，并描述了严格性分析和let-to-case转换。第4节描述了它们使用Template Haskell的实现，并展示了一些示例。最后，在第5节中，我们总结并讨论了可以使其更有用的工具的改进。Haskell代码抽象语法C. 塞古拉角Torrano/理论计算机科学电子笔记177（2007）201203数据Exp =LitELit--字面变量名称--变量ConE名称--构造函数LamE[Pat] Exp-- lambda抽象AppE Exp Exp--应用程序CondE Exp Exp Exp--条件LetE [Dec] Exp-- let表达式CaseE Exp[Match]-- case表达式后缀E（可能Exp）Exp（可能Exp）--原始操作。. . .数据匹配=MatchPat Body [Dec]-- pat-> body where decs数据Pat =VarPName-- variableConPName [Pat]-- constructor. . .数据体=NormalB Exp--只是一个表达式. . .数据Dec =ValD Pat Body [Dec]--v = e其中decsFunD Name [Clause [Pat] Body [Dec]]-- fp1. pn=e--在哪里decs图二. 表示Haskell语法2模板HaskellTemplate Haskell是Haskell的一个最新扩展，用于编译时元编程。这种扩展允许程序员观察程序代码的结构，并转换该代码，从中生成新代码或分析其属性。在本节中，我们总结了一些由扩展提供的设施。Haskell表达式的代码由代数数据类型Exp表示，类似地，Haskell程序的每个语法类别都表示，如声明（Dec）或模式（Pat）。在图2中，我们展示了这些数据类型的部分定义，我们将在后面的第4节中使用。准引用机制允许一个代表模板，即。编译时的Haskell程序准引号是通过放置括号，[|and|]，一种复杂的结构，例如： 的|\x->x|]中。204C. 塞古拉角Torrano/理论计算机科学电子笔记177（2007）201这个机制建立在一元库之上。引用monadQ将元编程特性封装为新名称生成。它是IOmonad的一个扩展。通常的一元运算符bind，return和fail都是可用的，还有do-notation [19]。函数runQ使Qmonad内的抽象语法树可用于IOmonad，例如用于打印。这就是我们需要知道的关于引用单子的一切。引用的Haskell代码的翻译使其抽象语法树作为ExpQ类型的值可用，其中类型ExpQ =Q Exp;例如。 的|\x->x|]：：ExpQ。TH提供语法构造函数建 立在 引用 单子 之上 它们 的名 字类 似 于代 数数 据类 型的 构造 函数 ， 例如lamE：：[PatQ] ->ExpQ->ExpQ。例如，我们可以构建表达式[|\x->x|]也可以写lamE[varP（mkName“x”）]（varE（mkName“x”）），其中mkName：：String-> Name。计算可以在编译时通过拼接符号$进行。它在编译时评估其内容（ExpQ类型），将生成的抽象语法树转换为Haskell代码，并将其插入程序中的调用位置。例如，[|\x->$qe|]在编译时计算qe，计算的结果，一个Haskell表达式qe' ， 被 拼 接 到lambda抽象中，给出[|\x->qe'|]中。我们将在第4节中使用准引用机制来分析和转换Haskell程序，并使用拼接符号来在编译时完成这一工作。一个漂亮的打印库Language.Haskell.TH.PprLib将有助于可视化我们示例的结果我们在这里没有使用Template Haskell的其他功能;感兴趣的读者可以查看[17，18]以获得更多细节。3不确定性分析与信案转换3.1动机像Haskell这样的函数式语言的实际实现使用按需调用的参数传递机制。一个参数只有在函数体中使用时才被求值;一旦它被求值为弱头范式，它就会被更新为新值，这样后续对该参数的访问就不会从头开始求值。这种机制的实现为实际参数构建了一个闭包或挂起，并在评估时进行更新。由let表达式绑定的变量也会发生同样的情况：当主表达式需要它的值时，它被求值并随后被更新。精确性分析[9，1，20，2]检测将由函数体评估的参数。在这种情况下，可以避免闭合结构，并且可以立即进行评估。这意味着按需调用被按值调用取代。同样的分析可以用来检测那些由let表达式绑定的变量，这些变 量 将由le t 的主表达式求值。 这些变量可以是C. 塞古拉角Torrano/理论计算机科学电子笔记177（2007）201205ee立即求值，这样let表达式就可以被转换成case表达式，而不需要修改表达式的语义[16]。这被称为let-to-casetransformation：设x = e，在E J中，x→ eJ的情形E。注意，这个转换假定case表达式有严格的语义。核心case表达式在判别式上是严格的，但Haskellcase具有唯一性变量模式的替代方案是懒惰的。 由于我们的分析和转换是在Haskell级别进行的，因此我们无法通过之前的转换获得预期的效果。此外，从类型的角度来看，它甚至可能是不正确的，因为let绑定变量是多态的，而case绑定变量是单态的。例如表述设x=[]，如果xof[]→（1：x，是类型正确的，因为x具有多态类型[a]，这意味着元组中x的两次出现的类型可能是它的不同实例，即[Int]和[Char]。但是它的变形版本case[ ]ofx→casexof[ ]→（1：x，不是类型正确的，因为x是单态的，并且两次出现的类型是不可统一的。然而，我们可以使用Haskell它将第一个参数赋值为弱头范式，然后返回第二个参数作为结果因此，我们转换如下：JJletx= ein x'seq '.3.2用抽象解释法可以通过使用抽象解释来进行精确性分析[10]。这种技术可以被认为是一种非标准的语义，其中值的域被值描述的域所取代，并且其中每个语法运算符都被赋予一个非标准的解释，允许在编译时近似于正在研究的属性的运行时行为。Mycroft [9]第一次给出了一阶函数语言的基于抽象解释的严格性分析。 后来，Burn等人[1]扩展了它，到高阶程序和Wadler [20]介绍了数据类型的分析。Peyton Jones和Partain [13]描述了如何使用签名来使抽象解释更加有效。我们在这里展示了一个基于抽象解释的严格性分析，用于Haskell的一阶子集的表达式和数据类型，其语法如图3所示。目前，这种分析对我们的目的来说已经足够了。在第5节中，我们讨论了高阶分析的扩展，以及一般的完整Haskell。206C. 塞古拉角Torrano/理论计算机科学电子笔记177（2007）201e→c{常数}| v{ variable}| e1op e2{primitive operator }| if e1then e2then e3{conditional}| λb.e{first-order lambda}| C e1...{constructor application}| e1e2{function application}| let v1 = e1... v n= e nine{let expression}| case e of alt 1... alt n{case表达式}alt→C b1. b n→ e| b → e图三. Haskell的一阶子集请注意，出于可扩展性的原因，我们允许lambda抽象作为表达式，但我们将其限制为一阶lambda抽象，即参数是只能绑定到零阶表达式的变量b由于语言是一阶的，唯一允许lambda抽象的地方是函数应用程序和let绑定的右侧。函数和构造函数应用程序必须饱和。Let绑定可以是递归的。请注意，如果我们取消前面提到的限制，我们就有了Haskell的高阶子集。这就是我们定义的原因。大小写表达式最多可以有一个默认选项（b→e）。基本的抽象值是和T，分别表示严格性和 算子H和H分别是最大下界和最小上界。为了表示函数在其不同参数中的严格性，我们在基本抽象值a上使用抽象函数。 例如，λa1.λa2.a1Ha2表示函数在两种情况参数，而λa1.λa2.a1表示它在第一个参数中是严格的，但我们对第二个一无所知。在图4中，我们展示了每个语言表达式的解释，其中ρ表示为变量分配抽象值的抽象环境。环境ρ+ [v→av]要么扩展环境ρ，如果变量v没有赋值的抽象值，或者更新v的抽象值（如果已经有）。的解释是标准的，所以我们只给出一些细节。原始二元运算符，如+或，在两个参数中都是严格的，所以我们使用H操作符.构造函数应用程序的抽象值是T，因为构造函数是惰性的。 例如，这意味着函数λx.x：[ ]在第一个论点。请注意，在列表抽象域中，我们已经安全地将Wadler [20]的四值抽象域折叠成二值域，其中例如，[1，1，2，3]和[1， 2， 3]被抽象为T，并且只有[1，2，3]被抽象C. 塞古拉角Torrano/理论计算机科学电子笔记177（2007）201207[[c]]ρ=T[[v]]ρ=ρ（v）[[e1ope2]]ρ=[[e1]]ρH[[e2]]ρ[[ife1thene2thene3]]ρ=[[e1]]ρH（[[e2]]ρH[[e3]]ρ）[[λb.e]] ρ = λa. [[e]]（ρ +[b →a]）[[C e1. n]] ρ = T[[e1e2]]ρ=[[e1]]ρ[[e2]]ρ[[让v1= e1. v n= e nin e]] ρ =[[e]] ρJ其中ρJ=fixff= λρ.ρ +[v1→ [[e1]] ρ，. v n→ [[e n]] ρ][[caseeofb→eJ]]ρ=[[eJ]]（ρ+[b→a]）其中a=[[e]]ρ[[备选案文1的e.情况.] altn]] p = aH（a1H. Han）（n >1）其中a=[[e]]ρai=[[alti]]ρa[[C b1. b n→ e]] ρ a =[[e]]（ρ +[b1→ a，. b n→ a]）[[b→e]] ρ a = [[e]]（ρ + [b→ a]）见图4。 抽象解释到了。在这三个例子中，将列表评估为弱头范式是安全的。在一个case表达式中，由case替代约束的变量继承了判别式的抽象值。当只有一个默认的替代情况时，懒惰，否则它是严格的判别式。由于我们使用一阶抽象函数作为抽象值，函数应用可以很容易地解释为抽象函数应用。为了解释let表达式，我们需要一个标准的定点计算，因为它可能是递归的。3.3签名基于抽象解释的高阶函数分析是昂贵的。可以使用Signatures [13]来提高其效率，尽管它们意味着在分析中失去了一些精确度。我们在实现中使用它们，因为我们对完整的Haskell分析感兴趣。 不确定性基本签名是不确定的，T. n 个 参 数的函数的签 名 是签 名 的 n元组（s1，. ，s n）指示函数在每个参数中是否严格。 例如，（t，T，t）是一个有三个参数的函数的签名，第一个和第三个参数是严格的。一个n元函数的严格签名是通过用n参数的组合分量si通过应用以下函数计算：208C. 塞古拉角Torrano/理论计算机科学电子笔记177（2007）201第i个参数的值为T，其余参数的值为T。例如，函数λx.λy.λz.x + y的签名（λ，λ，T）可以通过将函数应用于（λ，T，T），（T，λ，T）和（T，T，λ）来获得。当考虑高阶时，必须使用适当函数类型的签名来探测函数例如，在λf.λx.f3+x中，第一个参数是一个函数，因此必须用（（，），T）和（（T，T），）来探测它，给出（，），如下所示：预期在第5节中，我们将讨论在这种情况下遇到的问题，当试图扩展分析时。4使用Template Haskell实现在本节中，我们将描述使用Template Haskell实现严格性分析和相应的转换。给定一个Haskell表达式e，程序员想要求值，这是他/她必须编写的模块module Mainwhereimport严格import System.IO导入语言.Haskell.THmain = putStr（show $（int m [|e|]））模块Strict包含转换函数和严格性分析。首先，我们引用Haskell表达式，以便能够检查抽象语法树;然后我们使用下面定义的函数m修改这样的树。我们使用$在编译时执行转换。这些小的修改可以是平凡的概括，他们甚至可以完全透明的，程序员如果我们自动生成它们如果我们想让新的pass做其他的事情，我们只需要修改函数fieldm。4.1敏捷性分析实现分析由函数strict：：Exp -> Env -> AbsVal执行，给定表达式和严格环境，该函数返回表达式的抽象值抽象值使用数据类型AbsVal表示：数据库Annot= Bot|顶部导出（显示，Eq）data AbsVal = B tAnnot|F [tAnnot]|FB内部基本的注释是表示严格性的Bot和表示“不知道”值的BTop具有n个参数的函数的抽象值通过形式F[b1，b2，...，bn]，其中每个bi表示函数在第i个参数中是否严格。特殊FB n值是一个具有n个参数的完全Unfined函数的抽象值也就是说，函数抽象域的底部，这在几个地方很有用。转换函数调用函数strict，但如果我们想单独C. 塞古拉角Torrano/理论计算机科学电子笔记177（2007）201209strict：：Exp -> Env -> AbsValstrict（VarE s）rho = getEnvsrhostrict（LitE l）rho =BTopstrict（InfixE（Just e1）e（Juste2））rho=如果（isCon e），则（B Top）else inf（stricte1 rho）（stricte2rho） strict（CondE e1 e2 e3）rho =inf（严格e1rho）(sup（严格e2 rho）（严格e3rho））图五.敏捷性分析实现-基本案例用例子证明原型，我们可以写如下：main = putStr（show $（strict2[|e|]空））其中e是我们要分析的封闭表达式，empty表示空的严格环境，函数strict2定义如下：strict2：：ExpQ -> Env -> ExpQstrict2eq rho = do {e- eq;return（toExp（strict e rho））}其中函数toExp：：AbsVal -> Exp只是将抽象值转换为表达式。请注意，分析是在编译时进行的，我们将strict2定义为从一个表达式到另一个表示其抽象值的表达式的转换这是因为编译时的计算发生在引用monad中，所以strict2的参数和结果都必须是ExpQ类型。我们使用do-notation来将strict封装到一元世界中。函数strict是通过抽象语法树上的大小写区分定义的实际严格性分析：我们需要记住Exp数据类型定义（如图所示（图2）和我们语言的限制（在前面的部分中解释过）。在图5中，我们展示了常量、原始运算符、变量和条件表达式的解释，如前一节所示我们必须小心使用in fix运算符，因为一些构造函数，如list：，是in fix的。我们区分使用函数isCon，我们在这里没有显示。 运算符inf计算最大下界和最小上界，getEnv从环境中获取变量的抽象值在图6中，我们展示了lambda抽象的解释 其值是签名F [b1，...，bn]，n是参数的个数，通过用几个参数的组合探测函数得到，正如我们在3.3节中解释的那样。我们从第一个参数开始探测函数首 先 ，我们给它的值B Bot和辅助函数strictaux给其余的参数，值B顶部。然后我们给它一个值B Top，并递归地探测其余的的论点。 通过这种方式，我们获得了我们想要的所有组合。在图7中，我们展示了构造函数和函数应用程序的解释从语言的角度来看，它们是同一种表达方式，210C. 塞古拉角Torrano/理论计算机科学电子笔记177（2007）201strict（LamE（（VarP s）：[]）e）rho =设Bb=strictaux e（addEnv（s，0，B Bot）rho），如果（stricte（addEnv（s，B Top）rho））B b1 -> F（b：[]）F bs -> F（b：bs）strictaux：：Exp ->Env->AbsValstrictaux（LamE（（VarPs）：[]）e）rho=strictaux e（addEnv（s，BTop）rho）strictaux e rho=strict erho见图6。 精确度分析实现-Lambda表达式strict（ConEcons）rho =BTopstrict（AppE（ConEcons） e）rho=BTopstrict（AppEe1 e2）rho =if（isCon e1）thenBTopelse absapply（strict e1 rho）（stricte2 rho）absapply：：AbsVal -> AbsVal -> AbsValabsapply（FB n）a| n==1 =B机器人| n>1= FB（n-1）absapply（F（h：tl））（B b）| nullt1= B x| x== Top = Ftl| 否则= FB（长度tl），其中x=sups h b图7.第一次会议。敏捷性分析实现-应用所以我们再次使用函数isCon来区分它们。如果是函数应用程序，absapply执行抽象函数应用程序。抽象值FB n表示完全未定义的函数，因此它在完全应用时返回BBot，在有剩余参数要应用时返回FB（n-1）当签名F[b1，...，bn]应用于抽象值B b，我们需要知道它是否是最后一个参数。如果是这种情况，我们可以返回一个基本值，否则我们必须返回一个函数值。结果的抽象值取决于b1和b。如果b1是Top，则函数在其第一个参数中不一定是严格的，因此独立于b的值，如果它是最后一个参数，则我们可以返回B Top，或者通过返回列表的其余部分来继续将函数应用于其余参数如果b是Top，也会发生同样的情况，因为头部xs是通过给第一个参数值Bot获得的：我们已经丢失了信息，我们唯一能说的是C. 塞古拉角Torrano/理论计算机科学电子笔记177（2007）201211strict（LetE ds e）rho= stricte（strictdecs ds rho）strictdecs：：[Dec] ->Env->Env strictdecs [ ] rho= rhostrictdecs ds rho=让（varns，es）=splitDecsds init=extendEnv rho varnsf=\rhoaes = map（flip strict在combinesfix g（env，False）= env在fit（init，True）见图8。 精确度分析实现-let表达式如果b1和b都不是Top（即当最小上界sups返回Bot时），则函数在其第一个参数中是严格的，这是unfined，所以我们可以独立于其余参数返回B Bot然而，如果剩下参数，我们返回完全未定义的函数FB（n-1）。在图8中，我们展示了let表达式的解释辅助函数strictdecs执行定点计算。函数splitDecs将左侧（即绑定变量）和声明的右侧初始环境init是通过扩展环境构建的，新变量绑定到适当类型的未定义抽象值，由extendEnv完成。函数combines在每个定点步骤中用新的抽象值更新环境;当环境没有改变，因此到达定点时，它也返回一个布尔值False最后，在图9中，我们展示了一个case表达式的解释函数nostrict如果是惰性case表达式，则返回true。casealt的前两个分支对应于构造函数模式匹配（fix或prefix中），第三个分支对应于变量alternative。函数suplist计算备选方案的最小上限，casealt解释每个备选方案。由情况选择约束的变量继承判别式的抽象值，这由函数addEnvPat完成。例4.1给定表达式\x->\y->3 * x，分析返回F[Bot，Top]，正如预期的那样;即函数在第一个参数中是严格的。示例4.2另一个使用case表达式的示例如下：\x->\z->情况1：[]of[]->xy：ys -> x + z212C. 塞古拉角Torrano/理论计算机科学电子笔记177（2007）201strict（CaseE e ms）rho =让se =严格 e rhol= caseaux msse rhosl=suplist l在if（nostrictms）then slelse（inf se sl）caseaux：： [Match] -> AbsVal -> Env -> [AbsVal]caseaux ms se rho = map（casealt se rho）mscasealt：：AbsVal->Env->Match->AbsValcasealt abs rhom=案例mMatch（InfixP（VarP h）con（VarPtl））（NormalBe）[]->letrho在严格的erho'Match （ ConP con ps ） （ NormalBe）[]->letrho匹配（VarP x）（NormalBe）[]->letrho见图9。 准确性分析实现-case表达式结果是F[Bot， Top]，正如预期的那样，告诉我们函数在第一个参数中是严格的，但在第二个参数中可能不是，尽管我们知道它是。注意精度的损失。这是因为分析是静态的，而不是因为实现。例4.3在实现中使用签名意味着相对于第3节中所示的分析而言精度的损失。例如函数\x->\y->\z->如果z则x否则y具有抽象值λa1.λa2.λa3.a3H（a1H a2），但实现将为其分配签名F [Top，Top，Bot]，该签名与抽象值λa1.λa2.λa3.a3不可区分。函数\x->\y->\z-> z具有相同的签名。4.2改造实施字母到大小写的转换也是以类似的方式发展起来的。我们希望转换函数不仅应用于顶层的主表达式，而且在可能的情况下，还应用于它的所有子表达式。例如，在x +z中的函数\x->letz= 3可以转换为在x + z中的函数\x->letz=3。z'seq'（x + z）。但是，即使主表达式是关闭的，subex-C. 塞古拉角Torrano/理论计算机科学电子笔记177（2007）201213transf：：Exp->Env->Exptransf（LetE ds e）rho =如果（isFunRecords），则让(vs，es）= splitDecs dsrho让我们一起案件（标题ds）ValD（VarP x）（NormalBtete= transfe（addEnv（x，B Top）rho）dsFbs =strictlambda rho inif（headbs）==Bot thenLetEds(VarE（mkName“Prelude：seq”））（Just te））否则我们走见图10。 let表达式变量可以有自由变量。因此，我们需要一个严格的环境，最初是空的，携带自由变量的抽象值：Eq e= Eq 2 eempty Eq 2：：ExpQ->Env->ExpQ Eq 2 eq rho=do {e-eq;return（transf e rho）}在这种情况下，如果我们想查看转换的结果，而不是转换后的表达式的求值，我们可以使用monad的函数runQ，它允许我们在继续进行其余的编译之前提取转换后的表达式然后我们用函数ppr从库Language.Haskell.TH.PprLib中打印它：main =do {e- runQ（2 q empty）;putStr（show（ppr e））}做所有重要工作的函数是transf。我们在图10中只显示了最有趣的情况，let表达式。我们假设出现在let表达式中的几个定义是相互递归的。编译器将这些定义划分为强连接的组件，以便214C. 塞古拉角Torrano/理论计算机科学电子笔记177（2007）201尽可能多的多态性。所有准引用代码的内容都经过类型检查[8]，因此这似乎是一个合理的假设。因此，当let表达式定义一个函数或者是一组递归定义（由函数isRecordFun告诉）时，我们不需要在顶层应用转换，但是我们可以在声明的右侧和let的主表达式中应用它。当转换这些表达式时，绑定变量的抽象值是不相关的，所以我们给它们顶部的抽象值。这是由addEnvtop完成的。当在eJ中只有一个非递归绑定letx=e时，我们构建一个lambda抽象λx.eJ并分析它，以查看let的主体在绑定变量中是否如果是这样的话，转换就完成了。在同一此时，装订线的右手侧和主体也可以被变换。示例4.4以下表达式设a = 1in a + b设b = 2ina + b转换为：设a_0 = 1在a_0 Prelude：seq（let b_1 = 2在b_1 Prelude中：seq（a_0 GHC.Num.+ （b））例4.5在下面的例子中，可以看到转换不仅可以发生在顶层，而且可以发生在主表达式的任何子表达式中。功能\x->（设a=1ina+3）*（设y=2iny+x）转换为：\x_0 ->（设a_1=1，在a_1 Prelude：seq（a_1GHC.Num.+ （ 3））GHC编号 *(let在y_2 Prelude：seq（y_2 GHC. Number.+ x_ 0 ））5结论和今后的工作在本文中，我们已经研究了如何使用模板Haskell，以纳入新的分析和转换的编译器，而无需修改它。我们已经提出了一个严格性分析和随后的let-to-case转换的实现。源代码可以在http://dalila.sip.ucm.es/miem-bros/clara/publications.html上找到。这些都是众所周知的问题，这使我们能够专注于使用Template Haskell的困难和局限性，请参阅下面的讨论。据我们所知，这是Template Haskell第一次被用于开发静态分析。在尝试使用Template Haskell之前，我们考虑并放弃了另外两个选项。首先，有一些编译工具可用于GHC（见http://www.has-kell.org/libraries/#compilation），这些工具对编写分析原型很有用，但我们的目标是使用分析的结果，并继续使用GHCC. 塞古拉角Torrano/理论计算机科学电子笔记177（2007）201215毛发形成过程其次，分析和转换通常是在一种简化的语言上完成的，在这种语言中，语法糖已经消失了：GHC中的Core。目前，那些有兴趣编写新的简化器的研究人员只能通过将 他 们 的 代 码 链 接 到 GHC 可 执 行 文 件 中 来 实 现 ， 这 并 不 简 单 。 在http://www.haskell.org/-ghc/docs/latest/html/users guide/ext-core.html中，提供了Core的正式定义（草案）但目前只能将简化阶段后获得的Core代码以这种外部格式转储到文件中。我们现在讨论在当前状态下使用Template Haskell的有用性，以及可以改进或添加哪些功能以增加它。该分析是针对Haskell的一阶子集开发的。这是相对容易定义的。这里唯一的困难是没有一个适当注释的库文档这种分析方法可以推广到高阶程序.我们暂时没有这样做，原因如下。当分析高阶函数时，有必要探测具有函数签名的函数，我们必须生成函数签名，正如我们在3.3节中解释的那样。为了生成这样的签名，我们需要知道函数有多少个参数如果我们在语法树中有可用的类型，它将再次变得微不足道。在这个分析中，探测签名非常简单;如果参数函数有n个参数，那么探测签名是FBn。但在其他分析中，如非确定性分析[14]，探测签名更复杂，类型是正确生成它们的基础。尽管模板Haskell [8]有一个类型算法，但类型信息并不保存在语法树中。我们当然可以开发自己的类型算法，但如果不集成到工具中，对其他用户没有帮助。这对于我们计划研究的基于类型的分析也非常有用。使用Template Haskell进行分析和转换有几个缺点。首 先 ， 必 须 为 完 整 的Haskell定义分析和转换。如果可以控制我们希望在编译器的哪个阶段访问抽象语法树，那么定义Core的分析就有意义了，但目前情况并非如此。如果分析是为Haskell的一个子集定义的，就像我们的一样，那么就有必要研究GHC的去Sugar器所做的转换，以确定如何分析加糖的表达式。当我们想向用户提供有关分析结果的信息时，在编译过程的最开始进行分析仍然很有用在这种情况下，我们希望引用他/她编写的原始变量，这些变量通常会在编译器的后续阶段丢失请注意，在我们的示例中，变量被索引，但它们仍然保持原始的字符串名称。然而，去succurr生成程序员未知的新变量第二，我们只能从那些其结果被随后的变换所使用的分析中获益。分析的结果不能传播到其他地方。216C. 塞古拉角Torrano/理论计算机科学电子笔记177（2007）201编译器的阶段，这将是一个由他们审查。这种情况的例子是非确定性分析[14]，其结果用于停用简化器所做的一些转换，或者使用分析[21]，其影响到编译器生成的STG代码。因此，在其当前状态下，Template Haskell对于开发基于解释的分析非常有用，其结果可用于转换Haskell代码，并轻松将此类转换纳入编译过程。引用[1] G. L.伯恩角L. Hankin和S.艾布拉姆斯基高阶函数的线性分析理论。作为数据对象的程序，LNCS第217卷，第42-62页。Springer-Verlag，1986年10月。[2] T. P. Jensen 逻 辑 形 式 中 的 不 确 定 性 分 析 In R. J. M. Hughes ， 编 辑 ， Functional ProgrammingLanguages and Computer Architecture ， LNCS 第 523 卷 ， 第 352-366 页 。 Springer-Verlag ， NewYork，1991.[3] 联合 Klusik，Y. 或者是-M all l'en和R。 Penntoucha.ImplementingEden-or：Dr e ams Be comeR eality.在第10届函数式语言实现国际研讨会论文集，IFL'98，LNCS第1595卷，第103-119页。Springer-Verlag，1999.[4] 联合 克卢西克河 Pena和DC. 塞古河 比帕是在伊甸园里的钱尼。 在P。 Trinder，G. Michael s on和H.-W. Loidl，编辑，函数式编程趋势。第一届苏格兰函数式编程研讨会论文集，SFP'99，第2-10页。智力，2000。[5] R. Loogen，Y. Ortega-Malll'en，R. Penapa，S. Priebe和F。 鲁比奥。 P a r a l l el和DistributedComputing的Patter nsandSke let ons。F. Rabhi和S.Gorlatch（eds.）《伊甸园中的抽象》，第95-128页。Springer-Verlag，2002.[6] I.LynaghTemplateHaskell：来自现场的报告。（http://web.comlab.ox.ac.uk/oucl/work/ian.lynagh/papers/），2003年。[7] I.Lynagh 使 用 模 板 Haskell 展 开 和 简 化 表 达 式 。 （ http://web.comlab ）
我的内容管理
展开
