kamet | 基于 LLVM 的编程语言的实现

摘要

本文阐述了一门基于 LLVM 的编程语言的实现过程，分析并解决了多个实现难点，基于实际问题在现有的知识上进行拓展并得出更好的解决方案和理论知识，进而对编译原理获得更加深入的认识。

动机

Kotlin 是捷克软件开发公司 JetBrains 开发的编程语言，在语法简洁且富有拓展性的同时拥有（相对于 Scala）较快的编译速度，并在 2017 年的 Google I/O 大会上宣布成为 Android 的官方语言。尽管诸多优点使其备受开发人员欢迎，但由于其在设计之初便是一种 JVM 语言，其许多特性都表现出在简洁性和 JVM 兼容性上的矛盾：伴生对象 Companion Object 与 @JvmStatic 等注释，以及由 JVM 引入的“假”范型和单一继承所造成的诸多问题。

反观另一门新兴的语言 Rust，被认为是一种同时兼有低级语言和高级语言优点的语言。其在内存管理上几乎是独创了一套基于内存所有权和生命期的机制，超越了 C/C++ 的由程序员手动管理的内存安全和 JVM 安全但较为低效的自动内存回收：Rust 使得程序员有一套优雅的机制来在编译期实现内存安全，但也正是因为这一系列特性在一定方面上的复杂性，入门和掌握这门语言对大多数程序员并不简单；同时由于其不可避免地要与底层交互，由此引入了 unsafe 关键字，一定程度上又降低了其可读性。相比于 Kotlin，Rust 的设计良好，但并不容易入门。

由此我们引出问题，能否设计一种语言，兼有上面两者的大多数优点？

语言规范

对于这一种新的 使用 Kotlin 编写的 语言：kamet，我们决定挑选 Kotlin 和 Rust 的部分特性，包括：

• Kotlin 的大部分关键字
• Rust 的 trait
• …

kamet 被设计为一种底层语言，不基于虚拟机。在多平台兼容性这一点上，我们选择了 LLVM Compiler Infrastructure 这一编译器后端：这使得我们不必把大多数精力放在与语言本身无关的后端编译与优化身上。

语言实现

词法分析

在词法分析上我们使用了基于有限状态决策自动机 Finite Automaton 的一套分析方法。首先，我们根据识别 kamet 语言所需的所有 Token 构造了两个 NFA（分别对应顶层的分析状态和字符串中的状态），然后使用子集构造法将其转换为 DFA，并对其进行节点压缩：

但一个 DFA 只能解决“是否匹配”的问题，而不能解决“在何处匹配”的问题。为此，我们在 DFA 上做字符串匹配时记录 lastIndex，即最后一次匹配的位置，然后在失配时跳转到 lastIndex 并调用相关 action 从而实现贪婪匹配。对此过程施以类似 AC 自动机建立 Trie 图的想法是不现实的，尽管这能将期望的时间复杂度降至严格线性，但造成的空间代价是不可预料的。据粗略调查，著名的 JVM 平台上的词法分析生成器 jflex 采用的就是我们使用的方法。

语法分析

我们使用了递归下降分析法（LR(1)）来解析 kamet 语言。我们简单定义了如下语法：

• 二元运算符 Binary Operator：+、-、*、/、%、==、!=、<、<=、>、>=、<<、>>、&&、||、&、|、^、=、.、as
• 二元赋值运算符 Assigning Binary Operator：+=、-=、*=、/=、%=、&=、|=、^=、<<=、>>=
• 一元运算符 Unary Operation：-、~、!、++、--、*、&、delete
• 属性 Attributes：#[[Identifier]((Identifier) ...) ...]
• 变量定义 Var Declaration：val/var [Identifier](: [Type]) = [Expression] 定义一个有初始值的变量或 val/var [Identifier]: [Type] 来定义一个内存未定义的变量
• 常量定义 Let Declaration：let [Identifier](: Type) = [Expression]
• 类型强转 Explicit Cast：[Expression] as [Type]
• 代码块 Block：{[Statement] ...}
• 指针类型 Pointer Type：*(const )[Type]
• 引用类型 Reference Type：&(const )[Type]
• 数组类型 Array Type：[[Type], [Number]]
• 函数调用 Function Calling：[Identifier]([Identifier]: [Type], ...) 或 [Identifier]::<TypeArguments>([Identifier]: [Type], ...) 来调用一个范型函数
• 函数定义 Prototype Declaration：(Attributes) fun (<TypeParameters>) ([Type].)[Identifier]([Identifier]: [Type], ...): [Type]
• 函数实现 Function Implementation：(Attributes) fun (<TypeParameters>) [Identifier]([Identifier]: [Type], ...): [Type] [Block]
• 动态申请内存 Malloc：new [Type]
• 返回语句 Returning：return [Expression]
• 条件控制语句 If：if ([Expression]) [BlockOrStatement] (else [BlockOrStatement])
• 条件循环语句 While：while ([Expression]) [BlockOrStatement] 或 do [BlockOrStatement] while ([Expression])
• 结构体定义 Structure Declaration：struct [Identifier](<TypeParameters>) {[Identifier]: [Type], ...}
• 特性定义 Trait Declaration：trait (<TypeParameters>) [Identifier] {[Prototype] ...}
• 特性实现 Trait Implementation：impl [Identifier] for [Type] {[Function Implementation] ...}

下面简单对上面一些特殊语法做阐释：

• let 和 val/var 的区别

  kamet 使用三种定义符。其中 var 和 val 都声明了一个持有栈空间的变量（可能会被 LLVM 优化为寄存器），其中 val 为不可变变量而 var 为可变变量，而 let 仅申明一个临时变量，不可被取地址，当然它是不可变的。

• 语句块

  kamet 的语句块并不强制使用分号或换行符来分割，你只需要简单的写下每个语句。当然，如果你认为两个语句连接在一起有歧义，你也可以用换行来分割它们。下面这段代码是合法的：

  fun main() {
  	putchar('H') putchar('e') putchar('l') putchar('l') putchar('o')
  	return
  }

• 属性

  kamet 现在支持如下属性：

  • packed：标注一个结构体在空间分配上是紧凑的。
  • no_mangle：强制一个函数不被 mangle 分配函数名，类似于 C++ 中的 extern "C"。
  • extern：标注一个函数是申明但未实现的。可以通过这个方式调用外部函数。
  • inline：标注一个函数 应当 被编译器内联。它还有下面两个变体：
    • inline(never)：标注该函数不应被内联。
    • inline(always)：标注该函数应该总被内联。

  下面展示了使用属性的一个例子：

  #[packed]
  struct Pair {
  	first: Int,
  	second: Int
  }
  
  #[inline(never) no_mangle]
  fun test() {}

编译部分

在词法分析和语法分析后，我们得到了一个 AST（Abstract Syntax Tree）。我们对这个 AST 上的所有结点附加一个 codegen 函数，并在一个上下文 Context 下运行。一个 Context 同时也维护了一个对应到 LLVM 层的 LLVMModuleRef ，最终我们可以对这个生成的模块进行对应操作。

尽管有 phi node 这一类的控制流 API，LLVM 官方仍然推荐使用 mem2reg 来实现变量。具体来说，我们只需把所有的变量申明为栈空间，随后 LLVM 再专门进行栈空间转寄存器的优化。由于 mem2reg 要求变量申明必须处于函数入口，我们需要在 Context 中额外维护当前的函数及其入口。

细节

Kotlin 中可重载的有上下文的函数

至于如何实现 Context 上下文的可重载的函数调用，我们经过研究使用了如下方式：

// ASTNode.kt
internal abstract fun Context.codegenForThis(): Value

// Context.kt
fun ASTNode.codegen(): Value = codegenForThis()

这种方式使得我们不需要在 Context 对 ASTNode 进行 switch-case 的分发，同时也不需要在 codegen 函数中传递额外的 Context 参数。

数组类型

数组在 LLVM 中被定义为聚合类型（Aggregate Type），这意味这我们并不能对其取地址（它只是临时值），而无需取地址直接获取和修改聚合类型中的元素（insertvalue/extractvalue）要求提供常量而非动态的下标。由此我们定义对数组的引用（&[ElementType, Size]）是可以被隐式转化为指针（*ElementType）的，由此解决了问题并同时降低了代码复杂度（只需要实现指针访问部分代码）。

范型推断

在进行范型推断时，我们会给当前的线程打上标记。在判断两个类型是否相等时，我们首先会检查当前线程是否在进行范型推断，如果正在进行且正在进行比对的两个类型中有且仅有一个为范型参数（Type Parameter），我们会将其和当前线程持有的范型推断表进行比较：如果该范型参数已出现在表中，则判断已有的推断类型是否和当前类型相等；如果还没有出现，则将当前这一对推断信息插入表中，并返回 true。这样很脏，但确实能实现相关功能。

三目表达式

如果一个 if 语句有两个分支并返回的值类型相同，我们就会将其作为一个表达式处理，从而实现类似三目运算符的功能。例如：

putchar(if (1 < 2) 'a' else 'b')

Traits 的动态函数

这类似于 C++ 中的 virtual functions。C++ 采用的解决方式是在每一个带有 virtual 函数的结构体内存中新开辟一块存储指向类型信息的指针，但这造成了一定的空间浪费。我们采用了与 Rust 类似的实现，即胖指针（Fat Pointers）。在 kamet 中，一个特殊的类型 &dyn [TraitName] 会存储两个指针，一个指向实现该 Trait 的相应的函数表，另一个存储指向该对象的指针，从而实现相应的动态函数调用功能。

总结

本文大体上概述了一种新的编程语言的实现过程，然而该语言仍有大部分未实现的部分。此语言仅仅是一次编译原理的实践。这次实践经历使小组成员对编译原理和计算机技术有了更为深入的认识，并拓宽了自己的知识广度，实为一次难得的实践经历。同时感谢 @duangsuse 对本项目的纯兴趣动机的无私贡献和帮助。

本项目源码在 GitHub 上公开：Mivik/Kamet