基于函数式语言和单体的编译教学实验平台研究与实践

宋丽华，张兴元，王海涛

（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 结 语

编译原理介绍编译器涉及的基本概念、理论和方法，使得学生深入了解计算机程序的行为，培养“问题、形式化描述、计算机化”的问题求解习惯和解决复杂工程问题的能力。课程难度大、实验复杂耗时，而目前普遍采用的命令式语言实验环境，更是加剧了这一倾向，将学生精力消耗在编程细节上，难以自觉建构理论和代码之间的关联，造成理论实践脱节。基于函数式语言和单体编程技术的新型编译实验环境中，函数式语言抽象级别与数学语言接近，单体化函数式程序简洁、清晰，与算法之间有清楚的对应关系，其屏蔽低层细节的特点还有助于提高编程效率，缓解学时压力。采用新型实验平台在教学模式、教学内容组织、考核方式等方面都将产生同步的改革需要。已在应用的以ML 语言和单体编程平台为中心的改革方案，在过去两年的教学实践中取得了较好效果。