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

編譯 | bluemin

編輯丨陳彩嫻

1

抽象

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

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

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

計算機科學中的「抽象」往往包含以下內容：

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

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

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

1.1 編譯

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

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

圖1. 抽象層和算法層

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

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

1.2 抽象的分類法

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

1.2.1. 基本抽象  

與所有抽象一樣，基本抽象由數據模型和操作組成。這些抽象通常被認為是在面向對象編程語言中實現的抽象數據類型。但是基本抽象沒有操作的具體實現，也沒有表示數據的特定數據結構。人們也可以將這些抽象比作 Java 中的接口，但與接口不同的是，這些抽象對它們的操作具有預期的含義，而不僅僅表示操作的名稱。

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

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

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

1.2.2 抽象實現  

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

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

1.2.3 聲明性抽象  

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

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

1.2.4 計算抽象  

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

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

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

1.3 對抽象空間的探索  

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

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

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將是一組標識符，在程序中的每個點上都有定義好的含義。然而對于符號表，需要將數據附加到每個標識符上，例如它定義的數據類型和出現的嵌套塊的級別（以便我們可以區分具有相同名稱的標識符）。當編譯器找到一個聲明時，它會將聲明的標識符插入集合S。當它到達程序或函數的末尾時，它會刪除與該程序塊關聯的標識符。在程序中使用標識符時，編譯器會查找該標識符并檢索其類型和其他必要信息。

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

1.4 字典的實現  

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

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

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

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

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

1.5 哈希抽象  

哈希的數據模型包括以下內容：

• 全集 U。
• 哈希桶數 B，從 0 到 B-1 編號。
• 從 U 到 {0,1，…，B–1} 的哈希函數 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) 執行三個操作中的某一個。

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

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

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

1.6 二級存儲抽象  

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

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

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

2

編譯器的抽象

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

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

2.1 正則表達式和句法分析

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

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

編譯器構造方面的一大進步是創建了句法分析的生成器，一個像Lex這樣的程序，將標記的描述作為輸入，生成一個程序，將源程序分解為標記，并返回與源程序對應的標記序列。使Lex得以應用的抽象是正則表達式。像Lex這樣使用正則表達式抽象的系統使用了許多有用的速記，使編寫正則表達式更為簡單，但不會更改可以在此抽象中定義的字符串集。

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

letter = [a-zA-Z]

digit = [0-9]

id = letter (letter+digit)*

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

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

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

2.1.1 Lex程序產生之前：書目檢索

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

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

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

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

2.1.2 句法分析的生成器設計  

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

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

2.1.3 DFA的惰性評估  

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

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

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

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

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

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

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

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

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

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

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

2.2.1 LR(k)語法分析  

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

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

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

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

2.2.2 Yacc語法分析的生成器  

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

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

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

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

3

大規模數據抽象

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

3.1 數據的關系模型  

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

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

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

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

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

3.2 SQL抽象  

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

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

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

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

3.3 SQL編譯  

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

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

3.4 分布式計算抽象  

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

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

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

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

3.5 批量同步抽象  

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

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

3.6 映射歸約抽象  

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

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

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

4

量子計算

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

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

4.1 量子力學的假設

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

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

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

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

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

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

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

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

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

第四個假設展示了當我們組合物理系統時，復合物理系統的狀態空間的維數如何增長。

假設4：復合物理系統的狀態空間是組成物理系統的狀態空間的張量積。

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

4.2 量子電路

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

1）單量子比特門

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

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

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

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

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

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

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

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

2）多量子比特門

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

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

3）電路

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

測量門將一條線路作為輸入，在狀態中引入單個量子比特，并產生一個概率經典比特作為輸出，以的概率取值為0或以的概率取值為1。

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

圖5 根據輸入|00\rangle生成EPR狀態的量子電路

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

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

1）H門之前：

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

3）CNOT門之后：

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

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

4.3 量子算法

量子計算設備很可能被用作由經典計算機控制的輔助設備。量子計算機程序通常表示為經典計算和量子算法的混合體。量子算法經常呈現為具有以下結構的量子電路：

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

2）電路處于疊加狀態。

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

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

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

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

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

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

5

未來方向

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

5.1 量子未來

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

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

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

5.2 計算機系統和硬件的抽象  

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

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

5.3 抽象分類法  

多年來，人們發明了與編程語言處理相關的強大抽象，幫助編譯器設計領域從一門藝術轉變為一門科學。但最后的論文還沒有寫完。擴展我們在 1.2 節中抽象的基本分類法以涵蓋更多編程語言和編譯器領域，甚至更多的計算機科學領域，這將大有裨益。與連續運行的系統（如操作系統、網絡和互聯網）相關的抽象自然會包含在內。

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

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

原文鏈接：

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

雷峰網(公眾號：雷峰網)