萬字長文講解:什麼是「抽象」?

語言: CN / TW / HK

編譯 | 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 S QL抽象  

關係模型提出後不久,程式語言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