浩辰编写lisp_开发一个trivial的lisp编译器（一）

序言

我已经记不清写过多少个lisp-like语言的解释器，以及编译成自制字节码的编译器了，但我想这一次依然不会是最后一个。我还记得之所以入坑写第一个解释器，是因为当时正好学了一点Common Lisp，数据结构的课本中又正好提到一种叫做广义表的数据结构，顿时觉得：“这个广义表不是正好可以表达CL中的atom和cons吗？”于是便尝试写一段程序解析输入、创建广义表，并打印成S表达式。在此基础上，又尝试着实现加减乘除等运算功能，一步步地开启了编写解释器的旅程。后来我看了Peter Norvig写的《Paradigms of AI Programming》，里面有两章分别讲了如何编写解释器和编译器——编译到一个自制虚拟机的字节码的那种。在巨擘的指引下，我也开始写起了trivial的编译器。

这次开工的这一款有所不同：它不再将lisp-like代码编译成架空虚拟机的字节码，而是编译成macOS的x64汇编代码，着实是一个不小的挑战。众所周知，lisp-like的语言(Scheme、Common Lisp、Clojure等)都是一些高级语言，它们摆弄着一些高层次的概念：cons、continua、lambda、symbol，等等。这些语言中的概念无法直接对应到x64汇编上，因此我必须填补它们之间的鸿沟；另一方面，我对x86汇编可以说是一窍不通，完全是一边搜索资料一边写，生成的汇编代码的运行效率多半很低。但，管它呢，只要好玩就足够了。

开始来实现一个lisp-like语言到x64汇编的trivial编译器吧。

编译加法运算

如果你看过龙书，或其它经典的编译原理方面的书，那肯定知道编译器是一个很复杂的玩意儿。但我的编译器很简单，它会从一个小小的二元加法计算器开始演化。为了偷懒不写编译器的前端，我会使用Common Lisp来编写这个编译器的代码，也方便我直接从最让人兴奋的、生成汇编代码的环节入手。

首先从最简单的两个小整数的加法运算开始。在lisp家族的语言，比如Common Lisp中，一段加法运算的代码如下

1(+ 1 2)

对于寄存器可以容纳的整数的相加，直接输出add指令即可，两个操作数可以暂时随意地存放到寄存器中。按照这个思路，一个简单的、可以编译小整数加法运算的编译器就出来了

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24(defun jjcc2 (expr)

"支持两个数的四则运算的编译器"

(cond ((eq (first expr) '+)

`((movl ,(second expr) %eax)

(movl ,(third expr) %ebx)

(addl %eax %ebx)))))

(defun stringify (asm)

"根据jjcc2产生的S表达式生成汇编代码字符串"

(format t " .section __TEXT,__text,regular,pure_instructions~%")

(format t " .globl _main~%")

(format t "_main:~%")

(dolist (ins asm)

(format t " ~A ~A, ~A~%"

(first ins)

(if (numberp (second ins))

(format nil "$~A" (second ins))

(second ins))

(if (numberp (third ins))

(format nil "$~A" (third ins))

(third ins))))

(format t " movl %ebx, %edi~%")

(format t " movl $0x2000001, %eax~%")

(format t " syscall~%"))

在 REPL 中运行如下代码

1(stringify (jjcc2 '(+ 1 2)))

得到如下的汇编代码

1

2

3

4

5

6

7

8

9.section __TEXT,__text,regular,pure_instructions

.globl _main

_main:

MOVL $1, %EAX

MOVL $2, %EBX

ADDL %EAX, %EBX

movl %ebx, %edi

movl $0x2000001, %eax

syscall

将这段代码保存到名为jjcc.s的文件中再运行下列的命令，就得到一个能运行的a.out可执行文件了

1

2

3

4as -o jjcc.o jjcc.s

gcc jjcc.o

./a.out

echo $? # 输出3

后记

有了这个基本的框架后，便可以开始扩展出很多功能了。比如除了加法，还可以支持减法、乘法，以及除法；可以支持progn，实现顺序求值多个表达式的效果；可以支持setq，实现变量和赋值的功能，等等。

此外，这一小段代码也有不少问题。比如调用format输出.section的代码来自于gcc -S的结果，可以用更简短的.text代替；生成的汇编代码中，指令助记符和寄存器名字的大小写不统一，等等。之后我会尝试重构，将代码写得更好。