计算思维以设计问题的抽象为中心，这样就可以用计算步骤和高效算法来解决问题，这个概念不仅服务于计算机科学(CS)，而且越来越多地服务于科学和日常生活。珍妮特·温发表了她关于计算思维的影响深远的论文后，<年代up>50对计算思维的讨论在规模上大大扩大，包括诸如建模自然过程作为信息处理的主题。<年代up>18
计算思维的核心是抽象，这是本文的主要主题。虽然抽象一直是计算机科学的重要组成部分，但现代对计算思维的强调强调了它们在向广泛受众教授CS时的重要性。
抽象在几乎每一个科学领域都起着重要的作用。然而，在计算机科学中，抽象并不依附于物理现实，因此我们发现有用的抽象在该领域中随处可见。例如，我们将在第四节中遇到物理学的一个重要抽象:量子力学。有一种衍生的抽象计算方法叫做量子电路，它从物理概念开始，但已经产生了模拟量子电路的编程语言，以及利用量子电路独特功能的理论算法，有一天可能会在大规模机器上实现。
计算机科学中的每一个抽象都包含以下内容:
注意，正是第二部分将计算机科学中的抽象与其他领域中的抽象区分开来。
因此，每种抽象都允许我们设计算法以特定的方式操作数据。我们想要设计“好的”抽象，其中抽象的优点是多维的。使用抽象来设计解决方案的容易程度是一个重要的度量标准。例如，我们将在3.1节中讨论关系模型如何导致数据库使用的激增。还有其他性能指标，例如运行时间，在串行或并行的机器上，产生的算法。同样地，我们喜欢易于实现的抽象，并且易于创建重要问题的解决方案。最后，一些抽象提供了一种简单的方法来度量算法的效率(正如我们可以在传统编程语言中找到程序运行时间的“big-oh”估计值)，而其他抽象则要求我们在讨论算法效率之前在较低的级别指定一个实现，甚至是近似的实现。
1.1.编译。有些抽象处于足够高的级别，它们不能提供有意义的性能度量。因此，高级抽象的操作可能需要在较低的级别上实现——一个更接近于我们所认为的程序执行的级别。实际上，可能会有几个抽象级别逐步接近机器本身。书中建议的那样<一个href＝"https://dl.acm.org/cms/attachment/d8875c14-d9d5-4610-aafe-a15b804b86f9/f1.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=1021,height=632'); return false;">图1在这种情况下，高级抽象(抽象1)的操作可以由低级抽象(抽象2)实现，而低级抽象又可以由更低级的抽象实现(没有显示)。从高级程序到机器指令，到物理硬件，到逻辑门，到晶体管，最后到电子，抽象的层次非常有趣。然而，我们只将注意力集中在较高的层次上。
图1。抽象和算法层。
使用抽象1操作的算法被编译成低级抽象2中的算法。在本文中，我们将使用这个术语编译器在非常普遍的意义上——不仅仅是编程语言的传统编译器，就像“龙书”的重点一样<年代up>9但是任何把一个抽象的程序变成第二个抽象的程序的算法，假设是更低级的抽象。因此，在某些情况下，编译过程是直接的，较高层的每个操作都被较低层的一个或多个特定操作所取代。在其他情况下，特别是从传统语言(如C)编译到机器级语言时，翻译算法非常复杂。在其他情况下，例如当高级抽象使用强大的代数操作(如线性代数或关系代数)时，优化是至关重要的，因为原始编译通常会导致比优化编译生成的算法花费更多数量级的时间。
抽象2可能与机器足够接近，因此它具有有意义的性能度量。如果是这样，抽象1可以继承这些度量，为用抽象1编写的算法提供质量的概念。然而，我们应该记住，高级抽象通常可以在几个不同的低级抽象中实现。这些抽象中的每一个都可能提供完全不同的运行时间或其他度量的概念，因此在高级别上意味着不同的算法优秀性概念。
例1.1。对于一个许多读者应该很熟悉的例子，我们将在第2.1节详细讨论，抽象1可以是正则表达式(REs)，它的数据模型是字符串集，其“编程语言”是正则表达式，可以由三个操作组成:联合、连接和Kleene *。我们可以通过将正则表达式转换为确定性有限自动机(DFA)来实现正则表达式，从而扮演抽象2的角色。正则抽象中的算法就是正则本身。该算法可以被“编译”成一个DFA，然后用某种传统的编程语言“编译”(即模拟)DFA，后者又被编译成机器的语言。在合理的仿真条件下，DFA的运行时间为O(1）每个输入符号。因此，原始正则的运行时间也是O(1）每个输入符号，即使这一点远不明显，只考虑REs的定义。
1.2.抽象的分类法。我们可以确定至少四种不同的抽象类型，它们根据其预期目的进行区分。在构成本文主体的讨论中，我们将给出每种方法的示例并探讨它们的相互作用。
1.2.1.基本抽象。与所有抽象一样，这些抽象由数据模型和操作组成。这些抽象通常被认为是抽象数据类型31，<一个href＝"#R46">46在面向对象的编程语言中实现。然而，基本抽象没有操作的特定实现，也没有表示其数据的特定数据结构。人们还可以将这些抽象类比为接口在Java中,<年代up>48但与接口不同的是，这些抽象为它们的操作提供了预期的含义，而不仅仅是操作的名称。
研究基本抽象实际上有两个不同的目的。在某些情况下，它们代表了一些共同的操作，这些操作本身就值得研究，并且有各种实现方法。例如，我们将在第1.4节讨论字典(包含插入、删除和查找操作的集合)。这种类型的其他例子包括栈、队列、优先队列和我们在Aho等人中编目的许多其他抽象。<年代up>7以及阿霍和厄尔曼。<年代up>10
其他抽象足够广泛，可以支持应用程序的大型组件。熟悉的例子包括树和各种类型的图——例如，有向、无向、有标记和无标记。我们将在2.3节中讨论一个重要的示例—流程图。
这些抽象具有大量的操作集，可以以各种方式进行组合。然而，操作不是这样的turing(能够描述图灵机可以执行的任何计算)。相反，它们被假设嵌入到图灵完备语言中，在图灵完备语言中使用该模型构建算法。例如，在一个图形抽象中，我们可能有一个诸如“查找相邻节点”的操作。在这个抽象之外，我们可以假设存在一种允许在所有相邻节点上迭代的编程语言。这个操作的实现和图形本身的表示没有指定，因此我们没有具体的运行时间概念。我们可以将这些抽象与面向对象编程语言中的典型类及其方法进行类比。区别在于类的方法在底层编程语言中具有特定的实现。我们同样可以把诸如编程语言库或TeX包之类的东西看作是这种类型的抽象。
1.2.2.抽象的实现。这些表示实现的方法，大概是一个或多个基本抽象的实现。它们本身不是图灵完备语言，通常可以编译成几种不同的机器模型——例如，串行或并行机器，或者假设主内存或辅助内存的模型。每一个机器模型都提供了一个运行时间的概念，可以将其转换为抽象实现的运行时间，然后转换为受支持的基本抽象的运行时间。例如，我们将在第1.6节中讨论哈希表作为字典的实现。许多其他数据结构也属于这一类，例如各种类型的链表或树(参见第1.5和1.7.2节)。在这一组中还有自动机，如确定性或非确定性有限自动机(见第2.1.1节和2.1.3节)和移减解析器(见第2.2.1节)。
1.2.3.声明抽象。抽象最重要的用途之一是培养一种编程风格，在这种风格中，您只说想要做什么，而不说如何做。因此，我们发现了许多不同的抽象，它们由一个数据模型和一种比传统语言更高层次的编程语言组成;通常这些语言是某种代数。例子包括正则表达式(将在第2.1节中讨论)和关系代数(将在第3节中提到)。上下文无关语法(第2.2节)是这种抽象类型的另一个例子，尽管不是严格意义上的代数。
这些抽象的特殊之处在于，它们的编译需要进行严格的优化。与传统语言的优化不同(在传统语言中，您很乐意将一台机器上的运行时间提高两倍)，对于这些抽象来说，好的和坏的实现的运行时间之间可能存在数量级的差异。另一个特点是声明抽象的编程语言不是图灵完备的。任何图灵完备语言的不可测性属性都将排除一个优化器的存在，该优化器通常有效地处理程序想要做的事情，而不被告知如何做。
1.2.4.计算抽象。与抽象实现相比，这些抽象接近于物理实现的机器。也就是说，没有人会只为了实现抽象实现而构建一台机器，但人们通常会实现计算抽象或易于转换的东西。因此，计算抽象提供了有意义的性能度量，即使它们不是100%准确。
您可能熟悉其中的一些抽象，因为它们包括所有常见的编程语言以及机器指令集。这种类型的其他抽象更具理论性，例如随机访问机(RAM)模型<年代up>19或并行ram (PRAM)模型。<年代up>20.这里，我们将在第1.7节中讨论一个强调二次存储器作用的常规机器模型。我们还将讨论并行计算的抽象:3.5节中的大容量同步和3.6节中的MapReduce。
虽然许多计算抽象与传统计算机相关，但也有一些例外。的图灵机<年代up>43是一个，还有一些甚至不是图灵完备的，但在计算机科学中起着重要作用。例如，继Claude Shannon的MS论文之后，布尔电路和布尔代数是发展中的计算科学中最早使用的抽象概念。我们在第4节中讨论的量子电路抽象是最新的。
1.3.一些分类意见。我们并不声称这种分类法是详尽无遗的，也不认为它是最好的分类法。读者可以对这个结构进行补充或反思。然而，我们确实相信这个组织反映了计算机科学领域的四个最重要的发展。从某种意义上说，基本抽象是由应用程序的需求决定的。另一方面，抽象实现代表了计算机科学家对支持基本抽象的响应，它们代表了许多关于数据结构的早期思考。声明性抽象代表了计算机科学的趋势，即通过支持将大型、复杂的操作封装为单个步骤的符号来逐步简化编程。计算抽象代表了不断变化的硬件技术对我们计算方式的影响。
1.4.对抽象空间的探索。为了获得抽象链的本质及其关系的一些观点，我们将看一个基本抽象的常见例子:字典。然后，我们将探究低于该级别的实现级别及其对运行时评估的影响。
例1.2。的字典是抽象的一个常见示例，它具有许多可选实现，并说明了在将高级抽象编译为低级抽象时突然出现的一些问题。字典的数据模型由以下部分组成：
字典的“编程语言”由以下三个操作的直线序列组成:
插入(x)
删除(x)
查找(x)
真正的
例如，字典可以用来描述编译器中符号表的行为。U是编程语言可能的标识符集合。当编译器扫描程序时，S将是一组标识符，在程序的每个点都定义了含义。但是，对于符号表，您需要将数据附加到每个标识符—例如，它定义的数据类型和它出现在其中的嵌套块的级别(因此我们可以区分具有相同名称的标识符)。当编译器找到一个声明时，它将声明的标识符插入到集合s中。当它到达过程或函数的末尾时，它删除与该程序块相关联的标识符。当在程序中使用标识符时，编译器查找该标识符并检索其类型和其他必要信息。
请注意，字典的编程语言相当简单，它当然没有图灵机的功能。此外，这里没有算法设计的真正概念，因为“程序”只是一些其他进程正在做什么的反映——例如，示例1.2中提到的符号表操作。同样，也没有真正的运行时间概念，因为不清楚每个操作需要多长时间。我们可以定义每个操作花费单位时间，但是由于我们不能控制“程序”的长度，所以这个运行时间没有任何意义。
1.5.字典的实现。可以使用许多不同的抽象实现来实现字典。即使对于最高效的列表实现，链表也可以发挥作用，尽管它们不能提供良好的运行时间。
例1.3。链表是一种抽象的实现，大家应该都很熟悉。其数据模型由以下部分组成:
我们假定读者熟悉所允许的典型操作，例如创建单元格或标题，从列表中插入和删除单元格，以及返回包含在指定单元格中的数据。可以通过创建集合s中所有元素的链表来实现字典。将三个字典操作编译为列表操作非常简单。
如果我们假设链表是在计算机的RAM模型中实现的，我们就有了一个实际的运行时间概念。我们可以为列表单元格上的每一个基本操作分配一个时间单位，因为我们知道在RAM上，每一个操作都将花费恒定的时间，与集合s的大小无关。这一观察使我们可以将RAM的运行时间概念提升到链表的运行时间概念，然后提升到字典的级别。不幸的是，消息并不乐观。平均来说，我们必须至少从列表的一半向下，通常一直到最后，才能实现任何字典操作。因此，单个字典操作的运行时间与当时集合S的大小成正比。
另一个很容易理解的实现字典的抽象类使用搜索树。当三种字典操作的算法保持树的平衡时——例如，AVL树<年代up>2或“红-黑”树<年代up>22-每个操作的运行时间以集合的大小为对数年代在手术的时候。但通常首选的实现字典的抽象是哈希表，<年代up>36我们接下来会讨论这个问题。
1.6.哈希的抽象。Hash的数据模型包括以下内容:
通常的操作是计算h（x) (x是U-插入、删除或查找x在编号的桶里h（x)．例如，将标记哈希表的插入操作h-insert（x，b）b＝h（x)．哈希的程序由交替地计算一些组成h（x)，然后做三个操作中的一个x和斗h（x)．
h-insert
将字典程序编译为哈希程序很简单。例如，字典操作插入(x)是翻译成B：＝h(x);h-insert (x, b)。
B：＝h(x);h-insert (x, b)。
哈希距离机器不够近，我们不能直接使用它来确定运行时间。一个问题是哈希非常不寻常，在最坏情况下，集合中的所有元素年代最后都在同一个桶里，这比平均情况要糟糕得多，当我们对所有可能的哈希函数求平均值时。为了简单起见，我们应该正确地假设，在平均情况下，几乎所有的桶都包含接近平均数量的元素——即，年代/B。但是，即使我们同意只讨论平均情况，我们仍然不知道对一个元素和一个桶的每次操作需要多长时间。
本质上，每个桶本身就是一个小字典，所以我们必须决定如何实现它的操作。如果尺寸年代仍然是B，我们可以使用bucket的链表实现，并期望每个操作占用O(1)在RAM或真实机器上的平均时间。然而,如果年代要比B，则表示桶的列表的平均长度为O（年代/B)．这还是比O（年代)每个操作，就像链表的情况一样。然而,当年代是如此之大，以致于它无法装入主存，RAM模型不再适用，我们需要完全考虑另一种计算抽象。
1.7.二级存储抽象。作为RAM计算抽象的替代方案，任何数据都可以访问O(1)时间上，我们可以引入多个层次的局部性访问。我们将只讨论具有基于磁盘的辅助内存的抽象，其中大块数据(如64KB)作为一个整体在磁盘和主内存之间移动。如果要读或写数据，就必须在主存中。在主内存和辅助内存之间移动一个块的成本与在主内存中对数据本身进行典型操作的成本相比非常大。因此，可以合理地将这个新模型中的运行时间简单地视为磁盘I/ os的数量——也就是说，一个块从辅助内存移动到主内存的次数或从辅助内存移动到主内存的次数。<年代up>一个
在底层计算机的辅助存储模型中，实现哈希表的最佳方法与使用RAM模型的首选方法有些不同。特别是，每个桶将由一个或多个完整的磁盘块组成。为了利用局部性，我们希望典型的存储块由尽可能少的磁盘块组成，但我们希望使这些磁盘块尽可能满。因此，假设主存能够保存米元素的通用集，而磁盘块持有P这样的元素。然后我们想要的B，桶的数量，要B＝M / P因此，我们可以为主内存中的每个桶保留一个磁盘块，而这个磁盘块很可能接近满。
作为集合的大小年代增长时，我们使用一个磁盘块链表来表示每个桶，只有第一个桶在主存中。最坏的情况下，这三个字典操作需要我们检查单个桶中的所有磁盘块。因此，平均而言，我们期望每个操作的磁盘I/ o数为O（年代/英国石油公司)，因为元素年代将大致平均分配给B桶，桶的元素将被打包P到磁盘块。自B＝M / P，每个操作的运行时间为O年代/米)．
1.7.1.通过哈希的数据库操作。这个运行时间令人印象深刻吗?不是真的。如果我们使用链表实现，但允许链表随机增长到磁盘上，我们可以使用米桶，平均桶将由一个长度的链表表示年代/M。即使列表中的每个单元位于不同的磁盘块中，我们仍然只需要O（年代/米)每个字典操作的磁盘I/ o。但是，在数据库管理世界中有一类重要的操作，其中磁盘块模型产生了重要的效率。在这些操作中，其中哈希连接<年代up>25是不是一个主要的例子，我们只需要分一组年代放入桶中，同时既不删除也不查找元素。
例1.4。让我们考虑一个比散列连接更简单的问题，但它在基于磁盘的抽象中有类似的解决方案。假设我们有一个S对集合（x，y)，我们想通过计算一个表来对x进行聚合每个x给出相关y的和。我们假设S太大了，它不适合放在主存中。如上所述，我们将使用B = M/P桶，但我们的哈希函数只是x的函数，而不是y的函数。然后我们将S中的每个成员插入到适当的桶中。最初，主存中每个桶的块都是空的。当它被填满时，我们将它移动到磁盘，并在主内存中为该桶创建一个新的空块。新的块链接到我们刚刚移动到磁盘的块，而磁盘又链接到该桶的前一个块(如果有的话)。S的整个分区所需的磁盘I/ o数将近似于容纳S所需的块数，即，年代/P.这是处理该大小的磁盘集所需的最小磁盘I/ o数。
然后，我们一次处理一个桶。假设存储桶本身足够小，可以放入主内存中，年代≤米2/P- - - - - -我们只需要将每个磁盘块移到主内存中一次。因为一个桶要么包含所有的对，要么不包含任何对（x, y）对于给定的x，我们可以根据x的值依次对每个bucket排序，从而计算哈希到该bucket的每个x的y的和。因为在这个模型中，我们只计算磁盘I/O，而实际上，对一个桶进行排序的时间往往小于将其块移进或移出主存的成本，这个算法的运行时间为O（年代/P）磁盘I/ o是现实的，在一个小的常数因子内，是可以想象的最好的。
1.7.2.b树。二级存储抽象的另一个有趣的结果是，它提供了一种通常比哈希更有效的字典抽象实现。在RAM计算模型中，在实现字典方面，即使平衡搜索树通常也不会被认为比哈希表更有效。但是在二级存储模型中，平衡搜索树的模拟是非常有效的。一个b -树13本质上是一个平衡搜索树，其中树的节点是整个磁盘块。每个叶块在集合的成员的一半和完全满之间年代被代表。此外，每个内部节点至少有半满的值，这些值分隔其子树的内容和指向这些子树的指针。
由于磁盘块很大，每个内部节点都有许多子节点，以至于在实践中，即使非常大的集合也可以存储在三层b树中。而且，至少根节点，也许还有根节点的子节点，都可以存储在主存中。结果是，除去重新平衡树的偶尔磁盘I/ o，每个插入或删除操作只需要2到4个I/ o，查询只需要1到2个I/ o。
回到顶部
现代编译器将翻译过程细化为多个阶段的组合，其中每个阶段将源程序的一种表示转换为另一种语义等价的表示，通常在较低的抽象级别上。编译器中的阶段通常包括词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。所有阶段共享的符号表用于收集源程序中各种构造的信息并使其可用。前四个阶段通常被称为前端的编译器，最后两个后端。
编译器实现的进展涉及到许多重要的抽象。我们将具体讨论三种这样的抽象:正则表达式、与上下文无关的语法和流程图。前两个是带有有趣优化故事的声明抽象。第三个，虽然不是声明性的，但也提出了有趣的实现挑战。
2.1.正则表达式和词法分析。词法分析是编译器的第一个阶段，它将源程序作为字符序列读取，并将其映射为称为标记的符号序列，该符号序列被传递到下一个阶段，即语法分析器。
例2.1。如果源程序包含该语句
华氏度=摄氏* 1.8 + 32
词法分析器可以将此语句映射为七个标记的序列:
<=> <*> <+>
在这里、身份证令牌是用于任何程序变量，还是标识符。运营商= *,而且+是符号本身吗?两个常量变成了符号吗真正的而且int，分别。b
int
编译器构造的一个重大进步是创建词法分析程序生成器-一个像Lex这样的程序<年代up>30.它接受令牌的描述作为输入，并生成一个程序，该程序将源程序分解为令牌，并返回与源程序对应的令牌序列。让Lex成为可能的抽象概念是正则表达式。26正如最初由Kleene定义的那样，我们可以将正则表达式视为一种抽象，其数据模型是某些特定字符字母表(例如，ascii)上的字符串，其编程语言是带有运算符联合、连接和Kleene星号(或“任意数量”的运算符)的代数。我们假设读者熟悉这些操作符及其对字符串集的影响。在实践中，像Lex这样使用正则表达式抽象的系统使用了许多有用的简写，使编写正则表达式更加容易，但不改变可以在此抽象中定义的字符串集。
例2.2。在某些编程语言中作为合法标识符的字符串集可以定义如下:
信= [a-zA-Z] 数字= [0 - 9] Id =字母(字母+数字)*
信= [a-zA-Z]
数字= [0 - 9]
Id =字母(字母+数字)*
在这个简写中，有一个短语像a - z表示与ASCII码之间的单字符字符串的并集一个而且z。的正则表达式信，在原来的三个操作符集合中:
以类似的方式定义数字，然后是标记的字符串集定义为由任意字母后面跟着任意零个或多个字母和/或数字组成的字符串。
2.1.1.在Lex之前:书目搜索。从理论研究中可以很好地理解到，正则表达式抽象可以编译成几种抽象实现之一，如确定性或非确定性有限自动机(分别为NFA和DFA)。然而，当实际问题需要解决时，仍然有一些技术有待发现。贝尔实验室采取了一个有趣的步骤，第一次尝试自动搜索相关文献。他们把整个贝尔实验室图书馆的标题都录了下来，他们还开发了一种软件，可以列出关键词，然后找到带有这些关键词的文档。然而，当给出一长串关键字时，搜索速度很慢，因为每个关键字都要遍历磁带一次。
阿霍和科拉西克的情况有了很大的改善。<年代up>6与单独搜索每个关键字不同，关键字列表被视为包含任何关键字出现的所有字符串集合的正则表达式，即:
注意，点是表示“任何字符”的扩展名。该表达式被转化为确定性有限自动机。这样一来，无论涉及多少关键词，都可以在磁带上进行一次传递。每个标题由有限自动机检查一次，看是否有关键词在其中找到。
2.1.2.词法分析器生成器的设计。本质上，像Lex这样的词法分析器生成器使用与第2.1.1节相同的思想。我们为每个令牌编写正则表达式，然后对这些表达式应用联合运算符。该表达式被转换为一个确定性有限自动机，它被设置为从程序中的某个点开始工作。这个自动机将读取字符，直到找到与令牌匹配的字符串前缀。然后，它从输入中删除读取的字符，将令牌添加到输出流中，并重复此过程。
这里还有一些额外的考虑，因为与关键字不同，令牌之间可能存在一些复杂的交互。例如,而看起来像一个标识符，但它实际上是一个关键字，用于程序中的控制流。因此，当看到这个字符序列时，词法分析器必须返回标记，而不是返回标记。在Lex中，在其输入文件中列出正则表达式的顺序打破了诸如此类的歧义，因此您所要做的就是在标识符之前列出关键字，以确保关键字被这样对待，而不是作为标识符。另一个问题是，一些令牌可能是另一个令牌的前缀。如果输入中的下一个字符是=，则不希望将<识别为标记。相反，我们希望将<=识别为一个标记。为了避免这种错误，词法分析器被设计成只要它所看到的结果被有限自动机接受为合法的标记，它就会继续读取。
而
2.1.3.DFA的惰性评估。还有一种优化可以提高使用正则表达式抽象的算法的运行时间:延迟求值。您可能熟悉将正则表达式转换为确定性有限自动机的标准方法。首先利用McNaughton和Yamada算法将正则表达式转化为非确定性有限自动机。<年代up>34这种转换很简单，它产生的NFA最多为2n表示正则表达式是否具有长度n。当您将NFA转换为DFA时，问题就开始了，这需要Rabin和Scott的子集构造。<年代up>38在最坏的情况下，该结构可以将NFA转换为2n状态转换为具有2的DFA<年代up>2n状态，即使对于相对较短的正则表达式，它也不是真正可用的。在实践中，最糟糕的情况很少发生——例如，为典型编程语言的词法分析而构造的DFA的状态甚至可能不超过其每个令牌的正则表达式长度的和。
然而，在正则表达式的其他应用程序中，可能而且确实会发生接近最坏情况的情况。最早的UNIX命令之一是grep，代表“获取正则表达式并打印”。该命令将接受一个字符串，并确定它是否具有给定正则表达式语言中的子字符串。最简单的实现是将正则表达式转换为NFA，然后再转换为DFA，并让DFA读取字符串。当DFA很大时，将NFA转换为DFA所花的时间要比扫描字符串所花的时间多得多。
然而，当正则表达式只用于扫描字符串一次时，有更有效的方法来实现命令，例如grep．肯·汤普森的第一篇研究论文<年代up>42与将小的NFA转换为大的DFA相比，直接模拟NFA更有效。也就是说，读取字符串的NFA通常在读取每个字符后处于一组状态。因此，只需跟踪每个字符之后的NFA状态，并在读取下一个字符时，从前面的状态集构建该字符上可访问的状态集。
grep
通过将NFA惰性转换为DFA，甚至可以获得更高的效率。也就是说，每次读取输入字符串的一个字符，然后将到目前为止读取的前缀实际生成的NFA状态集制成表格。这些NFA状态集对应于DFA状态，因此我们只构建DFA转换表中处理这个特定输入字符串所需的那部分。如果给定正则表达式的DFA不是太大，那么它的大部分或全部将在我们完成字符串处理之前构造，并且我们可以直接使用DFA，而不是在字符串的每个字符之后构造NFA状态集。但是如果DFA大于字符串，我们就不会构造大部分的DFA，所以我们会得到两种情况的最佳结果。的版本中实现了此改进grep被称为egrep。<年代up>4
egrep。
2.2.上下文无关的语法和解析。编译器的第二阶段是语法分析器或“解析器”，它将词法分析器生成的标记序列映射为树状表示，使标记序列中的语法结构显式显示出来。典型的表示形式是语法树，其中每个内部节点表示某种结构，该节点的子节点表示该结构的组件。
例2.3。例如，语法分析器可能映射令牌序列
A + b * c
中所示的语法树<一个href＝"https://dl.acm.org/cms/attachment/8a7c3e3a-7d16-4e29-a9bd-534cdbdf76ad/f2.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=492,height=429'); return false;">图2．这里，E表示一个表达式。操作数a、b和c本身就是表达式。但是b * c也是一个表达式，由操作符令牌*和两个表达式b和c组成。在根目录中，我们看到了另一个表达式，它使用了操作符+两个操作数表达式，a和b * c。
图2。表达式a + b的语法树<年代up>＊c。
遵守关于……的众多公约之一是很重要的运算符优先级。通常，乘法优先于加法，这就是为什么语法树在添加a之前先用b乘以c，而不是先添加a和b。
对于给定的编程语言，所需的语法树结构通常由声明性抽象定义上下文无关文法(CFG)，我们希望您对这个概念很熟悉。CFG是规则的集合，称为产品它们提供了各种方法，可以从其他语法类别和构造各种语法类别，例如表达式或语句终端，它们是词法分析器生成的标记。例如,如果E表示该语言格式良好的表达式的语法类别，那么我们可能会找到诸如
这意味着构造表达式的一种方法是在两个较小的表达式之间加一个加号。
2.2.1.LR (k)解析。在20世纪60年代，有一系列关于如何从cfg构建高效语法分析器的建议。人们认识到，对于常见的编程语言，可以从左到右进行一次程序扫描，而不回溯，并根据该语言的语法构建语法树，前提是该语法具有某些属性。
有些决定很棘手。例如，在处理表达式时一个+b＊c，只在阅读后一个+b您必须决定是否组合这些表达式一个而且b加上加号，得到一个更大的表达式。如果您向前看一个标记并看到*，您就知道合并是不正确的一个而且b，而是必须进一步进行，最终合并b与c。只有在这一点上，合并才是正确的一个与表达b＊c。
这种语法分析风格被称为shift-reduce解析。您保留了一堆符号，这些符号可以是标记或语法类别。在扫描输入时，每一步都要决定是否转变通过将下一个输入令牌推入堆栈或减少栈顶的符号。当你缩减时，缩减的符号必须是CFG的一些生产的右边。这些符号从堆栈中弹出，并被相同产品的左侧替换。此外，还为产品左侧的符号创建语法树的节点。它的子结点是与刚从堆栈中弹出的符号相对应的树的根。如果从堆栈中弹出一个标记，那么它的树只是一个节点，但如果弹出一个语法类别，那么它的树就是堆栈上之前为该符号构造的任何东西。
在阿霍等人总结了一系列越来越普遍的建议后，<年代up>9唐·克努斯提议LR(k)解析,<年代up>27从本质上讲，哪一种语法适用于最通用的语法类，能够在一次从左到右的输入扫描中正确解析，使用移位-减少范式并查看最多k输入前面的符号。这项工作似乎解决了语法分析器应该如何构造的问题。然而，并不是每一种CFG，甚至不是每一种典型编程语言的CFG都满足成为LR(k)任何语法k。虽然常见的编程语言似乎确实有LR(1)语法——也就是说，只需在输入中使用一个向前看的符号就可以对语法进行shift-reduce解析——但这些语法设计起来相当复杂，而且通常具有比直观需要的语法类别多一个数量级的语法类别。例如，不是针对所有表达式使用一个语法类别，而是针对语言中操作符优先级的每个级别使用一个语法类别，通常有十几个或更多级别。
2.2.2.解析生成器Yacc。因此，在Knuth的论文之后，人们多次尝试寻找使用LR(1)解析方法的方法，但要使其在更简单的cfg上工作。我们的灵感来自于普林斯顿大学的研究生Al Korenjak，他的论文是关于压缩LR(1)解析器的方法。<年代up>28我们突然想到，对于普通语言，可以从不是LR(1)的语法开始，并为该语法构建一个从左到右的移位减少解析器。当语法不是LR(1)时，在某些情况下，语法会告诉我们使用两个不同的结果来减少和转移或减少。但在实际情况下，我们可以通过考虑操作符的优先级并在输入前查找一个令牌来解决这种模糊性。
例2.4。考虑例2.3中建议的情况。处理完+B(输入a)+b * c，栈顶是E+E，其中a和b之前都被简化为表达式。有一个产物E→E+E，所以我们可以化简E+E到E，并构建一个带有标签E和子E的解析树节点+,和e，但事实上*优先于+,我们看到*作为下一个输入符号，告诉我们将*移到堆栈上是正确的。之后，我们将c也移开，并将c简化为表达式E+E * E在堆栈的顶部。我们正确地将前三个符号简化为E，剩下E+现在，正确的做法是将这些符号简化为E，因为输入中什么都没有剩下(或者输入中有不属于表达式的东西，例如语句结束的分号)。通过这种方式，我们将生成中显示的语法树<一个href＝"https://dl.acm.org/cms/attachment/8a7c3e3a-7d16-4e29-a9bd-534cdbdf76ad/f2.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=492,height=429'); return false;">图2．
我们在贝尔实验室的同事Steve Johnson采用了这个想法，实现了一个名为Yacc的解析器生成器。<年代up>8为了帮助解决shift和reduce操作之间的歧义，或者两个不同产品之间的歧义，Yacc使用产品出现的顺序。无论哪个产物最先出现，在两个产物都可以用来减少的情况下都是首选。为了解决shift和reduce之间的冲突，假设在Yacc输入文件中最先出现的操作符具有优先级。<年代up>c
Yacc很快成为实现编译器的必要工具——不仅是传统编程语言的编译器，而且是许多用途更有限的“小语言”的编译器。与Lex一起，Yacc提供了一种简单的方法来试验新语言的语法结构设计。这两种工具经常在学术界的一学期编译器课程中使用，在这些课程中，学生们设计并实现了一种新的特定于领域的编程语言。<年代up>5
2.3.流程图和代码优化。编译器的代码优化阶段采用源程序的中间形式，通常类似于三址代码。在那里，大表达式被分解成简单的步骤，其中(最多)两个操作数应用一个操作符来产生一个结果—例如，a:= b + c。三地址代码使用了其他步骤，例如基于单个值的分支，但是在本文的简短讨论中我们将忽略这些步骤。
代码优化的一个关键抽象是流图。起源于维索茨基和韦格纳<年代up>45对这种抽象算法的科学研究通常被认为是从艾伦的工作开始的。<年代up>11流图的数据模型从有向图开始，其中每个节点表示一个基本块中间代码的一个由三个地址的步骤组成的序列，只能在没有中间分支的情况下执行。关于数据模型还有更多的内容，我们稍后会讲到。使用流图抽象的算法通常旨在收集关于程序的整体信息，并确定何时可能进行某些优化。
例2.5。使用流图抽象我们可以收集的一种有用的信息是实现定义。我们想知道，在中间语言程序的每一点p处，对于该程序的每一个变量X，程序中X最后在哪里被定义。通常情况下，会有几个不同的地方。但是如果只有一个这样的位置，并且这个位置将一个常数c赋给X，那么我们就知道在点p处，X肯定具有c的值。如果在点p处使用X，那么我们可以用c替换X的使用，这通常会导致代码的执行速度比我们必须读取X的值要快。
由于Kildall，有一个优雅的流图抽象。<年代up>24在这个框架中，有一个半格l的值，它是数据模型的一部分，与图本身一起。的两个成员与流图的每个节点相关联l，一个用于节点所代表的三地址码的开始，一个用于结束。这个抽象的操作如下:
刚刚描述的流图抽象允许使用许多不同的算法来求解每个节点的开始和结束的值，给定与每个节点和汇流算子相关的传递函数。大多数方法本质上都是迭代的，慢慢地收敛到正确答案。然而，有许多有趣的变体，通常从时间间隔艾伦的方法<年代up>11这利用了程序的通用结构，其中循环只嵌套到很小的深度。此外，这些算法不仅可以用来求解定义，还可以用于求解对代码优化有用的程序信息的任何类型。我们邀请你去研究阿霍等人的长篇故事。<年代up>9
当我们考虑最大的可用数据集和可用于操作它们的算法时，我们需要几个新的抽象。第1.7节中的二级存储模型很重要，但是还有其他抽象表达了各种形式的并行性和分布式计算。我们将在这里概述最相关的抽象。
3.1.数据的关系模型。开始,关系模型的科德<年代up>15已被证明是处理大规模数据的核心。简单地说，数据被组织为表或关系的集合，其中两个例子在<一个href＝"https://dl.acm.org/cms/attachment/65246690-a341-4e7d-9d6f-2edcb128fd9f/f3.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=1021,height=528'); return false;">图3．左边是一个名为Cities的关系，它有两列:City和State。的模式关系的值是其名称和列名列表—在本例中为Cities (City, State)。关系本身是一组行或元组。例如，关系城市的其中一行是(Toronto, Ontario)。第二种关系叫做“国”;它有名为州、国家和流行(州的人口，以百万计)的列。
图3。两种关系:城市(City, State)和州(State, Country, Pop)。
为关系模型选择编程语言是一个有趣的过程。Codd可以将关系模型视为嵌入在通用语言中的基本抽象，就像树或图一样。关系语言的操作可能是简单的导航步骤，例如“在给定的行和列中查找值”或“给定的行，查找下面的行”。事实上，早期的数据库抽象，如网络和分层模型，正是如此。幸运的是，Codd的观点是声明性抽象，随着编程语言的发展，这种选择一直被遵循，它有助于使关系模型成为数据库管理的主要方法。
在最初的公式中，<年代up>16关系模型的编程语言被认为是非递归的一阶逻辑，或者等效地，是五种代数操作的集合:联合、集差、选择、投影和连接，称为关系代数。后三个可能不熟悉，但定义如下:
例3.1。假设我们把城市和州这两个关系从<一个href＝"https://dl.acm.org/cms/attachment/65246690-a341-4e7d-9d6f-2edcb128fd9f/f3.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=1021,height=528'); return false;">图3使用两个关系的State列必须一致的条件。原则上，我们必须考虑所有36对行，每对行来自一个关系。但是，每一行的Cities都将只满足具有相同列State值的一行State的条件。例如，城市的第一行，
(多伦多,安大略省)
只匹配States的第四行，即，
(加拿大安大略省,14.57)
因此，结果中的六行之一是这两行的拼接:
(多伦多，安大略省，安大略省，加拿大，14.57)
在通常情况下，条件只要求两个属性之间相等，我们通常删除两个相同列中的一个，并将结果关系的模式写为(City, State, Country, Pop)，并将刚刚讨论的行写为(Toronto, Ontario, Canada, 14.57)。d
3.2.SQL抽象。在关系模型被提出后不久，一种叫做SQL的更丰富的编程语言的开发向前迈出了一大步。<年代up>14在最初的表述中，SQL仍然不是一种图灵完备语言。但是，它确实比原始的关系模型支持更多。底层数据模型既允许集合也允许包——也就是说，同一行可以出现多次——还可以基于一列或多列中的值对关系中的行进行排序。除了前面描述的关系代数运算符外，还支持SQL分组和聚合。也就是说，SQL允许程序员根据一个或多个属性中的值对关系的行进行分组，然后聚合(例如，和或平均)每个组中一个或多个列的值。回想一下，示例1.4讨论了用和作为聚合进行分组。
例3.2。考虑国家之间的关系<一个href＝"https://dl.acm.org/cms/attachment/65246690-a341-4e7d-9d6f-2edcb128fd9f/f3.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=1021,height=528'); return false;">图3．我们可以根据Country列的值对行进行分组，然后对每个国家的每个州的人口求和。结果表显示在<一个href＝"https://dl.acm.org/cms/attachment/54802b62-a0da-4d65-a08c-27ec6ba337ff/f4.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=493,height=281'); return false;">图4．
图4。按国家分组和流行程度相加。
随着SQL的发展，标准中添加了更多的功能，包括编写递归程序的能力和调用通用编程语言中的代码的能力。因此，SQL现在在原则上是图灵完备的。幸运的是，绝大多数SQL程序不使用使其具有图灵完备性的特性。因此，在实践中，仍然有可能以一种利用许多机会进行优化的方式编译SQL，而这种优化是我们对声明式抽象所期望的。
3.3.编译的SQL。用SQL编写的程序通常编译成低级语言，如C语言。C代码大量使用库函数，例如，执行选择或连接等操作。编译的早期阶段——词法分析、解析等等——与任何通用语言的编译阶段相似。SQL与常规的不同之处在于代码优化阶段(通常称为查询优化)．回想一下，像C语言这样的语言的优化必须满足于在这里或那里保存一条机器指令，所以速度提高两倍是一个很好的结果。<年代up>e但是SQL的操作和关系模型通常要比机器指令强大得多。例如，语法树的一个操作符可以连接两个巨大的关系，就像它是一个步骤一样。
因此，与C语言或类似语言相比，SQL程序由相对较少的步骤组成，但如果按此方式实现，每一个步骤都可能花费大量的时间。因此，SQL的编译器通常会对等价语法树进行几乎详尽的搜索，而这些语法树的执行时间要短几个数量级。即使花费SQL程序的指数级大小的时间来优化只执行一次的程序也是有意义的，因为这个程序通常会在足够大的关系上执行，以证明编译时间的花费是合理的。关于优化SQL或类似语言的技术我们已经了解了很多;参见Garcia-Molina等人。<年代up>21为例。
例3.3。下面是一个非常简单的示例，说明查询优化可以极大地提高SQL程序的运行时间。假设我们已知城市和州的关系，如<一个href＝"https://dl.acm.org/cms/attachment/65246690-a341-4e7d-9d6f-2edcb128fd9f/f3.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=1021,height=528'); return false;">图3但是这些关系要大得多;他们为地球上的每个城市和每个州都排了队。我们想找出多伦多所在的国家。下面是人们很自然会写的SQL查询:
选择国家 来自城市,州 城市的地方。状态＝状态年代．年代tate AND城市= '多伦多';
选择国家
来自城市,州
城市的地方。状态＝状态年代．年代tate
AND城市= '多伦多';
本程序的字面意思如下:
该计划可以直接转换成C代码并执行。但这是一场灾难。它要求我们将两个关系整体连接起来——即使有效地完成了这项任务，例如使用1.7.1节中讨论的散列连接技术，也需要与关系大小的总和成正比的运行时间。
但是，至少在某些情况下，可以使用花费恒定时间的计划，而不依赖于关系的大小。实际上，我们颠倒了前两个步骤的顺序。也就是说，我们首先使用选择操作符从Cities关系中只选择Toronto的行。然后，我们为Toronto获取State的值，并从States关系中仅选择该State的行。最后，打印该行的Country值。
但我们需要小心一点。仅仅因为我们只想要来自Cities的Toronto row并不意味着我们总是第一个找到它，正如在<一个href＝"https://dl.acm.org/cms/attachment/65246690-a341-4e7d-9d6f-2edcb128fd9f/f3.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=1021,height=528'); return false;">图3．相反，因为关系是集合或包，我们可以在任何地方找到那一行。然而，我们也可以使用另一种抽象来组织关系，使某些操作非常快。关于如何对各种操作进行这种组织已经有了大量的理论，但在本例中，至少有一种组织是显而易见的。我们可以根据City的值对Cities的行进行散列。然后，给定任何城市名，我们就可以立即转到包含该城市的行的bucket，而不必扫描整个关系。同样，我们可以将States关系组织到一个哈希表中，哈希函数只依赖于State值，这样可以非常快速地找到给定状态的行。
3.4.分布式计算抽象。多年来，人们已经认识到单个处理器的能力正在达到极限。为了处理越来越大的数据集，有必要开发使用多个独立机器的算法。许多让我们思考分布式计算算法的抽象概念已经实现并得到了认真的使用。一般来说，这些抽象具有一些共同的特性:
这类抽象具有几个令人感兴趣的不同性能度量。最明显的一个是在所有节点上并行执行所涉及的程序所花费的时钟时间。但有时，瓶颈是节点之间通信所需的时间，特别是当需要在节点之间共享大量数据时。的数量是第三个运行时问题轮(一个计算阶段之后是一个通信阶段)由算法执行。
3.5.bulk-synchronous抽象。一个流行的抽象概念，我们将不详细讨论，是bulk-synchronous勇敢的模型。<年代up>44该模型最近通过谷歌的Pregel系统在计算集群环境中得到推广<年代up>32从那以后，它得到了许多类似的实现。看到一个调查。<年代up>47
在大容量同步模型中，可以将计算节点视为一个完整图的节点。在初始化阶段，每个节点对其本地数据执行初始化程序，从而为其他特定节点生成一些消息。当所有的计算都完成时，所有的消息都被传递到它们的目的地。在第二轮中，所有节点对它们的传入消息和本地数据执行一个“主”程序，这可能导致生成额外的消息。计算结束后，这些消息被发送到它们的目的地，第三轮开始，在新的传入消息上再次执行主程序。这种计算和消息传递的交替继续进行，直到某一轮不再生成任何消息。
3.6.MapReduce抽象。MapReduce<年代up>17是一种抽象，它已被证明是一种非常强大的工具，用于创建并行程序，而无需程序员显式地考虑并行性。Dean和Ghemawat在谷歌上的最初实现是由Hadoop普及的<年代up>12以及最近的Spark。<年代up>51此外，该模型能够轻松地支持通常耗时最多的关系模型操作:连接和分组/聚合，以及对大规模数据的许多其他重要操作。
MapReduce的数据模型是集合键值对。然而，这种意义上的“键”通常不是唯一的;它们只是对的第一个分量。MapReduce中的程序是用一些传统的编程语言编写的，每个MapReduce工作它有两个相关联的程序，不出所料，叫做“映射”和“减少”。作业的输入是一组键值对。Map程序被编写为应用于单个键-值对，它生成任意数量的键-值对作为输出。输出对的数据类型通常与输入对的类型不同。由于Map独立地应用于每个键值对，我们可以创建许多任务，称为映射器，每个函数都接受输入对的一个子集，并对每个输入对应用Map。因此，映射器可以使用尽可能多的处理器并行执行。
在映射器完成它们的工作之后，通信阶段接受Map应用到所有输入对的所有输出，并按键对它们进行排序。也就是说，输出键-值对的整个集合被组织成异径接头，每一个都是一个键x，以及所有相关值的列表，即的列表y这样就有一个输出对(x, y)．然后我们在每个减速器上执行程序Reduce。由于每个reducer都是独立的，我们可以将reducer组织成任务，并在不同的处理器上运行每个任务。整个作业的输出是由每个约简器产生的键-值对的集合。
例3.4。让我们看看如何连接的两个关系<一个href＝"https://dl.acm.org/cms/attachment/65246690-a341-4e7d-9d6f-2edcb128fd9f/f3.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=1021,height=528'); return false;">图3条件是两个关系的国值相同。连接的MapReduce实现本质上与示例3.1中讨论的散列连接算法相同。但是，我们不是将行放入桶中，而是将它们放入reducer中，每个reducer保证只有一个State值，而bucket可以包含多个状态。
输入由键值对组成（x，y)，其中y是关系x的一行。Map函数接受一个输入（x，y）并生成单个键值对（年代, (x，z）)其中s是第y行的State分量，z是第y行的其他分量。也就是说，如果x是Cities，那么z就是rowy的City分量，但如果x是States，那么z就是y的Country和Pop分量。
现在，按键排序操作将所有这些键-值对(任意关系的每一行都有一对键-值对)分组为reducer。每个reducer由单个State值和与该State任一关系的所有行列表组成。使用的数据<一个href＝"https://dl.acm.org/cms/attachment/65246690-a341-4e7d-9d6f-2edcb128fd9f/f3.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=1021,height=528'); return false;">图3任何一个州都只有一行州，但通常会有许多行市。States的reducer的工作是将每一行具有State = s的Cities与每一行具有State = s的States结合起来。输出是一组键-值对，其中键总是输出关系的名称(由Reduce程序选择)，每对都有连接的一行作为其值。
3.7.MapReduce的性能指标。让MapReduce算法变得优秀的概念是令人惊讶的棘手。在例3.4这样的示例中，Map函数只产生一个键值对，通信不太可能成为瓶颈，因此，我们可以只考虑执行所有映射器和所有约简器所需的时间。映射器和减少器可以分配到可用的处理器中，因此挂钟时间与处理器数量成反比——也就是说，在给定可用硬件的情况下，时间越短越好。但在其他应用程序中，每个映射器产生许多对，然后通信可能成为瓶颈，或至少需要考虑到的问题。将一个包从一个处理器发送到另一个处理器需要大量的时间来形成包，并且可能在网络中有延迟。
对于许多问题，发送到每个减速器的键值对的数量之间存在关系(减速机尺寸)和一个映射器产生的配对数(复制的速度)．通常，这两个量的乘积有一个下界，但受限于这个约束，有许多不同的算法可供选择。如果我们把一个键值对的通信成本换算成时间，那么Afrati等人的设计理论。<年代up>3.让我们选择最佳的减速机尺寸和复制速率，受制于适用于手头问题的任何下限约束。因此，由于映射器和约简器的计算以及映射器和约简器之间的通信，我们可以最小化挂钟时间。
也有人试图调查轮MapReduce(一个映射阶段，接着一个reduce阶段)在某些问题上是必要的。这个问题有一个陷阱，在不限制MapReduce算法操作方式的情况下，答案总是“一轮”。也就是说，给定任何串行算法一个我们可以使用以下方法:
因此，所有的工作都在与键1相关的单个reducer上完成，我们简单地将一个串行算法伪装成MapReduce作业。
为了禁止这种行为，库特里斯和苏苏<年代up>29使用一个模型货币政策委员会，它将MapReduce算法视为由参数表征的算法R，轮数，和l，任何任务允许使用的最大数据量。两个参数都是的函数n，给定问题实例的输入大小。他们进一步要求l是O（n1 -ε)对于某些ε > 0;也就是说，随着输入变得越来越大，任何任务都不能访问超过正在消失的数据部分。在这个限制下，他们能够得到关系的下界l而且R对某些问题。Karloff et al。<年代up>23增加两个额外的要求:任务必须以多项式时间作为输入大小的函数来执行n，且轮数必须为的多对数n。在这个模型中有许多有趣的开放问题——例如，您能否找到一个大小的图的连接组件n在o(日志n轮吗?
最近，量子计算和量子编程语言在世界范围内引起了很大的兴趣。量子计算之所以特别有趣，是因为量子编程语言的计算模型与经典编程语言中的计算模型有很大的不同。
故事从量子力学开始，这是20世纪20年代早期发展起来的物理学基础理论<年代up>th在原子和亚原子粒子的尺度上描述自然的物理性质。我们将提出量子力学的基本假设，所有的量子力学定律都可以从这些基本假设推导出来。从这些假设中，我们可以推导出量子电路的抽象，这是量子编程语言基础计算的基本模型之一。
4.1.量子力学的假设。复线性代数和希尔伯特空间(具有内积的复向量空间)通常被用来描述量子力学的假设。尼尔森和壮族<年代up>35是学习这门学科的一个很好的来源。首先，让我们回顾一下在假设中使用的一些复杂线性代数的基本定义。把算符看作作用于向量的复数矩阵是有帮助的。的厄密共轭一个矩阵的U来标示U__；它是矩阵的共轭转置U也就是，对的转置U然后对每个值的复数部分求负值。
一个概念酉算子是量子力学的核心。一个操作员U是统一的,如果UU__＝我,在那里我是身份。这意味着每一个酉变换的作用是可逆的。可逆意味着可逆——也就是说，我们可以从输出重构输入。一个操作员U据说是埃尔米特如果U＝U__．厄密算符是自伴的。
假设1。孤立物理系统的状态空间可以用希尔伯特空间来模拟。系统的状态完全由这个状态空间中的一个单位向量描述。
假设1允许我们定义量子位作为二维状态空间中的单位向量。量子比特是经典计算中比特(0或1)的量子计算模拟物。如果用向量|0 =(1,0)和|1 =(0,1)作为二维希尔伯特空间的标准正交基，那么该空间中的任意状态向量|ψ可以写成(α，β)或
α和β是复数。因为|ψ是单位向量，|α|<年代up>2+ |β|<年代up>2= 1。
量子比特|ψ表现出量子力学的一个内在现象称为叠加。不像经典计算中的位，它总是0或1，不知道α和β不能说量子比特|ψ一定处于|0或|1的状态。我们只能说它是这两种状态的某种组合。
假设2。封闭量子系统的状态从一个时间点到另一个时间点的演化可以用酉算符来描述。
有一个等价的方法来表述公设2使用Schrödinger的方程。然而，我们在这里只考虑一元公式，因为它自然会导致计算的量子电路模型。
假设3。为了从一个封闭的量子系统中获取信息，我们可以对该系统进行测量。测量返回具有一定概率的结果。所有可能结果的概率之和是1。测量会改变量子系统的状态。
我们不会深入公设3的细节，但为了我们在这里讨论的目的，我们可以把对单个量子比特|ψ的测量想象成一个厄米算符，它返回的结果0的概率是|α|<年代up>2结果1的概率是|β|<年代up>2．回想一下，因为|ψ是一个单位向量，|α|<年代up>2+ |β|<年代up>2= 1。测量将状态向量折叠为二维希尔伯特空间的两个基向量之一。我们注意到，量子力学中著名的海森堡测不准原理可以从复线性代数的规则和假设1-3中推导出来。
第四个假设说明了当我们组合物理系统时，复合物理系统的状态空间的维数是如何增长的。
假设4。复合物理系统的状态空间是各组成物理系统的状态空间的张量积。<年代up>f
假设4表明，如果我们在物理系统中添加一个量子比特，我们将使其状态空间的维度数翻倍。因此，如果我们结合n单量子位系统，我们得到一个状态空间为2维的复合系统<年代up>n通过取状态空间的张量积nsingle-qubit系统。这种状态空间的指数级增长使得在经典计算机上模拟大型量子系统的行为变得困难。
4.2.量子电路。从量子力学的四个假设中，我们可以推导出一种叫做量子电路的计算模型，它是量子编程语言的基本抽象。量子电路由门和线组成。它们与经典计算中的布尔电路相似，但有几个重要的区别。把量子门看作一个复数的标准正交矩阵，把它的输出看作一个通过将矩阵应用到输入向量上得到的向量，这是很有帮助的。
Single-qubit盖茨。单量子比特门有一条线通向门，一条线通向门。输入线输入一个量子位|ψ到栅极。这个门应用了一个酉变换U到输入量子位|ψ，输出一个量子位U|ψ到输出行。
在经典的布尔电路中，只有一个非平凡的单比特逻辑门，即布尔非门。在量子电路中，二维复希尔伯特空间中的任何幺正变换都可以是单量子比特量子门。这是两个重要的单量子位量子门。
例4.1。的quantum-NOT门,通常表示为X，映射量子位α| 0 +β| 1量子位的β| 0 +α| 1。基本上，它翻转了二维希尔伯特空间中表示量子比特的向量的系数。请注意,X= | 1 | 0和X| 1 = | 0。
quantum-NOT门口X可以用2 × 2矩阵表示:
例4.2。的quantum-Hadamard门,表示为H，映射量子位α| 0 +β| 1量子位:
注意HH = I，单位运算符。
quantum-Hadamard门口H可以用2 × 2矩阵表示:
还有许多其他有用的单量子位量子门。
Multiple-qubit盖茨。一个多量子比特的量子门n输入线通向门和n输出线从门发出。该门由一个酉算子组成U它可以用2表示<年代up>nX 2<年代up>n列行正交的复数矩阵。
例4.3。可控非门(control - not gate，简称CNOT)是一种非常有用的双量子比特门。它有两条输入线和两条输出线，其中一条叫做控制另一个叫目标。门动作的动作如下。如果控件上的传入量子位为| 0,目标线上的量子位不变地通过。如果传入控制量子位为| 1目标量子位翻转。在任何一种情况下，控制量子位都不会改变。如果|ψ<年代ub>1ψ<年代ub>2>代表|ψ<年代ub>1⊗|ψ<年代ub>2，量子位的张量积|ψ<年代ub>1而且|ψ<年代ub>2)，那么我们可以描述CNOT门的作用如下:
电路。我们现在可以描述量子电路，这是量子计算和量子编程语言的基础计算模型。量子电路是由线、量子门和测量门组成的无环图。因为量子电路是无环的，所以不可能有循环或反馈。因为逻辑或不是一个酉运算，所以不能有将行连接在一起的扇入。此外，在量子力学中，不可能复制一个未知的量子态no-cloning定理)，所以扇向也不可能。
一个测量门取一行作为输入，输入状态为|ψ = α|0 +的单个量子比特β|1，并输出一个概率经典位，其值为0，概率为|α|<年代up>21的概率是|β|<年代up>2．
我们用一个例子来结束量子电路的讨论，这个例子说明了量子计算的一个不同寻常的特性:纠缠。
例4.4。考虑一个有两条输入线x和y的量子电路，如图所示<一个href＝"https://dl.acm.org/cms/attachment/3414f84a-6c45-4621-85b6-588df9208264/f5.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=1022,height=414'); return false;">图5．x线连接到一个阿达玛门，阿达玛门的输出成为一个c波门的控制线。y线是CNOT门的目标线。我们将称之为EPR量子电路，以爱因斯坦、波多尔斯基和罗森的名字命名，他们指出了这种电路的输出状态的奇怪性质。这是这个电路对两个输入量子位的四个值的作用|xy>：
图5输入|00产生EPR状态的量子电路。
你可以把量子电路的运行描述为显示量子系统在应用每一级门之后的状态向量的序列。为<一个href＝"https://dl.acm.org/cms/attachment/3414f84a-6c45-4621-85b6-588df9208264/f5.jpg" onclick="window.open(this.href, '', 'resizable=yes,status=no,location=no,toolbar=no,menubar=no,fullscreen=no,scrollbars=no,dependent=no,width=1022,height=414'); return false;">图5，我们会有以下资料:
一个复合量子系统的状态不能被写成其组成系统的状态的张量积，我们说它是纠缠。可以看出，上述EPR输出状态是纠缠的。没有两个单量子位态和|ψ<年代ub>1和|ψ<年代ub>2这样国家
纠缠在量子计算中起着至关重要的作用，但纠缠的物理现象对物理学家来说仍然是一个谜。事实上，爱因斯坦称之为“幽灵般的超距作用”。
4.3.量子算法。量子计算设备很可能被用作由经典计算机控制的辅助设备。量子计算机的程序通常表示为经典计算和量子算法的混合。量子算法通常以具有以下结构的量子电路的形式出现:
1994年，贝尔实验室的彼得·肖尔(Peter Shor)发布了一种分解矩阵的算法，量子计算得到了巨大的推动n-比特整数与混合经典计算机/量子计算机使用O（n3.)操作。<年代up>39即使在今天，也没有已知的多项式时间算法在经典计算机上分解整数。
肖尔利用经典数论将整数分解问题简化为的问题订单发现。求序问题如下:给定正整数x而且N,x<N而且xcoprime来N，求最小的正整数r这样x<年代up>r国防部N= 1。整数r叫的顺序x在N。例如，21中5的阶是6，因为6是最小的正整数，使得5<年代up>6Mod 21 = 1。
肖尔设计了一个量子算法来解决多项式数量的量子门的顺序查找问题。在经典计算机上，没有已知的多项式时间内求解寻阶问题的算法。
量子算法通常使用传统计算机算法中没有的专门技术。例如，肖尔的算法使用量子傅里叶变换作为其寻序计算的一部分。
正如本文所论证的，抽象已经对计算机科学的许多领域产生了相当大的影响。但是关于计算机科学中抽象的故事有更多的论文。这里有一些方向，可能会被理论家们证明是有趣的，也有实际的重要性。
5.1.量子的未来。量子计算仍是一个处于初级阶段的领域。尽管量子电路可以近似任意酉算符到任何期望的精度，但今天的量子门计算机只有50-100个可用的量子位。此外，实际有用的量子算法屈指可数，因此要克服这些限制，在量子计算的硬件和算法领域都需要做更多的工作。<年代up>33
在理论方面，还有许多悬而未决的问题。例如，如果我们能证明经典计算机不能在多项式时间内分解整数的问题，那么我们就有了一个量子计算机能比经典计算机更快解决的问题的例子。这只是许多仍未解决的深层次理论问题之一。你最好去问问阿隆森<年代up>1列举了量子抽象中的算法挑战。
许多全栈量子计算编程语言已经被开发出来。哥伦比亚大学的博士生Krysta Svore<年代up>40表明在第2节中讨论的编译器体系结构可以与错误校正合并到量子计算设计工具的分层软件体系结构中。毕业后，她加入了微软研究院，在那里她和她的同事随后开发了q#量子编程语言，这是微软量子开发工具包的一部分。<年代up>41除了q#，维基百科“量子编程”一栏现在列出了十多种量子编程语言。
5.2.计算机系统和硬件的抽象。MapReduce和针对特定类型计算平台(在本例中是计算集群)的其他高级抽象的成功表明，对于其他平台可能存在类似的抽象。例如，目前有兴趣serverless计算，<年代up>49数据单独保存在一个文件系统中，通过短期租用一个或多个服务器来进行计算。
在更小的范围内，专用硬件是一个增长的趋势，并且可能在加速大型数据上的重要算法的执行方面发挥越来越重要的作用。您可能听说过图形处理单元(gpu)和现场可编程门阵列(fpga)。橡皮泥<年代up>37是另一种设计用于支持高通信带宽和并行性的芯片，可能很快就会上市。拥有与这些体系结构相匹配的高级抽象是很有用的，因为使用这些抽象编写的算法可以编译成使用一种或多种此类芯片类型的高效实现。
5.3.抽象分类。在多年的过程中，与编程语言处理相关的强大抽象已经被发明出来，它们帮助编译器设计领域从一门艺术转变为一门科学。但是最终的论文还没有写出来。扩展1.2节中抽象的基本分类法，以涵盖更多的编程语言和编译器领域，以及更多的计算机科学，将会很有用。与连续运行的系统(如操作系统、网络和Internet)相关的抽象是自然要包含的。
此外，我们希望分类法的用途不仅仅是在数据结构课程中组织讲座。特别地，我们希望将会有一个研究是什么使一个抽象比另一个更有用。例如，我们在3.1节中提到关系模型如何自然地成为声明性抽象，而以前的数据库模型不适合SQL等支持非常高级编程的语言。类似地，正则表达式似乎非常适合描述编程语言标记和其他有趣的字符串集，而等价的表示法，如乔姆斯基的type-3语法(cfg的一个特例)，在诸如词汇分析等应用程序中从未得到过多的应用。人们自然会问:“为什么?”
一个有趣的新领域是使用机器学习使用数据而不是用某种编程语言编写的源程序来创建软件应用程序。在某种意义上，机器学习是一种不涉及传统编译的软件开发方法。能够使用机器学习指导高效创建健壮应用程序的抽象是非常有益的。
我们感谢Peter Denning的仔细阅读和评论。我们也要感谢几位匿名推荐人的评论和帮助。
数字观看作者在独家报道中讨论这项工作通信视频。<一个href＝"//www.eqigeno.com/videos/abstractions-algorithms-compilers">//www.eqigeno.com/videos/abstractions-algorithms-compilers
1.量子计算理论的十个半宏大挑战。(2005),<一个href＝"https://www.scottaaronson.com/writings/qchallenge.html">https://www.scottaaronson.com/writings/qchallenge.html．
2.一种信息组织的算法。在Akademii Nauk博士夫人(1962)，俄罗斯科学院，263-266。
3.Afrati F.N, Sarma, a.d.， Salihoglu, S.和Ullman, J.D.地图约简计算成本的上下限。在VLDB基金会议录， 4(2013)， 277-288。
4.哦。，一个．V.在字符串中寻找模式的算法。麻省理工学院出版社，剑桥，马萨诸塞州，美国(1991)，255-300。
5.哦。，一个．V. Teaching the compilers course.SIGCSE牛40， 4(2008年11月)，6-8。
6.哦。，一个．V. and Corasick, M.J. Efficient string matching: An aid to bibliographic search.通讯。ACM 18， 6(1975年6月)，333-340。
7.哦。，一个．V., Hopcroft, J.E., and Ullman, J.D.数据结构与算法。addison - wesley, 1983)。
8.哦。，一个．V., Johnson, S.C., and Ullman, J.D. Deterministic parsing of ambiguous grammars. InACM编程语言原理研讨会记录。P.C.费舍尔和J.D.厄尔曼，艾德。ACM出版社，(1973年10月)，1-21。
9.阿霍，a.v.，拉姆，m.s.，塞西，R，厄尔曼，J.D.编译器:原理、技术和工具，第二版。艾迪生-韦斯利·朗曼出版公司，美国，(2006)。
10.阿霍，A.V.和乌尔曼，J.D.计算机科学基础。W.H.弗里曼公司，美国(1994年)。
11.控制流分析。Sigplan不是5(1970) -。
12.Apache软件基金会。Hadoop。
13.大型有序指数的组织和维护。在1970年ACM SIGFIDET数据描述和访问研讨会记录, 107 - 141。
14.续:一种结构化的英语查询语言。SIGFIDET 74，计算机协会(1974)，249-264。
15.用于大型共享数据库的数据关系模型。Commun。ACM 13， 6(1970年6月)，377-387。
16.数据库子语言的关系完整性。在数据库系统。新世纪(1972),65 - 98。
17.Dean, J.和Ghemawat, S. MapReduce:大型集群的简化数据处理。在OSDI(2004), 137 - 150。
18.丹宁，p和特雷，M。计算思维。麻省理工学院出版社基本知识系列。麻省理工学院出版社(2019)。
19.随机存取存储程序机，一种编程语言的方法。11 .选c4(1964年10月)，365-399。
20.组合计算的并行算法技术。年度审核公司。(1988), 233 - 283。
21.加西亚-莫利纳，H.，乌尔曼，j.d.和Widom, J。数据库系统:全书。普伦蒂斯霍尔出版社，美国(2008)。
22.古伯斯，L.J.和塞奇威克，R.平衡树木的二色框架。在19<年代up>th计算机科学基础年度研讨会(1978),在8至21。
23.Karlo, H.， Suri, S.和Vassilvitskii, S. MapReduce的计算模型(2010)，938-948。
24.全局计划优化的统一方法。在第一届ACM SIGACT-SIGPLAN年度会议论文集。编程语言原理(1973), 194 - 206。
25.田中健，田中健。哈希在数据库机器中的应用及其体系结构。新件。第一版1， 1(1983)， 63-74。
26.神经网络和有限自动机中的事件表示，自动机研究34，普林斯顿大学出版社，美国新泽西州普林斯顿(1956)，37-40。
27.论语言从左向右的翻译。正控制8。， 6(1965)， 607-639。
28.构造LR(k)处理器的实用方法。Commun。ACM 12(1969年11月)，613-623。
29.koutis, P.和Suciu, D.大规模并行系统中连接处理的形式化分析指南。ACM SIGMOD Rec 45， 4(2016)， 18-27。
30.莱斯克，法医，施密特，E。词法分析器生成器。W.B.桑德斯公司，美国(1990)，375-387。
31.Liskov, B.和Zilles, S.抽象数据类型编程。SIGPLAN不是94(1974年3月)，50-59。
32.G. Malewicz, Austern, m.h.， Bik, a.j.， Dehnert, j.c.， Horn, I.， Leiser, N.， Czajkowski, G. Pregel:用于大规模图形处理的系统。SIGMOD的10，计算机协会(2010)，135-146。
33.Martonosi M.和Roetteler M.量子计算的下一步:计算机科学的角色。计算社区联盟(2019)。
34.McNaughton, R.和Yamada, H.自动机的正则表达式和状态图。电子计算机汇刊， 1(1960)， 39-47。
35.尼尔森，M.A.和庄，I.L.量子计算与量子信息:十周年版。美国剑桥大学出版社(2011)。
36.彼得森，W.W.随机存取存储器的寻址。IBM J. of Res. Dev 1， 2(1957)， 130-146。
37.Prabhakar, R.， Zhang, Y.， Koeplinger, D.， Feldman, M.， Zhao, T.， Hadjis, S.， Pedram, A.， Kozyrakis, C.和Olukotun, K. Plasticine:并行模式的可重构架构。在44人会议记录<年代up>th年度实习生。计算机协会。在计算机体系结构(2017), 389 - 402。
38.拉宾，M.O.，斯科特，D.有限自动机及其决策问题。IBM J. Res. Dev, 3(1959年4月),114 - 125。
39.量子计算算法:离散对数和因式分解。在第35届交响乐年会论文集。计算机科学基础(1994), 124 - 134。
40.sore, k.m.， Aho, a.v.， Cross, a.w.， Chuang, I.L.，和Markov, I.L.量子计算设计工具的分层软件架构。电脑39， 1(2006)， 74-83。
41.Svore, k.m.， Geller, A.， Troyer, M.， Azariah, J.， Granade, C.E, Heim, B.， Kliuchnikov, V.， Mykhailova, M.， Paz, A.和Roetteler, M. Q#:使用高级DSL实现可扩展的量子计算和开发。在真实世界领域特定语言研讨会论文集(2018年2月),7:1-7:10。
42.编程技术:正则表达式搜索算法。Commun。ACM 11(1968年6月)，419-422。
43.图灵,点关于可计算数，并应用于赋值问题。在Proc。伦敦数学。Soc 2， 42(1936)， 230-265。
44.并行计算的桥接模型。Commun。ACM 33， 8(1990年8月)，103-111。
45.Vyssotsky, V.和Wegner, P.图理论Fortran源语言分析器。贝尔实验室内部文件(1963年)。
46.维基百科, 2021年。<一个href＝"https://en.wikipedia.org/wiki/Abstract_data_type">https://en.wikipedia.org/wiki/Abstract_data_type．
47.维基百科, 2021年。<一个href＝"https://en.wikipedia.org/wiki/Bulk_synchronous_parallel">https://en.wikipedia.org/wiki/Bulk_synchronous_parallel．
48.维基百科, 2021年。<一个href＝"https://en.wikipedia.org/wiki/Interface_(Java)">https://en.wikipedia.org/wiki/Interface_ (Java)．
49.维基百科, 2021年。<一个href＝"https://en.wikipedia.org/wiki/Serverless_computing">https://en.wikipedia.org/wiki/Serverless_computing．
50.计算思维。Commun。ACM 49， 3(2006)， 33-35。
51.Zaharia, M.， Xin, r.s.， Wendell, P.， Das, T.， Armbrust, M.， Dave, A.，孟，X.， Rosen, J.， Venkataraman, S.， Franklin, m.j.， Ghodsi, A.， Gonzalez, J.， Shenker, S.和Stoica, I. Apache spark:大数据处理的统一引擎。Commun。ACM 59， 11(2016年10月)，56-65。
阿尔弗雷德·霍是纽约哥伦比亚大学计算机科学名誉教授Lawrence Gussman。
Jeffrey Ullman他是加州斯坦福大学计算机科学荣誉教授。
a.虽然我们不讨论它，但还有另一种类似的抽象，即假设数据在主存中，但需要移动到缓存中进行读或写。数据以单位在主存和缓存之间移动高速缓存线路，其大小通常约为磁盘块的千分之一，但仍然使访问的局部性很重要。
b.在实践中，词法分析器不仅会产生一个标记序列，而且会在某些标记中包含一个值，用来区分标记的一个实例和另一个实例。例如,每个id令牌将具有指向符号表的关联指针，令牌如真正的或int会有指向表的指针，该表给出了这些常量的实际值。像=这样的运算符令牌将没有关联的值。在接下来的讨论中，我们将忽略这些相关的值。
id
c.尽管在编译器中词法分析先于解析，但从历史上看，Yacc先于Lex。因此，利用外观顺序来解决歧义的技巧确实属于Steve Johnson。
d.现在我们可以看到如何使用例1.4中的基于磁盘的哈希技术来实现基于哈希的高效连接算法。我们可以在两个关系的State组件上对它们的所有行进行散列，并确保连接的任何两行最终都位于同一个桶中。这允许我们通过一个接一个的桶来生成连接的行，就像我们在那个示例中所做的那样。
e.当然，让世界上所有的软件以两倍的速度运行是很棒的;我们并不想贬低传统语言代码优化的重要性。
f.举个例子，如果一个= (一个1，一个2，一个3.，一个4),B= (b1，b2)为两个向量，则一个⊗B的张量积一个而且B，为向量(一个1b1，一个1b2，一个2b1，一个2b2，一个3.b1，一个3.b<年代ub>2，一个4b1，一个4b2)．
©2022 0001 - 0782/22/2 ACM
允许为个人或课堂使用部分或全部作品制作数字或硬拷贝，但不得为盈利或商业利益而复制或分发，且副本在首页上附有本通知和完整的引用。除ACM外，本作品的其他组件的版权必须受到尊重。允许有信用的文摘。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，都需要事先获得特定的许可和/或费用。请求发布的权限<一个href＝"mailto:permissions@acm.org">permissions@acm.org传真(212)869-0481。
数字图书馆是由计算机协会出版的。版权所有©2022 ACM, Inc.
没有发现记录
