递归数据类型的特化与优化——泛型编程的新方法

理论计算机科学电子笔记229（5）（2011）57-74www.elsevier.com/locate/entcs递归类型泛型函数的代数特殊化阿尔西诺·库尼亚1号和乌戈·帕切科2号DEP. deInformatica（CentrodeCienciaseTecnologiasdaComputacao），UniversidadedoMinho，Campus deGualt，P-4710-057，Braga，葡萄牙摘要在大型的，可能是递归的数据结构上定义函数通常涉及到很多样板文件。这段代码只是遍历数据中不感兴趣的部分，很快就变成了一个可维护性问题。 已经提出了许多泛型编程库来解决这个问题。 它们中的大多数允许用户仅为结构中感兴趣的部分指定行为，并提供遍历组合子来“废弃样板”。这些库的表达能力通常以效率为代价，因为运行时检查用于检测在何处应用类型特定的行为。在以前的工作中，我们已经开发了一个有效的重写系统的专业化和优化的通用程序。在本文中，我们将其扩展到也包括递归数据类型。其关键思想是使用众所周知的递归模式（如折叠或仿形）来专门化遍历组合子。这些都是由一组丰富的代数定律所支配的，这些定律可以实现积极的优化。我们提出了一个类型安全编码的重写系统在Haskell中，基于最近的语言扩展，如类型索引类型的家庭。关键词：泛型编程，递归模式，重写系统，特化，类型族1引言用函数式语言对现实世界的问题建模通常会导致大量的递归数据类型，每种类型都有许多不同的构造函数。例如，当开发语言处理工具时，语法使用每个非终结符的不同数据类型和每个产生式规则的不同构造函数来类似地，模式感知的XML处理通常涉及将一个巨大的模式映射到一个等效的数据类型，将许多元素中的每一个映射到不同的这种数据类型的扩散使得即使是概念上简单的函数也很难实现，这些函数操作数据构造函数的一个非常小的子集。1电子邮件：alcino@di.uminho.pt2电子邮件：hpacheco@di.uminho.pt1571-0661 © 2011 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2011.02.01658A. Cunha，H.Pacheco/Electronic Notes in Theoretical Computer Science 229（5）（2011）一个经典的（但仍然是良性的）用来说明这个问题的例子是所谓的假设有一个XML模式来建模一个有几个部门的公司，每个部门都有一个名称、一个经理和一组雇员或子部门。这个模式可以用下面的Haskell数据类型表示dataCompany=C[Dept]dataDept=D Name Manager[任一员工部门]data员工=E人员工资数据人员=P姓名地址数据工资=S Int类型经理=雇员typeName=StringtypeAddress=String假设人们还想定义一个函数，使所有工资增加一个固定的量k。这个函数的一个可能的定义是increase：：Int→Company→Companyincrease k（C ds）=C（map（incDk）ds）其中incD k（D nm mgr us）=D nm（incE k mgr）（map（incU k）us）incU k（Left e）=Left（incE k e）incU k（Right d）= Right（incD kd）incE k（E p s）= E p（incS ks） incS k（S s）=S（s+k）即使是这个相当简单的定义也充满了样板代码，其唯一的目的是执行公司数据类型的标准遍历，以发现工资增加。除了美学上的原因，这种样板有一些主要的缺点：（1）它使代码理解相当困难，因为唯一的交互函数（在这种情况下是inCS）在大量不感兴趣的代码中丢失了;（2）它很快成为一个可维护性问题，因为每个模型演化都意味着对许多函数的更改，这些函数只涉及模型的一部分，而不是演化所涉及的部分。已经提出了许多泛型编程库来解决这个问题。它们中的大多数允许用户仅为结构中感兴趣的部分指定行为最成功的库之一是方便命名的使用这个库，增加函数可以重新定义如下。increase：：Int→Company→Company increasek=everywhere（mkT（incS k））其中incS k（S s）=S（s+k）A. Cunha，H.Pacheco/Electronic Notes in Theoretical Computer Science 229（5）（2011）59everywherecombinator以自底向上的方式遍历数据结构，将给定的泛型转换应用于其所有节点。mkT组合子从类型特定的转换构建了一个泛型转换：给定一个函数f：：a→a，mkT f对于所有类型a的值都表现得像f，否则就像恒等函数。除了更容易理解增加的作用之外，即使公司数据类型发生变化，其定义也将保持不变。不幸的是，这种风格的泛型编程提供的明显优势是有代价的：泛型函数的性能比类似的非泛型函数差得多。在[18]中，一组标准基准函数的SYB实现被报告比非通用实现平均慢7倍。这种性能损失的一部分是由于运行时检查需要在每个节点上确定是应用特定的还是通用的。剩下的是由于这种风格的泛型编程固有的结构原因：遍历组合子必须盲目地遍历整个数据结构，即使某个分支没有提到特定行为适用的类型。一些新的SYB类泛型编程库已经被提出来解决这个效率问题。根据最近的调查[20]，其中两个最有效的是Uniplate [18]和Smash [11]。前者通过限制遍历组合子的能力而优于SYB。后者将一些运行时检查设置为编译时检查，但需要程序员进行额外的工作以支持新的数据类型。在以前的工作[7]中，我们采取了不同的方法来解决这个问题：我们开发了一个重写系统，专门针对特定类型的通用函数。这种专门化分为两个阶段：（1）将泛型函数专门化为非优化的无点定义;（2）然后使用无点组合子的标准代数定律优化这些定义。这种方法的主要缺点是缺乏对用户定义的递归类型的支持，例如上面的Company类型本文的主要贡献是扩展了专门化机制，使其也涵盖递归数据类型。更具体地说，我们将专注于可以定义为函子定点的归纳数据类型。其关键思想是使用归纳类型的众所周知的递归模式（如折叠或仿形）对遍历组合子进行特殊化。与标准的无点组合子类似，这些递归模式的特征也在于丰富的代数定律集，这些代数定律可以在专门化后进行进一步的优化。新重写系统产生的大多数定义的运行时都接近于手写的非泛型定义。另一个贡献是这些新定律的Haskell编码：由于最近的语言扩展，如类型索引类型族，我们设法得到了一个与理论非常相似的实现第2节简要介绍了泛型编程的SYB方法，并回顾了我们以前在非递归类型的泛型函数专门化方面的工作第3节用递归类型专门化的新代数规则扩展了这项工作.第4节讨论了如何将这些新规则60A. Cunha，H.Pacheco/Electronic Notes in Theoretical Computer Science 229（5）（2011）Haskell中实现的类型安全重写系统。第5节介绍了专门化的例子，并比较了各自的加速比。第6节介绍了相关工作，第7节做了一些总结，包括一些未来的工作思路。2非递归类型的专门化在本文中，我们将重点关注一组有限的组合子，它们捕捉了SYB等战略泛型编程库的本质。泛型函数有两种类型：类型保持（转换）和类型统一（查询）。为了定义类型保持函数，我们有以下组合子：nop：：T（D）：：T→T→TgmapT：：T→Teverywhere：：T→TmkTA：：（A→A）→TapTA：：T→（A→A）在SYB库中，类型保持泛型函数的类型T定义为你好数据aa→a。像Data这样的类型类在SYB中被广泛使用，推断数据类型的类型表示。其中，这些在mkT的定义中是必要的，以确定类型特定的转换应该应用于何处。为了简化表示，我们将使用显式类型表示来参数化mkT，而不是使用类型类。除了无处不在之外，我们还有组合子来将变换映射到节点的所有直接子节点（gmapT），序列变换（D），并表示恒等变换（nop）。我们还有一个显式的组合子来将泛型转换应用于特定类型（apT）。在SYB中，这是通过类型类隐式完成的。增加所有工资的转换现在将写如下。增加：：Int→Company→Company增加k=apT公司无处不在（mkT工资（incS k））其中incS k（S s）=S（s+k）为了定义类型统一函数，我们有以下组合子：中文（简体）（）：：Q R→Q R→Q RgmapQ：：Q R→Q R一切：：Q R→Q R mkQA ：：（A→R）→Q R apQA：：Q R→（A→R）在这种情况下，Q R表示结果类型为R的通用查询的类型。再次，为了简化专门化定律的表述，我们假设： R是一个幺半群，有一个零元素和一个结合加算子。在实际操作中，A. Cunha，H.Pacheco/Electronic Notes in Theoretical Computer Science 229（5）（2011）61id：：A→A（）：：（B→C）→（A→B）→（A→C）π1：：A×B→Aπ2：：A×B→B（Δ）：：（A→B）→（A→C）→（A→B×C）×：：（A→B）→（C→D）→（A×C→B×D）i1：：A→A+Bi2：：B→A+B（C）：：（A→C）→（B→C）→（A+B→C）（+）：：（A→B）→（C→D）→（A+C→B+D）Fig. 1.无点组合子这几乎没有区别，因为大多数典型的结果，即列表和整数，确实是幺半群。mkQA从类型特定的查询中创建一个泛型查询，对于A以外的类型返回零。everything使用加号运算符在自底向上遍历中收集所有结果gmapQ收集将查询应用于所有直接子查询的结果，对两个查询的结果进行求和，并且表示始终返回零的查询。要将泛型查询应用于特定类型，我们有apQ。例如，要计算公司的总工资账单，我们可以定义以下通用查询：工资：：公司→国际salaries=apQ公司的一切（mkQSalarybillS）其中billS（S s）=s在以前的工作[7]中，我们已经提出了一个重写系统，将泛型函数专门化在无点编程风格中，函数是使用一组标准的高阶组合子组成的，避免了显式地将域点作为变量。这种无变量风格（由John Backus在他1977年的图灵奖演讲中推广[2]）特别适合程序计算，因为它的组合子具有丰富的代数定律。我们使用一组相当标准的无点组合子来处理乘积和和（见图1）。它们的行为应该在类型签名中很清楚。关于这个组合子和无点程序计算的更多信息，请参见[9，5]。大多数用户定义的数据类型可以定义为常规函子的定点。捕获数据类型A签名的基函子将表示为FA（当类型A在上下文中很清楚时，我们通常会在下标中省略它）。正则函子可以是恒等函子Id、常数函子A（总是返回A）、和双函子和乘积双函子的提升或函子的复合。例如，对于列表，我们有F[A]=1AId。如果类型不是递归的，它的基函子将没有任何标识。比如说，F（也许A）=1<$A。与每个数据类型A相关联，我们也有两个唯一的函数inA：FAA→A和outA：：A→FA A，它们是彼此他们允许我们分别编码和检查给定类型的值62A. Cunha，H.Pacheco/Electronic Notes in Theoretical Computer Science 229（5）（2011）ΣapTAnop=id nop-APPLYapTA（fDg）=apTAfapTAgapTA（gmapT f）=id，ifA base typeapTA（gmapT f）=inAapTF AfoutA，ifA datatypeD-A应用程序gmapT-应用程序apTA（everywhere f）=apTA（gmapT（everywhere f）Df）everywhereapTA（mkTA f）=fapTA（mkTB f）=id，如果A/mkTBAmmkT-应用程序apTA×Bf=apTAf×apTBf×-A应用apTA+Bf=apTAf+apTBf+-A应用apT1f=id1-APPLY图二、专门化泛型转换的法则图2展示了用于将类型保持组合子专门化为无点组合子的法则。专门化通过向下推apT组合子来进行，直到它被mkT-A应用定律消耗。对于类型统一组合子也存在类似的定律。虽然不是通用的，但由专门化阶段产生的定义是非常不必要的，因为它们仍然遍历整个数据结构。然而，使用无点程序计算法则，它们可以被优化以消除冗余遍历。请注意，无处不在的应用法则使用了这个遍历组合子的递归定义，使用了gmapT和D。由于先前的重写系统只处理非递归的用户定义的数据类型，因此该定律不会造成任何终止问题。然而，对于递归类型，它不能使用，因为它会导致定义的无限扩展（由于类型递归出现时处处连续扩展3递归类型避免无限扩展的关键是使用基于标准递归模式（如折叠）的替代定义来专门化遍历组合子。与无点组合子一样，这些递归模式的特征在于强大的代数定律，这将使我们能够优化专门的定义。关于大多数标准递归模式和相应定律的全面介绍，请参见[17]。迭代的标准递归模式，通常称为折叠或变形，通过用给定的参数函数替换其构造函数来消耗归纳类型。 对于归纳型A，给定函数g：：F B → B，（|G|）A：：A →B表示在该类型上的折叠，其产生类型B的值。它的递归定义可以在下图中清楚地描述AoutAF A（|G|）ACJF（|G|）ACJB，g虽然folds可以表示由迭代定义的函数，但paramorphism可以表示A. Cunha，H.Pacheco/Electronic Notes in Theoretical Computer Science 229（5）（2011）63（|中|）A= idre pixelex-C ATA（|G|）Ain A= g <$F（|G|）Acancel-C ATA2016年10月22日，|G|）A=（|H|）Af g = h F ffusion-C ATA（|in[A]（id + f×id）|）[A]= map fmap-C ATA⟨|在A<$F π1中|A= idRE⟨|G |A|G |AΔ id）cancel-P ARAf |G |A= |H|A⟨|f<$F π1|A=（|F|）Acata-P ARA图3.第三章。褶皱和变质的一些规律按下所有可以由原始递归定义的函数[16]。实际上，这意味着结果不仅依赖于递归结果，还依赖于类型的递归出现。对于归纳型A，给定一个函数g：：F（B×A）→B，|G|A：：A→B表示在该类型上产生B类型值的仿形。同样，它的递归定义可以用一个图表来表达。AoutAF AF（idΔid）F（A×A）×|G|A.A.CJF（×|G |A× id）JC地下bF（B×A）注意递归调用之前是如何复制递归实例的。对于定义为折叠和仿形的函数的优化，我们将使用图3中给出的定律。当应用于归纳类型时，自底向上的遍历将被专门化为该类型上的折叠。无处不在-应用 定律现在将被定义如下。A =A（|apT A f in A apTF A（everywhere f）|）A通过下图可以更好地理解此折叠的行为AoutAF A（|·|）ACJF（|·|）ACJA，A，在F A，F AapTAfAapTF A（处处f）函数apTF A（everywhere f）的目的是将转换应用于类型的所有内容，除了它的递归出现（已经由折叠本身递归处理）。此行为是通过将以下定律添加到图2中所示的集合来实现的：apTAf=id rec-APPLY这条定律保证apT忽略用上划线标记的类型组合子例如，对于列表，apTF A（everywhere f）将被实例化为apT1+ A ×[A]（处处f），等价于id + apTA（处处f）× id。64A. Cunha，H.Pacheco/Electronic Notes in Theoretical Computer Science 229（5）（2011）输出AΔ由于处处f是自底向上的遍历，在转换递归出现和剩余内容之后，f仍然需要应用于结果值。要做到这一点，首先使用inA来重构A类型的值，然后应用apTA f。要将泛型转换的特殊化转换为递归类型，请考虑以下示例，其中f=mkTIntsucc：apT[Int]（everywhere f）={everywhere-APPLY}（|apT [Int]（mkT Intsucc）在[Int]中取apTF [Int]（everywhere f）|）[Int]={mkT-APPLY;+-APPLY;×-APPLY;rec-APPLY}（|id int[Int] int（id + apT Int（everywhere f）× id）|）[Int]={everywhere-APPLY}（|in[Int]（id + apT Int（gmapT（everywhere f）D f）× id）|）[Int]={D-APPLY;gmapT-APPLY}（|in[Int]（id+（id apT Int（mkT Int succ））× id）|）[Int]={mkT-APPLY}（|in[Int] int（id + succ × id）|）[Int]={map-CATA}地图成功正如预期的那样，如果将f应用于不包含整数的类型，是恒等函数：apT[Char]（处处f）{... }（|in[Char]（id+（id apTChar（mkT Intsucc））×id）|）[字符]={mkT-APPLY}（|in[Char]（id + id × id）|）[字符]={id×id=id;id+id=id}（|在[Char]|）[字符]={re ex-CATA}ID自底向上的everythingcombinator将被特化成一个paramorphism：apQA（所有f）=⟨|加上<$（apQFR（一切f）× apQA f）<$（F π1Δ in A<$F π2）|A.A.再一次，用一个图表来理解这种变形现象更容易：F（idid）AFAF（A×A）×|·|A.A.CJF（×|·|A×id）CJR，R×R，F R×A，F（R×A）加上apQFR（所有f）×apQAfFπ1ΔinA<$Fπ2A. Cunha，H.Pacheco/Electronic Notes in Theoretical Computer Science 229（5）（2011）65在递归之后，输入值将使用inA重新构造，以便将其提供给通用查询。同时，查询被应用于非递归类型的内容，最后两个结果都用monoidplus运算符放在一起。4Haskell中的编码为了将上述代数定律应用到类型安全的重写系统中，泛型函数的特殊化，我们必须为函数和类型提供类型安全的表示。对于函数，我们将使用[7]中提出的相同表示，基于广义代数数据类型（GADT）[19]：数据PF a其中Id：：PF（a→a）（Δ） *PF（a→b）→PF（a→c）→PF（a →（b，c））（×）：：PF（a→b）→PF（c→d）→PF（（a，c）→（b，d））（×）：：PF（a→c）→PF（b→c）→PF（ab→c）（+）*PF （a→b）→PF（c→d）→PF（a c之一→b d之一）mkT：：类型a→PF（a→a）→PF TapT：：Type a→PF T→PF（a→a）...此类型包含无点组合子和SYB组合子。泛型转换和查询具有以下类型：类型T=α。类型a→a→ a类型Q r=α。类型a→a→ r不使用类型类来推断类型表示，而是显式地将这些类型传递给泛型函数。类型表示也使用GADT定义。对于基本类型，和和和积，类型a可以定义如下。dataTypeawhereInt：：TypeIntChar：：TypeChar...Sum：：Type a→Type b→Type（Either ab）Prod：：Type a→Type b→Type（a，b）功能：类型a→类型b→类型（a→b）使用GADT编码组合子的一个结果是能够定义求值函数eval：：PF a→a。例如，mkT的求值严格遵循SYB语义：eval（mkT a f）=λb x→Just Eq的caseteq a b→eval f x无x66A. Cunha，H.Pacheco/Electronic Notes in Theoretical Computer Science 229（5）（2011）如果将结果泛型函数应用于类型a的值，则其行为与f相同，否则将其行为与恒等函数相同。函数teq测试了类型表示的相等性，并且现在是GADT有用性的经典例子[19]：data等于a b其中等式：：等于a ateq：：Type a→Type b→Maybe（Equal ab）teq Int Int=return Eqteq（Sum a b）（Sum c d）=do等式←teq a cEq←teq b dreturn Eq...Teq=无EqualGADT的构造函数Eq可以看作是类型a和b的证明的确是平等的。用户定义的递归类型的表示直接遵循第2节中给出的理论定义。 对于每个类型A，我们需要表示它的基函子F A。 当将一个仿函数应用于另一个类型时，我们希望得到一个作为结果的乘积的和，能够用无点组合子处理。如果函子是用正常的Haskell多态数据类型定义的，那么就不可能获得这种行为，因为Haskell中的类型等价不是结构性的，而是基于名称的。为了克服这个问题，我们决定使用类型索引类型家族来表示函子[21，3]，这是GHC中已经支持的Haskell类型系统的新扩展。在开发时考虑到类型级编程，类型族是表示类型集的类型构造函数。集合成员根据传递给类型族构造函数的类型参数聚合，称为类型索引：族构造函数可以为不同的类型索引提供不同的表示类型。表示函子的类型族可以定义如下。类型族F a x：：在这个定义中，a是类型索引，代表其函子被定义的类型，x是函子本身的类型参数。例如，对于列表，我们有以下实例：类型实例F[a]x=Either One（a，x）表示函数的GADT现在可以用递归模式的构造函数以及in和out函数进行扩展。数据PF a其中...输入 ：：PF（F aa→a）输出：：PF（a→F a a）A. Cunha，H.Pacheco/Electronic Notes in Theoretical Computer Science 229（5）（2011）67Cata：：PF（F a c→c）→PF（a→c）Para：：PF（F a（c，a）→c）→PF（a→c）在我们的重写系统中，我们需要将函子应用于类型和函数表示。使用上面的类型家族，我们可以在下面的数据类型中捕获这种行为，它表示归纳类型a的函子。data函数a =函数{map：：b. b型→（F a b）型，mapF：：mapxy. PF（x→y）→PF（Fax→Fay）}我们的类型表示现在可以用一个新的构造函数来扩展，以表示用户定义的递归类型。数据类型a，其中...Data：：String→Functor a→Type a给定一个基类型a，可以使用Haskell类型系统来推断它的表示。我们可以定义一个具有所有可表示类型的类classTypeable a where类型：：类型a例如，对于列表，Typeable实例可以定义如下：instanceTypeable a实例Typeable[a]，其中typeof=数据名函数其中name=“[”+show（typepeof：：Typea）++“]”函子=函子{mapT=λb→和一（b的乘积类型），mapF=λf→Id+（Id×f）}为了保证重写系统是类型安全的，重写规则由一元函数表示，该函数接受函数表示并返回相同类型的表示typeRule= Rulea。类型a→PF a→重写M（PF a）RewriteM是一个有状态的monad，它可以跟踪应用的规则，并且是MonadPlus的一个实例，因此可以在规则应用中对RewriteM进行建模。作为参数传递的额外类型表示允许规则做出基于类型的重写决策。图2的特化法则和无点优化法则（如图3中针对折叠和仿形的法则）都被编码为重写规则。例如，褶皱的反射率规则可以定义如下。re Republicex Cata：：Rulere Eq ex Cata（Func a b）（Cata In）=doEq←teq a b68A. Cunha，H.Pacheco/Electronic Notes in Theoretical Computer Science 229（5）（2011）成功“reflex-Cata”IDre=mzero这个规则使用teq来保证只适用于a→a类型的函数。 monadic函数success更新RewriteMmonad以跟踪成功的归约。重写系统是使用一组标准的策略组合器从基本规则构建的。有两种主要的顶级策略：优化syb，用于将类型保持和类型统一的泛型程序专门化为无点表达式;优化pf，用于简化和优化无点定义。后者还应用了一些5示例现在我们将给出一些特殊化的例子，并比较得到的定义和原始SYB函数之间的性能。第一个例子是提高所有工资的通用转型。为了增加专门的无点定义的可读性，我们将考虑类型特定的行为是针对Employee类型而不是Salary。在SYB中，我们有以下定义。increase：：Int→Company→Company increasek=everywhere（mkT（incE k））其中incE k（E p（S s））=E p（S（s+k））在使用PF a类型对这个定义进行编码，并应用专门化和优化策略之后，我们得到以下定义，其中C代表公司，D代表部门。在C++地图（|in D（id ×（incE k × map（incE k + id）|）D输出C这个定义是PF a中相应表示的精美印刷。它近似于第1节中的手写：折叠将递归地应用于公司的每个部门;在每个部门，经理和所有直接员工的工资都将通过函数incEk增加。第二个例子，在第2节中介绍过，解决了通用查询的专门化，以计算公司的总工资账单工资：：公司→国际工资k=一切（mkQ billE）其中billE（E p（S s））=s在这种情况下，我们得到以下定义。图1-2（|plus（billE ×（sum map（billE id））<$π2）|）D输出C请注意，由于查询没有提到递归类型Dept，因此将仿形简化为折叠。表达式sum_map（billE_map_id）收集A. Cunha，H.Pacheco/Electronic Notes in Theoretical Computer Science 229（5）（2011）69来自部门直接雇员的所有工资，以及来自子部门的所有递归然后将此结果与经理的工资相加，以计算总工资账单。本例中使用的表达式sum_map_f事实上，它们被重写系统融合在一起作为单个折叠最后一个例子将前面的两个例子合并为一个函数：更高的工资：：Int→Company→Int更高的工资k=工资增加k虽然这两个操作在原始查询中是按顺序执行的，但在专门化之后，我们得到的结果与前一个非常相似，只对类型进行了一次遍历。设aux=billE在夏季，|plus（aux ×（sum map（aux id））<$π2）|）D输出C与专门设计用于实现聚变的系统（如[23]）不同，我们的重写系统无法实现聚变定律的全部功能。然而，它涵盖了在泛型函数的专门化过程中发生的大多数特定实例。例如，上述优化是可能的，因为下面的融合实例-CATA。（|F|）A（|在一份声明中，|）A=（|F-1|）AF（|F|）Ag = g F（|F|）A为了验证这个定律的边条件，我们首先应用重写系统optimize pfF =（|F|）Ag和g F（|F|）A，然后检查语法相等性。性能分析我们比较了前两个例子的运行时，分别是用SYB和Uniplate编写的手写、专用和通用定义。结果如图4所示。 SYB的效率低下很大一部分是由于大量使用来推断类型表示。为了消除这种损失，并更好地量化我们的专门化机制所实现的加速，我们还包括两个泛型函数的运行时，这些函数是通过使用第4节中提供的eval函数（在图形中表示为SYB GADT）来评估它们的表示而获得的我们使用GHC 6.8.2编译了每个函数，并优化了O2。每个示例都使用大小不断增加的公司值进行了测试（以存储每个值的Haskell定义正如预期的那样，对于这两个示例，SYB通用定义的性能比手写定义差得多SYBGADT变体的速度至少是手写的两倍，但仍然比手写的慢得多。专业的无积分定义表现得更接近手写，最大样本的损失系数为1.11（增加100）和2.85（工资）。该百分比损失主要是由于使用in和out在用户定义的类型之间进行转换，对于这些特定70A. Cunha，H.Pacheco/Electronic Notes in Theoretical Computer Science 229（5）（2011）见图4。 计时结果。例如，专门的无点代码的性能比Unipate略好。正如下一节所讨论的，Uniplate也有一些机制来避免遍历不必要的分支，这证明了结果的接近性虽然在比较泛型编程库时是相当标准的，但这些示例并没有特别影响我们的优化机制：事实上，在遍历中没有可以避免的大数据分支。例如，如果Company数据类型除了departments（不包含Salary类型）之外还包含任何其他信息，则运行时将保持不变，从而进一步扩大与SYB的差距。在优化通用函数的组合时，我们也取得了显著的优势：例如，在工资较高的例子中，我们的专业无点定义已经比最大的Unipate快了1.35倍。sample.6相关工作Uniplate与SYB不同，一些泛型编程库在设计时考虑到了性能问题，通常以牺牲表现力为代价。 一个这样的图书馆 是Uniplate [18]，这是目前Haskell中泛型编程最快的库之一[20]。这一事实，再加上它的组合器的SYB般的兼容性，促使在前一节的比较性能分析中明显包括在内Uniplate背后的关键思想是，大多数通用遍历只对一种类型具有值特定的行为。基于这种见解，这个库提供了两个关键的组合子来指定自底向上的通用转换：transform：：单板a<$（a→a）→a→atransformBi：：双板b a<$（a→a）→b→btransformcombinator将其参数应用于类型a的值中出现的每个a，而transformBi将其参数应用于不同类型b的值中出现的每个a。回顾我们的例子，可以使用transformBi来定义增加转换，因为它查找公司内部的所有工资。的A. Cunha，H.Pacheco/Electronic Notes in Theoretical Computer Science 229（5）（2011）71Uniplate和Biplate类包含分别在类型a和b的值中找到类型a的子结构的基本方法这些类中的类可以使用多种方法来定义，从更通用、效率较低到更详细、效率较高最有效的方法（在上一节的比较中使用）是手工定义实例，对于Biplate来说，需要定义n2个实例来支持n个类型。当定义Biplate b a的实例时，可以避免向下遍历a的不包含目标类型b的分支，从而优化泛型遍历。Uniplate的主要优点是通用函数开箱即用，无需显式优化阶段。另一方面，与SYB类似，我们的优化技术可以处理更强大的组合子，在单个遍历中针对不同类型。使用融合技术，我们的方法还可以进一步优化遍历的组合，而Uniplate加速被限制到单个遍历。优化通用程序的其他技术另一个非常有效的类SYB泛型编程库是Smash [11]。它不是使用运行时检查来查找目标类型，而是通过使用异构集合[12]来编码泛型函数的类型特定情况，从而将它们设置为编译时。不幸的是，使用这种技术获得的加速是以程序员的额外工作为代价的：为了支持新的数据类型，所有不同的遍历组合子必须从头开始定义，而在SYB中，它们都可以使用两个基本方法来通用地实现在[1]中遵循了一种不同的方法，其中开发了一种名为符号评估的技术来优化通用Haskell程序[15]。它专注于完全应用的函数的专门化，并试图消除类型及其结构表示之间的转换。符号计算保证了中间结构完全从优化的代码中删除。在我们的框架中可以使用类似的技术来进一步优化无点定义，通过额外的翻译步骤显式递归逐点代码。应用场景如前所述，我们的主要目标是扩展[7]中提出的专门化机制，以涵盖归纳类型。在[7]中，我们已经描述了如何使用它来优化结构型查询语言。这种技术被利用到原型模式感知编译器XPTO中[8]。XPTO中的查询编译过程如下：XML模式被解析为使用Type a的产品表示的总和; XML查询被解析为PF a类型的类型安全表示;重写系统用于将查询专门化为给定模式;专用的无点定义被输出到新的Haskell程序中，以进行编译并与XML解析器和无点执行库链接;然后，生成的程序可以用于对符合给定模式的我们目前正在将这里介绍的新技术部署到XPTO编译器中，以便处理72A. Cunha，H.Pacheco/Electronic Notes in Theoretical Computer Science 229（5）（2011）一些递归XML模式。在[6]中也使用了类似的类型安全重写系统来优化两级数据转换[4]。两级数据转换由类型级转换和相应居住者的值级转换组成。更具体地说，我们开发了一个框架，允许我们使用策略组合子指定数据类型细化A≤B，并免费获得A和B类型值之间的迁移函数，反之亦然。类型和迁移函数再次使用Type a和PF a编码，允许我们使用重写系统来优化它们，并将查询/生产者从抽象类型A迁移到具体类型B。在重写系统中包含归纳类型将使我们能够扩展这个框架的适用性模板元编程我们相信，我们的代数方法可以指导在较低的水平通过模板Meta编程提供泛型函数的编译时专门化[22]。这个重写过程将包括通过直接操作Haskell泛型程序的抽象语法树来转换然而，由于Haskell中模板元编程的当前实现是完全无类型的，我们将失去重写系统是类型安全的保证。模板元编程也可以用来自动推断递归类型7总结发言我们已经扩展了一个现有的机制来专门化类似SYB的泛型函数，以覆盖用户定义的递归数据类型。通过关注归纳类型（函子的定点），我们能够使用递归模式，如折叠和仿形来编码泛型遍历。这些递归模式的特征在于良好的代数法则，这些法则被纳入类型安全重写系统中，以进一步优化专用代码。我们的专业化机制产生的定义由于Haskell类型系统的最新扩展，例如类型索引类型族或一般化代数数据类型，我们的重写系统的实现紧密地模仿了理论演示。当前方法的主要局限性是它只支持单递归归纳类型。我们目前正在研究如何扩展它以覆盖更一般的递归形式，例如相互归纳的数据类型或嵌套数据类型。与这一努力特别相关的是[10]中描述的工作，表明高阶函子可以用于为嵌套数据类型（类似于标准归纳类型）提供初始代数语义。A. Cunha，H.Pacheco/Electronic Notes in Theoretical Computer Science 229（5）（2011）73引用[1] Alimarine，A.和S. Smetsers，优化泛型函数，在：D。Kozen和C. Shankland，编，“Proc. of 7th Int.Conf. on Mathematics of Program Construction, MPC 2004 (Stirling, July 2004),” 16比31[2] Backus，J.，编程能从冯·诺依曼风格中解放出来吗？一个函数式风格和它的程序代数，Commun。ACM21（8）（1978），pp.613-641[3] Chakravarty，M. M. T.，G. Keller和S. Peyton Jones，Associated type synonyms，in：“Proc. of 10thACM SIGPLAN Int. Conf.