Skip to content

Latest commit

 

History

History
209 lines (157 loc) · 12.3 KB

project.md

File metadata and controls

209 lines (157 loc) · 12.3 KB
Raw

一种基于“不定类型”的编程语言设计与实现

我将实现一种语法基于ML家族语言，融合Go语言动态编程特性的静态类型语言Beren，作为我的毕设课题。

1.前期准备

我从中学时开始学习编程，接触多种编程语言后也逐渐有了自己设计一门语言的想法，不过一直没有付诸实现。19年夏天进入字节跳动实习以后，我开始认真考虑这个想法，因为经过大二大三的专业课学习，我已经掌握了实现一门语言的理论基础，剩下待考验的就只有动手能力了。

参考了Go，Rust，Crystal，Typescript等新兴语言后，我逐渐有了心目中的理想型语言：一种执行静态类型检查、编译型，保证类型安全的，支持类型推断、垃圾回收、轻量级线程的，DSL化的通用编程语言。但是以我目前的能力，无法一人实现这样一门语言。我只能将期望调低，阶段式地提升目标，由动态解释型语言做起，逐步升级至静态解释型语言，静态编译型语言，最后到支持高并发的通用编程语言。

未完成的Léa解释器

在字节跳动实习的几个月中，我利用闲暇时间，开始了第一次尝试。我给这个项目起名叫Léa，定位是一门动态解释性语言，语法混合了C/C++，Go，Lisp以及Mathematica，作为练手。

当时的想法很天真，很不切实际。我企图在毫无编译器设计经验的情况下就开发一门功能完整的语言，结果注定与期望相距甚远。因为对开发语言的难度缺乏认知，同时也想练习C语言水平，我就选用C开始了这个项目。最初的几周我精神饱满，花了很多时间琢磨语法，定义抽象语法树（AST），并用flex和bison实现了一个parser。

从字符流转换到AST的过程相对简单，随后的AST解释执行的过程显然困难不少。当时我决定用环境模型（environment model）为Léa语言编写一个运行时（runtime）。边写边发现，我需要自己实现哈希表、垃圾回收、语法树节点的深拷贝，还要大量操作void*指针，程序编写得十分不安全。另外，在开始写runtime之前，有许多细节我并没有仔细想好，编写过程中意识到与之前设计的AST结构有不少的冲突，实现难度越写越大。我逐渐明白一定要先大幅降低目标难度，才有可能真正完成第一个项目。等到9月开学的时候，我写出了一个半成品解释器，可以完整解析语法，进行变量定义和一些简单计算，之后便搁置了这个项目。

MyLisp解释器

随后等到申请学校结束，我又开始了新一次尝试。这回我将目标定的非常低：实现一个功能极其简单的Scheme解释器。这个项目的名字叫MyLisp，也是一门动态解释型语言。在尝到C语言的苦头之后，我决定用一门高级语言来减轻心智负担。在字节跳动实习4个月后，我对Go语言已掌握得比较熟练，于是决定使用Go来实现这个项目。

为了避免在parser花费过多时间，我改变了原先的开发顺序。我先定义好了各个AST节点，然后根据AST来设计runtime的结构，定义了runtime能够处理的值类型，之后再去处理语法。我先搭好各个部分的框架，随后逐步填充。Scheme简单的语法大幅度的缩短了各阶段的编写用时，并且使用高级语言确实带来了效率上的提升。最终完成的MyLisp解释器可以支持布尔型、整型、符号、函数和闭包几种核心类型，虽然运行效率较差，但也基本上达成了设定的目标。接下来就可以开始毕设项目Beren的工作了。

Beren解释器

Beren作为我的毕设项目，设想中是一门执行静态类型检查，类型安全的单线程解释型语言。有了MyLisp的一些经验，我对于Beren实现成功的可能比较有把握。这个项目对我来说极具挑战，必将耗费大量时间。如果能成功完成，将是我一次极大的锻炼。

2.思路来源

再说回我想要设计的语言Beren本身，这门语言以ML家族语言的类型系统为主体，以“不定类型”为核心，另外参考Go语言的接口抽象形式，作为ML家族中的module子语言的简化。这一设计想法来源于两条相互关联的思维路径。

路经一

第一条路径，从观察编程语言中的错误处理方式开始。19年大三快结束的时候，我开始接触Rust语言；入职字节跳动以后，我接着去学习Go语言。这两门语言共同点是诞生时间不久，拥有许多不同于传统语言的革新特性，比如类型继承方式，以及错误处理。在同事们推荐的文章里，我看到了很多关于Go语言的讨论，许多人都说它的错误处理方式不够优雅，不如Rust中Result类型的处理模式，甚至不如try catch机制。

try catch错误处理机制不区分普通错误和异常，要记清楚一个个异常类型的名字不是一件容易的事。以前我图省事，经常写出一些类似下面的几乎无用的错误处理代码。此外，源于try catch的实现机制，在异常多发的情况下会导致不小的性能损耗。

try {
  ...
} catch (Exception e) {}

Go语言区分可预知的错误和不可预知的异常，普通错误通过函数的最后一个error类型的返回值来获取，异常则使用panic和recover机制来处理。error类型是一个非常简单的接口，只提供一个打印错误信息的方法。

type error interface {
  Error() string
}

对于一般的网络服务器场景的应用来说，相对轻便简单，将错误作为返回值也不会造成太大的性能损耗。如果需要更为细分的错误类型，可以用Go的类型断言或反射机制来推断error接口的类型。

func foo() (int, error) {
	a, b, err := someCalculation()
	if err != nil {
 		return 0, fmt.Errorf("foo: %w", err)
	}
	return a+b, nil
}

至于难以预测的异常，可以用panic迅速终止函数的运行。这一机制整体上是不错的，不过很多人认为不够优雅，因为作为返回值的error类型和正常的返回值在同一时间必有一个是浪费的，而且这种错误码返回机制并不保证编程者一定会进行错误处理。

Rust的错误处理与Go语言类似，同样区分可预知的错误和不可预知的异常。Result类型是Rust内置的一种“不定类型”，用于处理可预知的错误。函数正常返回的时候Result会保存正常的返回值，出错的时候则会保存错误信息。

enum<T, E> Result {
  Ok(T),
  Err(E)
}

想要使用Result类型返回值的内容，需要先判断到底收到的是Ok还是Err，然后再分别处理，这种做法可以保证错误处理不会缺失。如果遇到了异常，利用panic!宏迅速终止程序运行就好。

fn foo() -> Result<(i32, i32), String> {
  let result = some_calculation();
  match result {
    Ok(a, b) => a + b,
    Err(s) => Err(s)
  }
}

正是因为Rust支持enum type，也就是通常所说的“不定类型”，才能够提供这种相较之下最为完善的错误处理方式。

由此，我对Rust中的“不定类型”产生了兴趣。后来又看了一些讨论，其中一条评论令我印象深刻，提到说Rust的设计受了OCaml语言很大的影响，但是语法上并不如OCaml那么自然纯粹。受好奇心的驱使，我又开始学习OCaml，以及同为ML家族的SML，这才明白为什么大家都说Rust像是ML家族的新一代语言。只有在接触ML家族语言为模式匹配专门设计的语法之后，我才体会到这种类型系统，尤其是“不定类型”的优雅和强大。

type expr =
| Int of int
| Plus of expr * expr
| Times of expr * expr

let rec calc = function
| Int x -> x
| Plus (a, b) -> calc a + calc b
| Times (a, b) -> calc a * (calc b

let () =
  let e = Times (Plus (Int 2, Int 3), Times (Int 4, Int 5)) in
  print_int (calc e)

路径二

第二条路径，从Go语言的接口类型开始。Go语言仓库的proposal中，有许多人支持向Go添加一种数据类型用于专门处理“不定类型”。但是这些proposal大多遭到否决，因为Go的接口已经部分提供了“不定类型”的功能，没有必要添加另一种新的语法元素。

Go语言的接口，配合switch case语言以及类型断言，可以展现出类似模式匹配的效果，可以说Go接口很多时候都可以当作ML中的“不定类型”来使用。

type expr interface {
  Expr()
}

type Int int
type Plus struct { a, b expr }
type Times struct { a, b expr }

func (Int) Expr() {}
func (Plus) Expr() {}
func (Times) Expr() {}

func calc(e expr) int {
  switch v := e.(type) {
  case Int:
    return v
  case Plus:
    return calc(v.a) + calc(v.b)
  case Times:
    return calc(v.a) * calc(v.b)
  }
}

但是两者之间存在本质区别，Go接口是对行为的抽象，每一个接口类型的变量保存的都是一个虚函数表和具体内容的元组，变量的类型信息和虚函数表存放在一起，在类型断言或者使用反射机制时，类型信息会被用到。ML中的“不定类型”更类似于C语言中的struct套union的结构，是对不同数据组合的抽象。

struct expr {
  enum {INT, PLUS, TIMES} tag;
  union {
    int value;
    struct { int a, b; } plus;
    struct { int a, b; } times;
  };
};

两者在出发点有着较大差别。因此，Go接口只能限定数据的行为，无法限制具体的数据种类，所以它代表的是一个“无限”的类型集合；而ML的“不定类型”只能限定数据种类，定义之后便不能拓展，所以其代表的是一个“有限”的类型集合。这是两者最本质的差别。也有Go语言proposal提出向interface中增设语法，可以将接口支持的类型限制在有限的集合内，基本模拟“不定类型”。但是我认为这一提案不太可能通过，因为它与接口语法的出发点不相符，而且不是十分必要。

从我的角度而言，接口更应作为行为方式的抽象存在，属于数据抽象而非行为抽象的内容，则由“不定类型”来实现。ML语言的数据抽象方式以及语法能发挥出“不定类型”最大的优势，而类似Go接口的行为抽象方式可以更好地组织和复用代码。这两种思想的结合，在目前的我看来，是一件非常美妙的事情。

3.语言介绍

见语言介绍。

4.项目计划

时间表

  1. 开题报告+任务书：3.1（已完成）
  2. 语法树（AST）设计：3.11（已完成）
    1. Token和AST定义：3.4（已完成）
    2. lexer和parser实现：3.11（已完成）
  3. 类型检查：3.18 -> 3.31（正在进行，期限推迟）
    1. 类型定义：3.17（已完成）
      • 类型别名、元组、函数
      • 不定类型
      • 记录
      • 接口
      • 泛型、泛型具体化
    2. 类型推断：3.31（完成主体部分）
      • 全部表达式
      • 泛型自动推断（存在一些小问题）
      • 方法绑定、接口类型检查
  4. 运行时（Runtime）设计：4.15 -> 4.30
    1. 虚拟机设计：3.31 -> 4.15（正在进行）
      • 数据方式
      • 类型注解
      • 指令集
      • 内存模型
    2. 翻译方案设计：4.15 -> 4.30
      • 文本形式
      • 字节码形式
  5. LLVM翻译方案设计（量力而为）
  6. 毕设论文

开发环境

  • MacOS
  • VS Code
  • OCaml