基于函數(shù)式語言和單體的編譯教學(xué)實(shí)驗(yàn)平臺(tái)研究與實(shí)踐

宋麗華，張興元，王海濤

（1.陸軍工程大學(xué) 指揮控制工程學(xué)院，江蘇 南京 210007；2.南京審計(jì)大學(xué)金審學(xué)院 信息科學(xué)與工程學(xué)院，江蘇 南京 210023）

0 引 言

編譯原理主要介紹構(gòu)造編譯器涉及的基本概念、理論和方法，是計(jì)算機(jī)專業(yè)核心課程。學(xué)習(xí)編譯的意義不僅在于學(xué)習(xí)編譯技術(shù)本身，使學(xué)生通過編譯過程深入了解計(jì)算機(jī)程序的行為，其更深遠(yuǎn)的意義則在于培養(yǎng)“問題→形式化描述→計(jì)算機(jī)化”的問題求解習(xí)慣，培養(yǎng)將基礎(chǔ)理論和基本方法用于解決難度較大的問題、處理復(fù)雜軟件系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)的能力[1-2]。

由于編譯原理課程固有的難度和實(shí)驗(yàn)復(fù)雜度，部分高校要么不開設(shè)，要么實(shí)驗(yàn)課時(shí)不足甚至不開實(shí)驗(yàn)。從提高學(xué)生理論和實(shí)踐綜合能力的角度看這確是一個(gè)遺憾。國內(nèi)外一流高校通常將編譯原理作為必修課，配套大量實(shí)驗(yàn)學(xué)時(shí)，考核上也更注重實(shí)踐，要求學(xué)生實(shí)現(xiàn)一個(gè)小型完整編譯器或關(guān)鍵組件，給學(xué)生提供充分訓(xùn)練[3-6]。目前的編譯實(shí)驗(yàn)基本上使用C、Java、Python 等命令式語言實(shí)現(xiàn)，導(dǎo)致一方面學(xué)生編程時(shí)需要采用復(fù)雜的內(nèi)部數(shù)據(jù)結(jié)構(gòu)處理大量細(xì)節(jié)問題，另一方面最終呈現(xiàn)的代碼與算法理論描述在形式上有比較大的差別，學(xué)生很可能只見樹木（程序）不見森林（思想），最后結(jié)果往往是理論和實(shí)驗(yàn)的彼此脫節(jié)。

1 函數(shù)式語言及其上面的單體編程技術(shù)

與廣為熟知的命令式語言（Imperative Language）相比，函數(shù)式語言（Functional Language）（如 ML、Ocaml、Haskell、Lisp）代表一種不同的程序設(shè)計(jì)“范型（paradigm）”。后者是人們對(duì)前者進(jìn)行研究的過程中，為了準(zhǔn)確而簡潔地表達(dá)程序的語義而提出的。函數(shù)式語言實(shí)質(zhì)上是數(shù)學(xué)語言的子語言，其中的數(shù)據(jù)表示為數(shù)學(xué)表達(dá)式，程序表示為數(shù)學(xué)中的等式，計(jì)算則體現(xiàn)為用程序中的等式對(duì)數(shù)據(jù)進(jìn)行化簡。對(duì)編程者來說，使用函數(shù)式語言編寫程序就像在做數(shù)學(xué)題，并且只需要列公式，結(jié)果將自動(dòng)得出。

以ML 為例，函數(shù)式程序相比C 和Python更為簡潔，它屏蔽了指針、內(nèi)存分配等硬件相關(guān)的低層細(xì)節(jié)，程序代碼更接近于算法的抽象描述。此外，作為解釋型語言，ML 不需安排專門的打印語句即可自動(dòng)顯示結(jié)果。

單體（Monad）是函數(shù)式程序設(shè)計(jì)中的一種“構(gòu)件”技術(shù)，被稱為“可編程的分號(hào)”[7]。通過單體上的組合算子，小的計(jì)算步驟可以組合起來構(gòu)成大的計(jì)算步驟，不斷積累構(gòu)成最終的大程序[8]。

單體概念體現(xiàn)了函數(shù)式語言對(duì)“計(jì)算步驟”的刻畫，對(duì)“計(jì)算步驟”觀察角度不同產(chǎn)生了不同的單體定義，常見的有狀態(tài)單體、環(huán)境單體、異常處理單體、continuation 單體等。狀態(tài)單體將對(duì)狀態(tài)的修改看作“計(jì)算步驟”的副作用，通過Bind 算子把副作用按照計(jì)算步驟執(zhí)行順序從前往后傳遞。Bind 算子在隱式傳遞狀態(tài)的同時(shí)，還向后一個(gè)步驟傳遞前一個(gè)步驟的計(jì)算結(jié)果，這一巧妙設(shè)計(jì)帶來極大的靈活性，促使程序員在更高抽象層次思考問題，把注意力集中在各個(gè)計(jì)算步驟內(nèi)部，避免為中間結(jié)果、局部變量、接口之類的細(xì)節(jié)分神。

2 將函數(shù)式語言與單體用于編譯實(shí)驗(yàn)的優(yōu)勢

與命令式語言相比，使用函數(shù)式語言和單體技術(shù)進(jìn)行編譯實(shí)驗(yàn)，不僅可以屏蔽繁雜的低層實(shí)現(xiàn)細(xì)節(jié)，在接近算法原理級(jí)別的抽象層次上編程，還可以在相當(dāng)程度上減少實(shí)驗(yàn)工作量、壓縮學(xué)時(shí)需求。實(shí)踐表明，大約可以在60～80 學(xué)時(shí)內(nèi)配合課程進(jìn)度實(shí)現(xiàn)編譯全過程實(shí)驗(yàn)，每個(gè)學(xué)生最終完成3 000 行左右ML 代碼，實(shí)現(xiàn)一個(gè)具備基本功能的完整編譯器。這對(duì)很多希望加強(qiáng)實(shí)驗(yàn)環(huán)節(jié)但學(xué)時(shí)配置偏低的學(xué)校而言是一個(gè)可參考的解決方案。

1）提升編程效率，壓縮學(xué)時(shí)需求。

函數(shù)式語言將數(shù)據(jù)表示為數(shù)學(xué)表達(dá)式，其抽象級(jí)別的提高隱蔽了內(nèi)存分配和回收、指針運(yùn)算等低層細(xì)節(jié)，顯著降低了出錯(cuò)概率，節(jié)省程序調(diào)試時(shí)間。即使程序有錯(cuò)，由于所有的數(shù)據(jù)都是具有直觀含義的數(shù)學(xué)表達(dá)式，且無需額外編程就可以顯示，查錯(cuò)的工作量也大為減少。

2）算法和代碼之間有更明確的關(guān)聯(lián)映射關(guān)系，有助于學(xué)生緊密聯(lián)系理論和實(shí)踐。

命令式語言抽象級(jí)別低，程序中充斥大量與主體編程思想無關(guān)的低層操作細(xì)節(jié)，很容易將主體邏輯淹沒，難以看出原理和算法的脈絡(luò)，而函數(shù)式語言的抽象級(jí)別與各種形式化的定義和算法相同，用函數(shù)式語言和單體書寫的程序簡潔、可讀性很強(qiáng)，是這些定義和算法的嚴(yán)格形式化描述，但同時(shí)又是可以執(zhí)行的。這就使得學(xué)生可以方便地對(duì)算法進(jìn)行實(shí)驗(yàn)，通過反復(fù)的實(shí)驗(yàn)深刻理解背后思想原理。不僅如此，免于繁瑣編程細(xì)節(jié)還意味著，學(xué)生可以專注于思考更為重要的問題，即怎樣利用基本原理去解決編譯各個(gè)階段所出現(xiàn)的各種復(fù)雜工程問題。只要想法足夠具體，就能很快實(shí)現(xiàn)為程序，用程序的執(zhí)行檢驗(yàn)想法的可行性，想法中存在的偏差和漏洞也能及時(shí)暴漏出來。

3）支持師生對(duì)程序正確性進(jìn)行討論，方便教師對(duì)學(xué)生代碼的檢查和提問。

為貼切地表示各個(gè)具體計(jì)算問題中的數(shù)據(jù)，程序員可以使用函數(shù)式語言特有的“數(shù)據(jù)類型”功能歸納定義新的數(shù)據(jù)類型，遞歸實(shí)現(xiàn)這些類型上的計(jì)算。編譯器構(gòu)造過程中的抽象語法樹、中間代碼、機(jī)器指令等都可以表示為歸納定義數(shù)據(jù)類型，而語法分析、類型檢查、中間代碼生成、基本塊劃分、表達(dá)式化簡等模塊可實(shí)現(xiàn)這些數(shù)據(jù)類型上的遞歸程序。這就使得師生可以方便地使用歸納法對(duì)這些程序的正確性進(jìn)行討論。由于程序足夠明晰簡潔，清晰地體現(xiàn)了算法脈絡(luò)，教師可以隨堂對(duì)學(xué)生代碼進(jìn)行檢查和提問，確認(rèn)學(xué)生對(duì)程序及其背后原理的掌握程度，及時(shí)發(fā)現(xiàn)其認(rèn)知中的錯(cuò)誤。這種檢查還能有效地抑制不良行為，不必單純依賴事后測試或是代碼克隆檢測[9-10]。

3 基于函數(shù)式語言和單體構(gòu)建編譯實(shí)驗(yàn)平臺(tái)對(duì)課程教學(xué)改革的要求

最重要的是教學(xué)模式的變化，可以改變傳統(tǒng)上理論和實(shí)驗(yàn)分離的教學(xué)模式，采用以代碼為中心的授課模式：用函數(shù)式程序或者程序框架代替?zhèn)未a，課堂上圍繞代碼對(duì)算法進(jìn)行討論，學(xué)生課后把代碼補(bǔ)全。相比偽代碼描述，代碼是嚴(yán)格的、實(shí)在的，教師可以當(dāng)堂展示運(yùn)行過程和結(jié)果，學(xué)生也可以反復(fù)觀察、修改、調(diào)試、運(yùn)行，這就把理論教學(xué)和編程實(shí)踐無縫銜接起來。

采用以代碼為中心的教學(xué)模式，教學(xué)內(nèi)容設(shè)計(jì)與組織方面也要相應(yīng)調(diào)整。內(nèi)容編排上應(yīng)綜合考慮理論知識(shí)的前后銜接和代碼實(shí)現(xiàn)的完整性與獨(dú)立性。以每一周課時(shí)或每一小規(guī)模知識(shí)單元對(duì)應(yīng)一個(gè)相對(duì)完整的程序模塊為宜，如線性化、基本塊劃分、算術(shù)指令化簡等，使學(xué)生及時(shí)消化知識(shí)并將之應(yīng)用于實(shí)際問題求解。如果單元粒度過粗，或者理論授課與編程實(shí)踐脫節(jié)，都將影響教學(xué)實(shí)效。這種教學(xué)內(nèi)容編排無疑將使課程重心后移，因?yàn)橹虚g代碼生成及后續(xù)各階段的編程工作量相對(duì)較大，而詞法和語法分析部分理論講解多?？紤]到詞法和語法分析技術(shù)已非常成熟，有自動(dòng)生成工具，而自動(dòng)機(jī)、文法等知識(shí)點(diǎn)與計(jì)算理論、形式語言和自動(dòng)機(jī)等課程重疊，因此適當(dāng)簡化這些內(nèi)容、突出后續(xù)各個(gè)階段也是合理之舉，畢竟后端仍然是編譯技術(shù)的研究熱點(diǎn)。

上述調(diào)整還會(huì)帶來考核方式的變化，不再“一卷定終身”，也不靠幾個(gè)大實(shí)驗(yàn)?zāi)梅?，而是將每一個(gè)小的知識(shí)單元和代碼模塊均納入評(píng)分依據(jù)，督促學(xué)生把功夫用在平時(shí)。對(duì)每一個(gè)小模塊，教師可以圍繞代碼檢查學(xué)生對(duì)知識(shí)的理解情況，結(jié)合代碼質(zhì)量打分。由于程序足夠簡潔、貼近算法本身，這樣做并不會(huì)增加過多工作量。

4 基于新型實(shí)驗(yàn)平臺(tái)的教學(xué)實(shí)踐

建設(shè)基于函數(shù)式語言和單體的全新實(shí)驗(yàn)平臺(tái)，需要設(shè)計(jì)一組相互銜接、難度遞增的全過程實(shí)驗(yàn)，并同步完成教學(xué)內(nèi)容、教學(xué)模式和考核方法的改革。

4.1 課程教學(xué)設(shè)計(jì)

課程共劃分20 個(gè)實(shí)驗(yàn)內(nèi)容（見表 1），覆蓋編譯器構(gòu)造全程，全部使用ML 和狀態(tài)單體實(shí)現(xiàn)。實(shí)驗(yàn)1—16 為基本實(shí)驗(yàn)，內(nèi)容相對(duì)簡單或提供代碼框架；實(shí)驗(yàn)17—20 是高階實(shí)驗(yàn)，難度和工作量均有明顯提升。全部代碼量（含提供的代碼）約為3 000 行。各模塊完成后將實(shí)現(xiàn)一個(gè)完整的命令式語言（不支持指針、數(shù)組等復(fù)雜數(shù)據(jù)結(jié)構(gòu)）編譯器。

配合實(shí)驗(yàn)，需要對(duì)教學(xué)內(nèi)容進(jìn)行重新組織：從簡單的表達(dá)式語言開始，逐漸豐富語言功能，先介紹表達(dá)式語言的詞法、語法和語義分析，然后引入賦值、分支和循環(huán)結(jié)構(gòu)，再介紹中間代碼生成、基本塊、寄存器分配等后端處理技術(shù)，最后引入函數(shù)和過程調(diào)用，介紹與其相關(guān)的語義分析和后端處理。與傳統(tǒng)教學(xué)內(nèi)容相比，對(duì)前端詞法和語法分析部分作了適當(dāng)簡化，加強(qiáng)了后端，并引入了指稱語義、類型推導(dǎo)、錯(cuò)誤定位、漂亮格式打印等內(nèi)容。

表1 教學(xué)內(nèi)容編排與實(shí)驗(yàn)設(shè)計(jì)

課程采用以代碼為中心的授課模式，課堂在完成理論講解后即給出相關(guān)ML 類型定義和代碼框架，由學(xué)生在課后完成實(shí)驗(yàn)內(nèi)容，不安排專門的實(shí)驗(yàn)課時(shí)。課程成績以平時(shí)完成的實(shí)驗(yàn)作為評(píng)定依據(jù)，通過平時(shí)隨機(jī)抽查、課終答辯等手段確保學(xué)生對(duì)原理和程序設(shè)計(jì)思想的掌握，同時(shí)抑制代碼克隆等不良行為。

4.2 實(shí)踐效果

在當(dāng)前人才培養(yǎng)方案中，編譯原理課程為56 學(xué)時(shí)，開設(shè)時(shí)間是大三（上）學(xué)期。作為其預(yù)修課程，在大二（下）學(xué)期開設(shè)函數(shù)式程序設(shè)計(jì)（36 學(xué)時(shí)），教授ML 語言和單體編程技術(shù)。目前已經(jīng)完成的兩輪教學(xué)實(shí)踐取得了比較好的效果，學(xué)習(xí)積極性明顯提升，90%學(xué)生能完成基本實(shí)驗(yàn)，約1/4 學(xué)生完成了高階實(shí)驗(yàn)，獲得“頂峰體驗(yàn)”。相對(duì)課內(nèi)時(shí)間，學(xué)生平均需要投入3 倍以上的課外時(shí)間用于消化學(xué)習(xí)內(nèi)容和編程，其編程能力比往屆學(xué)生有了明顯的、普遍的提高。優(yōu)秀學(xué)生感覺自己收獲很大、學(xué)得扎實(shí)，很多學(xué)生反映用ML 和單體編程比C 方便。

5 結(jié) 語

編譯原理介紹編譯器涉及的基本概念、理論和方法，使得學(xué)生深入了解計(jì)算機(jī)程序的行為，培養(yǎng)“問題、形式化描述、計(jì)算機(jī)化”的問題求解習(xí)慣和解決復(fù)雜工程問題的能力。課程難度大、實(shí)驗(yàn)復(fù)雜耗時(shí)，而目前普遍采用的命令式語言實(shí)驗(yàn)環(huán)境，更是加劇了這一傾向，將學(xué)生精力消耗在編程細(xì)節(jié)上，難以自覺建構(gòu)理論和代碼之間的關(guān)聯(lián)，造成理論實(shí)踐脫節(jié)?；诤瘮?shù)式語言和單體編程技術(shù)的新型編譯實(shí)驗(yàn)環(huán)境中，函數(shù)式語言抽象級(jí)別與數(shù)學(xué)語言接近，單體化函數(shù)式程序簡潔、清晰，與算法之間有清楚的對(duì)應(yīng)關(guān)系，其屏蔽低層細(xì)節(jié)的特點(diǎn)還有助于提高編程效率，緩解學(xué)時(shí)壓力。采用新型實(shí)驗(yàn)平臺(tái)在教學(xué)模式、教學(xué)內(nèi)容組織、考核方式等方面都將產(chǎn)生同步的改革需要。已在應(yīng)用的以ML 語言和單體編程平臺(tái)為中心的改革方案，在過去兩年的教學(xué)實(shí)踐中取得了較好效果。