slisp:一门简单的JVM上的Lisp方言

之前经常变更学习方向,没有收到很好的学习效果,浪费了不少时间。最近痛定思痛,把方向定为JVM和编译原理,这次真的不改了。本文是学习该方向的阶段性总结。

一、前言

之前写过几个解释器,但还没写过编译器。刚好看到知乎Belleve给出的一幅学习路线图,于是决定实现一个lisp方言的编译器。

之所以选择JVM而不是X86作为目标平台,一是JVM平常用的多一些,可以互相印证、互相补充;二是文档和社区资源丰富友好,开发体验较好。

项目地址:https://github.com/gcnyin/slisp

截止最新的commit 77f126d4,实现的功能有:

  • 定义变量
  • 支持字符串、整数和布尔类型
  • 打印以上三种预置类型的值
  • 四则运算
  • 条件判断

二、编译和运行

来一段具体的Slisp程序:

(define a (+ 1 2 3 4))

(println a)

(define b (+ a a))

(println b)

(define a (+ b b))

(println a)

(println (+ (+ 1 1)
            (- 6 4)
            (* 2 2)
            (/ 4 2)))

(println "Hello Slisp!")

(define c "Hello world!")

(println c)

(println true)

(println false)

(define d true)

(println d)

(if true (println true) (println false))

(if (== 1 1) (println "1 == 1") (println "1 != 1"))

以上程序出自本项目/Slisp/Hello.slisp。

想要运行必须先打包编译器:

./gradlew clean build

得到了build/libs/slisp-0.1.0.jar,之后在命令行编译源代码:

java -jar build/libs/slisp-0.1.0.jar Slisp/Hello.slisp

即可生成Hello.class文件,java Hello运行该文件,输出为:

20
10
Hello Slisp!
Hello world!
true
false
true
true
== 1

三、编译器组成

这个编译器由三部分组成,一是前端部分,二是构建抽象语法树,三是递归下降生成字节码。

前端部分使用了Antlr来构建。Antlr是一个流行的parser generator,可以根据给定的文法,生成相应的parser。因为Slisp本身采用了lisp系的语法,并不复杂,所以很容易写出文法供Antlr使用。

构建抽象语法树使用了visitor模式。由于Antlr本身返回的结果已经是一棵树,所以这部分的工作是,根据每个节点不同的形态创建相应的类和实例。

这里有一些实现上的细节可以优化,比如针对四则运算,可以将这些运算全部用一个类来表示,只更改其中的一个字段以示区别。还有一点是,如果打算只使用一个visitor,那么每个节点类都需要继承同一个接口或父类。

还有,实现了一点简单的类型推导。传统的lisp方言大多是动态语言,不过Slisp是静态的,而且可以在定义变量时推导出变量的类型,不需要开发者手动声明变量的类型。(define a 123)、(define b “Hello”)和(define c true)可以由字面值推导出类型,而(define d (+ 1 (- 2 3))也可以推导出表达式(+ 1 (- 2 3))的类型并以此确定d的类型。

生成字节码部分采用了递归下降来生成。比如对(+ (+ 1 1) (- 6 4) (* 2 2) (/ 4 2)),生成了:

      44: bipush        1
      46: bipush        1
      48: iadd
      49: bipush        6
      51: bipush        4
      53: isub
      54: iadd
      55: bipush        2
      57: bipush        2
      59: imul
      60: iadd
      61: bipush        4
      63: bipush        2
      65: idiv
      66: iadd

这段代码是Hello.class文件中的一部分,使用OpenJDK中的javap反汇编器生成。

(+ 1 1)对应44、46和48,先将两个1压入栈中,然后相加,将之前的两个人从栈中弹出,然后将结果压入栈顶,继续执行(- 6 4)。

这里需要注意的是,并不是说执行完这四个运算(+ 1 1) (- 6 4) (* 2 2) (/ 4 2),然后再计算它们的和。而是在计算完(+ 1 1)和(- 6 4)之后(结果为2和2),立即计算了(+ 2 2)(得到4),然后计算(* 2 2)(得到4),再计算(+ 4 4),以此类推。过程如下所示:

(+ (+ 1 1) (- 6 4) (* 2 2) (/ 4 2))
(+ 2 (- 6 4) (* 2 2) (/ 4 2))
(+ 2 2 (* 2 2) (/ 4 2))
(+ 4 (* 2 2) (/ 4 2))
(+ 4 4 (/ 4 2))
(+ 8 (/ 4 2))
(+ 8 2)
(10)

为了契合这样的字节码运算方式,后端在创建抽象语法树的时候需要注意“左结合与右结合”的问题。这里采用了右结合的方式,大致结构如下所示:

(+ (/ 4 2)
   (+ (* 2 2)
      (+ (- 6 4)
         (+ 1 1))))

这样从底层开始生成字节码,每生成一层,就向上传递,继续生成上层节点的字节码。

实际开发中使用了ASM库来辅助生成字节码,只需要手动拼接好类似于bipush 1这样的文本传给ASM中合适的类和方法,最后调用generateBytecode这样的方法即可。

虽然ASM库很方便,但想要生成符合语义的字节码,开发者仍需要阅读JVM规范。JVM规范中定义了各字节码的名称与语义,对照着网络上的众多示例还是很容易理解的。

四、字节码简介

bipush是指将一个类型为byte扩充为int,然后压到栈上。

iadd是将栈最上面的两个int弹出,然后计算它们的和,将结果压入栈顶。imul、isub和idiv都类似于iadd,不同之处在于将运算符变为了*、-和/。

istore将int保存在局部变量中。

iload从局部变量中取出保存在其中的值。

astore是将对一个Ojbect的引用保存在局部变量中。

alocal是将保存在局部变量中的引用压入栈顶。

ifeq是将栈顶的值与0进行比较,如果相等,进入true branch,否则进行false branch。该指令还会指定一个数字作为false branch入口的地址。

if_icmpne是比较栈上的两个类型为int的值,如果不相等,进入true branch,否则进入false branch。

值得注意的是,诸如if这样的指令并不是单个存在,它们更多的像是一个家庭,比如比较两个int会有许多相似的指令,从JVM规范中抄录一段:

• if_icmpeq succeeds if and only if value1 = value2
• if_icmpne succeeds if and only if value1 ≠ value2
• if_icmplt succeeds if and only if value1 < value2
• if_icmple succeeds if and only if value1 ≤ value2
• if_icmpgt succeeds if and only if value1 > value2
• if_icmpge succeeds if and only if value1 ≥ value2

可以看到if_icmpne只是用来比较两个数相等时的情况,还有其它指令用于比较不等、大于、小于、相等时的情况。像这样相似而略有区别的指令,JVM规范大多将它们的文档合并在一起,并起名为if_icmp,这里的cond代表每个指令独特的部分。

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License