起因

最近在写一个关于 JavaScript 的静态分析器，作为我的毕业设计。我写静态分析主要是为了 ES6 层面的语法做更好的 DCE(Dead Code Elimination)。我选择 OCaml 来实现这个静态分析工具，用 flow 来 parse JavaScript。

为什么选择 OCaml

在和导师讨论题目的时候，我跟导师说这个项目用 Java 来写，主要是 Java 比较容易说服老师。实际上开始写的时候就塞了很多私货，我的第一个版本其实用的是 Scala，原因是：

Scala 里面的很多语言特性非常有 FP 风格，也很适合用来写编译器和静态分析工具。
运行在 JVM 上面更容易做多线程，可以使静态分析过程有较大的提升。
如果有需要，Scala 可以编译成 JS。JVM 上面也有很多可以和 JS 联动的方案，方便和其他 JS library 联动。

但是开始使用 Scala 的时候却发现了许多问题：

我使用的 Parser 和 AST 结构都是 Java 写的（使用了 Graal.js 的 Parser），因此无法使用 Scala 的 case class 风格，这意味着我要在 Scala 里面写 Java Style 的代码，我表示很拒绝。我当然可以用 implicit 语法写一层转换层，但是我觉得这样很蛋疼，所以放弃。
我要进行的静态分析是基于图（Graph）的，似乎没办法进行并行计算，即使可以，也会有超级多 overhead，还不如使用单线程。
巨慢的编译速度和启动时间。编译速度不说了。运行速度 Scala 应该是很快的，但是启动（预热）却很慢。

种种蛋疼的情况让我重新审视用 Scala 是不是特别好的方案，我想要一门执行速度相对较快，语法对写编译器相对友好的语言。Scala 已经很接近了，但是还不够。这让我想起之前用过 OCaml 来写过编译器，感觉代数形式的数据结构天生对编译器和静态分析非常友好。而且有两个项目非常启发到我：

Flow：静态分析工具，但是已经演化到类似 TypeScript 那样，变成一门语言了。我个人用过 flow，但是感觉非常慢，比 TypeScript 慢很多，但是我觉得不是 OCaml 慢，而是 flow 本身设计的问题。设计 TypeScript 的 Anders Hejlsberg 毕竟是编译器领域的大牛，很多坑都踩过，像 TypeScript 和 VSCode 联动体验这么好肯定是经过优良设计的。
BuckleScript：把 OCaml 编译到 JS 的编译器（其实也算一门语言？）。作者号称编译速度最快的语言，编译速度比 TypeScript 还快，并附上了 benchmark。这点也可以理解。毕竟 OCaml 这门语言比 TypeScript 简单太多了。这让我看到了一线生机，OCaml 写出来的编译器也可以很快的啊。

优点：

ADT
冷启动速度却可以秒杀 Scala。想象一下编译几个文件的项目，Scala 还要等 JVM 预热才能达到峰值，其实很蛋疼。
编译速度很快（相比 Scala）

缺点：

现在 OCaml 依然没有办法实现真正意义上的多线程：有 GIL。而我觉得这不是痛点，而且 multi-core OCaml 准备推出了（2020 年？）。
如果需要和 JS 联动，需要编译成 JS

使用 Flow Parser

Github: https://github.com/facebook/flow

Flow 是利器。

自己从头开始写 ES 的 Parser 是不太现实的。很幸运 flow 就提供了这么一个工具。Flow 的代码结构还是蛮清晰，我一看项目目录基本了解各个模块的作用，而 parser 是作为独立的一部分：Flow Parser

AST 定义：https://github.com/facebook/flow/blob/master/src/parser/flow_ast.ml

Flow 的 AST 都写在一个文件里面，我们看 program 的定义：

type ('M, 'T) program = 'M * ('M, 'T) Statement.t list * 'M Comment.t list [@@deriving show]

一个 program 就是 list of Statment.t。有两个泛型参数 'M 和 'T 充斥着整个 AST，虽然它的作用很巧妙，但是却并不是那么直观。实际上 parser 输出的结果中，'M 和 'T 都是 Loc.t，就是 AST 的位置信息，那么为什么需要两个范型呢？我们只要看 Statement 和 Expression 两个地方的定义就明白了：

Statement

  and ('M, 'T) t = 'M * ('M, 'T) t'
  and ('M, 'T) t' =
    | Block of ('M, 'T) Block.t
    | Break of 'M Break.t
    | ClassDeclaration of ('M, 'T) Class.t
    | Continue of 'M Continue.t
    | Debugger
    | DeclareClass of ('M, 'T) DeclareClass.t
    | DeclareExportDeclaration of ('M, 'T) DeclareExportDeclaration.t
    | DeclareFunction of ('M, 'T) DeclareFunction.t
    | DeclareInterface of ('M, 'T) Interface.t
    | DeclareModule of ('M, 'T) DeclareModule.t
    | DeclareModuleExports of ('M, 'T) Type.annotation
    | DeclareTypeAlias of ('M, 'T) TypeAlias.t
    | DeclareOpaqueType of ('M, 'T) OpaqueType.t
    | DeclareVariable of ('M, 'T) DeclareVariable.t
    | DoWhile of ('M, 'T) DoWhile.t
    | Empty
    | ExportDefaultDeclaration of ('M, 'T) ExportDefaultDeclaration.t
    | ExportNamedDeclaration of ('M, 'T) ExportNamedDeclaration.t
    | Expression of ('M, 'T) Expression.t
    | For of ('M, 'T) For.t
    | ForIn of ('M, 'T) ForIn.t
    | ForOf of ('M, 'T) ForOf.t
    | FunctionDeclaration of ('M, 'T) Function.t
    | If of ('M, 'T) If.t
    | ImportDeclaration of ('M, 'T) ImportDeclaration.t
    | InterfaceDeclaration of ('M, 'T) Interface.t
    | Labeled of ('M, 'T) Labeled.t
    | Return of ('M, 'T) Return.t
    | Switch of ('M, 'T) Switch.t
    | Throw of ('M, 'T) Throw.t
    | Try of ('M, 'T) Try.t
    | TypeAlias of ('M, 'T) TypeAlias.t
    | OpaqueType of ('M, 'T) OpaqueType.t
    | VariableDeclaration of ('M, 'T) VariableDeclaration.t
    | While of ('M, 'T) While.t
    | With of ('M, 'T) With.t

Expression

  type ('M, 'T) t = 'T * ('M, 'T) t'
  and ('M, 'T) t' =
    | Array of ('M, 'T) Array.t
    | ArrowFunction of ('M, 'T) Function.t
    | Assignment of ('M, 'T) Assignment.t
    | Binary of ('M, 'T) Binary.t
    | Call of ('M, 'T) Call.t
    | Class of ('M, 'T) Class.t
    | Comprehension of ('M, 'T) Comprehension.t
    | Conditional of ('M, 'T) Conditional.t
    | Function of ('M, 'T) Function.t
    | Generator of ('M, 'T) Generator.t
    | Identifier of 'T Identifier.t
    | Import of ('M, 'T) t
    | JSXElement of ('M, 'T) JSX.element
    | JSXFragment of ('M, 'T) JSX.fragment
    | Literal of Literal.t
    | Logical of ('M, 'T) Logical.t
    | Member of ('M, 'T) Member.t
    | MetaProperty of 'M MetaProperty.t
    | New of ('M, 'T) New.t
    | Object of ('M, 'T) Object.t
    | OptionalCall of ('M, 'T) OptionalCall.t
    | OptionalMember of ('M, 'T) OptionalMember.t
    | Sequence of ('M, 'T) Sequence.t
    | Super
    | TaggedTemplate of ('M, 'T) TaggedTemplate.t
    | TemplateLiteral of ('M, 'T) TemplateLiteral.t
    | This
    | TypeCast of ('M, 'T) TypeCast.t
    | Unary of ('M, 'T) Unary.t
    | Update of ('M, 'T) Update.t
    | Yield of ('M, 'T) Yield.t

上述代码就是在说，所有的 Expression 结点都会附上一个 'T 信息，所有的 Statement 都会附上一个 'M 信息，这就很容易理解了。所以这两个范型是用来区分 Statement 和 Expression 的。在 flow 里面进行 type infer 和 type check 的时候，实际上 'T 会是 (Loc.t * Type.t)。这个是 type check 阶段附上的信息，而 Statement 不需要这个信息，所以它仍然是 Loc.t。举个类型推导例子 🌰 来说明 'T 附在表达式上的作用：

var a = 1 + 1;

var a = ((1: 'T) + (1: 'T)): 'T
var a = ((1: number) + (1: number)): 'T
var a = ((1: number) + (1: number)): number
var a: number = ((1: number) + (1: number)): number

从上述过程可以推出 a 的类型是 number，这个类型信息挂在所有 expression 的 AST 的上面，而 var 语句的 node 不需要这个信息。

安装 Flow Parser

原本 flow_parser 可以从 opam 安装，但是我更新了 opam 之后似乎因为一些安全策略禁止包里面的 bash 脚本执行（当时社区发生了一件事，一个包的 bash 脚本把用户的整个 ~ 目录删掉，似乎是手滑写的脚本就发布了，后来 opam 对 bash 脚本做了些限制）。所以后来我只能 clone 了 flow 的代码本地进行安装

进入 src/parser 目录执行：

$ make ocamlfind-install

即可安装成功。如果使用 ocamlbuild 编译，进入 _tag 文件，加上 flow_parser。我的 _tag:

true: package(ppx_deriving.show), package(flow_parser), package(core_kernel)
<dist>: -traverse

使用方法

使用 Flow_ast 自带的 pp 和 show 方法可以把 AST 打印出来，前提是你要传入 'T 和 'M 的 pretty print 方法，这里我把 Loc.pp 传进去即可：

let ast, _ = Parser_flow.program code in
Flow_ast.show_program Loc.pp Loc.pp ast |> print_endline;

大功告成！

起因

为什么选择 OCaml

优点：

缺点：

使用 Flow Parser

安装 Flow Parser

使用方法

相关阅读