序言

我已经记不清写过多少个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
4

as -o jjcc.o jjcc.s
gcc jjcc.o
./a.out
echo $? # 输出3

后记

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

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

这篇文章就是在Boostnote 中写成的XD

来龙去脉

有一阵子，我沉迷于“笔记软件狩猎”中——就是不停寻找各种各样的笔记软件，再一个个试用，企图从中选出一个最强大的。回想起来，我尝试过有道云笔记、印象笔记、Quiver、Boostnote、OneNote、Yu Writer、Leanote（在本地搭建），等等。大部分都是浅尝辄止，例如OneNote，当我发现它不支持代码块语法高亮时，就放弃了它。目前仍然在使用的是Boostnote，并且也是最令我满意的。

作为一名自诩的non-trivial的Common Lisp程序员，在编码的时候经常会遇到令人不愉快的地方，其中一个便是LET。

一段典型的LET的示例代码如下

1
2

(let ((a 1))
   a)

大多数时候，LET不会只有一个绑定。并且，也不会只是绑定一个常量这么简单，而应当是下面这样的

1
2
3
4

(let ((a (foo x y))
      (b (bar z)))
  (function1 a b)
  (function2 a b))

有时候我会想看看某一个绑定的值——最好是在它计算完毕后立即查看。如果要查看foo函数的返回值，可以这样写

1
2
3
4
5

(let ((a (foo x y))
      (b (bar z)))
  (print a)
  (function1 a b)
  (function2 a b))

如果调用foo和bar都顺利的话上面的代码也就够了。比较棘手的情况是，如果a的值不符合预期，会导致b的计算过程出状况（尽管在上面的代码中看似不会）。这种情况多出现在LET*的使用中，如下面所示

1
2
3
4

(let* ((a (foo x y))
       (b (bar a)))
  (function1 a b)
  (function2 a b))

如果错误的a会导致bar的调用出错，那么在调用function1之前才调用print打印a已经为时过晚了——毕竟调用bar的时候就抛出condition往调用链的上游走了。一种方法是写成下面这样子

1
2
3
4
5
6

(let* ((a (let ((tmp (foo x y)))
            (print tmp)
            tmp))
       (b (bar a)))
  (function1 a b)
  (function2 a b))

这也太丑了！要不然写成下面这样子？

1
2
3
4
5

(let ((a (foo x y)))
  (print a)
  (let ((b (bar a)))
    (function1 a b)
    (function2 a b)))

本来一个LET就可以做到的事情，这下子用了两个，还导致缩进更深了一级。如果有十个变量需要打印，就会增加十个LET和十层缩进。如果心血来潮想查看一个变量的值，还要大幅调整代码。

问题大概就出在LET和LET*的语法上。以LET为例，它由截然分开的bindings和forms组成，两者不能互相穿插。因此，如果想在bindings中求值一段表达式，只能将bindings切开，写成两个LET的形式。好像写一个新的宏可以解决这个问题？是的，vertical-let就是。

vertical-let是一个我自己写的宏，源代码在此。其用法如下

1
2
3

(vertical-let
  :with a = 1
  a)

它借鉴了LOOP中绑定变量的方式（即:with和=），绑定变量和用于求值的代码还可以交织在一起，如下

1
2
3
4
5

(vertical-let
  :with a = 1
  (print a)
  :with b = 2
  (+ a b))

vertical-let最终会展开为LET，比如上面的代码，会展开为如下的代码

1
2
3
4

(LET ((A 1))
  (PRINT A)
  (LET ((B 2))
    (+ A B)))

vertical-let的算法很简单。它遍历表达式列表，当遇到:with时就把接下来的三个元素分别视为变量名、等号，以及待求值的表达式，将三者打包进一个列表中，再压栈；当遇到其它值时，就视为待求值的表达式（将会组成LET的forms部分），也放进列表中再压栈（具体方法参见源代码）。

将所有值都遍历并压栈后，接下来要遍历这个栈中的元素。先准备两个空的栈——一个存放bindings，一个存放forms。接着，对于每一个从栈中弹出的元素，分为如下两种情况：

1. 如果表示binding，则直接压入存放bindings的栈，否则；
2. 如果是待求值的表达式，并且上一个出栈的元素是binding，则说明已经有一段完整的LET的内容被集齐。因此，将目前在两个栈中的内容全部弹出，组合为一个LET表达式再压入存放forms的栈中。然后将方才弹出的表达式也压入forms。重复上述过程直至所有元素都被处理，最后将还在两个栈中的内容也组合为一个LET表达式便结束了。

全文完

本文只是简单地讲述我自己在使用GNU Emacs、Fork，以及Visual Studio Code查看Git仓库的不同分支的diff上的经历。

Emacs

当使用Emacs时，我更喜欢用M-x package-install安装的magit提供的功能——magit-diff，而不是它自带的vc-dir。按下M-x，输入magit-diff并敲下回车后，Emacs会在minibuffer中等待用户输入要比较的分支。就像在shell中使用git-diff一样，只需要输入两个以..连接的分支名并敲下回车，就可以列出它们间的差异。如下图所示

上图是master与re两个分支间的差异。magit-diff会列出两个分支间不一致的文件，与直接使用git-diff命令没有不同。往下滚动跨过文件清单后，还可以查看单个文件的差异。如下图所示

Fork

第一次知道Fork是在知乎闲逛的时候，好像是在浏览“Mac下有什么值得推荐的软件”这类问题时看到的。某一次，为了能直观地查看两个commit间的差异，便试用了一番，效果确实不错。Fork的界面如下图所示

还记得，当时为了能够比较两个commit间的差异，我还在Fork的菜单栏中翻了很久——虽然是毫无收获。结果发现，原来只需要选中两个commit就可以了。如下图所示

图片两行蓝色的就是我选中的两个commit——先用鼠标点击其一，按住control键后再选中另一个即可。图片下方的部分与magit-diff差不多，应该也算是一目了然了。

Visual Studio Code

原本我觉得Fork已经足够好了，某一天在用VSCode时才忽然发现，在Fork中显示的代码差异，是没有语法高亮的。通常来说，即使没有语法高亮，查看短小的diff也不成问题。但如果差异的内容很多，或是diff位于一个很长的函数内部，这时光靠diff来做代码审查已经不太够了——因为不好确定在这片diff中出现的变量和函数，到底是不是正确地定义了的。

后来我发现，VSCode自带的“源代码管理”，即便是在查看diff时也是有语法高亮的——不仅有语法高亮，对于Node.js代码而言，还有ESLint的提示和“跳转到定义”的功能，awesome！不愧是全宇宙最好用的编辑器（笑

为了可以用VSCode来查看两个分支间的差异，放狗搜了一下，找到了神器GitLens。

安装GitLens后，VSCode的最左侧会多出一个菜单项，在其中可以方便地选择两个分支来进行比较。首先，找到一个要比较的分支，选择“Select for Compare”。如下图所示

再选中另一个要比较的分支，右键单击选择“Compare with Selected”，然后便可以在下方看到VSCode罗列出不一致的文件清单了。如下图所示

VSCode是最吼的！

全文完。

cuckoo是一个我自己开发的类似待办事项的工具，运行在我本地的电脑上。它有如下两个接口：

1. 传入一个UNIX Epoch时间戳创建提醒
2. 传入一个标题以及提醒的ID来创建任务

这样一来，便能在设定的时刻调用alerter在屏幕右上角弹出提醒。

我喜欢用Emacs的org-mode来安排任务，但可惜的是，org-mode没有定点提醒的功能（如果有的话希望来个人打我的脸XD）。开发了cuckoo后，忽然灵机一动——何不给Emacs添砖加瓦，让它可以把org-mode中的条目内容（所谓的heading）当做任务丢给cuckoo，以此来实现定点提醒呢。感觉是个好主意，马上着手写这么些Elisp函数。

PS：读者朋友们就不用执着于我的cuckoo究竟是怎样的接口定义了。

为了实现所需要的功能，让我从结果反过来推导一番。首先，需要提炼一个TODO条目的标题和时间戳（用来创建提醒获取ID），才能调用cuckoo的接口。标题就是org-mode中一个TODO条目的heading text，在Emacs中用下面的代码获取

1

(nth 4 (org-heading-components))

org-headline-components在光标位于TODO条目上的时候，会返回许多信息（参见下图）

其中下标为4的component就是我所需要的内容。

接着便是要获取一个提醒的ID。ID当然是从cuckoo的接口中返回的，这就需要能够解析JSON格式的文本。在Emacs中解析JSON序列化后的文本可以用json这个库，示例代码如下

1
2

(let ((s "{\"remind\":{\"create_at\":\"2019-01-11T14:53:59.000Z\",\"duration\":null,\"id\":41,\"restricted_hours\":null,\"timestamp\":1547216100,\"update_at\":\"2019-01-11T14:53:59.000Z\"}}"))
  (cdr (assoc 'id (cdr (car (json-read-from-string s))))))

既然知道如何解析（同时还知道如何提取解析后的内容），那么接下来便是要能够获取上述示例代码中的s。s来自于HTTP响应的body，为了发出HTTP请求，可以用Emacs的request库，示例代码如下

1
2
3
4
5
6
7
8
9
10
11
12

(let* ((this-request (request
                      "http://localhost:7001/remind"
                      :data "{\"timestamp\":1547216100}"
                      :headers '(("Content-Type" . "application/json"))
                      :parser 'buffer-string
                      :type "POST"
                      :success (cl-function
                                (lambda (&key data &allow-other-keys)
                                  (message "data: %S" data)))
                      :sync t))
       (data (request-response-data this-request)))
  data)

此处的:sync参数花了我好长的时间才捣鼓出来——看了一下request函数的docstring后才发现，原来需要传递:sync为t才可以让request函数阻塞地调用，否则一调用request就立马返回了nil。

现在需要的就是构造:data的值了，其中的关键是生成秒级的UNIX Epoch时间戳，这个时间戳可以通过TODO条目的SCHEDULED属性转换而来。比如，一个条目的SCHEDULED属性的值可能是<2019-01-11 Fri 22:15>，将这个字符串传递给date-to-time函数可以解析成代表着秒数的几个数字

1

(date-to-time "<2019-01-11 Fri 22:15>")

时间戳字符串要怎么拿到？答案是使用org-mode的org-entry-get函数

1

(org-entry-get nil "SCHEDULED")

PS：需要先将光标定位在一个TODO条目上。

至此，所有的原件都准备齐全了，最终我的Elisp代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

(defun scheduled-to-time (scheduled)
  "将TODO条目的SCHEDULED属性转换为UNIX时间戳"
  (let ((lst (date-to-time scheduled)))
    (+ (* (car lst) (expt 2 16))
       (cadr lst))))

(defun create-remind-in-cuckoo (timestamp)
  "往cuckoo中创建一个定时提醒并返回这个刚创建的提醒的ID"
  (let (remind-id)
    (request
     "http://localhost:7001/remind"
     :data (json-encode-alist
            (list (cons "timestamp" timestamp)))
     :headers '(("Content-Type" . "application/json"))
     :parser 'buffer-string
     :type "POST"
     :success (cl-function
               (lambda (&key data &allow-other-keys)
                 (message "返回内容为：%S" data)
                 (let ((remind (json-read-from-string data)))
                   (setq remind-id (cdr (assoc 'id (cdr (car remind))))))))
     :sync t)
    remind-id))

(defun create-task-in-cuckoo ()
  (interactive)
  (let ((brief)
        (remind-id))

    (setq brief (nth 4 (org-heading-components)))

    (let* ((scheduled (org-entry-get nil "SCHEDULED"))
           (timestamp (scheduled-to-time scheduled)))
      (setq remind-id (create-remind-in-cuckoo timestamp)))
    
    (request
     "http://localhost:7001/task"
     :data (concat "brief=" (url-encode-url brief) "&detail=&remind_id=" (format "%S" remind-id))
     :type "POST"
     :success (cl-function
               (lambda (&key data &allow-other-keys)
                 (message "任务创建完毕"))))))

在create-task-in-cuckoo中，之所以没有再传递application/json形式的数据给cuckoo，是因为不管我怎么测试，始终无法避免中文字符在传递到接口的时候变成了\u编码的形式，不得已而为之，只好把中文先做一遍url encoding，然后再通过表单的形式（form/x-www-urlencode）发送给接口了。

全文完。