当一个 C 程序员需要一个有效的数据结构来解决一个特定问题时，他/她可以简单的在大量好的教科书或者手册里查找。不幸的是，例如 Standard ML 或者 Haskell 的函数式编程语言的程序员没有这种优势。虽然一些为类似 C 语言的命令式语言设计的数据结构可以简单地移植到函数式的设定，大多数数据结构不行，通常因为它们依赖于某种关键的赋值。为了解决这种不平衡，我们描述了设计函数式数据结构的几种技巧，以及基于这些技术的许多原始数据结构，包括列表、队列、双端队列和堆的多种变体，其中许多支持更奇特的功能，如随机访问或高效连接（catenation）。
Without the faith and support of my advisor, Peter Lee, I probably wouldn't even be a graduate student, much less a graduate student on the eve of finishing. Thanks for giving me the freedom to turn my hobby into a thesis.
I am continually amazed by the global nature of modern research and how email allows me to interact as easily with colleagues in Aarhus, Denmark and York, England as with fellow students down the hall. In the case of one such colleague, Gerth Brodal, we have co-authored a paper without ever having met. In fact, sorry Gerth, but I don’t even know how to pronounce your name!
I was extremely fortunate to have had excellent English teachers in high school. Lori Huenink deserves special recognition; her writing and public speaking classes are undoubtedly the most valuable classes I have ever taken, in any subject. In the same vein, I was lucky enough to read my wife's copy of Lyn Dupré's BUGS in Writing just as I was starting my thesis. If your career involves writing in any form, you owe it to yourself to buy a copy of this book.
Thanks to Maria and Colin for always reminding me that there is more to life than grad school. And to Amy and Mark, for uncountable dinners and other outings. We'll miss you. Special thanks to Amy for reading a draft of this thesis.
And to my parents: who would have thought on that first day of kindergarten that I'd still be in school 24 years later?
目录（Contents）
序言（Introduction）
1.1 函数式数据结构与命令式数据结构（Functional vs. Imperative Data Structures）
1.2 严格求值与懒惰求值（Strict vs. Lazy Evaluation）
1.3 贡献（Contributions）
1.4 源语言（Source Language）
1.5 术语（Terminology）
1.6 回顾（Overview）
懒惰求值与 \text{\textdollar} 记号
2.1 流（Streams）
2.2 历史记号（Historical Notes）
借助懒惰求值的均摊与可持久化（Amortization and Persistence via Lazy Evaluation）
3.1 传统可持久化（Traditional Amortization）
3.1.1 例子：队列（Example: Queues）
3.2 可持久化：多重未来的问题（Persistence: The Problem of Multiple Futures）
3.2.1 跟踪执行和逻辑时间（Execution Traces and Logical Time）
3.3 调和均摊与可持久化（Reconciling Amortization and Persistence）
3.3.1 懒惰求值的地位（The Role of Lazy Evaluation）
3.3.2 分析懒惰数据结构的框架（A Framework for Analyzing Lazy Data Structures）
3.4 银行家法（The Banker's Method）
3.4.1 证明银行家法（Justifying the Banker's Method）
3.4.2 例子：队列（Example: Queues）
3.5 物理学家法（The Physicist's Method）
3.5.1 例子：队列（Example: Queues）
3.5.2 例子：使用共享进行自下而上的归并排序（Example: Bottom-Up Mergesort with Sharing）
3.6 相关工作（Related Work）
消除均摊（Eliminating Amortization）
4.1 调度（Scheduling）
4.2 实时队列（Real-Time Queues）
4.3 使用共享进行自下而上的归并排序（Bottom-Up Mergesort with Sharing）
4.4 相关工作（Related Work）
懒惰重建（Lazy Rebuilding）
5.1 批量重建（Batched Rebuilding）
5.2 全局重建（Global Rebuilding）
5.3 懒惰重建（Lazy Rebuilding）
5.4 双端队列（Double-Ended Queues）
5.4.1 输出受限双端队列（Output-restricted Deques）
5.4.2 银行家的双端队列（Banker's Deques）
5.4.3 实时双端队列（Real-time Deques）
5.5 相关工作（Related Work）
数值表示（Numerical Representations）
6.1 按位计数制（Positional Number Systems）
6.2 二进制表示（Binary Representations）
6.2.1 二进制随机访问列表（Binary Random-Access Lists）
6.2.2 二项堆（Binomial Heaps）
6.3 线段化二进制数（Segmented Binary Numbers）
6.3.1 线段化二进制随机访问列表与二项堆（Segmented Binomial Random-Access Lists and Heaps）
6.4 斜二进制数（Skew Binary Numbers）
6.4.1 斜二进制随机访问列表（Skew Binary Random-Access Lists）
6.4.2 斜二项堆（Skew Binomial Heaps）
6.5 讨论（Discussion）
6.6 相关工作（Related Work）
数据结构自举（Data-Structural Bootstrapping）
7.1 结构分解（Structural Decomposition）
7.1.1 非一致递归与 Standard ML（Non-Uniform Recursion and Standard ML）
7.1.2 再探队列（Queues Revisited）
7.2 结构抽象（Structural Abstraction）
7.2.1 高效连接的列表（Lists With Efficient Catenation）
7.2.2 高效合并的堆（Heaps With Efficient Merging）
7.3 相关工作（Related Work）
隐式递归下降（Implicit Recursive Slowdown）
8.1 递归下降（Implicit Recursive Slowdown）
8.2 隐式递归下降（Implicit Recursive Slowdown）
8.3 支持递减函数（Supporting a Decrement Function）
8.4 队列与双向队列（Queues and Deques）
8.5 可连接的双端队列（Catenable Double-Ended Queues）
8.6 相关工作（Related Work）
结论
9.1 函数式编程（Functional Programming）
9.2 可持久化数据结构（Persistent Data Structures）
9.3 编程语言设计（Programming Language Design）
9.4 悬而未决的问题（Open Problems）
A. Standard ML 中懒惰求值的定义（The Definition of Lazy Evaluation in Standard ML）
A.1 语法 Syntax
A.2 静态语义（Static Semantics）
A.3 静态语义（Dynamic Semantics）
A.4 递归（Recursion）
参考文献
索引
1 序言（Introduction）
Efficient data structures have been studied extensively for over thirty years, resulting in a vast literature from which the knowledgeable programmer can extract efficient solutions to a stunning variety of problems. Much of this literature purports to be language-independent, but unfortunately it is language-independent only in the sense of Henry Ford: Programmers can use any language they want, as long as it’s imperative.^1 Only a small fraction of existing data structures are suitable for implementation in functional languages, such as Standard ML or Haskell. This thesis addresses this imbalance by specifically considering the design and analysis of functional data structures.
高效的数据结构已经被广泛研究了至少三十年（注：本文写于 1996 年 9 月），产生了大量文献，有经验的程序员可以从中提取出各种惊人问题的有效解决方案。这些文献大多声称是独立于语言的，不幸的是它只是 Henry Ford 意义上（in the sense of Henry Ford）的独立于语言：程序员可以使用他们想要的任何语言，只要那种语言是命令式的^1。只有少数数据结构适合在例如 Standard ML 或 Haskell 的函数式语言中实现。本文通过具体考虑功能数据结构的设计和分析来解决（addresses）这种不平衡。
$^1$Henry Ford 曾经对他的 T 型汽车的可用颜色说：“[顾客]可以将 T 型车漆成任何他所愿意的颜色，只要它是黑色的”
## 1.1 函数式数据结构与命令式数据结构（Functional vs. Imperative Data Structures）
The methodological benefits of functional languages are well known [Bac78, Hug89, HJ94], but still the vast majority of programs are written in imperative languages such as C. This apparent contradiction is easily explained by the fact that functional languages have historically been slower than their more traditional cousins, but this gap is narrowing. Impressive advances have been made across a wide front, from basic compiler technology to sophisticated analyses and optimizations. However, there is one aspect of functional programming that no amount of cleverness on the part of the compiler writer is likely to mitigate — the use of inferior or inappropriate data structures. Unfortunately, the existing literature has relatively little advice to offer on this subject.
函数式语言方法上的（methodological）优势是众所周知的 [Bac78, Hug89, HJ94]，但绝大多数程序仍然是用命令式语言（如 C）编写的。这一明显的矛盾可以很容易地解释为，函数式语言历来比其更传统的同类语言慢，但这一差距正在缩小。从基本的编译器技术到复杂的分析和优化，在各个领域都取得了令人印象深刻的进展。然而，函数式编程有一个方面是编译器编写者再聪明也无法减轻的——使用次等或不合适的（inferior or inappropriate）数据结构。不幸的是，现有文献对这一主题的建议相对较少。
Why should functional data structures be any more difficult to design and implement than imperative ones? There are two basic problems. First, from the point of view of designing and implementing efficient data structures, functional programming's stricture against destructive updates (assignments) is a staggering handicap, tantamount to confiscating a master chef's knives. Like knives, destructive updates can be dangerous when misused, but tremendously effective when used properly. Imperative data structures often rely on assignments in crucial ways, and so different solutions must be found for functional programs.
为什么函数式数据结构的设计和实现要比命令式数据结构更困难？有两个基本问题。首先，从设计和实现高效数据结构的角度来看，函数式编程对破坏性更新（赋值）的限制是一个惊人的障碍，相当于没收了一位主厨的刀。就像刀子一样，破坏性更新在误用时可能很危险，但在正确使用时却非常有效。命令式数据结构通常以关键的方式依赖于赋值，因此必须为函数式程序找到不同的解决方案。
The second difficulty is that functional data structures are expected to be more flexible than their imperative counterparts. In particular, when we update an imperative data structure we typically accept that the old version of the data structure will no longer be available, but, when we update a functional data structure, we expect that both the old and new versions of the data structure will be available for further processing. A data structure that supports multiple versions is called _persistent_ while a data structure that allows only a single version at a time is called _ephemeral_ [DSST89]. Functional programming languages have the curious property that _all_ data structures are automatically persistent. Imperative data structures are typically ephemeral, but when a persistent data structure is required, imperative programmers are not surprised if the persistent data structure is more complicated and perhaps even asymptotically less efficient than an equivalent ephemeral data structure.
第二个困难是，函数式数据结构预计比其必要的对应结构更灵活。特别是，当我们更新命令式数据结构时，我们通常接受旧版本的数据结构将不再可用，但当我们更新功能性数据结构时，我们预计旧版本和新版本的数据结构都将可用于进一步处理。支持多个版本的数据结构称为 _可持久化的_，而一次只允许单个版本的数据结构称为 _非持久化_ [DST89]。函数式编程语言具有一个奇怪的特性，即 _所有_ 数据结构都自动成为可持久化的。命令式数据结构通常是非持久化的，但当需要可持久化数据结构时，如果可持久化数据结构比等效的非持久化数据结构更复杂，甚至渐进效率可能更低，命令式语言的程序员也不会感到惊讶。
Furthermore, theoreticians have established lower bounds suggesting that functional programming languages may be fundamentally less efficient than imperative languages in some situations [BAG92, Pip96]. In spite of all these points, this thesis shows that it is often possible to devise functional data structures that are asymptotically as efficient as the best imperative solutions.
此外，理论家们已经得出了下界，这表明在某些情况下，函数式编程语言的效率可能根本不如命令式语言 [BAG92, Pip96]。尽管有所有这些点，本文表明，通常可以设计出与最佳命令式解法一样渐近有效的函数式数据结构。
## 1.2 严格求值与懒惰求值（Strict vs. Lazy Evaluation）
Most (sequential) functional programming languages can be classified as either _strict_ or _lazy_, according to their order of evaluation. Which is superior is a topic debated with religious fervor by functional programmers. The difference between the two evaluation orders is most apparent in their treatment of arguments to functions. In strict languages, the arguments to a function are evaluated before the body of the function. In lazy languages, arguments are evaluated in a demand-driven fashion; they are initially passed in unevaluated form and are evaluated only when (and if!) the computation needs the results to continue. Furthermore, once a given argument is evaluated, the value of that argument is cached so that if it is ever needed again, it can be looked up rather than recomputed. This caching is known as _memoization_ [Mic68].
大多数（相继的）函数式编程语言可以根据它们的求值顺序分类为 _严格求值_ 或 _懒惰求值_。哪一个更优越是函数式程序员们激烈争论的一个话题。这两个评估顺序之间的差异在处理函数的自变量时最为明显。在严格求值的语言中，函数的参数在函数体之前求值。在懒惰求值语言中，参数是以需求驱动的方式进行求值的；它们最初是以未求值的形式传递的，只有当（如果！）计算需要继续时才求值。此外，一旦求值了给定的参数，就会缓存该参数的值，这样，如果再次需要它，就可以查找它，而不是重新计算它。这种缓存称为 _记忆化_ [Mic68]。
Each evaluation order has its advantages and disadvantages, but strict evaluation is clearly superior in at least one area: ease of reasoning about asymptotic complexity. In strict languages, exactly which subexpressions will be evaluated, and when, is for the most part syntactically apparent. Thus, reasoning about the running time of a given program is relatively straightforward. However, in lazy languages, even experts frequently have difficulty predicting when, or even if, a given subexpression will be evaluated. Programmers in such languages are often reduced to pretending the language is actually strict to make even gross estimates of running time!
每种求值顺序都有其优点和缺点，但严格求值在至少一个方面显然是优越的：易于判断渐近复杂性。在严格求值的语言中，确切地求值哪些子表达式，以及何时评估，在很大程度上是语法上显而易见的。因此，对给定程序的运行时间进行判断是相对简单的。然而，在懒惰求值的语言中，即使是专家也经常难以预测何时甚至是否会求值给定的子表达式。使用这种语言的程序员往往会假装这种语言实际上严格求值，甚至这样对运行时间做出粗略的估计！
Both evaluation orders have implications for the design and analysis of data structures. As we will see in Chapters 3 and 4, strict languages can describe worst-case data structures, but not amortized ones, and lazy languages can describe amortized data structures, but not worst-case ones. To be able to describe both kinds of data structures, we need a programming language that supports both evaluation orders. Fortunately, combining strict and lazy evaluation in a single language is not difficult. Chapter 2 describes $\text{\textdollar}$-notation — a convenient way of adding lazy evaluation to an otherwise strict language (in this case, Standard ML).
这两种求值顺序对数据结构的设计和分析都有影响。正如我们将在第 3 章和第 4 章中看到的那样，严格求值语言可以描述最坏情况的数据结构，但不能描述均摊情况的数据结构；懒惰求值语言可以描述均摊情况数据结构，而不能描述最坏情况的数据结构。为了能够描述这两种数据结构，我们需要一种同时支持这两种求值顺序的编程语言。幸运的是，在一种语言中结合严格求值和懒惰求值并不困难。第 2 章描述了 $\text{\textdollar}$ 表示法——一种将懒惰求值添加到其他严格语言（在本例中为 Standard ML）中的方便方法。
## 1.3 贡献（Contributions）
$$\begin{array}{|l|l|}\hline\text{Name}&\text{Running Times of Supported Functions}\\\hline\text{banker's queues}&snoc/head /tail : O(1)\\\text{physicist's queues}&snoc/head/tail:O(1)\\\text{real-time queues}&snoc/head/tail:O(1)\\\text{bootstrapped queues}&head:O(1)^\dag,snoc/tail:O(\log^*n)\\\text{implicit queues}&snoc/head/tail:O(1)\\\hline\text{banker's deques}&cons/head/tail/snoc/last/init:O(1)\\\text{real-time deques}&cons/head/tail/snoc/last/init:O(1)^\dag\\\text{implicit deques}&cons/head/tail/snoc/last/init:O(1)\\\hline\text{catenable lists}&cons/snoc/head/tail/+\!\!+:O(1)\\\text{simple catenable deques}&cons/head/tail/snoc/last/init:O(1),+\!\!+:O(\log n)\\\text{catenable deques}&cons/head/tail/snoc/last/init/+\!\!+:O(1)\\\hline\text{skew-binary random-access lists}&cons/head/tail:O(1)^\dag,lookup/update:O(\log n)^\dag\\\hline\text{skew binomial heaps}&insert:O(1)^\dag,merge/findMin/deleteMin:O(\log n)^\dag\\\text{bootstrapped heaps}&insert/merge/findMin:O(1)^\dag,deleteMin:O(\log n)^\dag\\\hline\text{sortable collections}&add:O(\log n),sort:O(n)\\\text{scheduled sortable collections}&add:O(\log n)^\dag,sort:O(n)^\dag\\\hline\end{array}$$
最坏运行时间用 $\dag$ 标记。其余运行时间为均摊的。
表 1.1：实现总结
This thesis makes contributions in three major areas:
本文主要在以下三个方面做出了贡献：
+ _Functional programming_. Besides developing a suite of efficient data structures that are useful in their own right (see Table 1.1), we also describe general approaches to designing and analyzing functional data structures, including powerful new techniques for reasoning about the running time of lazy programs.
_函数式编程_。除了开发一套高效的数据结构（见表 1.1）外，我们还描述了设计和分析函数式数据结构的通用方法，包括用于判断懒惰求值程序运行时间的强大的新技术。
+ Persistent data structures. Until this research, it was widely believed that amortization was incompatible with persistence [DST94, Ram92]. However, we show that memoization, in the form of lazy evaluation, is the key to reconciling the two. Furthermore, as noted by Kaplan and Tarjan [KT96b], functional programming is a convenient medium for developing new persistent data structures, even when the data structure will eventually be implemented in an imperative language. The data structures and techniques in this thesis can easily be adapted to imperative languages for those situations when an imperative programmer needs a persistent data structure.
可持久化数据结构。在这项研究之前，人们普遍认为均摊与可持久化不相容 [DST94, Ram92]。然而，我们表明，以懒惰求值的形式进行的记忆化是调和两者的关键。此外，正如 Kaplan 和 Tarjan [KT96b] 所指出的，函数式编程是开发新的可持久化数据结构的方便媒介，即使数据结构最终将以命令式语言实现。当命令式程序员需要可持久化数据结构时，本文中的数据结构和技术可以很容易地适应命令式语言。
+ _Programming language design_. Functional programmers have long debated the relative merits of strict and lazy evaluation. This thesis shows that both are algorithmically important and suggests that the ideal functional language should seamlessly integrate both. As a modest step in this direction, we propose $\text{\textdollar}$-notation, which allows the use of lazy evaluation in a strict language with a minimum of syntactic overhead.
_编程语言设计_。函数式程序员长期以来一直在争论严格求值和懒惰求值的相对优点。这篇论文表明了两者在算法上的重要性，并建议理想的函数语言应该将两者无缝集成。作为朝着这个方向迈出的一步，我们提出了 $\text{\textdollar}$ 表示法，它允许在严格求值的语言中使用懒惰求值，同时将语法开销降至最低。
## 1.4 源语言（Source Language）
All source code will be presented in Standard ML [MTH90], extended with primitives for lazy evaluation. However, the algorithms can all easily be translated into any other functional language supporting both strict and lazy evaluation. Programmers in functional languages that are either entirely strict or entirely lazy will be able to use some, but not all, of the data structures in this thesis.
所有源代码都将以 Standard ML [MTH90] 表达，并使用 primitives 进行扩展以进行懒惰求值。然而，这些算法都可以很容易地翻译成任何其他支持严格和懒惰求值的函数语言。使用完全严格求值或完全懒惰求值的函数式语言的程序员将能够使用本文中的部分（但不是全部）数据结构。
In Chapters 7 and 8, we will encounter several recursive data structures that are difficult to describe cleanly in Standard ML because of the language’s restrictions against certain sophisticated and difficult-to-implement forms of recursion, such as polymorphic recursion and recursive modules. When this occurs, we will first sacrifice executability for clarity and describe the data structures using ML-like pseudo-code incorporating the desired forms of recursion. Then, we will show how to convert the given implementations to legal Standard ML. These examples should be regarded as challenges to the language design community to provide a programming language capable of economically describing the appropriate abstractions.
在第 7 章和第 8 章中，我们将遇到几种递归数据结构，这些结构很难在 Standard ML 中清晰地描述，因为该语言对某些复杂且难以实现的递归形式（如多态递归和递归模块）有限制。当这种情况发生时，为了清晰起见，我们将首先牺牲可执行性，并使用包含所需递归形式的类似 ML 的伪代码来描述数据结构。然后，我们将展示如何将给定的实现转换为合法的 Standard ML。这些例子应该被视为对语言设计社区的挑战，以提供一种能够节约地描述适当抽象的编程语言。
## 1.5 术语（Terminology）
Any discussion of data structures is fraught with the potential for confusion, because the term _data structure_ has at least four distinct, but related, meanings.
任何关于数据结构的讨论都充满了潜在的混乱，因为 _数据结构_ 一词至少有四个不同但相关的含义。
+ _An abstract data type (that is, a type and a collection of functions on that type)_. We will refer to this as an _abstraction_.
_一个抽象数据类型（即一个类型和该类型上的函数集合）_。我们将把它称为一个 _抽象_。
+ _A concrete realization of an abstract data type_. We will refer to this as an _implementation_, but note that an implementation need not be actualized as code — a concrete design is sufficient.
_一个抽象数据类型的具体实现_。我们将把它称为 _实现_，但请注意，实现不需要作为代码来展示——具体的设计就足够了。
+ _An instance of a data type, such as a particular list or tree_. We will refer to such an instance generically as an _object_ or a _version_. However, particular data types typically have their own nomenclature. For example, we will refer to stack or queue objects simply as stacks or queues.
+ _数据类型的一个实例，例如列表或树_。我们将把这样一个实例称为 _对象_ 或 _版本_。然而，特定的数据类型通常有自己的命名法。例如，我们将把堆栈对象或队列对象简单地称为堆栈或队列。
+ _A unique identity that is invariant under updates_. For example, in a stack-based interpreter, we often speak informally about "the stack" as if there were only one stack, rather than different versions at different times. We will refer to this identity as a _persistent identity_. This issue mainly arises in the context of persistent data structures; when we speak of different versions of the same data structure, we mean that the different versions share a common persistent identity.
_在更新下的唯一同一性不变_。例如，在基于堆栈的解释器中，我们经常非正式地谈论“堆栈”，就好像只有一个堆栈，而不是不同时间的不同版本。我们将把这个身份称为 _持久同一性_。这个问题主要出现在可持久化数据结构的背景下；当我们谈到同一数据结构的不同版本时，我们的意思是不同版本共享一个共同的持久同一性。
Roughly speaking, abstractions correspond to signatures in Standard ML, implementations to structures or functors, and objects or versions to values. There is no good analogue for persistent identities in Standard ML.$^2
粗略地说，抽象概念对应于 Standard ML 中的 signatures，实现对应于 structures 或 functors，对象或版本对应于 values。在 Standard ML 中，没有好的持久同一性的对应。^2
The term operation is similarly overloaded, meaning both the functions supplied by an abstract data type and applications of those functions. We reserve the term operation for the latter meaning, and use the terms operator or function for the former.
$^2$ 非持久化数据结构的持久同一性可以具体化为引用，但这不足以对可持久化数据结构的持久同一性进行建模。
## 1.6 概述（Overview）
This thesis is structured in two parts. The first part (Chapters 2 - 4) concerns algorithmic aspects of lazy evaluation. Chapter 2 sets the stage by briefly reviewing the basic concepts of lazy evaluation and introducing $\text{\textdollar}$-notation.
论文由两部分构成。第一部分（第 2 到 4 章）与懒惰求值的算法方面有关。第 2 章通过简要回顾懒惰求值的基本概念并引入 $\text{\textdollar}$ 表示法来奠定基础。
Chapter 3 is the foundation upon which the rest of the thesis is built. It describes the mediating role lazy evaluation plays in combining amortization and persistence, and gives two methods for analyzing the amortized cost of data structures implemented with lazy evaluation.
第 3 章是论文其余部分的基础。描述了懒惰求值在结合均摊和可持久化中所起的中间作用，并给出了两种分析用懒惰求值实现的数据结构均摊成本的方法。
Chapter 4 illustrates the power of combining strict and lazy evaluation in a single language. It describes how one can often derive a worst-case data structure from an amortized data structure by systematically scheduling the premature execution of lazy components.
第 4 章阐述了在一种语言中结合严格求值和懒惰求值的好处。它描述了如何通过系统地调度懒惰部分的延迟执行从均摊数据结构产生最坏情况数据结构。
The second part of the thesis (Chapters 5 - 8) concerns the design of functional data structures. Rather than cataloguing efficient data structures for every purpose (a hopeless task!), we instead concentrate on a handful of general techniques for designing efficient functional data structures and illustrate each technique with one or more implementations of fundamental abstractions such as priority queues, random-access structures, and various flavors of sequences.
论文的第二部分（第 5 到 8 章）涉及函数式数据结构的设计。我们没有为每一个目的对高效的数据结构进行编写（一项没有希望的任务！），而是专注于设计高效函数式数据结构的少数通用技术，并用一个或多个基本指令的实现来说明每种技术，如优先级队列、随机访问结构和各种类型的序列。
Chapter 5 describes _lazy rebuilding_, a lazy variant of _global rebuilding_ [Ove83]. Lazy rebuilding is significantly simpler than global rebuilding, but yields amortized rather than worst-case bounds. By combining lazy rebuilding with the scheduling techniques of Chapter 4, the worst-case bounds can be recovered.
第 5 章描述了 _懒惰重构_，这是 _全局重构_ [Ove83] 的一个懒惰变体。懒惰重构比全局重构简单得多，但产生了均摊下界，而非最坏情况下界。通过将懒惰重构与第 4 章的调度技术相结合，可以恢复最坏情况下界。
Chapter 6 explores _numerical representations_, implementations designed in analogy to representations of numbers (typically binary numbers). In this model, designing efficient insertion and deletion routines corresponds to choosing variants of binary numbers in which adding or subtracting one take constant time.
第 6 章探讨了 _数值表示_，这些实现类似于数字表示（通常是二进制数字）。在这个模型中，设计有效的插入和删除程序对应于二进制数的变体的选择，其中加一或减一需要常数时间。
Chapter 7 examines _data-structural bootstrapping_ [Buc93]. Data-structural bootstrapping comes in two flavors: structural decomposition, in which unbounded solutions are bootstrapped from bounded solutions, and structural abstraction, in which efficient solutions are bootstrapped from inefficient solutions.
第 7 章研究了 _数据结构自举_。数据结构自举有两种形式：结构分解和结构抽象，前者是从有界解中自举无界解，后者是从低效解中自举高效解。
Chapter 8 describes _implicit recursive slowdown_, a lazy variant of the recursive-slowdown technique of Kaplan and Tarjan [KT95]. As with lazy rebuilding, implicit recursive slowdown is significantly simpler than recursive slowdown, but yields amortized rather than worst-case bounds. Again, we can recover the worst-case bounds using scheduling.
第 8 章描述了 _隐式递归下降_，这是 Kaplan 和 Tarjan [KT95] 的递归下降技术的一个懒惰变体。与懒惰重建一样，隐式递归下降比递归下降简单得多，但产生均摊下界，而非最坏情况下界。同样，我们可以使用调度来恢复到最坏情况下的界限。
Finally, Chapter 9 concludes by summarizing the implications of this work on functional programming, on persistent data structures, and on programming language design, and by describing some of the open problems related to this thesis.
最后，第 9 章总结了这项工作对函数式编程、可持久化数据结构和编程语言设计的影响，并描述了与本文相关的一些悬而未决的问题。
# 2 懒惰求值与 $\text{\textdollar}$ 记号
Lazy evaluation is an evaluation strategy employed by many purely functional programming languages, such as Haskell [H$^+$92]. This strategy has two essential properties. First, the evaluation of a given expression is delayed, or _suspended_, until its result is needed. Second, the first time a suspended expression is evaluated, the result is _memoized_ (i.e., cached) so that the next time it is needed, it can be looked up rather than recomputed.
懒惰求值是许多纯函数式编程语言所采用的一种求值策略，如 Haskell [H$^+$92]。这种策略有两个基本特性。首先，对给定表达式的求值被延迟或 _挂起_，直到需要它的结果。第二，第一次计算挂起的表达式时，会对结果进行 _记忆化_（即缓存），以便下次需要它时，可以查找它，而不是重新计算。
Supporting lazy evaluation in a strict language such as Standard ML requires two primitives: one to suspend the evaluation of an expression and one to resume the evaluation of a suspended expression (and memoize the result). These primitives are often called $delay$ and $force$. For example, Standard ML of New Jersey offers the following primitives for lazy evaluation:
在 Standard ML 等严格语言中支持懒惰求值需要两个 primitives：一个用于暂停对表达式的求值，另一个用于恢复对暂停的表达式的求值（并记忆化结果）。这些 primitives 通常被称为 $delay$ 和 $force$。例如，New Jersey 的 Standard ML 为惰性求值提供了以下 primitives：
$\textbf{type }\alpha\text{ susp}\textbf{val }\text{delay}:\text{(unit}\to\alpha\text)\to\alpha\text{ susp}\textbf{val }\text{force}:\alpha\text{ susp}\to\alpha
These primitives are sufficient to encode all the algorithms in this thesis. However, programming with these primitives can be rather inconvenient. For instance, to suspend the evaluation of some expression e, one writes delay (fn () to e ). Depending on the use of whitespace, this introduces an overhead of 13-17 characters! Although acceptable when only a few expressions are to be suspended, this overhead quickly becomes intolerable when many expressions must be delayed.
To make suspending an expression as syntactically lightweight as possible, we instead use \text{\textdollar}-notation — to suspend the evaluation of some expression e, we simply write \text{\textdollar}e. \text{\textdollar}e is called a suspension and has type \tau\ susp, where \tau is the type of e. The scope of the \text{\textdollar} operator extends as far to the right as possible. Thus, for example, \text{\textdollar}f\ x parses as \text{\textdollar}(f\ x) rather than (\text{\textdollar}f)\ x and \text{\textdollar}x+y parses as \text{\textdollar}(x+y) rather than (\text{\textdollar}x)+y. Note that \text{\textdollar}e is itself an expression and can be suspended by writing \text{\textdollar}\text{\textdollar}e, yielding a nested suspension of type \tau\ susp\ susp.
If s is a suspension of type \tau\ susp, then force\ s evaluates and memoizes the contents of s and returns the resulting value of type \tau. However, explicitly forcing a suspension with a force operation can also be inconvenient. In particular, it often interacts poorly with pattern matching, requiring a single case expression to be broken into two or more nested case expressions, interspersed with force operations. To avoid this problem, we integrate \text{\textdollar}-notation with pattern matching. Matching a suspension against a pattern of the form \text{\textdollar}p first forces the suspension and then matches the result against p. At times, an explicit force operator is still useful. However, it can now be defined in terms of \text{\textdollar} patterns.
如果 s 是一个类型为 \tau\ susp 的挂起，那么 force\ s 求值并记忆化 s 的内容，然后返回类型为 \tau 的结果。但是，带有 force 操作的显式强制求值一个挂起可能也不方便。特别地，它经常与模式匹配相互作用，
\textbf{fun}\ \text{force}(\text{\textdollar}x)=x
To compare the two notations, consider the standard take function, which extracts the first n elements of a stream. Streams are defined as follows:
为了比较这两种记号，考虑这个标准的 take 函数，提取一个流（stream）的前 n 个元素。流定义如下：
\textbf{datatype }\alpha\text{ StreamCell}=\text{Nil}\mid\text{Cons}\textbf{ of }\alpha\times\alpha\text{ Stream}\textbf{withtype }\alpha\text{ Stream}=\alpha\text{ StreamCell susp}
However, this third implementation is not equivalent to the first two. In particular, it forces its second argument when take is applied, rather than when the resulting stream is forced.
但是，第三种实现方式于前两种并不等价。特别的，当 take 被应用时，它强制求值它的第二个参数，而不是等待结果流被强制求值。
The syntax and semantics of \text{\textdollar}-notation are formally defined in Appendix A.
## 2.1 流（Streams）
As an extended example of lazy evaluation and $\text{\textdollar}$-notation in Standard ML, we next develop a small streams package. These streams will also be used by several of the data structures in subsequent chapters.
作为 Standard ML 中懒惰求值和 $\text{\textdollar}$ 表示法的扩展示例，我们接下来开发一个小型的流的包（package）。这些流也将被后续章节中的几个数据结构所使用。
Streams (also known as lazy lists) are very similar to ordinary lists, except that every cell is systematically suspended. The type of streams is
流（也被称为懒惰列表）与普通的列表很相似，除了每个单元都被系统地（systematically）挂起。流的类型是
$\textbf{datatype }\alpha\text{ StreamCell}=\text{Nil }|\text{ Cons}\textbf{ of }\alpha\times\alpha\text{ Stream}\textbf{withtype }\alpha\text{ Stream}=\alpha\text{ StreamCell susp}
A simple stream containing the elements 1, 2, and 3 could be written
It is illuminating to contrast streams with simple suspended lists of type \alpha\ list\ susp. The computations represented by the latter type are inherently monolithic — once begun by forcing the suspended list, they run to completion. The computations represented by streams, on the other hand, are often incremental — forcing a stream executes only enough of the computation to produce the outermost cell and suspends the rest. This behavior is common among datatypes such as streams that contain nested suspensions.
To see this difference in behavior more clearly, consider the append function, written s+\!\!\!+\ t. On suspended lists, this function might be written
Once begun, this function forces both its arguments and then appends the two lists, producing the entire result. Hence, this function is monolithic. On streams, the append function is written
Once begun, this function forces the first cell of s (by matching against a \text{\textdollar} pattern). If this cell is Nil, then the first cell of the result is the first cell of t, so the function forces t. Otherwise, the function constructs the first cell of the result from the first element of s and — this is the key point — the suspension that will eventually calculate the rest of the appended list. Hence, this function is incremental. The take function described earlier is similarly incremental.
一旦开始，此函数将强制求值 s 的第一个单元（通过 \text{\textdollar} 模式匹配）。如果这个单元是 Nil，那么结果的第一个单元是 t 的第一个单元，因此函数强制求值 t。否则，该函数将从 s 的第一个元素构造结果的第一个单元和 — 这是关键点 — 计算追加列表的其余部分的挂起。因此，这个函数是增量的。前面描述的 take 函数也是类似的增量的函数。
However, consider the function to drop the first n elements of a stream.
但是，考虑这个扔掉一个流前 n 个元素的函数。
2.2 历史记号（Historical Notes）
3 借助懒惰求值的均摊与可持久化（Amortization and Persistence via Lazy Evaluation）
3.1 传统可持久化（Traditional Amortization）
3.1.1 例子：队列（Example: Queues）
3.2 可持久化：多重未来的问题（Persistence: The Problem of Multiple Futures）
3.2.1 跟踪执行和逻辑时间（Execution Traces and Logical Time）
3.3 调和均摊与可持久化（Reconciling Amortization and Persistence）
3.3.1 懒惰求值的地位（The Role of Lazy Evaluation）
3.3.2 分析懒惰数据结构的框架（A Framework for Analyzing Lazy Data Structures）
3.4 银行家法（The Banker's Method）
3.4.1 证明银行家法（Justifying the Banker's Method）
3.4.2 例子：队列（Example: Queues）
3.5 物理学家法（The Physicist's Method）
3.5.1 例子：队列（Example: Queues）
3.5.2 例子：使用共享进行自下而上的归并排序（Example: Bottom-Up Mergesort with Sharing）
3.6 相关工作（Related Work）
消除均摊（Eliminating Amortization）
4.1 调度（Scheduling）
4.2 实时队列（Real-Time Queues）
4.3 使用共享进行自下而上的归并排序（Bottom-Up Mergesort with Sharing）
4.4 相关工作（Related Work）
懒惰重建（Lazy Rebuilding）
5.1 批量重建（Batched Rebuilding）
5.2 全局重建（Global Rebuilding）
5.3 懒惰重建（Lazy Rebuilding）
5.4 双端队列（Double-Ended Queues）
5.4.1 输出受限双端队列（Output-restricted Deques）
5.4.2 银行家的双端队列（Banker's Deques）
5.4.3 实时双端队列（Real-time Deques）
5.5 相关工作（Related Work）
6 数值表示（Numerical Representations）
6.1 按位计数制（Positional Number Systems）
6.2 二进制表示（Binary Representations）
6.2.1 二进制随机访问列表（Binary Random-Access Lists）
6.2.2 二项堆（Binomial Heaps）
6.3 线段化二进制数（Segmented Binary Numbers）
6.3.1 线段化二进制随机访问列表与二项堆（Segmented Binomial Random-Access Lists and Heaps）
6.4 斜二进制数（Skew Binary Numbers）
6.4.1 斜二进制随机访问列表（Skew Binary Random-Access Lists）
6.4.2 斜二项堆（Skew Binomial Heaps）
6.5 讨论（Discussion）
6.6 相关工作（Related Work）
7 数据结构自举（Data-Structural Bootstrapping）
7.1 结构分解（Structural Decomposition）
7.1.1 非一致递归与 Standard ML（Non-Uniform Recursion and Standard ML）
7.1.2 再探队列（Queues Revisited）
7.2 结构抽象（Structural Abstraction）
7.2.1 高效连接的列表（Lists With Efficient Catenation）
7.2.2 高效合并的堆（Heaps With Efficient Merging）
7.3 相关工作（Related Work）
8 隐式递归下降（Implicit Recursive Slowdown）
8.1 递归下降（Implicit Recursive Slowdown）
8.2 隐式递归下降（Implicit Recursive Slowdown）
8.3 支持递减函数（Supporting a Decrement Function）
8.4 队列与双向队列（Queues and Deques）
8.5 可连接的双端队列（Catenable Double-Ended Queues）
8.6 相关工作（Related Work）
9 结论
9.1 函数式编程（Functional Programming）
9.2 可持久化数据结构（Persistent Data Structures）
9.3 编程语言设计（Programming Language Design）
9.4 悬而未决的问题（Open Problems）
A Standard ML 中懒惰求值的定义（The Definition of Lazy Evaluation in Standard ML）
The syntax and semantics of Standard ML are formally specified in The Definition of Standard ML [MTH90]. This appendix extends the Definition with the syntax and semantics of the lazy evaluation primitives (\text\textdollar-notation) described in Chapter 2. This appendix is designed to be read in conjunction with the Definition; it describes only the relevant changes and additions.
Standard ML 的语法和语义在 The Definition of Standard ML [MTH90] 中有正式规定。本附录使用第 2 章中描述的懒惰求值 primitives（\text\textdollar-符号）的语法和语义扩展了定义。本附录应与定义一并阅读；它仅描述了相关的更改和添加。
Paragraph headers such as [2.8 Grammar (8,9)] refer to sections within the Definition. The numbers in parentheses specify the relevant pages.
段落标题如 [2.8 语法 (8,9)] 是指定义中的章节。括号中的数字表示相关页面。
A.1 语法 Syntax
[2.1 Reserved Words (3)]\text{\textdollar} is a reserved word and may not be used as an identifier.
[2.1 保留字 (3)]\text{\textdollar} 是一个保留字且不能用作标识符。
[2.8 Grammar (8,9)] Add the following productions for expressions and patterns.
[2.8 语法 (8,9)] 向表达式与模式中加入下列产生式。
exp::=\text\textdollar exppat::=\text\textdollar pat
[Appendix B: Full Grammar (71-73)] Add the following productions for expressions and patterns.
[附录 B：完整语法 (71-73)] 向表达式与模式中加入下列产生式。
exp::=\text\textdollar exppat::=\text\textdollar pat
这些产生式的优先级低于任何其它形式（即，在列表中最后出现）。
A.2 静态语义（Static Semantics）
[4.4 Types and Type functions (18)]\taususp does not admit equality.
[4.4 类型与类型函数 (18)]\taususp 不适用等号运算符。
Remark: This is an arbitrary choice. Allowing an equality operator on suspensions that automatically forces the suspensions and compares the results would also be reasonable, but would be moderately complicated.\quad\diamond
[4.7 Non-expansive Expressions (20)]\text\textdollar expressions are non-expansive.\quad\diamond
[4.7 非扩展性表达式 (20)]\text\textdollar 表达式是非扩展的。
Remark: The dynamic evaluation of a \text\textdollar expression may in fact extend the domain of memory, but, for typechecking purposes, suspensions should be more like functions than references. \quad\diamond