編譯 | bluemin

編輯丨陳彩嫻

1

抽象

計(jì)算思維以設(shè)計(jì)問題的抽象模型為中心，應(yīng)用計(jì)算步驟和高效算法解決問題——這一概念不僅服務(wù)于計(jì)算機(jī)科學(xué)（CS），而且逐漸滲透到科學(xué)和日常生活中。

「抽象」（Abstraction）是計(jì)算思維的核心，也是本文的主題。「抽象」一直是計(jì)算機(jī)科學(xué)的重要概念，在向廣大受眾教授計(jì)算機(jī)知識(shí)時(shí)，對(duì)計(jì)算思維的強(qiáng)調(diào)更是突顯了抽象的重要性。

在計(jì)算機(jī)科學(xué)中，抽象并不局限于物理現(xiàn)實(shí)，因此我們發(fā)現(xiàn)有用的抽象無處不在，例如「量子力學(xué)」。它有一種衍生的計(jì)算抽象，叫「量子電路」，從物理概念開始，催化出用于模擬的編程語言，以及利用其獨(dú)特功能的理論算法，有望在大型機(jī)器上實(shí)現(xiàn)。

計(jì)算機(jī)科學(xué)中的「抽象」往往包含以下內(nèi)容：

• 數(shù)據(jù)模型包含一種或多種類型的數(shù)據(jù)以及數(shù)據(jù)之間可能存在的關(guān)系。例如，無向圖可以描述為由節(jié)點(diǎn)和邊組成，每條邊連接兩個(gè)節(jié)點(diǎn)。
• 某些編程語言不進(jìn)行數(shù)據(jù)操作。這可能是一種傳統(tǒng)的編程語言，也可能只進(jìn)行一些特定的操作。這種語言總是有一個(gè)正式的語義——關(guān)于程序如何影響數(shù)據(jù)的規(guī)范。

因此，每個(gè)抽象模型都允許我們?cè)O(shè)計(jì)算法，以特定的方式操作數(shù)據(jù)。

我們的目標(biāo)是設(shè)計(jì)「優(yōu)質(zhì)」、具有多項(xiàng)優(yōu)勢(shì)的抽象模型。在設(shè)計(jì)解決方案時(shí)，抽象的難易程度是一項(xiàng)重要指標(biāo)。例如，我們將在 3.1 節(jié)討論關(guān)系模型如何導(dǎo)致數(shù)據(jù)庫使用頻率的激增。生成的算法還有其他性能指標(biāo)，例如串行或并行機(jī)器上的運(yùn)行時(shí)間。同樣，我們傾向易于實(shí)現(xiàn)的抽象。最后，一些抽象提供了一種簡(jiǎn)單的方法來衡量算法的效率（因?yàn)閷?duì)于傳統(tǒng)編程語言，我們可以估計(jì)程序運(yùn)行時(shí)間的上界），而其他抽象則要求我們即使是近似討論算法的效率，也要先在較低層級(jí)進(jìn)行實(shí)現(xiàn)。

1.1 編譯

有些抽象的層次太高，無法提供有意義的性能指標(biāo)。因此，高級(jí)抽象的操作可能需要在較低的層級(jí)上實(shí)現(xiàn)。

實(shí)際上，在逐漸接近機(jī)器本身的層次上，可能存在多個(gè)抽象層次。如圖1所示，高級(jí)抽象（抽象1）的操作可以由較低級(jí)別的抽象（抽象2）實(shí)現(xiàn)，而較低級(jí)別的抽象又可以由更低級(jí)別的抽象（圖中未顯示）實(shí)現(xiàn)。有一些有趣的抽象層次將我們從高級(jí)程序帶到機(jī)器指令、物理硬件、邏輯門、晶體管，最后到電子。不過，我們只關(guān)注更高的層次。

圖1. 抽象層和算法層

使用抽象1的操作的算法被編譯為較低級(jí)別的抽象2中的算法。在本文中，我們使用的是普遍意義上的術(shù)語編譯器，不僅僅是《龍書》中重點(diǎn)介紹的編程語言的常規(guī)編譯器，還會(huì)使用將一個(gè)抽象的程序轉(zhuǎn)換為另一個(gè)程序的算法，這大概屬于較低級(jí)別的抽象。因此，在某些情況下，編譯過程很簡(jiǎn)單，較高級(jí)別的每個(gè)操作都被較低級(jí)別的一個(gè)或多個(gè)特定操作所取代。在其他情況下，尤其是從傳統(tǒng)語言（比如C語言）到機(jī)器級(jí)語言編譯時(shí)，翻譯算法非常復(fù)雜。還有其他的一些情況，例如當(dāng)高級(jí)抽象使用強(qiáng)大的代數(shù)運(yùn)算（如線性代數(shù)或關(guān)系代數(shù)）時(shí)，優(yōu)化是至關(guān)重要的，因?yàn)樵季幾g通常會(huì)導(dǎo)致算法比通過優(yōu)化編譯生成的算法多花費(fèi)幾個(gè)數(shù)量級(jí)的時(shí)間。

這可能是因?yàn)槌橄?與機(jī)器層次太接近，因此具備有意義的性能指標(biāo)。如果是這樣，抽象1可以繼承這些指標(biāo)，為抽象1中編寫的算法提供優(yōu)質(zhì)概念。但是高級(jí)抽象通?？梢栽趲讉€(gè)不同的低級(jí)抽象中實(shí)現(xiàn)。每個(gè)低級(jí)抽象都可能提供一個(gè)完全不同的運(yùn)行時(shí)間或其他度量的概念，因此在高層次上必然包含不同的算法優(yōu)度概念。

1.2 抽象的分類法

我們至少可以確定四種不同類型的抽象，可以根據(jù)它們的預(yù)期目標(biāo)進(jìn)行劃分。在構(gòu)成本文主體的討論中，我們將給出相應(yīng)的例子并探討它們的相互作用。

1.2.1. 基本抽象  

與所有抽象一樣，基本抽象由數(shù)據(jù)模型和操作組成。這些抽象通常被認(rèn)為是在面向?qū)ο缶幊陶Z言中實(shí)現(xiàn)的抽象數(shù)據(jù)類型。但是基本抽象沒有操作的具體實(shí)現(xiàn)，也沒有表示數(shù)據(jù)的特定數(shù)據(jù)結(jié)構(gòu)。人們也可以將這些抽象比作 Java 中的接口，但與接口不同的是，這些抽象對(duì)它們的操作具有預(yù)期的含義，而不僅僅表示操作的名稱。

研究基本抽象實(shí)際上有兩個(gè)截然不同的目的。在某些情況下，它們代表了值得單獨(dú)研究的常見操作，并且有多種實(shí)現(xiàn)方法。例如，我們?cè)?1.4 節(jié)討論字典（一個(gè)包含插入、刪除和查找操作的集合）。這種類型的其他示例包括堆棧、隊(duì)列、優(yōu)先級(jí)隊(duì)列，以及許多其他抽象。

其他抽象非常廣泛，可以支持應(yīng)用程序的大型組件。常見的例子包括各種各樣的樹和圖，例如有向圖、無向圖、有標(biāo)簽圖和無標(biāo)簽圖。

這些抽象具有廣泛的操作集，可以通過各種方式組合。但是，這些操作本身并不是圖靈完備的。相反，它們被假定嵌入在圖靈完備的語言中，并構(gòu)建了使用該模型的算法。例如，在圖抽象中，我們可能有一個(gè)操作，例如「查找相鄰節(jié)點(diǎn)」。在這個(gè)抽象之外，我們可以假設(shè)有一種編程語言允許在所有相鄰節(jié)點(diǎn)上進(jìn)行迭代。這個(gè)操作的實(shí)現(xiàn)和圖本身的表示都沒有具體說明，因此我們沒有運(yùn)行時(shí)間的具體概念。我們可以將這些抽象與面向?qū)ο缶幊陶Z言中的典型類及其方法進(jìn)行類比。區(qū)別在于類的方法在底層編程語言中有特定的實(shí)現(xiàn)。同樣，我們可以將諸如編程語言庫或 TeX 包之類的東西視為這種類型的抽象。

1.2.2 抽象實(shí)現(xiàn)  

這些表示實(shí)現(xiàn)的方法，可能是一個(gè)或多個(gè)基本抽象的實(shí)現(xiàn)。這些語言本身并不是圖靈完備語言，通?？梢员痪幾g成幾種不同的機(jī)器模型，例如，串行或并行機(jī)器，或者采用主內(nèi)存或輔助內(nèi)存的模型。每一個(gè)機(jī)器模型都提供了運(yùn)行時(shí)間的概念，可以將其轉(zhuǎn)換為抽象實(shí)現(xiàn)的運(yùn)行時(shí)間，然后轉(zhuǎn)換為支持的基本抽象的運(yùn)行時(shí)間。

這一類型還包括自動(dòng)機(jī)，如確定性或非確定性有限自動(dòng)機(jī)（見第2.1.1和2.1.3節(jié)）和移位歸約解析器（見第2.2.1節(jié)）。

1.2.3 聲明性抽象  

抽象最重要的用途之一是培養(yǎng)一種編程風(fēng)格，只需說明想做什么，而不是如何去做。因此，我們發(fā)現(xiàn)許多不同的抽象，包括一個(gè)數(shù)據(jù)模型和一種比傳統(tǒng)語言更高級(jí)的編程語言；這些語言通常是某種代數(shù)。例如正則表達(dá)式（將在第2.1節(jié)中討論）和關(guān)系代數(shù)（將在第3節(jié)中提到）。上下文無關(guān)文法（第2.2節(jié)）盡管不是嚴(yán)格意義上的代數(shù)，也是這類抽象的另一個(gè)例子。

這些抽象的特點(diǎn)是它們的編譯需要高度優(yōu)化。對(duì)于傳統(tǒng)語言，好的優(yōu)化可以使其在機(jī)器上的運(yùn)行時(shí)間加快兩倍，而對(duì)于這些抽象，好實(shí)現(xiàn)和壞實(shí)現(xiàn)的運(yùn)行時(shí)間之間可能存在數(shù)量級(jí)差異。另一個(gè)特點(diǎn)是聲明性抽象的編程語言不是圖靈完備的。任何圖靈完備語言的不可判定性屬性都將排除優(yōu)化器的存在。優(yōu)化器可以有效地、全面地處理程序想要做的事情，而無需被告知如何做。

1.2.4 計(jì)算抽象  

與抽象實(shí)現(xiàn)相比，這些抽象接近于物理實(shí)現(xiàn)的機(jī)器。也就是說，沒有人會(huì)僅僅為了形成一個(gè)抽象實(shí)現(xiàn)而構(gòu)建一臺(tái)機(jī)器，但通常會(huì)實(shí)現(xiàn)計(jì)算抽象或易于轉(zhuǎn)換的東西。因此計(jì)算抽象提供了有意義的性能指標(biāo)，即使它們不是100%準(zhǔn)確。

你可能熟悉許多計(jì)算抽象，因?yàn)樗鼈儼ㄋ型ㄓ镁幊陶Z言以及機(jī)器指令集。這種類型的其他抽象更具理論性，例如隨機(jī)存取存儲(chǔ)器（RAM）模型或并行隨機(jī)存取存儲(chǔ)器（PRAM）模型。在這里，我們將在 1.7 節(jié)討論一個(gè)強(qiáng)調(diào)二級(jí)存儲(chǔ)作用的傳統(tǒng)機(jī)器模型。我們還將討論并行計(jì)算的抽象：3.5 節(jié)中的批量同步和 3.6 節(jié)中的映射規(guī)約模型（MapReduce）。

雖然許多計(jì)算抽象與傳統(tǒng)計(jì)算機(jī)有關(guān)，但也有一些例外。圖靈機(jī)就是其中之一，還有一些甚至不是圖靈完備的，但在計(jì)算機(jī)科學(xué)中發(fā)揮著重要作用。例如，在克勞德·香農(nóng)的碩士論文之后，布爾電路和布爾代數(shù)是計(jì)算科學(xué)最早使用的抽象概念之一，而量子電路抽象則是最新的概念。

1.3 對(duì)抽象空間的探索  

為了解抽象鏈的本質(zhì)及其關(guān)系，接下來看一個(gè)基本抽象的常見示例：字典。

字典是抽象的一個(gè)常見示例，它具有許多替代實(shí)現(xiàn)，并說明了隨著高級(jí)抽象被編譯為低級(jí)抽象而暴露出的一些問題。字典的數(shù)據(jù)模型包括以下內(nèi)容：

1. 一個(gè)全集 U。
2. 全集 U 的子集 S，初始化時(shí)，S為空。

字典的「編程語言」由以下三種操作的直線序列組成：

1. 插入(x)：如果U的元素x不在集合S中，則將其插入集合S中，即 S: = S ∪ {x}。
2. 刪除(x)：從集合S中去除元素x，S:= S – {x}。
3. 查找(x)：如果元素x在集合S中返回真，否則為假。

例如，字典可用于描述編譯器中符號(hào)表的行為。U將是編程語言的可能標(biāo)識(shí)符集。當(dāng)編譯器掃描程序時(shí)，S將是一組標(biāo)識(shí)符，在程序中的每個(gè)點(diǎn)上都有定義好的含義。然而對(duì)于符號(hào)表，需要將數(shù)據(jù)附加到每個(gè)標(biāo)識(shí)符上，例如它定義的數(shù)據(jù)類型和出現(xiàn)的嵌套塊的級(jí)別（以便我們可以區(qū)分具有相同名稱的標(biāo)識(shí)符）。當(dāng)編譯器找到一個(gè)聲明時(shí)，它會(huì)將聲明的標(biāo)識(shí)符插入集合S。當(dāng)它到達(dá)程序或函數(shù)的末尾時(shí)，它會(huì)刪除與該程序塊關(guān)聯(lián)的標(biāo)識(shí)符。在程序中使用標(biāo)識(shí)符時(shí)，編譯器會(huì)查找該標(biāo)識(shí)符并檢索其類型和其他必要信息。

請(qǐng)注意，字典的編程語言相當(dāng)簡(jiǎn)單，不具備圖靈機(jī)的功能，也沒有真正的算法設(shè)計(jì)概念，因?yàn)椤赋绦颉怪皇欠从称渌M(jìn)程正在做什么。同樣，也沒有真正的運(yùn)行時(shí)間概念，因?yàn)椴磺宄總€(gè)操作需要多長(zhǎng)時(shí)間。我們可以將每個(gè)操作定義為占用單位時(shí)間，但由于我們無法控制「程序」的長(zhǎng)度，因此這個(gè)運(yùn)行時(shí)間也沒有意義。

1.4 字典的實(shí)現(xiàn)  

字典可以使用許多不同的抽象方法來實(shí)現(xiàn)。鏈表應(yīng)該是大家非常熟悉的抽象實(shí)現(xiàn)，其數(shù)據(jù)模型包括以下內(nèi)容：

• 單元格包含值（某個(gè)全集U的成員）和指向另一個(gè)單元格的鏈接（可能為空）。
• 標(biāo)頭，簡(jiǎn)單命名為指向單元格的鏈接（可能為空）。

假設(shè)讀者熟悉可以執(zhí)行的典型操作，例如創(chuàng)建單元格或標(biāo)頭、從列表中插入和刪除單元格以及返回包含在指定單元格中的數(shù)據(jù)?？梢酝ㄟ^創(chuàng)建集合 S 中所有元素的鏈表來實(shí)現(xiàn)字典。將三個(gè)字典操作編譯為列表操作很簡(jiǎn)單。

如果假設(shè)鏈表是在計(jì)算機(jī)的 RAM 模型中實(shí)現(xiàn)的，那么我們就有了一個(gè)現(xiàn)實(shí)的運(yùn)行時(shí)間概念。我們可以為列表單元格上的每個(gè)基本操作分配一個(gè)時(shí)間單位，因?yàn)樵?RAM 上，每個(gè)操作都需要恒定的時(shí)間。這一觀察結(jié)果讓我們將運(yùn)行時(shí)間的RAM概念提升到運(yùn)行時(shí)間的鏈表概念，然后提升到字典級(jí)別。但這不是個(gè)好消息，平均而言，我們必須至少走到列表的一半，通常一直到最后，才能實(shí)現(xiàn)任何字典操作。因此，單個(gè)字典操作的運(yùn)行時(shí)間與當(dāng)時(shí)集合 S 的大小成正比。

另一種易于理解的實(shí)現(xiàn)字典的抽象類的方法是使用搜索樹。當(dāng)三個(gè)字典操作的算法保持樹平衡時(shí)，例如AVL 樹或紅黑樹，每個(gè)操作的運(yùn)行時(shí)間與操作時(shí)集合 S 的大小是對(duì)數(shù)關(guān)系。但是通常首選的實(shí)現(xiàn)字典的抽象是哈希表。

1.5 哈希抽象  

哈希的數(shù)據(jù)模型包括以下內(nèi)容：

• 全集 U。
• 哈希桶數(shù) B，從 0 到 B-1 編號(hào)。
• 從 U 到 {0,1，…，B–1} 的哈希函數(shù) h。每個(gè)哈希桶 b 是全集 U 的元素 x 的子集，使得 h(x)=b。

通常的操作是計(jì)算h(x)，其中x是U的一個(gè)成員，并在編號(hào)為 h(x) 的哈希桶中插入、刪除或查找 x。例如，哈希表的插入操作將表示為 h-insert (x, b)，其中 b = h(x)。哈希程序包括交替計(jì)算一些 h(x)，然后對(duì) x 和哈希桶 h(x) 執(zhí)行三個(gè)操作中的某一個(gè)。

將字典程序編譯成哈希程序很簡(jiǎn)單。例如，字典操作insert (x) 被翻譯成b: = h (x); h-insert (x, b)。

哈希與機(jī)器的距離有些遠(yuǎn)，我們無法直接使用它來確定運(yùn)行時(shí)間。存在的問題是，哈希法相當(dāng)獨(dú)特，因?yàn)樽顗那闆r下的性能，即集合中的所有元素都在同一個(gè)哈希桶中，比我們對(duì)所有可能的哈希函數(shù)進(jìn)行平均時(shí)的平均情況要差得多。為簡(jiǎn)單起見，應(yīng)該正確地假設(shè)，在平均情況下幾乎所有的哈希桶都包含接近平均數(shù)的元素，即S/B。但即使同意只討論平均情況，仍然不知道對(duì)一個(gè)元素和哈希桶的每個(gè)操作需要多長(zhǎng)時(shí)間。

本質(zhì)上，每個(gè)哈希桶本身就是一個(gè)小型字典，所以我們必須決定如何實(shí)現(xiàn)它的操作。如果 S 的大小保持在 B 的數(shù)量級(jí)，我們可以使用哈希桶的鏈表實(shí)現(xiàn)，并期望每個(gè)操作在 RAM 或真實(shí)機(jī)器上平均花費(fèi) O(1) 時(shí)間。但是，如果 S 比 B 大得多，則表示哈希桶的列表的平均長(zhǎng)度為 O (S/B)。這仍然比每個(gè)操作的時(shí)間復(fù)雜度為O (S) 要好。然而，當(dāng) S 太大而無法放入主存時(shí)，RAM 模型不再適用，我們就需要考慮另一種計(jì)算抽象。

1.6 二級(jí)存儲(chǔ)抽象  

作為 RAM 計(jì)算抽象的替代方案，在 O(1) 時(shí)間內(nèi)可以訪問任何數(shù)據(jù)片段，我們可以在多個(gè)級(jí)別引入訪問局部性。我們將只討論一個(gè)具有基于磁盤的輔助內(nèi)存的抽象，其中大數(shù)據(jù)塊（比如64KB）作為一個(gè)整體在磁盤和主存之間移動(dòng)，且必須在主存中讀取或?qū)懭霐?shù)據(jù)。與在主存中對(duì)數(shù)據(jù)本身進(jìn)行的典型操作的成本相比，在主存和輔助內(nèi)存之間移動(dòng)數(shù)據(jù)塊的成本高昂。因此，在這種新模型中，將運(yùn)行時(shí)間簡(jiǎn)單地視為磁盤I/O的數(shù)量是合理的，即一個(gè)數(shù)據(jù)塊從輔助內(nèi)存移動(dòng)到主存的次數(shù)，反之亦然。

在底層機(jī)器的二級(jí)存儲(chǔ)模型中，實(shí)現(xiàn)哈希表的最佳方法與使用 RAM 模型的首選方法有些不同。特別是，每個(gè)哈希桶將由一個(gè)或多個(gè)完整的磁盤塊組成。為了利用局部性，希望典型的哈希桶由盡可能少的磁盤塊組成，但希望盡可能使這些磁盤塊充滿。因此，假設(shè)主存能夠容納全集中的M個(gè)元素，而磁盤塊能夠容納P個(gè)這樣的元素。然后希望哈希桶的數(shù)量 B 為 B = M/P，那么就可以在主存中為每個(gè)哈希桶保存一個(gè)磁盤塊，并且該磁盤塊可能會(huì)近乎充滿。

隨著集合S的大小增加，我們使用磁盤塊的鏈表來表示每個(gè)哈希桶，只有第一個(gè)哈希桶在主存中。最壞的情況下，這三個(gè)字典操作需要檢查單個(gè)哈希桶中的所有磁盤塊。因此，平均而言，預(yù)計(jì)每個(gè)操作的磁盤I/O數(shù)為O(S/BP），因?yàn)镾的元素將在B個(gè)哈希桶中大致平均分配，將單個(gè)哈希桶的元素每隔P個(gè)劃分成一組，放入一個(gè)磁盤塊中。由于B=M/P，每個(gè)操作的運(yùn)行時(shí)間為O（S/M）。

2

編譯器的抽象

現(xiàn)代編譯器將翻譯過程細(xì)化為多個(gè)階段，每個(gè)階段將源程序的一種表示形式轉(zhuǎn)換為另一種語義等價(jià)的表示形式，通常處于較低的抽象級(jí)別。編譯器中的階段通常包括詞法分析、句法分析、語義分析、中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成。所有階段共享的符號(hào)表用于收集和提供有關(guān)源程序中各種結(jié)構(gòu)的信息。前四個(gè)階段通常稱為編譯器的前端，后兩個(gè)階段稱為后端。

編譯器實(shí)現(xiàn)的進(jìn)展涉及許多重要的抽象。我們將具體討論三種這樣的抽象：正則表達(dá)式、上下文無關(guān)文法和流圖。前兩個(gè)是帶有有趣優(yōu)化故事的聲明性抽象。第三個(gè)雖然不是聲明性的，但也帶來了有趣的實(shí)現(xiàn)挑戰(zhàn)。

2.1 正則表達(dá)式和句法分析

句法分析是編譯器的第一個(gè)階段，它將源程序讀取為一個(gè)字符序列，并將其映射為一個(gè)稱為標(biāo)記的符號(hào)序列，然后傳遞到下一個(gè)階段，即語法分析器。

例2.1 如果源程序包含語句：華氏溫度=攝氏度*1.8+32，句法分析器可以將該語句映射為七個(gè)標(biāo)記的序列：<id><=><id><*><real><+><int> 。這里id是任何程序變量或標(biāo)識(shí)符的標(biāo)記，運(yùn)算符=、*、和+本身就是標(biāo)記，這兩個(gè)常量分別被轉(zhuǎn)換為標(biāo)記real和int。

編譯器構(gòu)造方面的一大進(jìn)步是創(chuàng)建了句法分析的生成器，一個(gè)像Lex這樣的程序，將標(biāo)記的描述作為輸入，生成一個(gè)程序，將源程序分解為標(biāo)記，并返回與源程序?qū)?yīng)的標(biāo)記序列。使Lex得以應(yīng)用的抽象是正則表達(dá)式。像Lex這樣使用正則表達(dá)式抽象的系統(tǒng)使用了許多有用的速記，使編寫正則表達(dá)式更為簡(jiǎn)單，但不會(huì)更改可以在此抽象中定義的字符串集。

例2.2  在某些編程語言中，作為合法標(biāo)識(shí)符的字符串集可以定義如下：

letter = [a-zA-Z]

digit = [0-9]

id = letter (letter+digit)*

在這個(gè)簡(jiǎn)寫法中，像a-z這樣的表達(dá)式表示 a 到 z 之間帶有ASCII 碼的單字符串的并集。因此字母的正則表達(dá)式在最初的三個(gè)運(yùn)算符集合中：

a+b+...+z+A+B+...+Z

類似地定義數(shù)字，然后將標(biāo)記<id>的字符串集定義為字母后跟0個(gè)或多個(gè)字母和/或數(shù)字串組成的字符串。

2.1.1 Lex程序產(chǎn)生之前：書目檢索

從理論研究中可以很好地理解，正則表達(dá)式抽象可以編譯成幾種抽象實(shí)現(xiàn)之一，例如確定性或非確定性有限自動(dòng)機(jī)（NFA和DFA）。然而，當(dāng)需要解決實(shí)際問題時(shí)，仍有一些技術(shù)有待突破。

貝爾實(shí)驗(yàn)室在首次嘗試自動(dòng)搜索相關(guān)文獻(xiàn)時(shí)采取了一個(gè)有趣的步驟：他們?cè)诖艓媳４媪苏麄€(gè)貝爾實(shí)驗(yàn)室圖書館的標(biāo)題，并且開發(fā)了軟件來獲取關(guān)鍵字列表、找到包含這些關(guān)鍵字的文檔。然而，當(dāng)給定一長(zhǎng)串關(guān)鍵字時(shí)，搜索速度很慢，因?yàn)樗克阉饕粋€(gè)關(guān)鍵字就會(huì)遍歷一次磁帶。

Aho-Corasick算法對(duì)此做了改進(jìn)，與單獨(dú)搜索每個(gè)關(guān)鍵字不同，關(guān)鍵字列表被視為包含任何關(guān)鍵字出現(xiàn)的所有字符串集的正則表達(dá)式，即：

請(qǐng)注意，點(diǎn)是「任何字符」的擴(kuò)展名。該表達(dá)式被轉(zhuǎn)換為確定性有限自動(dòng)機(jī)。無論涉及多少關(guān)鍵字，都可以在磁帶上進(jìn)行一次傳遞。每個(gè)標(biāo)題由有限自動(dòng)機(jī)檢查一次，以查看是否在其中找到了任何關(guān)鍵字。

2.1.2 句法分析的生成器設(shè)計(jì)  

本質(zhì)上，Lex之類的句法分析的生成器與第2.1.1節(jié)體現(xiàn)的思想異曲同工。為每個(gè)標(biāo)記編寫正則表達(dá)式，然后對(duì)這些表達(dá)式應(yīng)用聯(lián)合運(yùn)算符。該表達(dá)式被轉(zhuǎn)換為確定性有限自動(dòng)機(jī)，讀取字符，直到找到與標(biāo)記匹配的字符串前綴，然后刪除從輸入中讀取的字符，將該標(biāo)記添加到輸出流中，并重復(fù)該過程。

還有一些額外的考慮，因?yàn)榕c關(guān)鍵字不同，標(biāo)記之間可能存在一些復(fù)雜的交互。例如，雖然看起來像一個(gè)標(biāo)識(shí)符，但它實(shí)際上是一個(gè)用于程序中控制流的關(guān)鍵字。因此，當(dāng)看到這個(gè)字符序列時(shí)，詞法分析器必須返回標(biāo)記<while>，并非<id>。在 Lex 中，正則表達(dá)式在其輸入文件中列出的順序打破了諸如此類的歧義，因此所要做的就是在標(biāo)識(shí)符之前列出關(guān)鍵字，確保關(guān)鍵字被正確區(qū)分，而不是被當(dāng)作標(biāo)識(shí)符。另一個(gè)問題是某些標(biāo)記可以是另一個(gè)標(biāo)記的前綴。如果輸入的下一個(gè)字符是 =，我們不希望將 < 識(shí)別為標(biāo)記。相反，我們希望將 <= 識(shí)別為標(biāo)記。為了避免這樣的錯(cuò)誤，句法分析器被設(shè)計(jì)為一直讀取，只要它所看到的內(nèi)容被有限自動(dòng)機(jī)接受為合法標(biāo)記。

2.1.3 DFA的惰性評(píng)估  

還有一種可以使用正則表達(dá)式抽象來提高算法的運(yùn)行時(shí)間的優(yōu)化方法——惰性評(píng)估。

你可能熟悉將正則表達(dá)式轉(zhuǎn)換為確定性有限自動(dòng)機(jī)的標(biāo)準(zhǔn)方法。正則表達(dá)式首先通過 McNaughton-Yamada 的算法轉(zhuǎn)換為非確定性有限自動(dòng)機(jī)。這種轉(zhuǎn)換很簡(jiǎn)單，如果正則表達(dá)式的長(zhǎng)度為 n，則生成最多具有 2n 個(gè)狀態(tài)的 NFA。將NFA轉(zhuǎn)換為DFA時(shí)，開始困難重重，這需要Rabin-Scott子集構(gòu)造。在最壞的情況下，這種構(gòu)造可以將具有2n個(gè)狀態(tài)的NFA轉(zhuǎn)換為具有個(gè)狀態(tài)的DFA，這實(shí)際上是不通的。在實(shí)踐中，最壞的情況發(fā)生的概率很小。

然而，在正則表達(dá)式的其他應(yīng)用中，可能并且確實(shí)會(huì)出現(xiàn)接近最壞情況的情形。grep 是最早的 UNIX 命令之一，代表「獲取正則表達(dá)式并打印」。該命令將接受一個(gè)字符串并確定它是否具有給定正則表達(dá)式語言的子字符串。最簡(jiǎn)單的實(shí)現(xiàn)是將正則表達(dá)式轉(zhuǎn)換為 NFA，然后再轉(zhuǎn)換為 DFA，讓 DFA 讀取字符串。當(dāng)DFA較大時(shí)，將NFA轉(zhuǎn)換為DFA比掃描字符串要耗費(fèi)更多的時(shí)間。

但是，當(dāng)正則表達(dá)式僅用于一次掃描字符串時(shí)，有更有效的方法來實(shí)現(xiàn)命令，例如 grep。Ken Thompson 的第一篇研究論文表明，與其將小型 NFA 轉(zhuǎn)換為大型 DFA，不如直接模擬 NFA 更有效。也就是說，讀取字符串的 NFA 通常在讀取每個(gè)字符后處于一組狀態(tài)中。因此，只需在每個(gè)字符之后跟蹤這些 NFA 狀態(tài)，并在讀取下一個(gè)字符時(shí)，從前一組狀態(tài)構(gòu)建該字符可到達(dá)的狀態(tài)集。

通過 NFA 到 DFA 的惰性轉(zhuǎn)換可以實(shí)現(xiàn)更高的效率。也就是說，每次讀取一個(gè)字符的輸入字符串，然后將到目前為止所讀取的前綴實(shí)際產(chǎn)生的 NFA 狀態(tài)集制成表格。這些 NFA 狀態(tài)集對(duì)應(yīng)于 DFA 狀態(tài)，因此我們只構(gòu)建處理此特定輸入字符串所需的 DFA 轉(zhuǎn)換表部分。如果給定正則表達(dá)式的 DFA 不太大，完成處理字符串之前將構(gòu)建大部分或全部的DFA，會(huì)獲得直接使用 DFA 的好處，而不是在字符串的每個(gè)字符后構(gòu)造NFA狀態(tài)集。但是如果DFA比字符串大，大部分的DFA永遠(yuǎn)不會(huì)被構(gòu)造，所以我們會(huì)充分利用這兩種情況。這項(xiàng)改進(jìn)是在名為 egrep 的 grep 版本中實(shí)現(xiàn)的。

圖2. 表達(dá)式 a + b * c 的語法樹

2.2 上下文無關(guān)文法和語法分析  

編譯器的第二個(gè)階段，語法分析器或「解析器」將詞法分析器生成的標(biāo)記序列映射為樹狀表示，從而明確標(biāo)記序列中的語法結(jié)構(gòu)。一種典型的表示是語法樹，其中每個(gè)內(nèi)部節(jié)點(diǎn)代表某個(gè)結(jié)構(gòu)，該節(jié)點(diǎn)的子節(jié)點(diǎn)代表該結(jié)構(gòu)的組件。

例2.3 語法分析器可以將標(biāo)記序列 a+b*c 映射成如圖2所示的語法樹。這里，E代表一個(gè)表達(dá)式。操作數(shù)a、b和c本身就是表達(dá)式。但b*c也是一個(gè)表達(dá)式，由運(yùn)算符標(biāo)記*和兩個(gè)表達(dá)式b和c組成。在根部，我們看到另一個(gè)表達(dá)式，這個(gè)表達(dá)式使用運(yùn)算符+和兩個(gè)操作數(shù)表達(dá)式a和b*c。

遵守有關(guān)運(yùn)算符優(yōu)先級(jí)的許多約定很重要。通常，乘法優(yōu)先于加法，這就是為什么語法樹在加a之前將b乘以c，而不是先將a和b相加。

給定編程語言所需的語法樹結(jié)構(gòu)通常由聲明性抽象定義，即上下文無關(guān)文法（context free grammar，CFG），希望讀者熟悉此概念。CFG 是稱為產(chǎn)生式規(guī)則的集合，提供了從其他句法類別和終端（句法分析器生成的標(biāo)記）構(gòu)造各種語法類別（如表達(dá)式或語句）的方法。例如，如果 E 表示該語言的良構(gòu)表達(dá)式的語法類別，那么我們可能會(huì)找到如下規(guī)則：，這意味著一種構(gòu)造表達(dá)式的方法是在兩個(gè)較小的表達(dá)式之間放置一個(gè)加號(hào)。

2.2.1 LR(k)語法分析  

在20世紀(jì)60年代，有一系列關(guān)于如何從CFG構(gòu)造高效語法分析器的提議。人們認(rèn)識(shí)到，對(duì)于通用編程語言，只要語法具有某些屬性，就可以對(duì)程序進(jìn)行一次從左到右的掃描，而無需回溯，并根據(jù)該語言的語法構(gòu)建語法樹。

有些決定很棘手。例如，在處理表達(dá)式a+b*c時(shí)，僅讀取a+b后，必須決定是否將表達(dá)式a和b與加號(hào)組合成更大的表達(dá)式。如果向前看一個(gè)標(biāo)記并看到*，就會(huì)知道把a(bǔ)和b結(jié)合起來是不正確的，但必須繼續(xù)前進(jìn)，最終把b和c結(jié)合起來。只有在此基礎(chǔ)上，把a(bǔ)和表達(dá)式b*c結(jié)合起來才是正確的。

這種語法分析方式稱為「移位-歸約解析」。在掃描輸入時(shí)，每一步都需決定是通過將下一個(gè)輸入標(biāo)記推入堆棧來移動(dòng)它還是對(duì)堆棧頂部的符號(hào)進(jìn)行歸約。歸約時(shí)，歸約的符號(hào)必須在CFG的右側(cè)。這些符號(hào)出棧后被替換到同一產(chǎn)生式的左側(cè)。此外，為產(chǎn)生式左側(cè)的符號(hào)創(chuàng)建語法樹節(jié)點(diǎn)。它的子節(jié)點(diǎn)是剛剛出棧的符號(hào)對(duì)應(yīng)的樹根。如果一個(gè)標(biāo)記出棧，它的樹只是一個(gè)節(jié)點(diǎn)，但如果一個(gè)語法類別出棧，那么它的樹就是之前為堆棧上的符號(hào)構(gòu)造的樹。

Don Knuth提出了LR(k)語法分析，適用于最普遍的語法類別，對(duì)輸入進(jìn)行單次從左到右掃描，使用移位-歸約范式并查看輸入前面的最多k個(gè)符號(hào)后可以正確解析。這項(xiàng)工作似乎解決了語法分析器應(yīng)該如何構(gòu)造的問題。然而，并非每個(gè)CFG，甚至每個(gè)典型編程語言的CFG，都滿足成為任何 k 的 LR(k) 文法所必需的條件。雖然普通編程語言似乎確實(shí)有LR(1)語法，即僅使用輸入上的一個(gè)先行符號(hào)就可以進(jìn)行移位-歸約分析的語法，但這些語法的設(shè)計(jì)相當(dāng)復(fù)雜，通常比直觀需要的語法類別多出一個(gè)數(shù)量級(jí)。

2.2.2 Yacc語法分析的生成器  

因此，在 Knuth 的論文之后，有幾次嘗試尋找使用 LR(1) 解析的方法，但要使其適用于更簡(jiǎn)單的 CFG。我們受到普林斯頓大學(xué)的一位研究生 Al Korenjak 的啟發(fā)，他的論文是關(guān)于壓縮 LR(1) 解析器的方法。我們茅塞頓開，對(duì)于通用語言，可以從一個(gè)非LR(1)的語法開始，仍然為該語法構(gòu)建一個(gè)從左向右的移位-歸約解析器。當(dāng)語法不是LR(1)形式時(shí)，在某些情況下，我們也可以使用兩種不同的產(chǎn)生式進(jìn)行歸約和移位或只進(jìn)行歸約。但是我們可以通過考慮運(yùn)算符的優(yōu)先級(jí)并在輸入中向前看一個(gè)標(biāo)記來解決實(shí)際情況中的歧義。

例2.4 考慮例2.3中所提及的情況。在處理輸入a+b*c的a+b之后，堆棧的頂部將有E+E，其中a和b之前都被簡(jiǎn)化為表達(dá)式。存在產(chǎn)生式 E → E + E，可以將 E + E 歸約成一個(gè) E，并用標(biāo)簽 E 和子式 E、+ 和 E 構(gòu)建解析樹的一個(gè)節(jié)點(diǎn)。但是 * 優(yōu)先級(jí)高于+， 我們看到 * 作為下一個(gè)輸入符號(hào)，這說明將 * 移到堆棧上是正確的。稍后，我們也移動(dòng) c 并將 c 歸約為表達(dá)式 E。此時(shí)堆棧頂部有 E + E * E。我們正確地將前三個(gè)符號(hào)歸約成 E，留下 E + E?，F(xiàn)在，將這些符號(hào)歸約成 E 是正確的，因?yàn)闆]有任何內(nèi)容輸入（或者還有其他不屬于表達(dá)式部分的輸入，例如結(jié)束語句的分號(hào)）。通過這種方式，我們將生成如圖 2 所示的語法樹。

我們?cè)谪悹枌?shí)驗(yàn)室的同事 Steve ohnson 采納了這個(gè)想法并實(shí)現(xiàn)了一個(gè)名為 Yacc的語法分析的生成器。為了幫助解決移位和歸約操作之間的歧義，或者兩個(gè)不同產(chǎn)生式的歸約之間的歧義，Yacc 根據(jù)產(chǎn)生式出現(xiàn)的順序進(jìn)行判斷。在兩個(gè)產(chǎn)生式都可以歸約的情況下，無論哪個(gè)產(chǎn)生式首先出現(xiàn)都是首選的。為了解決移位和歸約之間的沖突，假設(shè)在 Yacc 輸入文件中首先出現(xiàn)的運(yùn)算符優(yōu)先。

Yacc很快成為了編譯器實(shí)現(xiàn)的重要工具，編譯器不僅指?jìng)鹘y(tǒng)編程語言的編譯器，而且包含許多用途更有限的“小眾語言”的編譯器。與 Lex 一起，Yacc 提供了一種試驗(yàn)新語言句法結(jié)構(gòu)設(shè)計(jì)的簡(jiǎn)單方法。這兩種工具貫穿學(xué)術(shù)界整個(gè)學(xué)期的編譯器課程，學(xué)生在課程中設(shè)計(jì)并實(shí)現(xiàn)一種新的領(lǐng)域特定編程語言。

3

大規(guī)模數(shù)據(jù)抽象

我們需要幾種新的抽象來考慮最大的可用數(shù)據(jù)集和可用于操作它們的算法。第1.6節(jié)的二級(jí)存儲(chǔ)模型很重要，但也存在其他表示各種形式的并行和分布式計(jì)算的抽象。我們將在這里概述最相關(guān)的抽象。

3.1 數(shù)據(jù)的關(guān)系模型  

首先，Codd 的關(guān)系模型已被證明是處理大規(guī)模數(shù)據(jù)的核心。簡(jiǎn)而言之，數(shù)據(jù)被組織為表或關(guān)系的集合，其中兩個(gè)示例如圖 3 所示。左側(cè)是一個(gè)名為 Cities 的關(guān)系，它有兩列：City 和 State。關(guān)系的模式是它的名稱和列名列表，在本例中為 Cities (City, State)。關(guān)系本身是表格中一組行數(shù)據(jù)或元組。例如，(Toronto, Ontario)是關(guān)系 Cities 的其中一行記錄。第二種關(guān)系稱為States，它有名為 State、Country 和 Pop（該州的人口，以百萬計(jì)）的列。

圖3. 兩種關(guān)系：Cities (City, State) and States (State, Country, Pop)。

為關(guān)系模型選擇編程語言是一件趣事。Codd 可以將關(guān)系模型視為嵌入在通用語言中的基本抽象，如樹或圖。關(guān)系語言的操作是簡(jiǎn)單的導(dǎo)航步驟，例如「在給定的行和列中查找值」或「給定一行，查找下一行」。事實(shí)上，早期的數(shù)據(jù)庫抽象，例如網(wǎng)絡(luò)和層次模型，正是采用這種方法。但Codd的觀點(diǎn)是一種聲明性的抽象，隨著編程語言的發(fā)展，這種選擇一直在跟進(jìn)，有助于使關(guān)系模型成為數(shù)據(jù)庫管理的主要方法。

在最初的表述中，關(guān)系模型的編程語言被認(rèn)為是非遞歸的一階邏輯，或者等價(jià)于五種代數(shù)運(yùn)算的集合，即并集、差集、選擇、投影和連接，稱為關(guān)系代數(shù)。最后三種運(yùn)算可能比較生疏，定義如下：

• 選擇：在關(guān)系R的列名上采用條件C，并返回滿足條件C的R行。例如，如果將條件「Country=India」應(yīng)用于圖3中的關(guān)系狀態(tài)，會(huì)得到一個(gè)新的關(guān)系，它的列名為State、Country和Pop，但只包含第二行和第六行狀態(tài)。
• 投影：為一個(gè)關(guān)系獲取一組列名，并生成一個(gè)具有相同行集的新關(guān)系，但只包含獲取的列。
• 連接：接受兩個(gè)關(guān)系和一個(gè)涉及兩個(gè)關(guān)系的列名的條件 C，并通過以下方式生成一個(gè)新關(guān)系：1）考慮到每一對(duì)行，每個(gè)關(guān)系中的某兩行；2）如果這兩行中的值滿足條件 C，則將兩行合并后添加到結(jié)果關(guān)系中。

3.2 SQL抽象  

關(guān)系模型提出后不久，編程語言SQL的開發(fā)就向前邁出了一大步。在最初的表述中，SQL仍然不是圖靈完備語言。然而，它確實(shí)支持比原始關(guān)系模型更多的功能。底層數(shù)據(jù)模型支持集合和包，同一行可以出現(xiàn)多次，還可以根據(jù)一列或多列的值對(duì)關(guān)系中的行進(jìn)行排序。除了前面描述的關(guān)系代數(shù)操作符之外，SQL還支持分組和聚合，允許程序員根據(jù)一個(gè)或多個(gè)屬性中的值對(duì)關(guān)系的行進(jìn)行分組，然后對(duì)每組中一列或多列的值進(jìn)行聚合，例如求和或求平均值。

例 3.2 考慮圖 3 中的關(guān)系 States。我們可以按 Country 列的值對(duì)行進(jìn)行分組，然后對(duì)每個(gè)國(guó)家/地區(qū)的各州人口求和。結(jié)果表如圖 4 所示。

圖 4. 按Country分組并對(duì) Pop 求和。

隨著SQL的發(fā)展，更多的功能被納入標(biāo)準(zhǔn)，包括編寫遞歸程序的能力，以及在通用編程語言中調(diào)用代碼的能力。因此，原則上，SQL現(xiàn)在是圖靈完備的。但絕大多數(shù)SQL程序都沒有使用使其圖靈完備的特性，所以在實(shí)踐中，仍然有可能以一種利用許多優(yōu)化機(jī)會(huì)的方式編譯SQL，而這種優(yōu)化就是我們所說的聲明性抽象。

3.3 SQL編譯  

用 SQL 編寫的程序通常被編譯成低級(jí)語言，例如 C語言。C 代碼大量使用庫函數(shù)，例如執(zhí)行選擇或連接等操作。SQL編譯的早期階段（詞法分析和句法分析等）與任何通用語言的編譯階段相似。SQL與規(guī)范的不同之處在于代碼優(yōu)化階段（通常稱為查詢優(yōu)化）?；叵胍幌拢T如 C 這類語言的優(yōu)化必須滿足在各處保存機(jī)器指令，因此將速度提高兩倍是一個(gè)較好的優(yōu)化結(jié)果。但是SQL和關(guān)系模型的操作通常比機(jī)器指令強(qiáng)大得多。例如，語法樹的一個(gè)操作符可以連接兩個(gè)巨大的關(guān)系。

因此，與C程序或其同類程序相比，SQL程序由相對(duì)較少的步驟組成，但如果按原樣實(shí)現(xiàn)，這些步驟可能會(huì)花費(fèi)大量時(shí)間。因此，SQL 的編譯器通常會(huì)幾乎窮盡搜索等效的語法樹，從而減少幾個(gè)數(shù)量級(jí)的執(zhí)行時(shí)間。即使花費(fèi)與SQL程序大小成指數(shù)關(guān)系的時(shí)間來優(yōu)化一個(gè)只執(zhí)行一次的程序也是有意義的，因?yàn)檫@個(gè)程序通常會(huì)在較大的關(guān)系上執(zhí)行。

3.4 分布式計(jì)算抽象  

多年來，人們已經(jīng)認(rèn)識(shí)到單處理器的能力正在達(dá)到極限。為了處理越來越大的數(shù)據(jù)集，有必要開發(fā)使用多臺(tái)獨(dú)立機(jī)器的算法。許多引發(fā)我們思考的分布式計(jì)算算法的抽象已經(jīng)實(shí)現(xiàn)，并且正在被重點(diǎn)使用。

總的來說，這些抽象有一些共同的特點(diǎn)：

• 它們的數(shù)據(jù)模型是傳統(tǒng)編程語言的模型，但數(shù)據(jù)分布在許多不同的任務(wù)中，我們稱之為「計(jì)算節(jié)點(diǎn)」。實(shí)際上，多個(gè)任務(wù)可能在同一個(gè)處理器上執(zhí)行，但將這些任務(wù)視為處理器本身便于分析問題。
• 程序也用常規(guī)語言編寫，但同一程序可以在各個(gè)節(jié)點(diǎn)上同時(shí)運(yùn)行。
• 有一種設(shè)備可供節(jié)點(diǎn)與其他節(jié)點(diǎn)通信。這種通信分階段進(jìn)行，并與計(jì)算階段交替進(jìn)行。

這類抽象有幾個(gè)不同的性能指標(biāo)值得關(guān)注。顯而易見的一點(diǎn)是并行執(zhí)行所有節(jié)點(diǎn)上涉及的程序所需的掛鐘時(shí)間。但有時(shí)，瓶頸在于節(jié)點(diǎn)之間通信所需的時(shí)間，尤其當(dāng)需要在節(jié)點(diǎn)之間共享大量數(shù)據(jù)時(shí)。第三個(gè)運(yùn)行時(shí)間問題是算法的輪數(shù)（一個(gè)計(jì)算階段后接一個(gè)通信階段）。

3.5 批量同步抽象  

Valiant 的批量同步模型是一種流行的抽象，我們不再詳細(xì)討論。該模型最近在 Google 的 Pregel 系統(tǒng)的計(jì)算集群環(huán)境中得到普及，并已經(jīng)擁有了許多類似的實(shí)現(xiàn)。

在批量同步模型中，計(jì)算節(jié)點(diǎn)可以被視為完整圖的節(jié)點(diǎn)。在初始化階段，每個(gè)節(jié)點(diǎn)對(duì)其本地?cái)?shù)據(jù)執(zhí)行初始化程序，從而為其他特定節(jié)點(diǎn)生成一些消息。當(dāng)所有的計(jì)算完成后，所有的消息都被傳送到目的地。在第二輪中，所有節(jié)點(diǎn)對(duì)其傳入消息和本地?cái)?shù)據(jù)執(zhí)行「主」程序，這可能會(huì)導(dǎo)致生成額外的消息。計(jì)算結(jié)束后，這些消息被傳送到它們的目的地，第三輪開始，主程序再次在新傳入的消息上執(zhí)行。這種計(jì)算和消息傳遞的交替繼續(xù)進(jìn)行，直到在某一輪中不再生成消息。

3.6 映射歸約抽象  

映射歸約是一種抽象，已被證明是一種非常強(qiáng)大的工具，可用于創(chuàng)建并行程序，而無需程序員明確考慮并行性。谷歌的Jeff Dean 等人最初在Hadoop上實(shí)現(xiàn)，最近在Spark上的實(shí)現(xiàn)也推廣開來。此外，該模型能夠輕松支持通?；ㄙM(fèi)時(shí)間最多的關(guān)系模型操作：連接和分組/聚合，以及對(duì)大規(guī)模數(shù)據(jù)的許多其他重要操作。

映射歸約的數(shù)據(jù)模型是一組鍵值對(duì)。然而，這種意義上的「鍵」通常不是唯一的；它們只是成對(duì)的第一個(gè)組成部分。映射歸約中的程序是用一些傳統(tǒng)的編程語言編寫的，每個(gè)映射歸約作業(yè)都有兩個(gè)關(guān)聯(lián)的程序，不足為奇，它們分別稱為「映射」和「歸約」。作業(yè)的輸入是一組鍵值對(duì)。映射程序被編寫為應(yīng)用于單個(gè)鍵值對(duì)，并生成任意數(shù)量的鍵值對(duì)作為其輸出。輸出對(duì)的數(shù)據(jù)類型通常與輸入對(duì)的類型不同。由于映射獨(dú)立地應(yīng)用于每個(gè)鍵值對(duì)，所以我們可以創(chuàng)建許多任務(wù)，稱為「映射器」，每個(gè)任務(wù)都會(huì)獲取輸入對(duì)的一個(gè)子集，并將映射程序應(yīng)用于每個(gè)鍵值對(duì)。因此，映射程序可以使用盡可能多的處理器并行執(zhí)行。

映射器完成工作后，通信階段會(huì)獲取應(yīng)用于所有輸入對(duì)的映射的所有輸出，并根據(jù)鍵對(duì)它們進(jìn)行排序。也就是說，輸出鍵值對(duì)的整個(gè)集合被組織成歸約器，每個(gè)歸約器都是一個(gè)鍵，比如x，以及所有相關(guān)值的列表，也就是y的列表，這樣就有了一個(gè)輸出對(duì)（x，y）。然后我們?cè)诿總€(gè)歸約器上執(zhí)行歸約程序。由于每個(gè)歸約器都獨(dú)立于其他歸約器，我們可以將歸約器組織成任務(wù)，并在不同的處理器上運(yùn)行每個(gè)任務(wù)。整個(gè)作業(yè)的輸出是由每個(gè)歸約器生成的鍵值對(duì)集。

4

量子計(jì)算

近期，全世界對(duì)量子計(jì)算和量子編程語言興致勃勃。量子計(jì)算特別有趣，因?yàn)榱孔泳幊陶Z言中的計(jì)算模型與經(jīng)典編程語言中的計(jì)算模型大相徑庭。

故事從量子力學(xué)開始，量子力學(xué)是20世紀(jì)初期發(fā)展起來的物理學(xué)基本理論，它描述了原子和亞原子粒子尺度上的自然物理性質(zhì)。我們將介紹量子力學(xué)的基本假設(shè)，根據(jù)這些假設(shè)可以推導(dǎo)出量子力學(xué)的所有定律。從這些假設(shè)出發(fā)，我們可以導(dǎo)出量子電路的抽象，這是量子編程語言的基本計(jì)算模型之一。

4.1 量子力學(xué)的假設(shè)

復(fù)線性代數(shù)和希爾伯特空間（具有內(nèi)積的復(fù)向量空間）通常用于描述量子力學(xué)的假設(shè)。Nielsen和Chuang的著作《量子計(jì)算與量子信息：十周年紀(jì)念版》是學(xué)習(xí)這門學(xué)科的重要參考書籍。首先，讓我們回顧一下在假設(shè)中使用的復(fù)線性代數(shù)的一些基本定義。將運(yùn)算符視為作用于向量的復(fù)數(shù)矩陣會(huì)對(duì)理解很有幫助。矩陣U的厄米特共軛形式為U?，代表矩陣U的共軛轉(zhuǎn)置，即先取U的轉(zhuǎn)置，再對(duì)每個(gè)值的復(fù)數(shù)部分求反。

酉算子的概念是量子力學(xué)的核心。如果UU? = /，則運(yùn)算符U具有幺正性，其中/ 是恒等式。這意味著每個(gè)酉變換的作用都是可逆的?？赡嬉馕吨苫謴?fù)原狀，也就是說，我們可以根據(jù)輸出重構(gòu)輸入。如果U = U?，則稱算子U為厄米特算子，厄米特算子是自伴算子。

假設(shè)1：孤立物理系統(tǒng)的狀態(tài)空間可以用希爾伯特空間來建模。系統(tǒng)的狀態(tài)完全由狀態(tài)空間中的單位向量描述。

假設(shè) 1 允許我們將量子比特定義為二維狀態(tài)空間中的單位向量。量子比特是經(jīng)典計(jì)算中比特（0或1）的量子計(jì)算模擬。如果向量和用作二維希爾伯特空間的正交基，則該空間中的任意狀態(tài)向量可以寫成或。其中α和β是復(fù)數(shù)。因?yàn)?/span>是單位向量，故。

量子比特表現(xiàn)出一種稱為疊加態(tài)的量子力學(xué)的固有現(xiàn)象。與經(jīng)典計(jì)算中的比特總是0或1不同，在α和β未知的情況下，不能說量子比特肯定處于狀態(tài)或肯定處于狀態(tài)。我們只能說它是這兩種狀態(tài)的某種組合。

假設(shè)2：封閉量子系統(tǒng)的狀態(tài)從一個(gè)時(shí)刻到另一個(gè)時(shí)刻的演化可以用酉算子來描述。

有一種使用薛定諤方程來表述假設(shè)2的等效方法。但是，我們?cè)谶@里只考慮酉公式，因?yàn)樗匀坏匾隽肆孔与娐酚?jì)算模型。

假設(shè)3：為了從封閉的量子系統(tǒng)中獲取信息，我們可以對(duì)系統(tǒng)進(jìn)行測(cè)量。以某種概率返回測(cè)量結(jié)果。可能結(jié)果的概率之和為 1。測(cè)量會(huì)改變量子系統(tǒng)的狀態(tài)。

我們不會(huì)深入探討假設(shè)3的細(xì)節(jié)，但出于討論的目的，我們可以將單個(gè)量子比特的測(cè)量視為厄米特算子，它以的概率返回結(jié)果0，以的概率返回結(jié)果1。回想一下，因?yàn)?/span>是單位向量，故。測(cè)量將狀態(tài)向量坍縮至二維希爾伯特空間的兩個(gè)基向量之一。我們注意到，海森堡著名的量子力學(xué)不確定性原理可以根據(jù)復(fù)線性代數(shù)規(guī)則和假設(shè)1-3推導(dǎo)出來。

第四個(gè)假設(shè)展示了當(dāng)我們組合物理系統(tǒng)時(shí)，復(fù)合物理系統(tǒng)的狀態(tài)空間的維數(shù)如何增長(zhǎng)。

假設(shè)4：復(fù)合物理系統(tǒng)的狀態(tài)空間是組成物理系統(tǒng)的狀態(tài)空間的張量積。

假設(shè) 4 表明，如果我們將單個(gè)量子比特添加到物理系統(tǒng)，其狀態(tài)空間的維度會(huì)加倍。因此，如果我們組合n個(gè)單量子比特系統(tǒng)，通過取n個(gè)單量子比特系統(tǒng)的狀態(tài)空間的張量積，得到一個(gè)狀態(tài)空間維度是的復(fù)合系統(tǒng)。狀態(tài)空間的這種指數(shù)式增長(zhǎng)使得在經(jīng)典計(jì)算機(jī)上模擬大型量子系統(tǒng)的行為將困難重重。

4.2 量子電路

從量子力學(xué)的四個(gè)假設(shè)出發(fā)，我們可以導(dǎo)出一個(gè)稱為「量子電路」的計(jì)算模型，這是量子編程語言的基本抽象。量子電路由量子門和量子線路組成。它們類似于經(jīng)典計(jì)算中的布爾電路，但有幾個(gè)重要的區(qū)別。將量子門視為復(fù)數(shù)的正交矩陣，并將其輸出視為通過將矩陣應(yīng)用于輸入向量而獲得的向量，這對(duì)于分析很有幫助。

1）單量子比特門

單量子比特門有一條通向門的線路和一條引出門的線路。輸入線路將一個(gè)量子比特饋送到量子門。該量子門將酉變換U應(yīng)用于傳入的量子比特，并將輸出的量子比特傳送到輸出線路上。

在經(jīng)典的布爾電路中，只有一個(gè)非平凡的單位邏輯門，即布爾非門。在量子電路中，二維復(fù)希爾伯特空間中的任何酉變換都可以是單量子比特的量子門。這里介紹兩個(gè)重要的單量子比特門。

例 4.1 量子非門，通常表示為X，將量子比特映射為量子比特。從根本上說，它翻轉(zhuǎn)了二維希爾伯特空間中表示量子比特的向量系數(shù)。注意以及。

量子非門X可以用矩陣表示：

例 4.2 量子哈達(dá)瑪門表示為H，將量子比特映射成量子比特：

請(qǐng)注意恒等運(yùn)算符HH = I。

量子哈達(dá)瑪門H可用矩陣表示：

還有許多其他有用的單量子比特的量子門。

2）多量子比特門

多量子比特的量子門具有通向門的n條輸入線路和從門發(fā)出的n條輸出線路。該邏輯門由一個(gè)酉算子U組成，可以用一個(gè)的復(fù)數(shù)矩陣表示，該矩陣的行和列是正交的。

例4.3 受控非門（簡(jiǎn)稱CNOT）是一個(gè)非常有用的雙量子比特門。它有兩條輸入線和兩條輸出線，一條稱為控制線，另一條稱為目標(biāo)線。開關(guān)作用的動(dòng)作如下：如果控制線的輸入量子比特為，則目標(biāo)線上的量子比特將不變地通過；如果傳入的控制量子比特為，則翻轉(zhuǎn)目標(biāo)量子比特。在這兩種情況下，控制線的量子比特都不會(huì)發(fā)生改變。如果表示為（量子比特和的張量積），那么我們可以將CNOT 門的作用描述如下：：

3）電路

量子電路是量子計(jì)算和量子編程語言的基礎(chǔ)計(jì)算模型，是由線、量子門和測(cè)量門組成的非循環(huán)圖。因?yàn)榱孔与娐肥欠茄h(huán)的，所以不存在回路或反饋。由于邏輯或不是酉運(yùn)算符，所以線路連接在一起的地方不存在扇入。此外，在量子力學(xué)中，不可能復(fù)制未知的量子態(tài)（不可克隆定理），因此也不可能進(jìn)行扇出。

測(cè)量門將一條線路作為輸入，在狀態(tài)中引入單個(gè)量子比特，并產(chǎn)生一個(gè)概率經(jīng)典比特作為輸出，以的概率取值為0或以的概率取值為1。

我們用一個(gè)例子來結(jié)束量子電路的討論，這個(gè)例子闡釋了量子計(jì)算的一個(gè)不同尋常的特性：糾纏。

圖5 根據(jù)輸入|00\rangle生成EPR狀態(tài)的量子電路

例4.4 如圖5所示，考慮一個(gè)具有兩條輸入線路x和y的量子電路。x線路連接到哈達(dá)瑪門，哈達(dá)瑪門的輸出成為CNOT門的控制線。y線路是CNOT門的目標(biāo)線路。我們將其稱為 EPR 量子電路，以Einstein, Podolsky和Rosen名字的首字母命名，他們指出了該電路輸出狀態(tài)的奇怪特性。以下是該電路對(duì)兩個(gè)輸入量子比特的四個(gè)值的變換：

可以將量子電路的操作描述為狀態(tài)向量的序列，這些狀態(tài)向量展示了在應(yīng)用每一級(jí)門之后量子系統(tǒng)的狀態(tài)。對(duì)于圖5，將各階段獲得的狀態(tài)向量總結(jié)如下：

1）H門之前：

2）在H 門之后CNOT門之前：

3）CNOT門之后：

復(fù)合量子系統(tǒng)的狀態(tài)不能寫成其組成系統(tǒng)狀態(tài)的張量積，這稱之為糾纏態(tài)?？梢钥闯錾厦娴?EPR 輸出狀態(tài)是糾纏的。不存在兩個(gè)單量子比特狀態(tài)和使得下式成立。

糾纏在量子計(jì)算中的作用至關(guān)重要，但糾纏的物理現(xiàn)象對(duì)物理學(xué)家來說仍然是一個(gè)謎。事實(shí)上，愛因斯坦稱其為“超距離的幽靈效應(yīng)”。

4.3 量子算法

量子計(jì)算設(shè)備很可能被用作由經(jīng)典計(jì)算機(jī)控制的輔助設(shè)備。量子計(jì)算機(jī)程序通常表示為經(jīng)典計(jì)算和量子算法的混合體。量子算法經(jīng)常呈現(xiàn)為具有以下結(jié)構(gòu)的量子電路：

1） 電路開始時(shí)將所有輸入量子位設(shè)置為特定狀態(tài)，通常為。

2）電路處于疊加狀態(tài)。

3）電路通過幺正門作用于這種疊加。

4）通過測(cè)量門將經(jīng)典比特（0 和 1）作為輸出返回到控制的經(jīng)典計(jì)算機(jī)，對(duì)電路中的量子比特進(jìn)行測(cè)量。

量子計(jì)算在 1994 年迎來了飛躍式發(fā)展，當(dāng)時(shí)貝爾實(shí)驗(yàn)室的Peter Shor發(fā)表了一種在混合經(jīng)典計(jì)算機(jī)/量子計(jì)算機(jī)上分解n位整數(shù)的算法，其時(shí)間復(fù)雜度為。即使今日，也沒有可以用多項(xiàng)式時(shí)間在經(jīng)典計(jì)算機(jī)上分解整數(shù)的算法。

Shor利用經(jīng)典數(shù)論將整數(shù)分解問題簡(jiǎn)化為尋序問題。求序問題如下：給定正整數(shù)x和N，其中x<N 且x互質(zhì)于N，求最小正整數(shù)r，使得。整數(shù)r被稱為N中x的階數(shù)。例如，21中5的階數(shù)是6，因?yàn)橐?/span>成立，6是最小的正整數(shù)。

Shor設(shè)計(jì)了一種量子算法，用多項(xiàng)式數(shù)量的量子門來解決尋序問題。目前還沒有已知的算法可以在多項(xiàng)式時(shí)間內(nèi)解決經(jīng)典計(jì)算機(jī)上的尋序問題。

量子算法通常使用傳統(tǒng)計(jì)算機(jī)算法中沒有的特殊技術(shù)。例如，Shor的算法使用量子傅里葉變換作為其尋序計(jì)算的一部分。

5

未來方向

抽象對(duì)計(jì)算機(jī)科學(xué)的許多領(lǐng)域產(chǎn)生了相當(dāng)大的影響。關(guān)于計(jì)算機(jī)科學(xué)中的抽象故事還有更多的論文。以下是一些理論研究者可能會(huì)感興趣并且具有實(shí)際意義的方向。

5.1 量子未來

量子計(jì)算仍然是一個(gè)剛剛起步的領(lǐng)域。雖然量子電路可以將任意單一算子近似到任何期望的精度，但今天的量子門計(jì)算機(jī)只有50到100個(gè)可用的量子位。此外，實(shí)用的量子算法屈指可數(shù)，因此在量子計(jì)算的硬件和算法領(lǐng)域都需要做更多的工作來克服這些限制。

在理論上，許多懸而未決的問題也仍然存在。例如，如果我們可以證明不能在多項(xiàng)式時(shí)間內(nèi)在經(jīng)典計(jì)算機(jī)上分解整數(shù)的問題，那么我們將有一個(gè)量子計(jì)算機(jī)比經(jīng)典計(jì)算機(jī)更快地解決問題的示例。這只是許多尚未解決的深層理論問題之一。你可能會(huì)希望向 Aaronson 咨詢量子抽象中的算法挑戰(zhàn)列表。

目前研究人員已經(jīng)開發(fā)了許多全棧量子計(jì)算編程語言。哥倫比亞大學(xué)的博士生 Krysta Svore 表明，第 2 節(jié)中討論的編譯器架構(gòu)可以與糾錯(cuò)結(jié)合到量子計(jì)算設(shè)計(jì)工具的分層軟件架構(gòu)中。畢業(yè)后，她加入了微軟研究院，在那里她和她的同事隨后開發(fā)了 Q# 量子編程語言，它是微軟量子開發(fā)工具包的一部分。

5.2 計(jì)算機(jī)系統(tǒng)和硬件的抽象  

映射歸約和其他針對(duì)特定類型計(jì)算平臺(tái)（本例中為計(jì)算集群）的高級(jí)抽象的成功表明，其他平臺(tái)可能也有類似的抽象。例如，目前人們對(duì)無服務(wù)器計(jì)算很感興趣，其中數(shù)據(jù)僅保存在文件系統(tǒng)中，并且通過在短時(shí)間內(nèi)租用一臺(tái)或多臺(tái)服務(wù)器來完成計(jì)算。

在較小的規(guī)模上，專用硬件是一種增長(zhǎng)趨勢(shì)，并且很可能在加速對(duì)大規(guī)模數(shù)據(jù)執(zhí)行重要算法方面發(fā)揮越來越重要的作用。你可能聽說過圖形處理單元（GPU）和現(xiàn)場(chǎng)可編程門陣列（FPGA）。Plasticine 是設(shè)計(jì)的另一種用于支持高通信帶寬和并行性的芯片，可能很快就會(huì)上市。擁有與這些體系結(jié)構(gòu)相匹配的高級(jí)抽象將行之有效，因?yàn)槭褂眠@些抽象編寫的算法可以利用一種或多種芯片類型編譯成高效的實(shí)現(xiàn)。

5.3 抽象分類法  

多年來，人們發(fā)明了與編程語言處理相關(guān)的強(qiáng)大抽象，幫助編譯器設(shè)計(jì)領(lǐng)域從一門藝術(shù)轉(zhuǎn)變?yōu)橐婚T科學(xué)。但最后的論文還沒有寫完。擴(kuò)展我們?cè)?1.2 節(jié)中抽象的基本分類法以涵蓋更多編程語言和編譯器領(lǐng)域，甚至更多的計(jì)算機(jī)科學(xué)領(lǐng)域，這將大有裨益。與連續(xù)運(yùn)行的系統(tǒng)（如操作系統(tǒng)、網(wǎng)絡(luò)和互聯(lián)網(wǎng)）相關(guān)的抽象自然會(huì)包含在內(nèi)。

此外，我們希望通過數(shù)據(jù)結(jié)構(gòu)課程中組織的講座，大家能認(rèn)識(shí)到分類法的強(qiáng)大遠(yuǎn)不止如此。我們更希望研究是什么讓一種抽象比另一種更有用。例如，我們?cè)?3.1 節(jié)中提到關(guān)系模型如何自然地成為聲明性抽象，而以前的數(shù)據(jù)庫模型不適合 SQL 等語言，這為高階編程的出現(xiàn)奠定了條件。類似地，正則表達(dá)式似乎非常適合描述編程語言標(biāo)記和其他有趣的字符串集，而等價(jià)的表示法，例如 Chomsky 的 type-3 語法（CFG 的一種特殊情況）在句法分析等應(yīng)用程序中從未發(fā)現(xiàn)太多用途。可能自然會(huì)問：“為什么會(huì)這樣？”

一個(gè)有趣的新領(lǐng)域是使用機(jī)器學(xué)習(xí)來創(chuàng)建使用數(shù)據(jù)而不是用某種編程語言編寫的源程序的軟件應(yīng)用程序。從某種意義上說，機(jī)器學(xué)習(xí)是一種不涉及傳統(tǒng)編譯的軟件創(chuàng)建方式?？梢灾笇?dǎo)使用機(jī)器學(xué)習(xí)有效創(chuàng)建強(qiáng)大應(yīng)用程序的抽象將受益匪淺。

原文鏈接：

https://cacm.acm.org/magazines/2022/2/258231-abstractions-their-algorithms-and-their-compilers/fulltext

雷峰網(wǎng)(公眾號(hào)：雷峰網(wǎng))

雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。