基于函數式語言和單體的編譯教學實驗平臺研究與實踐

宋麗華，張興元，王海濤

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

0 引 言

編譯原理主要介紹構造編譯器涉及的基本概念、理論和方法，是計算機專業核心課程。學習編譯的意義不僅在于學習編譯技術本身，使學生通過編譯過程深入了解計算機程序的行為，其更深遠的意義則在于培養“問題→形式化描述→計算機化”的問題求解習慣，培養將基礎理論和基本方法用于解決難度較大的問題、處理復雜軟件系統的設計與實現的能力[1-2]。

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

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

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

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

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

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

2 將函數式語言與單體用于編譯實驗的優勢

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

1）提升編程效率，壓縮學時需求。

函數式語言將數據表示為數學表達式，其抽象級別的提高隱蔽了內存分配和回收、指針運算等低層細節，顯著降低了出錯概率，節省程序調試時間。即使程序有錯，由于所有的數據都是具有直觀含義的數學表達式，且無需額外編程就可以顯示，查錯的工作量也大為減少。

2）算法和代碼之間有更明確的關聯映射關系，有助于學生緊密聯系理論和實踐。

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

3）支持師生對程序正確性進行討論，方便教師對學生代碼的檢查和提問。

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

3 基于函數式語言和單體構建編譯實驗平臺對課程教學改革的要求

最重要的是教學模式的變化，可以改變傳統上理論和實驗分離的教學模式，采用以代碼為中心的授課模式：用函數式程序或者程序框架代替偽代碼，課堂上圍繞代碼對算法進行討論，學生課后把代碼補全。相比偽代碼描述，代碼是嚴格的、實在的，教師可以當堂展示運行過程和結果，學生也可以反復觀察、修改、調試、運行，這就把理論教學和編程實踐無縫銜接起來。

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

上述調整還會帶來考核方式的變化，不再“一卷定終身”，也不靠幾個大實驗拿分，而是將每一個小的知識單元和代碼模塊均納入評分依據，督促學生把功夫用在平時。對每一個小模塊，教師可以圍繞代碼檢查學生對知識的理解情況，結合代碼質量打分。由于程序足夠簡潔、貼近算法本身，這樣做并不會增加過多工作量。

4 基于新型實驗平臺的教學實踐

建設基于函數式語言和單體的全新實驗平臺，需要設計一組相互銜接、難度遞增的全過程實驗，并同步完成教學內容、教學模式和考核方法的改革。

4.1 課程教學設計

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

配合實驗，需要對教學內容進行重新組織：從簡單的表達式語言開始，逐漸豐富語言功能，先介紹表達式語言的詞法、語法和語義分析，然后引入賦值、分支和循環結構，再介紹中間代碼生成、基本塊、寄存器分配等后端處理技術，最后引入函數和過程調用，介紹與其相關的語義分析和后端處理。與傳統教學內容相比，對前端詞法和語法分析部分作了適當簡化，加強了后端，并引入了指稱語義、類型推導、錯誤定位、漂亮格式打印等內容。

表1 教學內容編排與實驗設計

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

4.2 實踐效果

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

5 結 語

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