理论计算机科学电子笔记148（2006）79-103www.elsevier.com/locate/entcs通用酸洗和最小化Guido Tack1 Leif Kornstaedt1 Gert Smolka1德国萨尔大学编程系统实验室摘要本文介绍了通用的pickle和最小化机制，提供类似于垃圾收集的服务。挑选用于外部化和内部化数据。最小化意味着最大化任意数据结构的共享。 本文介绍了一个抽象的存储的概念，作为一个正式的基础算法，并分析了设计决策的实施方面的酸洗和最小化。这里介绍的机制在Alice编程系统中完全实现。关键词：pickle，marshalling，serialization，graph minimization，persistence，distributedprogramming1引言挑选，也称为编组或序列化，意味着在运行时将数据外部化。这种机制存在于许多编程语言中，从Java 、.NET 和Python 到Mozart 、Caml 和Alice，仅举几例。本文提出了一种与语言无关的pickling体系结构。Alice ML语言是标准ML的保守扩展，通过支持并发、惰性计算和丰富的组件系统来丰富语言。在高阶语言中，例如Alice，组件系统和网络分布都可以基于pickle。因此，我们研究pickle作为一个基本的机制的编程系统。1Email：{tack，kornstaedt，smolka}@ps. 乌尼湾。De1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.11.04180G. Tack等人/理论计算机科学电子笔记148（2006）79讨论pickle的基础是抽象存储，这是一种语言中立的内存模型，可以用作虚拟机设计的基础。pickler和垃圾收集器一样，是作为抽象存储的一个通用服务引入的。所有数据，包括代码，都在抽象存储中表示，因此可以进行pickle。抽象存储提供了一个接口，用于连接到原始对象（如整数、字符串或连接到其他对象的结构化节点）的图形。除了酸洗，我们引入图形最小化作为商店的另一项服务。这特别适合于函数式编程语言，因为存储中的许多对象都是纯函数式的，并且可以从大量的共享中受益。Alice系统[2]在虚拟机中实现Alice ML，该虚拟机基于具有垃圾收集，pickle和最小化服务的抽象存储。文件的贡献本文提出的抽象存储是一个程序设计系统的堆模型，它既抽象到足以进行形式推理，又具体到足以进行高效实现。基于此模型，我们提出了一个通用的，平台和语言无关的采摘服务的详细描述。我们定义了它的pickle语言，开发了pickle和unpickle的算法，并展示了pickle如何与ML类语言集成。我们进一步讨论了在并发语言（如Alice）中使pickle定义良好所需的条件。 本文介绍了一般图最小化作为一种新的服务的抽象存储。我们正式以及实施细节，并表明，这样的服务是有效的和值得的。文件的结构在下一节中，我们将概述pickle如何集成到Alice语言和编程系统中。第3节介绍了一个正式的模型，在此基础上，酸洗服务是建立在第4和第5节。第6节开发最小化服务。之后，在第7节中，我们将扩展模型和算法，支持Alice中存在的并发。最后，我们讨论了第8节中的相关工作，并在第9节中总结和提出了未来工作的想法。2爱丽丝的腌制Alice ML语言以保守的方式扩展了标准ML，类型化开放式编程[24]：程序是由可以G. Tack等人/理论计算机科学电子笔记148（2006）7981从文件或通过网络动态创建和动态加载。组件可以由编译器静态创建，也可以在语言中动态创建。这需要三个主要特征：(i) 组件必须能够包含任意值（包括函数和代码）。(ii) 由于组件是从静态未知源获取的，因此必须动态地进行类型检查。(iii) 组件的动态创建需要一种机制来将组件外部化为适合持久存储或网络传输的格式。前两点通过扩展SML模块系统和动态类型检查来解决。第三点描述了所谓的pickle、marshalling或serialization。2.1模块和包Alice的一个关键特性是组成程序的组件是动态加载和链接的。Alice组件基于丰富的模块系统，并支持动态类型检查，以确保运行时系统的完整性。将动态类型检查引入静态类型语言的一种众所周知的方法是dynamics[1]。可以将任意值注入通用类型dyn。此类型的值携带足够的运行时类型用于投影类型情况操作的信息。对于Alice，我们稍微修改了这个概念：包（在Alice中称为动态）包含模块。Alice模块系统扩展了标准ML模块，支持高阶函子和本地模块，以及嵌套和抽象签名。包类型检查相当于将包签名与静态签名进行匹配。由于包是正确的Alice值，它们将第一类模块引入到语言中。包的语义在[23]中得到了正式的定义。一个包基本上是一对模块和它的签名。 它是通过注入一个模块来创建的，由SML中的结构表达式strexp包strexp：sigexp签名表达式sigexp定义包签名。模块表达式提供了逆运算投影解包exp：sigexp它接受一个包并提取包含的模块，前提是包签名与sigexp表示的目标签名匹配。否则，将引发异常。82G. Tack等人/理论计算机科学电子笔记148（2006）792.2酸洗和解酸洗包主要用作Alice组件系统的基础。Alice引入了组件的概念，这是Oz语言中系统的细化[8]。组件是一个外部化的包，可以存储在文件中或通过网络传输。这种包的外部化称为pickle，反向操作unpickle。Alice通过库结构Pickle为文件提供pickle：val保存：string×包→单元val加载：string→包保存操作将一个包写入一个具有给定名称的文件。pickle的语义要求pickle包含包的整个transitive闭包：valp =letfunf x = List.append（x，x）结构S =struct val b=（f，“b”）end在save（“pickle.alc”，pack S：sig val b：（αlist→αlist）×string end）端生成的pickle包含S的完整闭包，包括f的代码和List.append函数，但不包含完整的List结构。 可以使用load从文件中解包：结构SCopy = unpackPickle.load“pickle.alc”：sig valb：（α→α）×stringendPickling和unpickling保留pickle值的结构，特别是共享和循环。当解包的包被解包时，通常的动态类型检查被执行。如果类型检查成功，则对未pickle和未打包的模块的所有操作再次是静态类型3抽象商店Alice ML程序在运行时使用和产生的所有数据都表示在抽象存储（或简称为存储）中。在本节中，我们正式定义了抽象存储和Alice数据的表示方式。抽象存储器是高级程序设计语言存储器的一般模型。我们使用Alice作为例子，因为商店最初是为Alice设计的。然而，所有的抽象都很容易转移到其他编程语言中。G. Tack等人/理论计算机科学电子笔记148（2006）79833.1商店的正式模型形式上，抽象存储是一个有序的、有标签的图，有两种类型的节点：标量和结构化节点。定义3.1给定一组地址Adr，一组标签Lab和一组字节序列BSeq，抽象存储是一个有限函数g∈Adr~ Lab×（BSeq Adr）直观地说，存储将地址映射到标记节点，这些节点可以是标量或具有到其他节点的一系列边的结构化节点我们称标量存储节点为块，结构化节点为块。所有存储的集合用Store表示。为了简单起见，我们不考虑某些标量类型（如整数）的优化表示。存储的这种定义仅捕获静态部分-图形表示存储在某个时间点的快照。当然，程序通过创建新节点和重定向现有节点的边来动态修改存储。3.2存储中Alice数据的表示所有数据，如整数、字符串或元组，都可以直接映射到抽象存储中的对象上。整数是带有int标签的块。字符串是带有标签字符串的块。元组是具有标签元组和到元组的组件的边的块。元组也用来表示代数数据集的值代码就是数据。这是使悬挂物均匀化的基本假设，并允许我们只根据悬挂物来表示酸洗和最小化。可能的表示包括字节码块，或抽象语法树的嵌套元组。3.3有状态数据引用或数组等有状态数据的实现方式与无状态数据相同。然而，有状态数据的相等性是根据令牌相等来定义的：如果两个引用实际上表示相同的存储单元，则它们是相等的，而如果两个元组的结构相同并且它们的组件相等，则两个元组是相等的（结构相等）。为了支持这一点，我们对标签集进行分区：Lab = Lab 结 构 化 Lab 令 牌。这将允许我们在pickle和minimization期间不同地处理有状态数据。84G. Tack等人/理论计算机科学电子笔记148（2006）793.4垃圾收集在抽象存储方面，自动垃圾收集意味着从图中删除从可区分的根节点无法到达的节点。例如，根节点可以是堆栈，所有实时数据都应该以某种方式引用。形式上，垃圾收集是一个函数gc∈Store×Adr→Store× Adr使得gc（s，root）=（sJ，rootJ）且sJ同构于s从root可达，rootJ是sJ中的根节点。这种形式化的模型类似于复制垃圾收集。3.5执行Alice系统基于Seam，一个简单的可扩展抽象机器库[6]。Seam提供了一个抽象存储，它紧密地实现了本节中介绍的抽象。出于效率的原因，整数是优化的，它们实际上不需要在存储中分配的节点。Seam具有分代垃圾收集器，并内置了对pickle和minimization的支持，这些存储服务将在下面的部分中讨论。4碱性酸洗和不酸洗我们现在可以定义在实验室存储中pickle和unpickle的含义：将存储的子图转换为平台无关的外部格式，并构造与可能不同的存储中的原始子图等效的子图。我们首先开发unpickler和一个合适的pickle语言。在第二步中，我们将展示如何生成抽象存储的子图的泡菜。4.1pickle语言我们把pickle看作是解释器的一系列指令，解释器在存储中构造相应的图该语言将以bnf语法的形式呈现，但应该清楚的是，这种语言足够简单，可以直接对应于字节序列。在实际的实现中，pickler和unpickler都不产生或消耗中间的、类似数据类型的项，而是二进制数据。我们将要求pickle语言能够表达存储中的共享以及循环。循环在典型的Alice数据结构中无处不在G. Tack等人/理论计算机科学电子笔记148（2006）79856t一4tB5s1t3tC一B CS c“爱丽丝”chunk（s，区块（b，2）block（c，0）block（a，2）一S c“爱丽丝”chunk（s，存储$0块（b，2）加载$0块（a，2）(a) 一棵树（b）一个无圈图一BS c“爱丽丝”chunk（s，block（c，1）store$1 block（b，2）load $1fulfill（$0，2）2bs“alice”(c)循环图（d）DFS注释的存储Fig. 1. 抽象存储中的图和相应的pickle请注意，与经典ML实现相反，Alice数据可以包含不通过ref单元格建立的无状态循环4.2在存储区中构造图形：解压缩对于unpickler，我们从树的pickle语言开始，然后推广到非循环和最终循环图。构造树的常用方法是使用堆栈机以自底向上的方式。在抽象存储中构造树的pickle语言需要以下指令：pickle|ϵblock：：= block（label，arity）|chunk（label，string）指令块（l，n）将n个节点弹出堆栈，构造具有标签l和这n个子节点的新标量节点由块指令构造。在成功构建整个树之后，根节点是堆栈上唯一的项。图1（a）显示了抽象存储中的一棵树以及从中可以构建它的pickle自底向上构造也适用于有向无环图（DAG），但解释器必须通过一组无界寄存器进行扩展：B86G. Tack等人/理论计算机科学电子笔记148（2006）79具有多个前驱节点–我们用相应的指令扩展pickle语言存储寄存器|加载寄存器你可以在图1（b）中找到一个DAG及其对应的pickle。为了清楚起见，寄存器写有前导$。我们还不能构造循环数据，因为构造一个节点需要已经构造了它的所有子节点。因此，必须明确周期：promise += promise（register，label，arity）|fullfill（register，arity）promise指令创建一个节点，该节点承诺最终成为循环中的一个节点。使用promise作为占位符，循环中的所有其他节点都可以在promise被相应的fulfill指令填充之前构建。承诺只能兑现一次。图1（c）显示了一个由pickle构成的循环图。unpickler通过回打补丁实现promise和fulfill指令：一个带有标签l和arityn的节点的promise构造了一个带有该标签和arity的节点，但是是任意的满足这个承诺，就意味着用真正的孩子替换虚拟的孩子。当promise一个节点时，unpickler需要label和arity，所以promise指令将这些作为参数。对于fulfilling，它需要找到之前创建的promise，因此这两条指令都需要一个寄存器。我们省略了低级pickle格式的细节，因为它是从指令序列到字节序列的4.3优化pickle语言可以针对所得到的酸洗尺寸、有效的解酸洗或有效的酸洗来优化酸洗格式。如果pickle主要用于持久性存储，pickle大小和有效的unpickle是很重要的，因为pickle只被写入一次，但经常被读取。然而，对于网络传输，pickle可能成为瓶颈。为了优化pickle大小，可以将存储和块/组块指令组合成存储块和存储组块指令。解pickler可以从了解解pickle所需的最大堆栈高度以及pickle中使用的寄存器数量中受益，因为这样堆栈和寄存器组就不必能够动态增长可以使用活性分析和简单的寄存器分配器来最小化所需寄存器的数量我们还没有进一步调查G. Tack等人/理论计算机科学电子笔记148（2006）7987泡菜酱：：=日本泡菜|ϵ联系我们：：=内存块（label，arity）|标签存储块（标签，字符串）|加载寄存器|promise（register，label，arity）公司简介|：：=fullfill（register，arity）存储寄存器|ϵ表1pickle语言这是因为我们认为，寄存器稍微少一点的好处并不能证明pickler中的开销是合理的。我们提出的pickle格式必须在pickle语言的通用性和紧凑性之间做出妥协。一个不太通用的系统可以使用类型信息来使pickle更紧凑，并为公共语言实体提供专门的外部表示。总而言之，表1显示了完整的pickle语言。4.4存储的挑选子图剩下的问题是从存储的子图生成上述格式的pickle。如果unpickle意味着根据给定的指令构造一个图，pickle意味着以相同的顺序遍历图并生成这些指令。pickle可以同时被看作解pickler的指令，以及图遍历的协议4.4.1分享与循环保持共享和循环是我们想要开发的酸洗机的一个重要特性。虽然检测共享和循环会在pickle期间产生开销，但这对于提高pickle效率至关重要：pickle在不共享节点的情况下变得更大，指数爆炸是可能的。循环数据结构不能在没有共享的情况下表示，并且尝试pickle它们会产生分歧。4.4.2深度优先搜索图遍历的标准算法是深度优先搜索（DFS），由Tarjan在1972年发明[27]。我们现在将展示上面介绍的pickle格式类似于图的后序、深度优先的从左到右遍历的协议。树很容易腌制：它们的腌制物与序列完全对应88G. Tack等人/理论计算机科学电子笔记148（2006）79在后序从左到右DFS遍历中的节点。对于DAG和任意图，pickle对应于边的后序序列。深度优先搜索可以对图中的边进行排序和分类树边是DFS在第一次访问节点时遍历的边后边缘是从节点通向DFS树中的其祖先节点之一的边缘。共享边是剩余的边。边根据它们被访问的时间（前序）和DFS完成边的时间（后序）排序。如果节点只有一个前趋节点，则将其标记为非共享;如果节点至少有一个传入后边缘，则将其标记为已承诺;否则将其标记为共享。下面的定义扩展了边缘上带有DFS注释的抽象存储：定义4.1DFS注释的抽象存储是一个有限函数g∈Adr~ Lab× {unshared，shared，promised} ×(BSeq（Adr× N× {tree，back，sharing}））图1（d）显示了后序DFS注释的抽象存储。树、后和共享边缩写为t、b和s。不显示节点注释，因为它们与引入边之间是清晰的。为了规则性，根节点具有额外的传入边。这是一个树的边缘，并获得最高的后序数。在DFS注释的存储中，每个边缘对应于一个pickle指令。酸洗相当于在边缘的后序中读取这些指令到非共享节点v的树边对应于块或组块指令，这取决于v。到共享节点v的树边除了块或一大块一棵树的边缘到一个承诺的节点v成为一个完整的填充。注意，V的类型是块，因为只有块可以躺在一个圆上。节点v的后边缘对应于promise，如果它是v的后边缘用最小的后序数，否则到负载。共享边缘对应于加载指令。4.4.3交错DFS注释和线性化DFS可用于直接生成pickle指令序列因此，DFS注释的存储永远不会在内存中构造唯一的困难是确定一棵树的边缘是否指向一个非-G. Tack等人/理论计算机科学电子笔记148（2006）7989共享或共享节点。当DFS将后序编号分配给树边时，此信息不可用。所有其他边都不是关键的：共享边在指向同一节点的树边之后被访问，导致在相应的存储之后加载。对于后边缘，DFS可以确定它是否是该节点的第一个后边缘，从而确定promise是否是或者必须生成负载。在promise生成之后，访问到promise节点的树边，因此可以生成一个完整的填充指令。为了解决树边缘到未承诺节点的问题，我们应用两阶段方法：第一阶段创建没有任何存储指令的指令序列，同时维护一个有序的pickle程序操作集列表，之后必须插入存储指令。然后，第二阶段通过复制pickle程序并在必要的地方插入存储另一种方法是为每个树边缘插入存储使用组合的存储块指令，这不会增加pickle大小。然而，在unpickle解释器中需要更多的寄存器。对于很少共享的数据结构（如列表），开销与pickle的大小成线性关系4.4.4Pickling具有所需的语义Pickling和unpickling产生存储的子图的副本，就像复制垃圾收集一样，或者在较低级别上，操作系统的虚拟内存系统。正如复制垃圾回收不会改变复制数据的语义一样，- 在最简单的情况下-身份功能。 如果没有有状态的节点，也没有带有transform标签的节点，则pickle子图和unpickle子图的结果与原始结果无法区分。使用有状态数据，可以观察到原始和未pickle副本之间的差异。在Alice中，pickle的语义目前是这样定义的。如果需要不同的语义，则不能pickle有状态节点原始副本和未pickle副本之间的第二个差异来源是转换机制。在这里，抽象和实例化函数的实现者有责任确保这些函数的行为符合语言语义。4.4.5预定酸洗，自上而下的解酸洗后工序酸洗不规范。除了Alice，只有Python [21]似乎使用了后序线性化和自底向上构造。后序pickle和自底向上unpickle的双重方法是使用边的前序线性化，然后对应于图的自顶向下构造。90G. Tack等人/理论计算机科学电子笔记148（2006）79边的前序线性化需要稍微不同的pickle语言和解释器：promise和fulfill指令是不必要的，因为每个节点都在它的子节点之前构造。 一旦子节点被构造，解释器就需要将子节点反向修补到父节点中。这两种方法之间的区别在于递归的类型，用于酸洗和酸洗。自底向上的unpickle需要一个简单的递归，构造的节点被推到堆栈上，并保持在那里，直到它们的父节点被构造。自上而下的unpickle需要一个更复杂的堆栈，因为一个节点在它的子节点被构造之前被压入，并且必须在最后一个子节点被构造之后被弹出。pickling的情况是双重的：后序pickling需要比前序pickling更复杂的堆栈。这意味着只有当每个pickle只被读取一次时，这两种方法才具有相同的效率。一旦unpickle比pickle更频繁，自底向上的方法就更优越。4.4.6从右到左遍历这里介绍的深度优先搜索通常从左到右（从第一个孩子到最后一个）遍历节点的孩子。一些数据结构，例如ML中的列表，是右递归的。这里假设的从左到右的构造需要列表大小的堆栈，而从右到左的构造可以管理恒定的堆栈空间。因此，对某些节点（取决于标签）使用从右到左的遍历和构造可能是有意义的。对于Alice来说，实验表明，通常使用从右到左的策略可以显着减少unpickle时间。4.4.7广度优先搜索广度优先搜索（BFS）是经典抽象存储服务复制垃圾收集的首选算法。Cheney算法[7]使用存储区，将活节点复制到该存储区作为队列，即BFS的垃圾回收器不需要任何额外的内存。酸洗和解酸洗可以基于切尼算法的变体pickler使用Cheney扫描复制子图的节点，用抽象地址替换抽象存储中的真实地址，从图被复制到的内存的开始计数。然后，解包器可以使用另一个切尼扫描来重新创建图的副本，将抽象地址映射回真实地址。对于pickle，不使用任何额外内存的优势消失了：Cheneypickler不能在适当的位置标记节点，因为它们在pickle之后不会变成垃圾。它需要额外的内存来存储这些信息。解酸器G. Tack等人/理论计算机科学电子笔记148（2006）7991也不能直接在pickle中标记节点。仍然，不需要额外的控制数据结构（堆栈或队列）。一个复杂的问题是，在BFS期间，很难控制什么时候完成了pickle的子图的构造。我们将需要这些信息来实现下一节介绍的转换。5酸洗和酸洗解在本节中，我们将扩展pickle来处理不应该pickle的对象，并在pickle和unpickle期间应用转换5.1资源资源是存储中的一个节点，它在存储之外没有明确的含义。经典的例子是文件描述符或窗口句柄。资源不能被浪费。这很容易通过将标签集划分为资源标签和可挑选数据标签来实现。pickler在找到资源时抛出异常pickler不会尝试重新绑定资源（如[9，16]中所讨论然而，重新绑定可以通过下面介绍的转换机制来5.2转型pickle的重要设计目标是平台独立性。另一方面，实现抽象存储的重要设计目标必须是效率。pickler和unpickler到目前为止生成的存储的子图。这意味着存储可能不会以依赖于平台的方式优化数据然而，优化的内部表示是可取的;例如，浮动点数在大端和小端平台上具有不同的有效表示。解决方案是在pickler和解pickler中内置一个通用的转换机制。为此，我们引入特殊的变换存储标签，并假设对于每个这样的标签lt，有一对函数抽象lt∈Adr→ Adr和实例化lt∈Adr→ Adr2。当pickler下降到节点v时，抽象lt函数被应用于标签为lt的节点v。该函数然后计算v的抽象外部表示vJ，并且pickler下降到vJ。解酸器适用于2在实际的设置中，这些函数当然可以在商店中构造新的节点92G. Tack等人/理论计算机科学电子笔记148（2006）79在构造具有标签LT节点V之后实例化LT。 实例化产生一个节点vJ，然后解包器使用它来代替v进行进一步的构造。请注意，抽象和实例化都很适合后序pickle和自底向上的unpickle方法：抽象可以在第一次访问节点之前发生，实例化可以在完成其pickle之后发生。在前序和自上而下的场景中，unpickler必须为每个带有transform标签的节点引入一个占位符，unpickle节点及其子树，然后用实例化的结果填充占位符这模拟了使用占位符的自底向上构造。5.2.1即时编译转换机制的高级应用是即时编译：外部的、平台无关的代码表示被编译成高效的、内部的表示，如优化的字节码或本地机器码。在当前实现中，Alice编译器生成一个包含中间格式代码的组件，称为Alice抽象代码。代码被标记为转换存储标签，并且在解压缩时，抽象代码被编译为字节码或本机机器码。对于真正的即时编译，代码不是在加载时编译，而是在第一次执行时编译。在Alice中，我们可以使用lazy future（参见第7节）以一种简单的方式完成这一点：不是实例化未pickle的值，而是创建一个惰性挂起这有一个额外的好处，即实际的转换可以是完全并发的，并被垃圾收集中断，而unpickler中的实例化必须是原子的。实例化通常不能轻易撤销。 例如，不可能从机器代码中恢复Alice抽象代码。在这种情况下，实例化必须保留一个外部表示的副本，然后抽象可以简单地返回。6小化前面介绍的pickle精确地表示被pickle的抽象存储的子图的节点。可以说pickle是自动垃圾收集的，因为只有可到达的节点才被pickle。为了进一步减小pickle大小，可以移除冗余节点本节正式定义了哪些节点是冗余的，将其与图最小化算法联系起来，并介绍了除pickle之外的其他应用领域G. Tack等人/理论计算机科学电子笔记148（2006）79936.1抽象存储抽象存储中的节点是冗余的，如果它在语言中与存储中的其他节点无法区分。以平衡二叉树为例：数据类型t= N| T/T*Tval a= T（T（N，N），T（N，N））val b=let val c= T（N，N） in T（c，c）end这两棵树在语义上无法区分。然而，a的根的一个子节点是冗余的，如树b所示。树b共享根节点的两个子树。对于以这种方式构造的深度为d的树，不共享任何东西会导致分配2d-1个节点，而完全共享只需要d个节点。因此，人们总是试图设计具有最小冗余的数据结构。这当然很难实现，特别是从更全球的角度来看的观点。值通常是独立构建的，通常在系统的不同组件中，并且没有中央权威来控制共享。另一个限制是，不同类型的值永远不能共享，尽管它们可以以相同的方式在内部表示6.2最小化非循环图：散列consing如果所考虑的数据结构不包含循环，或者如果所有循环都是通过有状态节点建立的（例如在SML中），则可以使用称为散列consing的技术来最大化存储中的共享。在存储中构造节点v时，计算v的散列值并且将v存储在表中。如果构造了具有相同哈希值的节点w，则使用对v的引用而不是实际分配w。因此，最大化共享的成本在节点的构建过程中摊销在L ISP系统中，有一个简单的方法可以减少损失。 AppelandGoncalv讨论了如何将散列consing与SML/NJ垃圾收集器集成[3]。他们的系统只对至少经历过一次垃圾收集的节点进行散列，这样散列的成本只会支付给寿命更长的节点。散列consing的另一个应用领域是中间语言中类型信息的高效表示[25，26]。6.3一般图最小化在下文中，我们在抽象存储层上开发了一个通用的最小化服务该算法基于自动机和图最小化，并删除抽象存储的给定子图中的所有冗余节点94G. Tack等人/理论计算机科学电子笔记148（2006）79我对于Alice来说，最小化可以处理循环数据是很重要的，因为无状态循环无处不在：运行时类型的表示，代码表示以及函数闭包都可能包含这样的循环。最小化的定义依赖于抽象存储中节点的等价定义这是由等式关系∈Adr× Adr捕获的，该等式关系被定义为满足以下条件：(i) 如果v∈vJ，g（v）=（l，）且l∈Labtoken，则• v=vJ(ii) 若v<$vJ，g（v）=（l，s）且s∈Str，则• g（ vJ）= g（ v）(iii) 如果v ∈ vJ且g（v）=（l，v ∈v0，. ，v n），则• g（v，J）=（l，v，J，.，vJ）和0n• {0，.，n}：v ivJ两个相等关系的结合又是一个相等关系。定义为v=vJ：惠v = vJ的关系是一个等式关系。 设Eq是所有等式关系的集合”于是，他就被称为“不”。空）所有相等关系的并集：S=∼Eq由于等式关系在联合下是封闭的，因此，最大的等式关系是唯一的。它精确地表达了抽象存储中的语义平等：两个节点除了它们的地址之外不能区分。有必要考虑最大的这种关系，因为任何较小的关系都不会产生循环图所需的等价关系。存储中的语义平等由BLOSS定义，严格地比Alice中的语义平等更强：• 非eqtypes的值可以是 被视为平等。特别是，函数类型的值可以被认为是相等的。• 不同类型的值可以被认为是相等的，只要它们的表示允许这一点。• 循环值可以被认为是相等的，尽管应用于它们的相等运算符会发散。给定一个子图g，最小化计算g关于图S的等价类。 然后，我们可以使用这些信息来将g中的每个节点替换为其等价类的唯一表示。 由此产生的图gJ是最小的，在这个意义上，对于gJ中的两个节点w和wJ，w≠sJ意味着w = wJ。G. Tack等人/理论计算机科学电子笔记148（2006）7995图的最小化是一个众所周知的问题：最小化有限状态自动机的第一个算法可以在60年代的教科书中找到。1971年Hopcroft给出了一个最坏情况时间复杂度为O（nlogn）的算法[13]。他的算法很容易推广到有序图。其主要思想是细化初始等价关系，使其与图结构兼容：如果v≠vJ，则对于v的后继者wi在边编号i处，vJ在边i处具有后继wJ，使得wi≠wJ。这样的我我等价关系称为同余。如果我们从一个等价开始，使具有不同标签的节点完全不同，那么很容易看出，图最小化将产生一个同余，它描述了节点的语义等价。为了实际最小化图，必须选择每个同余类c的代表r，将c的所有其他成员的边重定向到r，并删除c我们的最小化的实现是基于一般的方法如Habib等人[10]所描述的分区细化。Hopcroft算法与这些思想的结合可以很容易地调整到抽象存储模型。它产生一个高效的通用最小化服务。6.4有状态数据为了在非纯语言中使用，最小化器必须能够处理有状态数据。有状态数据，即存储节点，其边缘可以被重定向，必须保持唯一。这直接源于以下事实：在下面的示例中，a和b在语言中是可区分的，而aJbJ不是：val a=ref3valb=ref3vala图的最小化只是细化了初始等价关系，因此它使得所有有状态的节点在初始划分中是不同的，并且它们在最小化之后将保持不同。最小化器在Alice标准库中作为函数minimize：它接受一个任意的Alice值，并最小化它在存储中的表示。6.5应用领域最小化可以看作是语义垃圾收集的一种形式：它不回收不可达的节点，而是回收冗余的节点至于任何96G. Tack等人/理论计算机科学电子笔记148（2006）79垃圾收集的形式，人们必须权衡它所需的运行时和较小内存占用的好处可以想象将极小化器与垃圾收集器集成在一起，例 如 Ap pel和Goncalved[3]。最小化可以应用于商店的某些区域，或者仅应用于主要集合。 我们还没有实现这一场景，ApelandGon c o nconves提供的ben c hm ark表明空间节省“不是很可观”。然而，对于Alice来说，情况这可能为极小化者提供更多的潜力。最直接的应用是在酸洗之前总是最小化一个pickle值应该是长期存在的，所以投资于最小化可能会付出代价。Alice编译器和静态链接器提供了在pickle之前最小化已编译组件的选项，这已被证明是可行的，也值得尝试（请参阅下一节中的基准测试最小化与令牌相等性测试一起提供了循环数据的结构相等性测试：fun cyclic_equal（x，y）=（minimize（x，y）; token_eq（x，y））其他应用程序更具体的问题。我们目前正在研究动态类型的运行时表示（如包所需）如何这里特别有趣的是快速结构相等测试：在最小化表示中，两个类型相等当且仅当它们由同一个节点表示6.6基准作为基准，我们编译了Alice库，由818个组件组成，有和没有最小化：组件大小pickle大小编译时间未最小化104.2912.58 22m36s最小71.80（69%）12.51（99%）22m26s（99%）组件大小是组件在存储区中占用的大小（以兆字节为单位）。最小化器可以将组件缩小30%。Pickle size（也以兆字节为单位）测量pickle的文件大小。pickler使用gzip压缩来进一步缩小pickle文件的大小，在压缩格式下，最小化的pickle只比普通的pickle略小。这是因为gzip压缩也消除了冗余，并且在最小化pickles中需要消除的冗余较少。最后一列是编译所有组件所需的时间它显示G. Tack等人/理论计算机科学电子笔记148（2006）7997这种最小化不会引起任何运行时开销，一方面是因为它很快，另一方面是因为编译器从加载较小的组件进行类型检查中受益所有Alice程序都受益于最小化的库，因为它减少了启动时间和内存占用。基准测试是在AMD 64 3000+上进行的，RAM为512MB，运行DebianLinux for AMD 64。组件大小的确切数字在32位平台上会有所不同，但相对压缩将保持不变。7并发和懒惰Alice是一种并发语言，并发所基于的基本概念是未来的概念。future是一个占位符，用于表示一个未知的值，例如并发计算或惰性计算的结果。Future提供数据流同步：需要访问Future的线程被隐式地阻塞，直到Future被确定。期货最早是在Multilisp中引入的[11]。期货的形式语义可以在[19]中找到。例如，考虑一个函数f：int -> int，它对整数执行一些复杂的计算我们可以在一个新的线程中使用表达式vala = spawnf3来计算它.这会立即返回一个future，同时计算f3如果我们现在访问a，例如在表达式val b = a + 3中，这个线程将阻塞，直到f3的计算结果可用。结果将替换未来，并且执行b的线程将自动恢复。懒惰类似于并发求值：表达式val a = lazyf3立即求值为懒惰的future。只有当实际需要该值时，例如在表达式val b = a + 4中，才会对应用程序f3进行求值，并将future绑定到结果。7.1抽象商店future语义要求在绑定future时将其替换为一个值。为了使这种替换有效，期货以带有特殊标签的节点的形式内置到抽象存储中：Lab{fut，lazy}。当一个并发的future被创建时，一个arity为1，标签为fut的块 构造了将未来的f替换为值v相当于对存储进行了一次become操作：表示f的节点的标签被更改为内部标签fwd（转发节点），边被重定向为指向98G. Tack等人/理论计算机科学电子笔记148（2006）79节点代表v。存储上的所有其他操作都透明地遵循fwd节点链，垃圾收集执行这些链的路径压缩。7.2同时酸洗和不酸洗到目前为止所描述的Pickling和unpickling对于顺序语言来说工作得很好然而，在爱丽丝的并发环境中，我们必须关注未来。解压缩并不重要：构造的子图的根只有在图完全构造之后才可用。然而，对于pickle，我们需要一个快照语义：pickle应该表示某个特定时刻的子图。最简单的解决办法是把未来视为资源，而不是把它们腌制起来。在像Alice这样的语言中，由于延迟链接，futures无处不在，这将使picking变得不那么有用。对于lazy future，有两种可能的方法：强制执行它们的求值，或者pickle完全的lazy suspension（也在store中表示）。Pickling并发futures将相当于pickling线程，这涉及更多，在这里将不讨论。我们假设，在酸洗过程中，必须强制对并发期货进行评估。如果我们只考虑无状态图，期货保证图单调增长。因此，在pickle期间强制执行它们的评估将导致pickle之后的图形快照。一旦我们有了用于pickle有状态数据的克隆语义，并发pickler就不能确保图在pic
我的内容管理
展开
