# 小型函数式编程语言的设计与实现模式 > 从70行CoC到3万行MicroHs，解析玩具语言的结构化构造与解释器工程路径，为开发者提供可落地的参数化实现指南。 ## 元数据 - 路径: /posts/2026/02/21/design-and-implementation-patterns-of-miniature-functional-programming-languages/ - 发布时间: 2026-02-21T00:00:00+08:00 - 分类: [compilers](/categories/compilers/) - 站点: https://blog.hotdry.top ## 正文 在编程语言的世界里，小型实现往往蕴含着最深刻的洞见。从两个组合子构成的 Iota，到 340 字节的 milliForth，再到能够自举的完整 Haskell 编译器 MicroHs，这些微型语言不仅仅是玩具，更是理解计算本质的钥匙。Taylor Troesh 在其"Lil' Fun Langs"项目中系统整理了从 70 行到 3 万行的各类小型函数式编程语言实现，为我们勾勒出一幅完整的微型语言工程图谱。 ## 极简主义的极限：70 行到 500 行的超紧凑实现 在能力与体积的比拼上，一些项目达到了令人惊叹的程度。Hirrolot 的 CoC 实现仅用约 70 行 OCaml 代码就实现了完整的 Calculus of Constructions 类型系统，包括双向类型检查、依赖函数类型和 type-in-type 宇宙。这是 lambda 立方体顶端的类型论，却只需要几十行代码即可运行。Harrop MiniML 则展示了另一种极端——利用 Camlp4 解析器和 OCaml 的 LLVM 绑定，在约 100 行代码内完成了一个面向原生代码的 ML 子集编译器，当然它缺少闭包和垃圾回收这些「奢侈品」。 进入 300 行量级，Algorithm W 成为 Hindley-Milner 类型推导的经典教学实现。这个约 300 行的 Haskell 程序逐步展示了类型推断的核心算法，几乎是所有后续类型系统学习的起点。tomprimozic 的 type-systems 仓库则更进一筹，在约 300 行 OCaml 中同时实现了基本的 Algorithm W、行多态性（row polymorphism）和 HMF——后者实现了首次类多态性的部分推导。THIH（Typing Haskell in Haskell）更是在 429 行核心 Haskell 代码中完整实现了 Haskell 98 的全部类型系统，包括种类、限定类型、类型类、模式匹配类型和默认规则——这相当于把 Hugs 类型检查器的 90 多页 C 代码浓缩到一个数量级的 Haskell 中。 ## 功能完备的分水岭：1000 行到 3000 行 从 500 行到 2000 行是功能从「教学演示」走向「实际可用」的关键跃迁。PLZoo 的 poly 实现了惰性纯函数式语言的多态性，约 500 行 OCaml 代码即可支撑完整的参数多态和 HM 推断。EYG（Eat Your Greens）则用约 500 行 Gleam 代码实现了一个完整解释器，包含行类型推断、代数效应作为唯一的 FFI 机制，以及闭包序列化——函数可以被发送到其他机器上执行。TinyML 在不到 700 行 Standard ML 代码中塞入了词法分析器、解析器、解释器和完整的 HM 类型检查器，可能是最小但真正完整的多态类型推断实现。 2000 行是一个重要的里程碑。MinCaml 用约 2000 行 OCaml 代码实现了完整的后端编译器，包括类型推断、闭包转换、尾调用优化、内联展开、常量折叠和图着色寄存器分配。它可以编译到 SPARC、PowerPC 和 x86 汇编，生成的代码在基准测试中与 GCC 和 ocamlopt 的差距在 2 倍以内——这是能力与代码量比值的黄金标准。Ben Lynn 的编译器更为惊人：约 2000 行 Haskell 加 350 行 C，通过约 20 个渐进式自举阶段，最终实现了类型推断、类型类、代数数据类型、模式匹配、守卫、where 子句、monadic I/O、模块和布局解析——几乎覆盖了 Haskell 98 的全部功能。 进入 3000 行以上，1ML 将 ML 的核心与模块层统一为单一语言，模块是一等值、类型是值、函子是普通函数，约 3000 到 5000 行 OCaml 代码实现了这一概念。mlml 和 AQaml 则展示了自举的路径——前者约 3000 到 5000 行实现了一个面向 x86-64 的自托管 OCaml 子集编译器，后者约 5000 到 8000 行增加了记录、变体、引用和垃圾回收。MicroHs 是这个量级的巅峰：约 15000 到 30000 行代码实现了一个完整的 Haskell 子集编译器，包括类型类、do 推导、deriving、记录语法、重载字面量、模块，并且可以仅用 C 编译器自举——这是小型语言工程能力的极限证明。 ## 特性实现的工程化参数 小型函数式语言的特性实现存在清晰的工程化路径。整型算术约需 50 行代码，涉及解析器、代码生成和 MinCaml 风格的实现。浮点数约需 100 行，需要 SSE/NEON 代码生成。布尔值和条件分支约 50 行，这是所有语言的共性基础。Let 绑定约 30 行，包括解析器和规范化。一等函数和闭包约 200 行，需要闭包转换和运行时支持。递归函数约 50 行，涉及类型推断中的出现检查。Tuple 和数组各约 100 行，后者需要运行时边界检查。 类型系统是复杂度的主要来源。单态类型推断约 100 行基于统一算法；多态 Hindley-Milner 推断约 300 行，需要泛化和实例化。代数数据类型约 200 到 400 行，包括解析器、类型检查器和运行时标签。基本模式匹配约 200 行，需要穷尽性检查；优化版本约 400 到 600 行，实现 Maranget 算法。类型类约 500 到 2000 行，涉及字典传递和实例解析。基础模块约 500 到 1000 行，高级函子和签名约 2000 到 5000 行。行多态约 300 到 800 行，需要扩展统一。代数效应约 500 到 1500 行，需要效应类型和运行时。惰性求值约 300 到 500 行，需要 thunk 和记忆化运行时。 ## 实践指引：如何选择你的起点 构建小型函数式语言的路径取决于你的目标。如果目标是理解类型推断的核心理念，从 Algorithm W 或 PLZoo poly 开始，约 300 到 500 行代码即可触及 HM 的精髓。如果目标是完整的语言实现，MinCaml 是最佳起点——它展示了从解析到汇编的完整编译流程，且代码量控制在 2000 行以内。如果目标是自举和底层控制，Ben Lynn 的编译器展示了如何用 C 运行时加渐进式自举构建完整功能集。 选择宿主语言时存在有趣的规律：OCaml 是最常见的选择，兼具函数式特性和接近 C 的性能；Haskell 在类型系统研究中占主导地位，其类型类机制本身就是强大的元编程工具；TypeScript/JavaScript 适合面向 Web 的实现；Rust 则是现代编译器的新兴选择，配合 Cranelift 实现原生代码生成。宿主语言的选择往往决定了目标语言的特性——例如用 Racket 宏实现的 Hackett 展示了「类型即宏」的可能性。 小型函数式编程语言的魅力在于它们证明了「计算」这个概念可以以多种精炼的方式表达。从几十行的类型论实现到能够自举的完整编译器，这些项目不仅仅是技术演示，更是对编程语言本质的探索。对于想要理解编译器或构建领域特定语言的开发者而言，这片「微型语言动物园」提供了取之不尽的灵感和可复制的工程模式。 资料来源：taylor.town/scrapscript-000 ## 同分类近期文章 ### [C# 15 联合类型：穷尽性模式匹配与密封层次设计](/posts/2026/04/08/csharp-15-union-types-exhaustive-pattern-matching/) - 日期: 2026-04-08T21:26:12+08:00 - 分类: [compilers](/categories/compilers/) - 摘要: 深入分析 C# 15 联合类型的语法设计、穷尽性匹配保证及其与密封类层次结构的工程权衡。 ### [LLVM JSIR 设计解析：面向 JavaScript 的高层 IR 与 SSA 构造策略](/posts/2026/04/08/jsir-javascript-high-level-ir/) - 日期: 2026-04-08T16:51:07+08:00 - 分类: [compilers](/categories/compilers/) - 摘要: 深度解析 LLVM JSIR 的设计动因、SSA 构造策略以及在 JavaScript 编译器工具链中的集成路径，为前端工具链开发者提供可落地的工程参数。 ### [JSIR：面向 JavaScript 的高级 IR 与碎片化解决之道](/posts/2026/04/08/jsir-high-level-javascript-ir/) - 日期: 2026-04-08T15:51:15+08:00 - 分类: [compilers](/categories/compilers/) - 摘要: 解析 LLVM 社区推进的 JSIR 如何通过 MLIR 实现无源码丢失的往返转换，并终结 JavaScript 工具链碎片化困境。 ### [JSIR：面向 JavaScript 的高层中间表示设计实践](/posts/2026/04/08/jsir-high-level-ir-for-javascript/) - 日期: 2026-04-08T10:49:18+08:00 - 分类: [compilers](/categories/compilers/) - 摘要: 深入解析 Google 推出的 JSIR 如何利用 MLIR 框架实现 JavaScript 源码的高保真往返，并探讨其在反编译与去混淆场景的工程实践。 ### [沙箱JIT编译执行安全：内存隔离机制与性能权衡实战](/posts/2026/04/07/sandboxed-jit-compiler-execution-safety/) - 日期: 2026-04-07T12:25:13+08:00 - 分类: [compilers](/categories/compilers/) - 摘要: 深入解析受控沙箱中JIT代码的内存安全隔离机制，提供工程化落地的参数配置清单与性能优化建议。