277网址：http://www.elsevier.nl/locate/entcs/volume64.html15页高阶函数的特殊化伯纳德·波普1墨尔本大学计算机科学与软件工程系澳大利亚墨尔本李奈什2墨尔本大学计算机科学与软件工程系澳大利亚墨尔本摘要因为函数是抽象值，没有方便的打印表示，所以实现支持高阶代码的调试器是一个挑战。我们提出了一个算法，用于静态地专门化高阶函数和编码高阶值以允许打印。我们为一个小的函数式语言设计了我们的算法，并讨论了如何将其扩展到支持现代函数式编程语言的复杂功能。 该研究是项目3的一部分。为Haskell构建一个声明式调试器，主要基于源到源转换。1引言高阶编程在现代函数式编程语言中的优势给调试器的设计者带来了挑战，特别是那些基于源转换或插装的调试器。高阶语言允许函数作为结果返回，作为参数传递，并包含在数据结构中。然而，由于函数是抽象值，它们很难转换为可打印的表示形式，这对于调试是必不可少的。函数的源代码标识符通常在编译期间被丢弃，新函数可以使用lambda动态3 由澳大利亚研究委员会支持。1 电子邮件地址：bjpop@cs.mu.oz.au2 电子邮件地址：lee@cs.mu.oz.auc 2002年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。278抽象和功能组合。Chitil等人 [2]进一步讨论了在调试环境中显示函数值的困难。我们的方法采用了一系列的数据结构来编码高阶值和这些值的可打印表示我们使用源到源转换（为了可移植性），避免编码一阶值（为了效率）。这在强类型多态语言中已被证明是不平凡的。多态性允许相同的源代码用于多个类型，其中一些是一阶的，而另一些不是。例如，考虑map函数：地图=\f l . 案例l[]->[]（：）x xs ->（：）（fx）（mapfxs）map的应用程序可以产生一个整数列表，如表达式mapid [1，2，3]，或者一个函数列表，如表达式map（+）[1，2，3]，等等。从这些应用程序的检查中产生的声明性调试器的输出分别可能具有以下形式：地图 id [1，2，3]= [1，2，3]，这是正确的吗？map（+）[1，2，3]=[（+）1，（+）2，（+）3]，这 是正确的吗？因此，要构建一个有用的调试系统，我们必须能够生成有意义的可打印函数表示。使用通过程序的调用图传播的类型信息，我们专门调用和定义高阶函数。为了保持生成的专用代码的类型正确性，我们可能需要克隆一些高阶函数。这项工作的背景是一个为Haskell构建可移植声明式调试器的项目，我们将在下一节中描述。接下来我们描述一个简单的函数式语言，并定义我们对这种语言的转换在讨论了一些扩展和相关的工作，我们结束。2声明式调试使用声明性语义来指导半自动搜索程序中错误来源的想法是由Shapiro提出的[11]。最初的工作集中在定位Prolog程序中的逻辑错误，但是该方法背后的原理可以扩展到其他编程语言和范式。4.该领域的许多原始工作都是在算法调试的标题下进行的，然而，我们采用声明式调试这个术语来强调声明式语义在该技术中的重要性用于函数式语言的若干声明性调试技术已经基于树的创建和遍历，该树描述（在某些方面）4 Westman和Fritzson [12]报告说，算法调试已应用于命令语言和并行逻辑语言。279抽象层次）对给定程序的评估。我们定义了一个评估依赖树（EDT）来表示程序评估的实例。EDT的关键特征是它反映了程序定义的语法依赖性，而不是由于求值而产生的执行依赖性。EDT中的每个节点表示在程序执行期间发生的函数应用。在每个节点上，我们记录了三件事的表示：应用程序的结果;应用的函数;以及应用该函数的参数。来自函数定义右侧的函数应用程序形成EDT节点的子节点，并且它们本身表示为EDT。在文献中有两种方法来构建EDT。第一种方法，如Nilsson等人的工作（例如[8]）所示，需要一个修改的语言实现，该实现生成EDT作为执行程序的副作用。正如这项技术的支持者所指出的，需要进行重要的工作来实现必要的语言实现修改。这样的技术允许在EDT的生成中进行若干优化，然而它在不同语言实现之间不是特别可移植的。第二种方法对程序文本使用源到源转换。 定义转换程序中每个函数的值，以返回包含函数的原始结果和表示执行期间该函数的应用的EDT节点的对。然后执行转换后的程序，产生一对包含原始程序的值和表示该执行的EDT的这种方法已经由Nilsson和Sparud [9]以及Naish和Barnard [7]独立指定。我们采纳了Naish和Barnard的建议。Pope [10]中给出了变换算法和EDT的详细阐述。EDT节点表示对函数的调用以及在程序执行的某些子计算中返回的结果。调试器打印EDT节点，用户识别错误的子计算。通过遍历树的一部分，注意哪些EDT节点是错误的，可以隔离bug在相对较小的代码段中。高阶程序的EDT在其节点中具有高阶值，本文讨论了打印它们的问题。3.对象语言我们定义了一个小型的函数式语言（称为Mini-Fp）作为我们转换算法的对象。它是按照Haskell和ML等大型语言的精神设计的。图1给出了该语言的抽象语法。该语言的具体语法基于Haskell。 我们假设各种基本数据类型，如整数、字符、列表和元组，5 评价依赖树这个术语是从Nilsson和Sparud [9]借用的。280vd2 声明：：=x= e J fv1：vz=fci t1：tygw都是语言中固有的。我们还假设这些类型上的常用函数（如整数加法）可用作原始函数。 我们没有定义Mini-Fp的求值语义，但是专门化算法适用于具有严格或非严格语义的语言。我们假设语言的静态类型系统和基于众所周知的Hindley-Milner系统的类型推理算法[6]。程序由一个或多个变量声明和零个或多个数据声明组成。类型注释是允许的，但不是必需的，用于top和let绑定变量。6.顶级值声明之一必须被称为main，它必须没有参数并且是单态的。程序的求值从对该函数的初始调用开始。f2类型构造函数 v2类型变量t2类型：：=v j t 1！t 2 J ft1： tzs2类型方案：：= 8：t x2变量c2数据构造器ii=1e2 表达式：：= x：eJe1 e2j x j cjletfd1;： ;dw ginejcaseeofa1：awa2个备选方案：=c x 1：：x z7！e J七！ e图1.一、Mini-Fp的抽象语法4专业化算法专门化算法有两个阶段。第一阶段称为克隆，第二阶段称为编码。 克隆的作用是扩大程序的静态调用图，使得基于每个高阶参数的类型的形状来区分对具有高阶参数的函数的调用。如果函数在一个或多个高阶参数中是多态的，克隆可能需要制作函数定义的多个副本。结果是减少6 如果语言支持多态递归，则在某些情况下需要类型注释。第5节对此作了更详细的介绍281在程序的多态性和程序中代码大小的扩展。编码的作用是提供函数值的可打印表示。编码后，所有高阶参数将被提升到一个特殊的表示形式，其中包含原始值和该值的可打印表示形式。编码阶段还提供了用于在编码值和未编码值之间进行转换的手段。克隆阶段是确保编码阶段保持程序的类型正确性属性所必需的。该算法是类型导向程序转换的一个例子，在精神上（但不是动机）类似于Bell等人 [1]的去功能化算法。4.1专业化的例子考虑以下Mini-Fp程序：main= compose plus（plus 1）3（两倍id5）compose =\f g x. f（g x）两次=\x. 组合xx加上=\x y。（+）xy id=\x.X每个函数都使用以下类型调用：main =>Int（+）=>I n t ->Int->Int请注意，compose是一个高阶多态函数，有两种不同的调用方式。克隆将通过制作编写代码的克隆（或副本）并对每个克隆进行唯一命名来区分编写算法还必须重命名这两个调用以进行组合。 在这个阶段，程序与原始程序相同，除了静态调用图的大小增加和修改。main= compose_1 plus（plus 1）3（twice_1 id 5）compose_1 =\f g x. f（g x）compose_2 =\f g x. f（g x）两次_1=\x{e76f} compose_2 x x专门化算法的编码阶段将通过将参数封装在数据结构内来将每个高阶参数转换为一阶值。数据结构将包含高阶函数和该函数的表示（为了简单起见，我们使用String作为表示）。在下面的代码中，类型F_1 a b将用于封装-组成=>=>(Int->Int->Int）->（Int->Int）->Int->Int->Int(Int->Int）->（Int->Int）->Int->Int两次=>(Int->Int）->Int->Int加上=>Int->Int->IntID=>Int->Int282隔离类型a->b的所有高阶值，使得b是第一阶的。更一般地，F_n v_1.v_n+1封装所有类型t_1->. ->的高阶值t_n+1，使得 t_n+1是数据F_1 a b=F_1（a->b）String数据F_2 a b c= F_2（a->b->c）Stringapply_1 =\x. （F_1 fs）的情况x-> fapply_2 =| x。（F_2fs）->f的情形xmain= compose_1（F_2加上“plus”）（F_1（加1）“加1”）3（twice_1（F_1 id“id”）5）compose_1：：（F_2 b c d）->（F_1 a b）-> a -> c-> d compose_1 =\ f g x. apply_2f（apply_1 gx）compose_2：：（F_1 b c）->（F_1 a b）-> a -> ccompose_2 =\ f g x. apply_1f（apply_1 gx）twice_1：：（F_1 a a）-> a-> atwice_1=\x{e76f}compose_2 xx当一个变量被绑定到一个编码值，并且该编码值被应用到一个表达式中时，我们必须在应用之前解码该值（到原始函数）。对于每个引入的类型F_n v_1. v_n+1，we de ne一个关联apply_n函数的类型F_n v_1. v_n+1 -> v_1->...-> v_n+1，其从编码表示中选择原始函数。在这一点上，当第二个类型只是rst的实例时，我们可能不清楚为什么要区分a->b和a->b->c（因此我们克隆了compose定义）。事实上，我们可以单独用F_1 a b执行上述编码其原因是由于在函数定义的结果中引入了EDT值例如，一个类型为a->b的函数在转换后的程序中将具有类型a->（b，EDT），类型a->b->c将变为a->b->（c，EDT），依此类推。 考虑类型为Int->Int->Int的函数plus。在转换后的程序中，类型将变为：Int->Int->（Int，EDT）。这对于加到两个参数的应用程序是正确的，但是，对于部分应用程序是不正确的如果函数的所有应用程序（包括部分应用程序）都要返回一个值和一个EDT，那么我们需要一个给出类型的转换：Int->（Int->（Int，EDT），EDT）。正如[7]中所指出的，这种转换通常会导致EDT中的许多无用节点。283为了避免更复杂的转换，我们必须区分a->b和a->b->c（等等），因为我们需要确保最右边的类型变量本身不会扩展为函数类型。只有通过使用一系列编码F_n，并要求最右边的参数是rst阶的，我们才能保证这种行为，并最终保持编码程序的类型正确性 使用多重编码意味着必须使用多个apply_n函数|这就是克隆定义的原因。在我们的例子中，compose被克隆了，因为支持编码的nal版本需要不同的apply_n函数（克隆阶段从compose被调用的类型推断出这一点）。需要澄清的一个最终细节是数据处理器对高阶值的应用这里我们遵循Bell等人的算法[1]。与函数应用程序一样，我们必须编码构造函数的高阶参数，但是不需要克隆构造函数定义，因为有值声明。这是因为所有数据构造函数的类型都具有t_1->. ->的形式 t_n，这样t_n就不是类型变量。数据构造函数的部分应用程序的编码方式与函数的部分应用程序相同当构造函数的高阶应用在类型的定义中显式化时（如上面构造函数F_1和F_2的第一个参数的情况），会出现一个复杂情况在这种情况下，我们用一个新的类型变量替换构造函数的每个函数参数，并用每个新引入的变量来概括类型的定义4.2克隆算法克隆算法在概念上非常简单，但是由于局部（let bound）值的存在以及嵌套表达式中变量的相关作用域，实现细节变得复杂我们以抽象函数风格定义克隆算法，由递归函数clone驱动，定义如下：克隆（Q1、S1、P1）=如果 Q1 ==然后返回P1else（x= e，t）2Q1Q2Q1-f（x=e，t）gS2S1[ f（x，|不|）gC调用（e，t）(Q3、P2）newCalls（C，S2，P1）returnclone（Q2[ Q3，S2，P2]）clone函数通过程序的调用图执行递归遍历，并确保声明在程序中正确的嵌套级别上被克隆，并且计算在递归声明出现时终止。假设所有顶部的类型方案284和let绑定变量可从类型推断获得。函数clone有三个参数。他们的作用如下。Q是一组pairs（d，t），其中d是let bound或top bound变量的声明，t是调用d的类型。Q包含一组未处理的调用。初始Q是包含main的定义和类型的单例集。当Q为空时，算法终止。S是对（x，|不|），这样x是一个let bound或top bound变量的名称，|不|是x被调用的类型的抽象。S记录克隆以前处理过的所有调用。S中的信息用于确保不执行不必要的工作，特别是实现正确数量的克隆，并且算法以递归定义终止。S最初是空集。P是整个程序的语法树。当一个声明被克隆时，新的（唯一命名的）声明被添加到语法树中，调用图被修改以适应新的名称。初始P是原始程序的语法树，在算法终止时，P是克隆程序的语法树给定一个调用类型tc，有许多方法可以形成一个抽象。一个简单的方法是将tc中的所有空类型构造函数映射到一个新的唯一空类型构造函数。在这样的模式下，我们会认为类型Int，Bool，Char是等价的，但我们会认为Int-> Int是不同的。这个方案的问题是它太保守，可能导致不安全。必要的克隆抽象技术的目标是减少所需的克隆量，同时允许编码算法保持类型正确性。我们对抽象方法的选择是由一个重要的观察所指导的：只有当变量的类型方案包含多态的箭头类型参数时，才需要由于我们对变量的多态性很感兴趣，我们必须利用通过类型推断推导出的其类型模式中包含的信息。因此，我们可以进一步缩小我们的抽象技术。把变量的类型模式看作一棵树，节点上有箭头和非空类型构造函数，叶子上有类型变量和空类型构造函数。作为箭头节点的右子节点出现的变量集称为区分类型变量（DTV）。调用这些变量的类型决定了如何对高阶参数进行编码，并最终决定了需要进行多少克隆。函数dtv计算给定类型方案的DTV集dtv（8v：t）=dtv（t）数字电视（f t1*tkKi=1 数字电视（ti）dtv（v）=dt v（t1！v）=dtv（t1）[fvgdt v（t1！t2）=dtv（t1）[dtv（t2），其中t2不是typ变量S）=285下表中示出了一些公知的类型方案及其对应的DTV集合类型方案DTV底部：：8a：aid：：8a：a！afagmap：：8a;b：（a！b）！[a]！[b]fbg作 曲 ： ： 8a;b;c ： （ b！ c ）！ （ a！ b ）！ 一个！Cfc;bg对于scheme s类型的变量x和调用类型tc，我们想知道当s和tc统一时s的DTV是如何实例化的。特别是，我们想知道当表示为树时每个实例化类型的最右边分支中的箭头的数量我们定义一个抽象类型为一个（可能为空）对（v; n）的集合，使得v是一个类型变量，n是一个自然数。给定函数mgu，它计算类型方案和类型（作为一组替换）的最一般单位，我们计算类型方案s的抽象类型，并使用下面的函数abstype调用类型tc绝对型=f（v; order（t v））g使得v2dtv（s）和（v; tv）2mgu（s; tc）order（ v）= 0order（f t 1：t k）=零o rde r（t1！t2）为 1 +rder（t2）如果我们考虑map的类型方案，下表显示了各种调用类型的抽象版本：呼叫类型抽象类型(Int->Int）->[Int]->[Int]f（b;0）g（布尔->[Char]）->[布尔]->[[Char]]f（b;0）g(Int->Int->Int）->[Int]->[Int->Int]f（b;1）g(Int->Int->Int->Int）->[Int]->[Int->Int->Int]f（b;2）g对于DTVs集为空的变量（如bottom），克隆算法将最多处理一次对它们的调用，因为对这些变量的所有调用总是被认为是等效的。此外，这些变量的定义永远不会被克隆。clone的定义依赖于函数calls和newCalls。函数calls接受一对（e;tc）作为它的参数，这样e是某个变量x的声明的右手边表达式，tc是x被调用的类型利用类型推理推导出的类型模式，286计算e的类型te并与tc统一。该union实例化对e中的多态函数的调用。这些调用的类型，以及被调用的函数的名称被收集在一起，并在集合C中返回。函数newCalls有三个参数：（变量，类型）对的集合C（调用的输出）描述新推导的调用;（变量，抽象类型）对的集合S描述已经处理的调用;和P语法树的当前状态。对于C中的每个调用（x; t），newCalls检查S以查看x是否先前在抽象调用中被处理过|不|. 所有未处理的调用的声明和调用类型都在一个集合中返回对于其抽象类型为非空集的调用，将进行克隆并添加到语法树中，并且更新现有语法树中的调用位置必须注意确保克隆声明中的递归调用被适当地重命名。4.3的编码算法编码算法对程序进行转换，以便将所有用作函数或数据构造函数的参数的高阶值进行编码（包装在F_n构造函数中）。这就需要对整个程序（高阶部分）的类型进行更改 顶级变量和let绑定变量的类型被更改，因此保留了类型最右侧分支中的箭头（分隔参数类型和结果的箭头），但所有嵌套函数类型都被相关的编码函数类型替换：t_1 ->... -> t_n+1（其中t_n+1是一阶）被F_nt_1.. t_n+1。 所有lambda函数类型和模式绑定变量都以相同的方式转换。 因此，compose_2的新类型模式，为形式为（b->c->d）->（a->b）->a->c->d的类型生成，是（F_2 b c d）->（F_1 a b）->a->c->d，并且在其定义内，f的类型从b->c->d转换为F_2 b c d，g从a->b转换为F_1a b（参见4.1节）。类似地，map的克隆，当在类型（a->b->c）-> [a] -> [b->c]下调用时，其类型模式转换为（F_2 a b c）-> [a] -> [F_1 b c]。需要对程序进行两种更改 我们需要对一些参数进行编码，我们需要对一些正在应用的变量进行解码。应用程序v e需要解码，其中v是一个lambda或模式绑定变量，最初具有函数类型（在类型转换后，它具有类型F_n t_1. t_n+1）。使用apply_n来解码v。 例如，在compose_2的定义中，其中应用f，apply_2用于对其进行解码（并且apply_1用于对g进行解码）。如果v是一个定义中的顶级表达式，它也应该被视为一个应用程序（或者定义可以被eta扩展以使应用程序显式）。对于应用e_1 e_2需要编码，其中e_2的原始类型是函数类型（新类型是F_n t_1. t_n+1）。编码e_2是287通过应用数据构造函数F_n并添加字符串表达式来完成对于let和顶级绑定变量，字符串以明显的方式生成对于应用程序，lambda，case和let表达式字符串是通过连接由适当的空格，关键字等分隔的不同组件来生成的（例如，参见第4.1节中的main对于lambda和模式绑定变量，我们需要一种通用的方法来将值（编码了任何高阶组件）转换为字符串（这是toString的角色）。形式为e_1（v e）的表达式，其中v是最初具有函数类型的lambda或模式绑定变量，并且（v e）也具有函数类型，需要解码和（重新）编码。函数和字符串必须从编码的函数v中提取出来，分别应用于e及其字符串表示，并与之连接我们使用一族函数，toF_i的类型为（F_i+1t_1. t_i+2）->t_1-> （F_i t_2.t_i+2）。 如果v的编码类型是F_i+1t_1. t_i+2，则上述表达式转换为e_1（toF_i v e）。toF_i函数定义如下：toF_1 =\x y. 案例XF_2 fs-> F_1（fy）（append s（toStringy））toF_2 =\x y. 案例XF_3fs -> F_2（fy）（appends（toString y））例如，上面讨论的map_1的定义需要解码和重新编码，其中f被应用：map_1：：（F_2 a b c）->[a]-> [F_1b c] map_1 =| f 1. 案例l[] ->[]（：）xxs->（：）（toF_1fx）（map_1fxs）5讨论和扩展当至少一个递归调用的类型一个函数的类型不等于，但它是函数被定义时的类型的实例。Hindley-Milner类型推理算法不支持这种递归。Hindley-Milner算法有各种扩展，允许多态递归。例如，Haskell语言的类型检查算法（如[4]中所述）仅当为在多态递归上下文中使用的所有函数提供足够的类型注释时才如果我们允许使用Haskell方案的多态递归，并遇到以下函数，则专门化算法的克隆阶段将无法终止：f：：（a->b）->cf=\g。f（\x {e76f （g）在表达式“fid”中，f的抽象调用ty pe是f（b;0）;（c;0）g。在对f的连续递归调用中，抽象的调用类型遵循以下模式288f（b; 1）;（c; 0）g，f（b; 2）;（c; 0）g等等。每个新调用被认为是不同的，因此需要f的克隆版本的一个内部家族。然而，并不是所有形式的多态递归都会导致克隆算法中的非终止性。例如，下面例子中的函数h是多态递归的：h：： [a]->bh =\x。h[x]然而，它的抽象调用类型对于每个递归调用保持不变：f（b;0）g。克隆算法将终止时，抽象类型的连续递归调用一个函数是平等的（对于一阶参数，这个标准是微不足道的）。查明未终止案件是今后工作的一个领域。如果检测是可能的，那么对这些函数的调用将不会被专门化。最终，这意味着声明性调试器将获得更少的关于此类函数的应用程序的信息。这会影响调试算法的完整性，但不会影响可靠性，并且在实践中，这可能是允许受限形式的多态递归所付出的很小代价。大多数现代函数式编程语言都提供模块作为细分和封装代码的手段，当这些代码组合在一起时就构成了一个程序。当函数调用跨越模块边界时，这会使专门化算法复杂化。目前的专门化算法假设整个程序定义将被转换。在存在多模块程序的情况下，这将需要以模块图的依赖顺序对程序进行整个遍历，当模块之间存在相互依赖时，该过程进一步复杂化。这个问题也与调试转换特别相关，我们希望能够将其应用于整个程序的子集。必须转换（和遍历）整个程序是次优的。此外，专门化和调试转换都在程序的执行中引入了开销。在调试的上下文中，目标是将转换的范围限制在可疑代码上，使代码的其余部分保持其原始状态。这是未来研究的一个重要领域。类型类是一种强大的机制，允许重载标识符，ers，并且是Haskell等语言的类型系统的组成部分。类型类使克隆算法复杂化，因为一个标识符可能具有类型类的多个实例的声明。目前的克隆算法假设每个标识符只有一个定义。可以基于所进行的调用的类型来选择性地克隆作为类成员的标识符的实例。类型类的合并将是专门化算法未来发展的一个重要方面为了使专门化算法合理，我们需要两件事。首先，所产生的专业程序是根据我们选择的类型良好的，289类型推理方案（现在我们假设Hindley Milner，可能的扩展允许多态递归）。其次，给定我们语言的求值对于克隆阶段，类型正确性的证明应该相对简单，我们可以从Bell等人的工作中获得一些优势。对于编码阶段，类型正确性可能更难证明，然而，设想证明将利用具有用于对函数值进行编码和解码的显式规则的增强类型推断算法。证明评价等价性还有待探索，然而，我们希望能够使证明独立于评价策略的严格性。为了完整性，我们需要提供EDT的语言的语义。在这样的语义下，算法被认为是完整的，如果当应用于类型正确的程序时，在相应的EDT中的所有节点相对于程序的源级定义除了调试之外，我们在这里介绍的算法可能还有其他用途例如，高阶语言的评估方案的设计Peyton Jones在讨论Spineless Tagless G-machine的设计空间时强调了这一点[5]：值得注意的是，在多态语言中，并不总是能够区分其值将被证明是函数的thunks和其值是数据值的thunks例如，考虑函数：composef g x=f（g x）（g x）是函数还是非函数？当然，这取决于g的类型，并且由于compose是多态的，这不是静态确定的。专门化算法的克隆阶段为静态确定表达式是否是函数的问题提供了一种可能的解决方案。反过来，这可以让我们弥合咖喱化和非咖喱化语言实现之间的差距。6相关工作Bell等人 [1]给出了类型驱动的去功能化算法。这需要一个高阶多态程序，专门删除一些多态性，并编码所有高阶值。与我们的工作相比，更多的多态性被这导致更大的代码扩展，更多的新类型和相关的解码函数，以及可能更大的运行时开销。我们的调试器的体系结构引入了进一步的代码扩展和开销，所以我们对高阶代码的处理是很重要的。去功能化的动机是将高阶程序翻译成只支持一阶函数的语言，而我们的290专门化算法的动机是需要用于调试的高阶值的可打印去功能化算法完全从程序中删除所有高阶值，而我们的特殊化算法只是将它们包装在一个数据结构中。这意味着我们失去的多态性比去功能化算法少得多。我们的专业化算法上的放松约束意味着它可以支持某些形式的多态递归，然而，去功能化算法不支持任何形式的多态递归。Hughes [3]提出了一种基于对源语言解释器的部分评估来专门化程序的方法。这提供了一个非常通用的框架，用于执行许多种类的程序专业化，包括单态化和重构。该方法的所得的还原（或去官能化）实现了与Bell等人类似的结果。研究这个更一般的框架是否可以被调整以生成我们调试所需的结果7结论本文提出了一种新的应用类型导向的程序specialisation的目的，产生可打印的表示高阶值的调试。 特别是，我们已经表明，该算法可以表示为两个部分，克隆和编码。已经提供了这些部分中的每一个的定义。该算法的一个关键特征是在专用程序中保留了很大程度的多态性，并且不对第一阶值进行编码。这有两个主要的好处。首先，减少了由专门化引入的开销，特别是与编码和解码值相关联的代码大小和成本的扩展。其次，该算法适用于某些形式的多态递归。的输出的spececialisation算法将被用于未来的调试转换，这将有望导致一个有效的和便携式的手段，用于诊断错误的强类型高阶多态函数编程语言。引用[1] J. Bell，F. Bellegarde和J.Hook.类型驱动的去功能化。在M. Tofte，编辑，Proceedings of the ACM SIGPLAN International Conferenceon Functional Programming（ICFP '97），第25页{37，1997.[2] O.奇蒂尔角Runciman和M.华莱士懒惰函数式程序的跟踪与消除|三种制度的比较评价。在M. Mohnen和P. Koopman，编辑，第12届函数式语言实现国际研讨会论文集，Aachener Informatik Berichte，AIB-00-7号，第47页。亚琛工业大学，2000年。[3] J·休斯。 微积分的类型专门化;或者，一种新的范式291用 于 基 于 类 型 推 断 的 部 分 评 估 。 在 OlivierDanvy， RobertGluck和PeterThiemann，编辑，Dagstuhl部分评估研讨会，LNCS。Springer Verlag，1996年2月[4] M. 琼 斯 在 Haskell 中 输 入 Haskell 。 Technical Report UU-CS-1999-28 ，Department of Computer Science ， University of Utrecht ， Utrecht ，Netherlands，1999.[5] S.佩顿·琼斯。在普通硬件上实现惰性函数式语言：无脊椎无标签的G机。Journal of Functional Programming，2（2）：127{202，1992.[6] R.米尔纳程序设计中的类型多态理论。Journal of Computer and SystemSciences，17（3）：348{375，1978.[7] L. Naish和T.巴托一个可移植的惰性函数声明式调试器。澳大利亚计算机科学通讯，18（1）：401{408，1996。[8] H. Nilsson 和 P. Fritzson 。 懒 惰 算 法 调 试 ： 实 际 实 现 的 想 法 。 在 P.Fritzson，编辑，自动化和并行计算，第749卷，计算机科学笔记，第117页{134，链接1993年，瑞典奥普。[9] H. Nilsson和J. Sparud。评估依赖树：惰性函数调试的执行记录。林雪平大学计算机与信息科学系技术报告，1996年。[10] B. Pope. Buddha：Haskell的声明式调试器。 技术报告98/12，计算机科学与软件工程系，墨尔本大学，1998年。[11] E.夏皮罗电子邮件 * 麻省理工学院出版社，1982年。[12] R. Westman和P. Fritzson。用于算法调试的图形用户界面。在P. Fritzson，编辑，计算机科学讲义，第749卷，第273页{286。Springer，May 1993.
我的内容管理
展开
