圖靈獎得主、《龍書》作者萬字長文講解：什么是「抽象」？

編譯 | bluemin

編輯丨陳彩嫻

1

抽象

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

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

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

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

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

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

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

1.1 編譯

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

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

圖1. 抽象層和算法層

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

這可能是因為抽象2與機器層次太接近，因此具備有意義的性能指標。如果是這樣，抽象1可以繼承這些指標，為抽象1中編寫的算法提供優(yōu)質(zhì)概念。但是高級抽象通常可以在幾個不同的低級抽象中實現(xiàn)。每個低級抽象都可能提供一個完全不同的運行時間或其他度量的概念，因此在高層次上必然包含不同的算法優(yōu)度概念。

1.2 抽象的分類法

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

1.2.1. 基本抽象  

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

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

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

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

1.2.2 抽象實現(xiàn)  

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

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

1.2.3 聲明性抽象  

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

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

1.2.4 計算抽象  

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

你可能熟悉許多計算抽象，因為它們包括所有通用編程語言以及機器指令集。這種類型的其他抽象更具理論性，例如隨機存取存儲器（RAM）模型或并行隨機存取存儲器（PRAM）模型。在這里，我們將在 1.7 節(jié)討論一個強調(diào)二級存儲作用的傳統(tǒng)機器模型。我們還將討論并行計算的抽象：3.5 節(jié)中的批量同步和 3.6 節(jié)中的映射規(guī)約模型（MapReduce）。

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

1.3 對抽象空間的探索  

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

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

1. 一個全集 U。
2. 全集 U 的子集 S，初始化時，S為空。

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

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

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

請注意，字典的編程語言相當簡單，不具備圖靈機的功能，也沒有真正的算法設計概念，因為「程序」只是反映其他進程正在做什么。同樣，也沒有真正的運行時間概念，因為不清楚每個操作需要多長時間。我們可以將每個操作定義為占用單位時間，但由于我們無法控制「程序」的長度，因此這個運行時間也沒有意義。

1.4 字典的實現(xiàn)  

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

• 單元格包含值（某個全集U的成員）和指向另一個單元格的鏈接（可能為空）。
• 標頭，簡單命名為指向單元格的鏈接（可能為空）。

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

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

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

1.5 哈希抽象  

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

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

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

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

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

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

1.6 二級存儲抽象  

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

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

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

2

編譯器的抽象

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

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

2.1 正則表達式和句法分析

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

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

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

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

letter = [a-zA-Z]

digit = [0-9]

id = letter (letter+digit)*

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

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

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

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

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

貝爾實驗室在首次嘗試自動搜索相關文獻時采取了一個有趣的步驟：他們在磁帶上保存了整個貝爾實驗室圖書館的標題，并且開發(fā)了軟件來獲取關鍵字列表、找到包含這些關鍵字的文檔。然而，當給定一長串關鍵字時，搜索速度很慢，因為它每搜索一個關鍵字就會遍歷一次磁帶。

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

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

2.1.2 句法分析的生成器設計  

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

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

2.1.3 DFA的惰性評估  

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

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

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

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

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

圖2. 表達式 a + b * c 的語法樹

2.2 上下文無關文法和語法分析  

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

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

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

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

2.2.1 LR(k)語法分析  

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

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

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

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

2.2.2 Yacc語法分析的生成器  

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

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

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

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

3

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

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

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

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

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

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

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

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

3.2 SQL抽象  

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

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

圖 4. 按Country分組并對 Pop 求和。

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

3.3 SQL編譯  

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

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

3.4 分布式計算抽象  

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

總的來說，這些抽象有一些共同的特點：

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

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

3.5 批量同步抽象  

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

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

3.6 映射歸約抽象  

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

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

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

4

量子計算

近期，全世界對量子計算和量子編程語言興致勃勃。量子計算特別有趣，因為量子編程語言中的計算模型與經(jīng)典編程語言中的計算模型大相徑庭。

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

4.1 量子力學的假設

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

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

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

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

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

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

有一種使用薛定諤方程來表述假設2的等效方法。但是，我們在這里只考慮酉公式，因為它自然地引出了量子電路計算模型。

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

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

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

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

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

4.2 量子電路

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

1）單量子比特門

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

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

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

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

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

請注意恒等運算符HH = I。

量子哈達瑪門H可用矩陣表示：

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

2）多量子比特門

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

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

3）電路

量子電路是量子計算和量子編程語言的基礎計算模型，是由線、量子門和測量門組成的非循環(huán)圖。因為量子電路是非循環(huán)的，所以不存在回路或反饋。由于邏輯或不是酉運算符，所以線路連接在一起的地方不存在扇入。此外，在量子力學中，不可能復制未知的量子態(tài)（不可克隆定理），因此也不可能進行扇出。

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

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

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

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

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

1）H門之前：

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

3）CNOT門之后：

復合量子系統(tǒng)的狀態(tài)不能寫成其組成系統(tǒng)狀態(tài)的張量積，這稱之為糾纏態(tài)。可以看出上面的 EPR 輸出狀態(tài)是糾纏的。不存在兩個單量子比特狀態(tài)和使得下式成立。

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

4.3 量子算法

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

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

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

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

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

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

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

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

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

5

未來方向

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

5.1 量子未來

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

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

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

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

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

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

5.3 抽象分類法  

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

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

一個有趣的新領域是使用機器學習來創(chuàng)建使用數(shù)據(jù)而不是用某種編程語言編寫的源程序的軟件應用程序。從某種意義上說，機器學習是一種不涉及傳統(tǒng)編譯的軟件創(chuàng)建方式。可以指導使用機器學習有效創(chuàng)建強大應用程序的抽象將受益匪淺。

原文鏈接：

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

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